【算法】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也是可拆分的
從中我們不難發現兩點
-
當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; };
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線
※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益
※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象
※台灣寄大陸海運貨物規則及重量限制?
※大陸寄台灣海運費用試算一覽表