前言
寫的比較匆忙，測試用例是能全部跑通的，不過考慮內存和效率的話，還有許多需要改進的地方，所以請多指教
在二叉樹中增加一行
題目描述
給定一個二叉樹，根節點為第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節點替換該目標深度對應的節點，並且
第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;
};
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線
※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益
※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象
※台灣寄大陸海運貨物規則及重量限制?
※大陸寄台灣海運費用試算一覽表
※台中搬家,彰化搬家,南投搬家前需注意的眉眉角角，別等搬了再說!
