【演算法】leetcode演算法筆記：二叉樹，動態規劃和回溯法
- 2019 年 11 月 20 日
- 筆記
前言
寫的比較匆忙，測試用例是能全部跑通的，不過考慮記憶體和效率的話，還有許多需要改進的地方，所以請多指教
在二叉樹中增加一行
題目描述
給定一個二叉樹，根節點為第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也是可拆分的
從中我們不難發現兩點
- 當A可拆且B可拆時，則A+B也是可拆分的
- 這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
基本思想
回溯法
具體分析
- 深度優先搜索搞一波，index在遞歸中向前推進
- 當index等於數組長度的時候，結束遞歸，收集到results中（數組記得要深拷貝哦）
- 兩次數字交換的運用，計算出兩種情況
總結
想不通沒關係，套路一波就完事了
具體程式碼
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; };
