總結(jié)
- 想清楚再編碼
- 分析方法：舉例子冠句、畫(huà)圖
第1節(jié)：畫(huà)圖分析方法
對(duì)于二叉樹(shù)轻掩、二維數(shù)組、鏈表等問(wèn)題懦底，都可以采用畫(huà)圖的方法來(lái)分析唇牧，例如：
- 面試題19二叉樹(shù)的鏡像：通過(guò)畫(huà)圖發(fā)現(xiàn)，實(shí)質(zhì)就是在遍歷樹(shù)的同時(shí)交換非葉節(jié)點(diǎn)的左右子節(jié)點(diǎn)。
- 面試題20順時(shí)針打印矩陣：通過(guò)畫(huà)圖發(fā)現(xiàn)丐重，實(shí)質(zhì)就是一圈一圈的打印數(shù)組腔召。
- 面試題26復(fù)雜鏈表的復(fù)制：畫(huà)圖，發(fā)現(xiàn)復(fù)制鏈表的過(guò)程扮惦，分三個(gè)步驟：復(fù)制節(jié)點(diǎn)臀蛛，設(shè)置random指針，拆分兩個(gè)鏈表崖蜜。
面試題 19：二叉樹(shù)的鏡像（反轉(zhuǎn)二叉樹(shù)）
題目：請(qǐng)完成一個(gè)函數(shù)浊仆，輸入一個(gè)二叉樹(shù)，該函數(shù)輸出它的鏡像豫领。
題目分析
LeetCode 226. Invert Binary Tree
何為鏡像：即照鏡子得到的像抡柿，與原像是左右顛倒的。
求二叉樹(shù)鏡像：即反轉(zhuǎn)二叉樹(shù)氏堤。
求解思路：對(duì)于每個(gè)非葉子節(jié)點(diǎn)沙绝，反轉(zhuǎn)其左右孩子節(jié)點(diǎn)。既可以用遞歸也可以用迭代鼠锈。
題目典故：著名的Homebrew的作者Max Howell在面試Google時(shí)被問(wèn)到這題，并且沒(méi)有做出來(lái)星著，原推文
- Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
題目考點(diǎn)及相關(guān)題目
問(wèn)題本質(zhì)：樹(shù)的DFS或BFS遍歷购笆。
擴(kuò)展：掌握非遞歸的實(shí)現(xiàn)。
我的代碼如下：
1.遞歸方法：
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
2.非遞歸DFS（棧）:
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()) {
final TreeNode node = stack.pop();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
stack.push(node.left);
}
if(node.right != null) {
stack.push(node.right);
}
}
return root;
}
3.非遞歸BFS（隊(duì)列）：
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
final Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
final TreeNode node = queue.poll();
final TreeNode left = node.left;
node.left = node.right;
node.right = left;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
面試題 20：順時(shí)針打印矩陣
題目：輸入一個(gè)矩陣虚循，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字同欠。
題目分析
LeetCode 54. Spiral Matrix
順時(shí)針打印矩陣：即螺旋矩陣輸出。
規(guī)律：一圈一圈的輸出數(shù)組里的數(shù)據(jù)横缔，注意邊界條件不好確定時(shí)铺遂，多畫(huà)幾個(gè)圖就很清楚了。
邊界： “上”肯定要打印茎刚，打印“右”的條件是至少有兩行襟锐，打印“下”至少兩行兩列；打印“左”至少要有三行兩列膛锭。
題目考點(diǎn)及相關(guān)題目
多畫(huà)圖粮坞，幫助理解。
相關(guān)題目有：LeetCode 59. Spiral Matrix II
我的代碼如下：
解法一：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if(matrix.length <= 0) return res;
int m = matrix.length, n = matrix[0].length;
int min = Math.min(m, n);
int k = min%2 == 0 ? (min/2 - 1) : min/2;
for(int i = 0; i <= k; i ++)
spiral(matrix, i, res, m, n);
return res;
}
public void spiral(int[][] matrix, int k, List<Integer> res, int m, int n){
// 上
for(int i = k; i < n - k; i ++)
res.add(matrix[k][i]);
// 右
for(int i = k + 1; i < m - k; i ++)
res.add(matrix[i][n-k-1]);
// 下(加判斷條件初狰，排除兩種情況：只有一列時(shí)莫杈，只有一行時(shí))
if(k < n - k - 1 && k < m - k - 1){
for(int i = n - k - 2; i >= k; i --)
res.add(matrix[m-k-1][i]);
}
// 左(加判斷條件，排除兩種情況：只有一列時(shí)奢入，只有不超過(guò)2行時(shí))
if(k < n - k - 1 && k < m - k - 2){
for(int i = m - k - 2; i > k; i --)
res.add(matrix[i][k]);
}
}
}
解法二：
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<Integer>();
if (matrix.length == 0) {
return res;
}
int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
// Traver Up
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin ++;
}
return res;
}
}
第2節(jié)：舉例分析方法
通過(guò)舉例子筝闹，理解題目意思并找到規(guī)律；最后也以用例子來(lái)測(cè)試程序是否完善。
- 面試題22棧的壓入关顷、彈出序列：通過(guò)舉實(shí)際棧的例子糊秆，來(lái)模擬棧的壓入和彈出操作，就能發(fā)現(xiàn)隱藏的規(guī)律解寝。
- 面試題24二叉搜索樹(shù)的后序遍歷序列：理解后續(xù)遍歷的特點(diǎn)扩然，并找到遞歸方法的思路。
- 面試題21包含min函數(shù)的棧：用一個(gè)棧來(lái)專門來(lái)存儲(chǔ)當(dāng)前棧中的最小值聋伦。
面試題 21：包含min函數(shù)的棧
題目：定義棧的數(shù)據(jù)結(jié)構(gòu)夫偶，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的min函數(shù)。在該函數(shù)中觉增，調(diào)用min兵拢、push、及pop的時(shí)間復(fù)雜度都是$O(1)$逾礁。
題目分析
- 使用兩個(gè)棧说铃，一個(gè)數(shù)據(jù)棧，一個(gè)最小數(shù)棧
- 每次存放數(shù)據(jù)時(shí)嘹履，若存放的數(shù)據(jù)比此時(shí)最小棧中的棧頂值要大腻扇，那么將最小數(shù)棧棧頂元素再存一次（即增加一個(gè)棧頂元素），如果要存的數(shù)據(jù)比棧頂元素小砾嫉，那么就將此值也存入最小值棧幼苛。
- 出棧時(shí)，兩棧都要同時(shí)出數(shù)據(jù)焕刮，使得最小數(shù)棧的棧頂元素總是目前數(shù)據(jù)棧中的最小值舶沿。兩個(gè)棧中的元素個(gè)數(shù)總是保持相等。
題目考點(diǎn)及相關(guān)題目
用一個(gè)輔助棧來(lái)存儲(chǔ)最小值元素配并。
相關(guān)題目：LeetCode 239. Sliding Window Maximum
我的代碼如下：
class MinStack {
Stack<Integer> data;
Stack<Integer> min;
public MinStack() {
// do initialize if necessary
data = new Stack<Integer>();
min = new Stack<Integer>();
}
public void push(int x) {
if (!min.isEmpty() && min.peek() < x) min.push(min.peek());
else min.push(x);
data.push(x);
}
public void pop() {
min.pop();
data.pop();
}
public int top() {
return data.peek();
}
public int getMin() {
return min.peek();
}
}
面試題 22：棧的壓入括荡、彈出序列
題目：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示 棧的壓入順序溉旋，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序畸冲。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列
1低滩、2召夹、3、4恕沫、5是某棧的壓棧序列监憎，序列4、5婶溯、3鲸阔、2偷霉、1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4褐筛、3类少、5、1渔扎、2就不可能是該壓棧序列的彈出序列硫狞。
題目分析
用一個(gè)輔助棧stack來(lái)存儲(chǔ)壓棧序列，如果下一個(gè)彈出的數(shù)字剛好是輔助棧頂數(shù)字晃痴，那么直接彈出残吩，并將輔助棧內(nèi)棧頂數(shù)字也彈出；如果下一個(gè)彈出的數(shù)字不在輔助棧頂倘核，我們把壓棧序列中還沒(méi)有入棧的數(shù)字壓入輔助棧泣侮，直到下一個(gè)需要彈出的數(shù)字壓入棧頂為止。如果 所有的數(shù)字都 壓入棧了仍然沒(méi)有找到下一個(gè)彈出的數(shù)字紧唱，那么該序列不可能是一個(gè)彈出序列活尊。
題目考點(diǎn)及相關(guān)題目
棧的壓入、彈出操作漏益。
我的代碼如下：
public boolean isPopOrder(List<Integer> push, List<Integer> pop){
if(pop.size() != push.size()) return false;
Stack<Integer> stack = new Stack<Integer>();
while(!pop.isEmpty()){
if(stack.isEmpty()) stack.push(push.remove(0));
while(stack.peek() != pop.get(0) && !push.isEmpty()) stack.push(push.remove(0));
if(push.isEmpty() && stack.peek() != pop.get(0)) return false;
else{
stack.pop();
pop.remove(0);
}
}
return true;
}
面試題 23：從上往下打印二叉樹(shù)
題目：從上往下拓印出二叉樹(shù)的每個(gè)結(jié)點(diǎn)蛹锰，同層的結(jié)點(diǎn) 按照從左到右的順序 打印。
題目分析
LeetCode 102. Binary Tree Level Order Traversal
即樹(shù)的層次遍歷绰疤，用到了隊(duì)列宁仔。
題目考點(diǎn)及相關(guān)題目
層次遍歷，隊(duì)列峦睡。
相關(guān)題目：LeetCode 103. Binary Tree Zigzag Level Order Traversal、LeetCode 107. Binary Tree Level Order Traversal II权埠、LeetCode 111. Minimum Depth of Binary Tree
我的代碼如下：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> rs = new ArrayList<List<Integer>>();
LinkedList<TreeNode> level = new LinkedList<TreeNode>();
if(root != null) level.push(root);
while(!level.isEmpty()){
int levelNum = level.size();
List<Integer> tmp = new ArrayList<Integer>();
for(int i=0; i<levelNum; i++){
TreeNode temp = level.removeFirst();
tmp.add(temp.val);
if(temp.left != null) level.add(temp.left);
if(temp.right != null) level.add(temp.right);
}
rs.add(tmp);
}
return rs;
}
}
面試題 24：二叉搜索樹(shù)的后序遍歷序列
題目：輸入一個(gè)整數(shù)數(shù)組榨了，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。如果是則返回
true攘蔽，否則返回false龙屉。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
題目分析
經(jīng)過(guò)分析可知满俗，后序遍歷得到的序列的特點(diǎn)：
- 最后一個(gè)數(shù)字是該二叉搜索樹(shù)的根節(jié)點(diǎn)转捕，前面的序列又可以分成兩部分；
- 前一部分是根節(jié)點(diǎn)的左子樹(shù)唆垃，它們的值都比根節(jié)點(diǎn)值形逯ァ；
- 后一部分是根節(jié)點(diǎn)的右子樹(shù)辕万，它們的值都比根節(jié)點(diǎn)值大枢步。
因此沉删，需要再次判斷該二叉樹(shù)的左子樹(shù)序列和右子樹(shù)序列是否滿足以上特點(diǎn)。很明顯地醉途，這是一個(gè)遞歸操作的過(guò)程矾瑰。
題目考點(diǎn)及相關(guān)題目
二叉搜索樹(shù)的概念以及后序遍歷的特點(diǎn)
相關(guān)題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的前序遍歷的結(jié)果隘擎。
我的代碼如下：
1.我的遞歸程序殴穴，沒(méi)有經(jīng)過(guò)完整的校驗(yàn)
public class Solution{
public boolean VerifySequenceOfBST(int[] sequence){
if(sequence.length <= 0) return false;
return verify(sequence, 0, sequence.length - 1);
}
public boolean verify(int[] sequence, int start, int end){
if(start >= end) return true;
int root = sequence[end];
int i = start, j = end - 1;
// 找到左右子序列的分界處，經(jīng)驗(yàn)證货葬，無(wú)論是只有左子樹(shù)還是只有右子樹(shù)采幌，或者左右子樹(shù)均有的情況，都會(huì)滿足i == j + 1宝惰；否則說(shuō)明該序列不滿足二叉搜索樹(shù)的性質(zhì)植榕。
while(i < end && sequence[i] < root) i ++;
while(j >= start && sequence[j] > root) j --;
if(i != j + 1) return false;
return verify(sequence, start, j) && verify(sequence, i, end - 1);
}
}
2.標(biāo)準(zhǔn)答案請(qǐng)見(jiàn)P158。
面試題 25：二叉樹(shù)中和為某一值的路徑
題目：輸入一棵二叉樹(shù)和一個(gè)整數(shù)尼夺，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑尊残。從樹(shù)的根節(jié)點(diǎn)開(kāi)始往下一直到葉子節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)形成一條路徑。
題目分析
- 首先這種題肯定是對(duì)樹(shù)遍歷淤堵，而樹(shù)的遍歷要么是深搜寝衫，要么是廣搜；
- 對(duì)于深搜拐邪，那就是遞歸了慰毅，關(guān)鍵問(wèn)題在：怎么計(jì)算并存儲(chǔ)遍歷到當(dāng)前節(jié)點(diǎn)時(shí)的和，可以用我的方法扎阶，用一個(gè)變量來(lái)記錄到達(dá)當(dāng)前節(jié)點(diǎn)的和汹胃，或者方法二中比較巧妙的思想。
- 深搜遞歸總會(huì)遇到的問(wèn)題是：變量（中間結(jié)果）在傳遞的過(guò)程中會(huì)發(fā)生改變东臀，比如方法一中的：list和cur着饥，一定要注意還原，這是非常重要的一步惰赋，否則會(huì)導(dǎo)致先前的結(jié)果仍然在list當(dāng)中宰掉。這也是形參和實(shí)參的問(wèn)題。
- 對(duì)于廣搜赁濒，那么就要用額外的變量存儲(chǔ)到達(dá)每個(gè)節(jié)點(diǎn)的和轨奄，這種方法的空間復(fù)雜度比較高，這里就不仔細(xì)介紹了拒炎。
題目考點(diǎn)及相關(guān)題目
樹(shù)的前序遍歷挪拟，也就是DFS
相關(guān)題目：Path Sum、Binary Tree Paths
我的代碼如下：
1.我的深搜代碼
public class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null) return res;
pathSumWithDFS(root, root.val, new ArrayList<Integer>(Arrays.asList(root.val)), sum);
return res;
}
public void pathSumWithDFS(TreeNode root, int cur, List<Integer> list, int sum){
if(root.left == null && root.right == null){
if(cur == sum) {
// 這是十分推薦的寫(xiě)法
List<Integer> temp = new ArrayList<Integer>(list);
res.add(temp);
}
return;
}
//if(cur >= sum) return; 注意這一句不能加枝冀，因?yàn)榭赡芄?jié)點(diǎn)值有負(fù)值舞丛。
if(root.left != null) {
list.add(root.left.val);
pathSumWithDFS(root.left, cur + root.left.val, list, sum);
// 這一步非常重要
list.remove(list.size()-1);
}
if(root.right != null) {
list.add(root.right.val);
pathSumWithDFS(root.right, cur + root.right.val, list, sum);
// 這一步非常重要
list.remove(list.size()-1);
}
}
}
2.他人更加簡(jiǎn)潔的代碼（用棧更好耘子，而且它這個(gè)函數(shù)不用記錄到目前節(jié)點(diǎn)的和，而是用sum-當(dāng)前節(jié)點(diǎn)的值球切，方法更加巧妙）
public class Solution {
private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
public void pathSumInner(TreeNode root, int sum, Stack<Integer>path) {
path.push(root.val);
if(root.left == null && root.right == null)
if(sum == root.val) resultList.add(new ArrayList<Integer>(path));
if(root.left!=null) pathSumInner(root.left, sum-root.val, path);
if(root.right!=null)pathSumInner(root.right, sum-root.val, path);
// 這一步非常重要
path.pop();
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root==null) return resultList;
Stack<Integer> path = new Stack<Integer>();
pathSumInner(root, sum, path);
return resultList;
}
}
第3節(jié)：分解讓復(fù)雜問(wèn)題簡(jiǎn)單化
分治法：先把大問(wèn)題分解成若干個(gè)小問(wèn)題谷誓，然后再逐個(gè)解決的思想。
- 面試題27二叉搜索樹(shù)與雙向鏈表：把大問(wèn)題分解成左子樹(shù)和右子樹(shù)兩個(gè)小問(wèn)題吨凑，然后再把轉(zhuǎn)換左右子樹(shù)得到的鏈表和根結(jié)點(diǎn)鏈接起來(lái)就解決了整個(gè)問(wèn)題捍歪。
- 面試題28字符串的排列：整個(gè)字符串的排列是一個(gè)大問(wèn)題，而第一個(gè)字符之后的字符串的排列就是一個(gè)小問(wèn)題鸵钝，因此分解問(wèn)題糙臼，并采用遞歸思想解決。
面試題 26：復(fù)雜鏈表的復(fù)制
題目：請(qǐng)實(shí)現(xiàn)函數(shù)
ComplexListNode *Clone(ComplexListNode *pHead)恩商，復(fù)制一個(gè)復(fù)雜鏈表变逃。在復(fù)雜鏈表中，每個(gè)結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)怠堪，還有一個(gè)m_pSibling指向的任意結(jié)點(diǎn)或者NULL揽乱。
題目分析
LeetCode 138. Copy List with Random Pointer
- 首先，要理解什么是深拷貝粟矿。
-深拷貝是指在拷貝對(duì)象時(shí)凰棉，同時(shí)會(huì)對(duì)引用指向的對(duì)象進(jìn)行拷貝。
-相對(duì)應(yīng)的陌粹，淺拷貝是指在拷貝對(duì)象時(shí)撒犀，對(duì)于基本數(shù)據(jù)類型的變量會(huì)重新復(fù)制一份，而對(duì)于引用類型的變量只是對(duì)引用進(jìn)行拷貝掏秩。- 此題深拷貝鏈表或舞，主要分為如下兩步：
-第一步復(fù)制原始鏈表中的結(jié)點(diǎn)，并用next指針連接起來(lái)蒙幻。
-第二步設(shè)置每個(gè)結(jié)點(diǎn)的random指針嚷那。- 第一步很容易就可以完成，主要在于第二步杆煞，很容易就會(huì)犯淺拷貝的錯(cuò)。只是復(fù)制了對(duì)象的引用腐泻，導(dǎo)致結(jié)果出錯(cuò)决乎。
- 第二步中復(fù)制random指針，應(yīng)該是根據(jù)原鏈表中節(jié)點(diǎn)N的random指針指向的節(jié)點(diǎn)S派桩，找到新鏈表中所對(duì)應(yīng)的S'构诚，而不是簡(jiǎn)單地將新鏈表中的N'的random指針指向S。
- 至于如何找到對(duì)應(yīng)的S'铆惑，有兩種方法：
-要么都從頭指針開(kāi)始遍歷經(jīng)過(guò)指針N范嘱，N'且經(jīng)過(guò)相同步分別找到S, S'送膳。這樣的話，時(shí)間復(fù)雜度會(huì)到O(n^2)丑蛤。
-要么就是用空間換時(shí)間叠聋，使用Map存儲(chǔ)新舊鏈表中的對(duì)應(yīng)的節(jié)點(diǎn)對(duì)<N, N'>- 還有另外一種方法，既不用開(kāi)辟新的空間來(lái)存儲(chǔ)節(jié)點(diǎn)受裹，也不用從頭遍歷查找碌补。方法比較巧妙：
>- 在第一步復(fù)制原始鏈表結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)鏈接在原結(jié)點(diǎn)后面棉饶，然后再將新結(jié)點(diǎn)的next指針指向原結(jié)點(diǎn)的next指針厦章，具體如下：
- 第二步鏈接新結(jié)點(diǎn)的random指針就很容易了，它對(duì)應(yīng)在原結(jié)點(diǎn)的random指針的后面一個(gè)結(jié)點(diǎn)照藻，具體如下：
題目考點(diǎn)及相關(guān)題目
把復(fù)雜鏈表的復(fù)制過(guò)程分解成三個(gè)步驟：復(fù)制結(jié)點(diǎn)袜啃、設(shè)置random指針、拆分兩個(gè)鏈表幸缕。
相關(guān)題目：Clone Graph
我的代碼如下：
1.使用HashMap群发，空間換時(shí)間，時(shí)間復(fù)雜度$O(n)$冀值，空間復(fù)雜度$O(n)$也物。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return head;
RandomListNode newHead = new RandomListNode(0);
RandomListNode p = newHead;
RandomListNode s = newHead;
RandomListNode q = head;
RandomListNode r = head;
Map<RandomListNode, RandomListNode> nodes = new HashMap<RandomListNode, RandomListNode>();
while(q != null){
RandomListNode tmp = new RandomListNode(q.label);
p.next = tmp;
p = p.next;
nodes.put(q, p);
q = q.next;
}
//p.next = null;
while(r != null){
s.next.random = nodes.get(r.random);
s = s.next;
r = r.next;
}
return newHead.next;
}
}
2.使用鏈接方式，方法巧妙列疗，時(shí)間復(fù)雜度$O(n)$滑蚯，空間復(fù)雜度$O(1)$。
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head == null) return null;
RandomListNode p = head, q = p;
while(p != null){
RandomListNode tmp = new RandomListNode(p.label);
RandomListNode next = p.next;
p.next = tmp;
tmp.next = next;
p = next;
}
while(q != null){
RandomListNode t = q.next;
t.random = q.random == null ? null : q.random.next;
q = t.next;
}
RandomListNode newHead = head.next, s = head;
while(s != null){
RandomListNode n = s.next;
s.next = n.next;
s = s.next;
n.next = s == null ? null : s.next;
}
return newHead;
}
}
面試題 27：二叉搜索樹(shù)與雙向鏈表
題目：輸入一棵二叉搜索樹(shù)抵栈，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表告材。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向古劲。
題目分析
- 注意題目要求：不能創(chuàng)建任何新的結(jié)點(diǎn)斥赋，只能調(diào)整指針的指向
- 因?yàn)樵诙鏄?shù)中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指向子結(jié)點(diǎn)的指針产艾，在雙向鏈表中每個(gè)結(jié)點(diǎn)也有兩個(gè)指針疤剑，它們分別指向前、后兩個(gè)結(jié)點(diǎn)闷堡。因此隘膘，在理論上有可能實(shí)現(xiàn)二叉搜索樹(shù)和排序的雙向鏈表的轉(zhuǎn)換。
- 由于要求轉(zhuǎn)換之后雙向鏈表是排好序的杠览，而二叉搜索樹(shù)的中序遍歷剛好是一個(gè)有序數(shù)組弯菊，因此此題的遍歷方法肯定是中序遍歷二叉搜索樹(shù)。
- 具體思想：如下圖踱阿，當(dāng)遍歷到根節(jié)點(diǎn)
10時(shí)管钳，我們將樹(shù)看成三部分钦铁，根節(jié)點(diǎn)10、根節(jié)點(diǎn)為6的左子樹(shù)才漆、根節(jié)點(diǎn)為14的右子樹(shù)牛曹，可以想像一下，如果左子樹(shù)已經(jīng)排好序成為了雙向鏈表栽烂，那么它的最后一個(gè)節(jié)點(diǎn)（也就是左子樹(shù)里的最大值8）的右指針將指向10躏仇，同理，10的右指針將指向右子樹(shù)里的最小值12腺办，如下圖所示：很明顯焰手，上述就是一個(gè)遞歸過(guò)程。
中序.png中序2.png
題目考點(diǎn)及相關(guān)題目
分治法的本質(zhì)：將復(fù)雜問(wèn)題分解成小問(wèn)題怀喉，然后遞歸調(diào)用函數(shù)功能书妻，即可完成對(duì)復(fù)雜問(wèn)題的求解。
相關(guān)題目：LeetCode 114. Flatten Binary Tree to Linked List
我的代碼如下：
1.未經(jīng)驗(yàn)證的Java代碼躬拢，時(shí)間復(fù)雜度較高躲履，全耗在了遍歷左子樹(shù)，找到最后一個(gè)節(jié)點(diǎn)上面聊闯， $O(n^2)$工猜。
public TreeNode Convert(TreeNode root){
if(root == null) return null;
TreeNode head = Convert(root.left);
if(head == null) head = root;
else{
TreeNode p = head;
while(p.right != null) p = p.right;
p.right = root;
root.left = p;
}
TreeNode right = Convert(root.right);
root.right = right;
if(right != null)
right.left = root;
return head;
}
2.標(biāo)準(zhǔn)答案見(jiàn)P170
面試題 28：字符串的排列
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列菱蔬。例如輸入字符
a篷帅、b、c所能排列出來(lái)的所有字符串abc拴泌、acb魏身、bac、bca蚪腐、cab和cba箭昵。
題目分析
- 先不談解題思路，先看題目要求：打印出該字符串中字符的所有排列回季，如果字符串存在相同字符家制，那么打印出的結(jié)果也肯定會(huì)包含相同的字符串，但是只從題目字面上理解泡一，是沒(méi)有讓我們?nèi)ブ氐奈看裕虼丝梢圆挥霉艽蛴〕龅淖址惺欠翊嬖谙嗤那闆r；但是如果讓我們?nèi)ブ氐脑採迹仁褂胠ist.contains(o)判斷一下是否存在，再?zèng)Q定是否添加哪亿。
- 求解思路：
-將一個(gè)字符串看成由兩部分組成：第一部分為它的第一個(gè)字符粥烁，第二部分是后面的所有字符贤笆；
-我們求整個(gè)字符串的排列，可以看成兩步：首先求所有可能出現(xiàn)在第一個(gè)位置的字符讨阻，即把第一個(gè)字符和后面所有的字符交換芥永；然后固定第一個(gè)字符，求后面所有字符的排列钝吮。
-很明顯埋涧，這是典型的遞歸思路。
題目考點(diǎn)及相關(guān)題目
本質(zhì)：按照一定要求擺放若干數(shù)字奇瘦，可以先求出這些數(shù)字的所有排列棘催，然后再一一判斷每個(gè)排列是否滿足題目所給定的要求。
本題擴(kuò)展：求字符的所有組合（如對(duì)于字符串
abc的所有組合a, b, c, ab, ac, bc, abc）耳标，求解思路仍然差不多醇坝，將輸入的n個(gè)字符看成兩部分：第一個(gè)字符和后面所有字符，在構(gòu)成長(zhǎng)度m的組合時(shí)次坡，分兩種情況考慮：1）如果包含第一個(gè)字符呼猪，則需要從后面的所有字符中選取m-1個(gè)字符，2）如果不包含第一個(gè)字符砸琅，則從后面的所有字符中選取m個(gè)字符宋距。分析到這里，就感覺(jué)可以用動(dòng)態(tài)規(guī)劃了症脂，遞推公式：$f(n,m) = f(n-1, m-1) + f(n-1, m)$谚赎，具體實(shí)現(xiàn)就不細(xì)說(shuō)了。
相關(guān)題目：八皇后問(wèn)題（回溯）摊腋；8個(gè)數(shù)字放在正方體8個(gè)頂點(diǎn)上沸版，問(wèn)是否有可能使得正方體三組相對(duì)的面上的4個(gè)頂點(diǎn)的和都相等。
我的代碼如下：
public List<String> Permutation(String string){
List<String> res = new ArrayList<String>();
Permutation(new StringBuffer(string), 0, res);
return res;
}
public static void Permutation(StringBuffer sb, int start, List<String> list){
if(start == sb.length()) {
// 這是去重后的結(jié)果
/* if(!list.contains(sb.toString())){
list.add(sb.toString());
System.out.println(sb);
}*/
// 不去重的結(jié)果
list.add(sb.toString());
}else{
for(int i = start; i < sb.length(); i ++){
char temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(start));
sb.setCharAt(start, temp);
Permutation(sb, start + 1, list);
// 對(duì)更改的內(nèi)容進(jìn)行還原
temp = sb.charAt(i);
sb.setCharAt(i, sb.charAt(start));
sb.setCharAt(start, temp);
}
}
}
第4節(jié)：本章小結(jié)
當(dāng)遇到難題兴蒸，沒(méi)有任何思路時(shí)视粮，一般的求解辦法：畫(huà)圖、舉例橙凳、分解蕾殴。
具體算法就會(huì)涉及到分治法、動(dòng)態(tài)規(guī)劃法岛啸，都是通過(guò)分解問(wèn)題而來(lái)钓觉。
