【算法】leetcode算法筆記:二叉樹,動態規劃和回溯法

前言

寫的比較匆忙,測試用例是能全部跑通的,不過考慮內存和效率的話,還有許多需要改進的地方,所以請多指教

在二叉樹中增加一行

題目描述

給定一個二叉樹,根節點為第1層,深度為 1。在其第 d 層追加一行值為 v 的節點。

添加規則:給定一個深度值 d (正整數),針對深度為 d-1 層的每一非空節點 N,為 N 創建兩個值為 v 的左子樹和右子樹。

將 N 原先的左子樹,連接為新節點 v 的左子樹;

將 N 原先的右子樹,連接為新節點 v 的右子樹。

如果 d 的值為 1,深度 d – 1 不存在,則創建一個新的根節點 v,原先的整棵樹將作為 v 的左子樹。

Example

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5  

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/add-one-row-to-tree

 
基本思想
二叉樹的先序遍歷   
代碼的基本結構
不是最終結構,而是大體的結構

/**
 * @param {number} cd:current depth,遞歸當前深度
 * @param {number} td:target depth, 目標深度
 */
var traversal = function (node, v, cd, td) {
    // 遞歸到目標深度,創建新節點並返回
  if (cd === td) {
    // return 新節點
  }
  // 向左子樹遞歸
  if (node.left) {
    node.left = traversal (node.left, v, cd + 1, td);
  }
  // 向右子樹遞歸
  if (node.right) {
    node.right = traversal (node.right, v, cd + 1, td);
  }
  // 返回舊節點
  return node;
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function (root, v, td) {
    // 從根節點開始遞歸
  traversal (root, v, 1, td);
  return root;
};

 

 

具體分析
我們可以分類討論,分三種情況處理  
第1種情況:目標深度<=當前遞歸路徑的最大深度 
處理方法:val節點替換該目標深度對應的節點,並且

  • 如果目標節點原來是左子樹,那麼重置后目標節點是val節點的左子樹

  • 如果目標節點原來是右子樹,那麼重置后目標節點是val節點的右子樹

 

第2種情況:目標深度>當前遞歸路徑的最大深度
閱讀題目發現,有這麼一個描述:“輸入的深度值 d 的範圍是:[1,二叉樹最大深度 + 1]”
所以呢,當目標深度恰好比當前路徑的樹的深度再深一層時,處理方式是:
在最底下那一層節點的左右分支新增val節點

 

第3種情況:目標深度為1

我們再分析題意,題目里說:“如果 d 的值為 1,深度 d – 1 不存在,則創建一個新的根節點 v,原先的整棵樹將作為 v 的左子樹。”

這說明當:目標深度為1時,我們的處理方式是這樣的 

 

全部代碼 

/**
 * @param {v} val,插入節點攜帶的值
 * @param {cd} current depth,遞歸當前深度
 * @param {td} target depth, 目標深度
 * @param {isLeft}  判斷原目標深度的節點是在左子樹還是右子樹
 */
var traversal = function (node, v, cd, td, isLeft) {
  debugger;
  if (cd === td) {
    const newNode = new TreeNode (v);
    // 如果原來是左子樹,重置后目標節點還是在左子樹上,否則相反
    if (isLeft) {
      newNode.left = node;
    } else {
      newNode.right = node;
    }
    return newNode;
  }
  // 處理上述的第1和第2種情況
  if (node.left || (node.left === null && cd + 1 === td)) {
    node.left = traversal (node.left, v, cd + 1, td, true);
  }
  if (node.right || (node.right === null && cd + 1 === td)) {
    node.right = traversal (node.right, v, cd + 1, td, false);
  }
  return node;
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} v
 * @param {number} d
 * @return {TreeNode}
 */
var addOneRow = function (root, v, td) {
  // 處理目標深度為1的情況,也就是上述的第3種情況
  if (td === 1) {
    const n = new TreeNode (v);
    n.left = root;
    return n;
  }
  traversal (root, v, 1, td);
  return root;
};

 

單詞拆分 

題目描述 

給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict,判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。

說明:

1.拆分時可以重複使用字典中的單詞。

2.你可以假設字典中沒有重複的單詞。

 

Example 

example1
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。
注意: 你可以重複使用字典中的單詞。

example2
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/word-break

 

基本思想 

動態規劃

具體分析
動態規劃的關鍵點是:尋找狀態轉移方程
有了這個狀態轉移方程,我們就可以根據上一階段狀態和決策結果,去求出本階段的狀態和結果
然後,就可以從初始值,不斷遞推求出最終結果。
在這個問題里,我們使用一個一維數組來存放動態規劃過程的遞推數據
假設這個數組為dp,數組元素都為true或者false,
dp[N] 存放的是字符串s中從0到N截取的子串是否是“可拆分”的布爾值
讓我們從一個具體的中間場景出發來思考計算過程
假設我們有

wordDict = ['ab','cd','ef']
s ='abcdef'

並且假設目前我們已經得出了N=1到N=5的情況,而現在需要計算N=6的情況

或者說,我們已經求出了dp[1] 到dp[5]的布爾值,現在需要計算dp[6] = ?  
該怎麼計算呢?
現在新的字符f被加入到序列“abcde”的後面,如此以來,就新增了以下幾種6種需要計算的情況

A序列 + B序列
1.abcdef + ""
2.abcde + f
3.abcd + ef
4.abc + def
5.ab + cdef
6.a + bcdef
注意:當A可拆且B可拆時,則A+B也是可拆分的

 

從中我們不難發現兩點

  1. 當A可拆且B可拆時,則A+B也是可拆分的

  2. 這6種情況只要有一種組合序列是可拆分的,abcdef就一定是可拆的,也就得出dp[6] = true了

下面是根據根據已有的dp[1] 到dp[5]的布爾值,動態計算dp[6] 的過程

(注意只要計算到可拆,就可以break循環了)  
具體代碼

var initDp = function (len) {
  let dp = new Array (len + 1).fill (false);
  return dp;
};
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  // 處理空字符串
  if (s === '' && wordDict.indexOf ('') === -1) {
    return false;
  }
  const len = s.length;
  // 默認初始值全部為false
  const dp = initDp (len);
  const a = s.charAt (0);
  // 初始化動態規劃的初始值
  dp[0] = wordDict.indexOf (a) === -1 ? false : true;
  dp[1] = wordDict.indexOf (a) === -1 ? false : true;
  // i:end
  // j:start
  for (let i = 1; i < len; i++) {
    for (let j = 0; j <= i; j++) {
      // 序列[0,i] = 序列[0,j] + 序列[j,i]
      // preCanBreak表示序列[0,j]是否是可拆分的
      const preCanBreak = dp[j];
      // 截取序列[j,i]
      const str = s.slice (j, i + 1);
      // curCanBreak表示序列[j,i]是否是可拆分的
      const curCanBreak = wordDict.indexOf (str) !== -1;
      // 情況1: 序列[0,j]和序列[j,i]都可拆分,那麼序列[0,i]肯定也是可拆分的
      const flag1 = preCanBreak && curCanBreak;
      // 情況2: 序列[0,i]本身就存在於字典中,所以是可拆分的
      const flag2 = curCanBreak && j === 0;
      if (flag1 || flag2) {
        // 設置bool值,本輪計算結束
        dp[i + 1] = true;
        break;
      }
    }
  }
  // 返回最後結果
  return dp[len];
};

全排列 

題目描述

給定一個沒有重複数字的序列,返回其所有可能的全排列。

Example

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/permutations

 

基本思想

回溯法

 

具體分析

  1. 深度優先搜索搞一波,index在遞歸中向前推進

  2. 當index等於數組長度的時候,結束遞歸,收集到results中(數組記得要深拷貝哦)

  3. 兩次数字交換的運用,計算出兩種情況

總結

想不通沒關係,套路一波就完事了 

具體代碼

var swap = function (nums, i, j) {
  const temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
};

var recursion = function (nums, results, index) {
  // 剪枝
  if (index >= nums.length) {
    results.push (nums.concat ());
    return;
  }
  // 初始化i為index
  for (let i = index; i < nums.length; i++) {
    // index 和 i交換??
    // 統計交換和沒交換的兩種情況
    swap (nums, index, i);
    recursion (nums, results, index + 1);
    swap (nums, index, i);
  }
};
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const results = [];
  recursion (nums, results, 0);
  return results;
};

 

 

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

台灣寄大陸海運貨物規則及重量限制?

大陸寄台灣海運費用試算一覽表

台中搬家,彰化搬家,南投搬家前需注意的眉眉角角,別等搬了再說!

您可能也會喜歡…