04. 二維陣列中的查找
最左下角開始找，一個數右邊的數比當前數大，上邊的數比當前數小，目標數比當前數大上移，比當前數小就右移
53 - II. 0～n-1中缺失的數字
mid>right,最小值一定在mid的右邊，left=mid+1
mid<right,最小值一定是mid，或在mid的左邊，right=mid
mid=left或mid=right，從right開始往左找最小值
50. 第一個只出現一次的字符
用LinkedHashMap
32.III. 從上到下列印二叉樹 III
奇數層佇列的值加到佇列尾部，偶數層佇列的值加到佇列頭部，奇數層反著加，偶數層正著加
26. 樹的子結構
A和B的根節點相同的話直接進入比較 isSubStructureDfs(A,B) A和B的根節點不相同看B是不是A的左子樹或右子樹的子結構 isSubStructure(A.left,B) || isSubStructure(A.right,B) ? 3 / \ 4 5 / \ 1 2 4 / 1 1、isSub(3,4) 3不等于4 回傳false，看B是不是A的左子樹的子結構 isSub(3的左子樹,4) 2、isSub(4,4),dfs（4,4），4等于4，進行下一層遞回 dfs（4的左子樹,4的左子樹），即dfs（1，1），1等于1，進行下一層遞回 dfs（1的左子樹,1的左子樹），即dfs（null，null），B等于null回傳true，進行下一層遞回 dfs（1的右子樹,1的右子樹），即dfs（null，null），B等于null回傳true，isSub(4,4)這個遞回回傳true結束遞回
10- I. 斐波那契數列
陣列的長度要n+1，因為有第0項
63. 股票的最大利潤
第i天最大利潤=max(前i-1天的最大利潤，當天價格-前i-1天的最低價格)
前i-1天的最大利潤的利潤只用一個變數maxProfit維護，不用陣列
當天價格-前i-1天的最低價格大于maxProfit就更新maxProfit
前i-1天的最低價格只用一個變數minPrice維護，不用陣列：
當天價格小于minPrice就更新minPrice
42. 連續子陣列的最大和
以每個位置為終點的和最大子陣列 都是基于其前一位置的和最大子陣列計算得出
轉移方程： 若 dp[i-1] ≤0 ，說明 dp[i - 1]對 dp[i] 產生負貢獻，即 dp[i-1] + nums[i]不如 nums[i] 本身大，
?
當 dp[i - 1] > 0 時：執行 dp[i] = dp[i-1] + nums[i] ；
當 dp[i - 1] ≤0 時：執行 dp[i] = nums[i] ；
47. 禮物的最大價值
i=0，j !=0,dp[i][j]=grid[i][j]+dp[i][j-1] i != 0，j = 0,dp[i][j]=grid[i][j]+dp[i-1][j] i != 0，j != 0,dp[i][j]=grid[i][j]+ max.（dp[i][j-1]，dp[i-1][j]）
46. 把數字翻譯成字串
48. 最長不含重復字符的子字串
dp*[*j] 代表以字符 s[j] 為結尾的 “最長不重復子字串” 的長度
當 i < 0 ，即 s[j] 左邊無相同字符，則 dp[j] = dp[j-1] + 1 ；
當 dp[j - 1] < j - i ，說明字符 s[j] 在子字串 dp[j-1]dp[j?1] 區間之外 ，則 dp[j] = dp[j - 1] + 1 ；
當 dp[j - 1] ≥j?i ，說明字符 s[i] 在子字串 dp[j-1]區間之中 ，則 dp[j] 的左邊界由 s[i] 決定，即 dp[j] = j - i；
哈希表法：用哈希表記錄字符所在的索引
線性遍歷：左邊界 i獲取方式： 遍歷到 s[j]時，初始化索引 i = j - 1，向左遍歷搜索第一個滿足 s[i] = s[j] 的字符即可
滑動視窗法
哈希表 dic統計： 指標 j遍歷字符 s，哈希表統計字符 s[j]s[j] 最后一次出現的索引 ，
更新左指標 i ： 根據上輪左指標 i 和 dic[s[j]] ，每輪更新左邊界 i，保證區間 [i + 1, j][i+1,j] 內無重復字符且最大，
i=max(dic[s[j]],i)
更新結果 res： 取上輪 res 和本輪雙指標區間 [i + 1,j]的寬度（即 j - i）中的最大值，
res=max(res,j?i)
18.洗掉鏈表的節點
雙指標法或dummy節點
初始化雙指標法頭結點是pre，頭結點的next節點是cur
22.鏈表中倒數第k個節點
用雙指標法不用統計陣列長度
快指標先走k步，走完后快指標和慢指標相差k步，
然后慢指標和快指標一起走直到快指標為空就到達倒數第k個節點
5.合并兩個排序的鏈表
用dummy節點
21. 調整陣列順序使奇數位于偶數前面
初始化left指標為0，right指標為nums.length-1
left指標指的一定是奇數，right指標指的一定是偶數
58 - I. 翻轉單詞順序
從尾開始往前找每個
36. 二叉搜索樹與雙向鏈表
中序遍歷構建雙向鏈表
當 pre 為空時： 代表正在訪問鏈表頭節點，記為 head ； 當 pre 不為空時： 修改雙向節點參考，即 pre.right = cur（前驅指向后繼） ， cur.left = pre （后繼指向前驅）； 保存 cur ： 更新 pre = cur ，即節點 cur 是后繼節點的 pre ；
中序遍歷完成后要頭指向尾，尾指向頭形成回圈鏈表
頭指向尾：head.left = pre
尾指向頭：pre.right = head
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296232.html
標籤：其他
上一篇：記憶體吞金獸(Elasticsearch)的那些事兒 -- 資料結構及巧妙演算法
下一篇：貪心演算法