1. 每日溫度(單調棧)
題目地址：https://leetcode-cn.com/problems/daily-temperatures/
題目 ：請根據(jù)每日氣溫列表temperatures，請計算在每一天需要等幾天才會有更高的溫度。如果氣溫在這之后都不會升高，請在該位置用0來代替。
示例 1:
輸入: temperatures = [73,74,75,71,69,72,76,73]
輸出: [1,1,4,2,1,1,0,0]
解法一 ： 比較容易想到的方法是暴力解法，遍歷每一個元素，并依次在后邊的元素中查找大于該元素的位置，下邊是我實現(xiàn)的代碼 ：
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] ans = new int[temperatures.length] ;
for (int i=0 ;i<temperatures.length ; i++){
for(int j=i+1 ;j<temperatures.length ;j++){
if(temperatures[j] > temperatures[i]){
ans[i] = j-i;
break;
}
ans[i] = 0 ;
}
}
return ans ;
}
}
這種方法時間復雜度很高，估計面試給出也不會是期望答案。
解法二：
首先，介紹單調棧數(shù)據(jù)結構。 單調遞增棧 ：從棧底到棧頂是從大到小。單調遞減棧 ：從棧底到棧頂是從小到大。
如果壓棧元素 <= 棧頂元素，那么入棧 ；否則彈出棧頂元素。 很明顯該題目使用的就是單調遞增棧。 因為最終要輸出的是第一個比該數(shù)大的數(shù)的下標，所以棧里邊存的是元素的位置，而不是元素本身。在輸出結果時，計算一下當前遍歷的元素的位置i和棧內存儲的位置的差（i-cur），就是要寫入目標數(shù)組的元素。這里要注意每次從棧彈出元素時，目標數(shù)組寫入一個值。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int tempLength = temperatures.length ;
int[] ans = new int[tempLength] ;
Stack<Integer> stack = new Stack<>() ;
for(int i=0 ;i<tempLength ;i++){
if(stack.isEmpty() || temperatures[i] <= temperatures[stack.peek()]){
stack.push(i);
}
else{
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
int cur = stack.pop() ;
ans[cur] = i - cur ;
}
stack.push(i) ;
}
}
return ans ;
}
}
2. 螺旋矩陣(矩陣、模擬)
題目地址： https://leetcode-cn.com/problems/spiral-matrix/
題目 ： 給你一個 m 行 n 列的矩陣 matrix ，請按照 順時針螺旋順序 ，返回矩陣中的所有元素。下邊是一個示例：
這道題個人感覺還是比較難的，我自己嘗試了一個種方法，先向右再向下再向左再向上挪一步，其間碰到矩陣的邊界，或者碰到已經訪問過的格子，就轉向。但是提交后發(fā)現(xiàn)并不正確，如果繞大圈需要從底往上到第一個元素才能轉向，這時候優(yōu)先向上而不是向右。可見第一次的思路還是有問題的，看了題解的答案，發(fā)現(xiàn)大部分代碼我還是想到了，例如方向、例如創(chuàng)建一個mn的矩陣保存哪些格子訪問過。最關鍵的一點，不是沒步驟按優(yōu)先級，而是把一個方向走到頭之后換方向*。
下邊的代碼是我的實現(xiàn) ：
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//保存輸出結果數(shù)組
int rl = matrix.length , cl = matrix[0].length ;
List<Integer> ans = new ArrayList<>() ;
//建立矩陣記錄哪些被訪問過
int[][] visited = new int[rl][cl];
int vt=1 ,m=0 , n=0;
//初始化第一個元素matrix[0][0] 先開始。
visited[m][n] = 1 ;
ans.add(matrix[m][n]) ;
//順時針，先往右挪，再往下挪，再往左挪，再往上挪。
int[][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}} ;
int initDirection = 0 ; //初始往右
while(vt < rl*cl){
int nextRow = m + directions[initDirection][0] ;
int nextColumn = n + directions[initDirection][1];
if(nextRow < 0 || nextRow == rl || nextColumn <0 || nextColumn == cl || visited[nextRow][nextColumn] == 1){
//達到邊界后，換一個方向
initDirection = (initDirection + 1)%4 ;
}
m+=directions[initDirection][0] ;
n+=directions[initDirection][1] ;
ans.add(matrix[m][n]) ;
//標記為訪問過
visited[m][n] = 1 ;
vt++ ;
}
return ans ;
}
}
這道題目確實考驗對數(shù)組API的使用熟練度，我有以下的積累，希望后邊能用到 ：
1.數(shù)組初始化、之后賦值的方法 ：
int[] intArr;
intArr = new int[]{1,2,3,4,5,9};
2.求二維數(shù)組的行和列 ：
行數(shù) = matrix.length ， 列數(shù) = matrix[0].length
3. 最長遞增子序列（動態(tài)規(guī)劃）
題目：https://leetcode-cn.com/problems/longest-increasing-subsequence/
動態(tài)規(guī)劃是一類重要而且常出的題目。 動態(tài)規(guī)劃（英語：Dynamic programming，簡稱 DP）是一種在數(shù)學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。
動態(tài)規(guī)劃類題目需要考慮能否將問題規(guī)模減小，將問題規(guī)模減小的方式有很多種，一些典型的減小方式是動態(tài)規(guī)劃分類的依據(jù)，例如線性，區(qū)間，樹形等。數(shù)組上常用的減少規(guī)模的方式包括：每次減少一半/每次減少一個。
解決動態(tài)規(guī)劃問題最難的地方有兩點：
如何定義 f(n)
如何通過 f(1), f(2), … f(n - 1) 推導出 f(n)，即狀態(tài)轉移方程。
該題目找最長嚴格遞增子序列，拆解子問題時，可以從只包含第一個元素開始迭代，每次找i的dp狀態(tài)值是，從0到i-1迭代dp[j] + 1 (如果a[i] > a[j] ，否則不加1)，這樣就找到轉移方程了。 我在紙上描述了狀態(tài)轉移方程如下 ：
這樣代碼就好寫了，下邊是代碼，調試過程中我遇到了幾個問題：1.dp方程的元素并不是單調遞增的，例如原始序列[1,3,6,4,2] ，dp[4] = 2 并不等于 dp[3] + 0 。 2. dp[0] 需要初始化為1 否則它之前沒有可比較的數(shù)字。
class Solution {
public int lengthOfLIS(int[] nums) {
//邊界情況
int len = nums.length ;
if (len == 0) return 0 ;
//狀態(tài)轉移方程 f(i) = max{f(j)} + 1
int[] dp = new int[len] ;
dp[0] = 1 ;
int ans = 0 ;
for (int i=1 ; i<len ;i++){
int maxLIS = 1; //最小是1
for (int j=0 ; j < i ;j++ ){
if (nums[j] < nums[i] ) {
maxLIS = Integer.max(maxLIS,dp[j] + 1 ) ;
}
}
dp[i] = maxLIS ;
}
for(int tp : dp) ans = Integer.max(ans,tp) ;
return ans ;
}
}
4.乘積最大子數(shù)組（動態(tài)規(guī)劃）
https://leetcode-cn.com/problems/maximum-product-subarray/
給你一個整數(shù)數(shù)組 nums，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應的乘積。
示例 1:
輸入: [2,3,-2,4]
輸出: 6
解釋:子數(shù)組 [2,3] 有最大乘積 6。
該題目也可以使用DP解決，線性DP，使用前一個位置計算。這里最大乘積會相對復雜一點，如果前一個數(shù)字是一個負數(shù)并且絕對值很大，如果第i個位置也是負數(shù)，負負得正。也可能得到正確答案，所以，我這里除了新建一個dp[]來保存最大值外，還定義了一個minDp[]來保存最小值，每次計算一個最大值一個最小值，分別存在這2個數(shù)組里。 下邊是我理解的動態(tài)轉移方程：
class Solution {
public int maxProduct(int[] nums) {
int len = nums.length ;
if(len ==0 ) return 0 ;
int[] dp = new int[len] ;
int[] minDp = new int[len] ;
dp[0] = nums[0] ;
minDp[0] = nums[0] ;
for(int i =1 ;i <len ;i++){
dp[i] = Integer.max(nums[i] , Integer.max(nums[i]*dp[i-1] , nums[i]*minDp[i-1])) ;
minDp[i] = Integer.min(nums[i] , Integer.min(nums[i]*dp[i-1] , nums[i]*minDp[i-1])) ;
}
int ans = Integer.MIN_VALUE ;
for (int k=0 ;k<len ;k++){
ans = Integer.max(ans,dp[k]) ;
}
return ans ;
}
}
5.打家竊舍（動態(tài)規(guī)劃）
題目地址： https://leetcode-cn.com/problems/house-robber/
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。
示例 1：
輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
該題目是典型的dp問題，相比前邊的最大和的子數(shù)組問題，難點在于，不能取相鄰的數(shù)組的數(shù)字，這里就需要找下規(guī)律，并改下動態(tài)規(guī)劃方程。 這里dp[0] 就是第一個元素（這里不解釋）。 dp[1] 應該是 max (dp[0] , nums[1]) 第2個元素可能是第一個元素，也可能是第2個元素。
一般情況下的動態(tài)轉移方程是 ：
dp[i]=max(dp[i?2]+nums[i],dp[i?1]) ，加上上邊說的邊界條件 ：
邊界條件為：
dp[0]=nums[0]
dp[1]=max(nums[0],nums[1])
分析到這里，代碼就太好寫了，下邊是我的實現(xiàn) ：
int len = nums.length ;
if (len == 1) return nums[0] ;
int[] dp = new int[len] ;
dp[0] = nums[0] ;
dp[1] = Integer.max(dp[0], nums[1]) ;
int ans = Integer.max(dp[0], dp[1]) ;
for (int i=2;i <len ;i++){
dp[i] = Integer.max(dp[i-2] + nums[i] , dp[i-1]) ;
ans = Integer.max(ans,dp[i]);
}
return ans ;
6.打家劫舍II
題目地址：https://leetcode-cn.com/problems/house-robber-ii/solution/da-jia-jie-she-ii-by-leetcode-solution-bwja/
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。
示例1：
輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。
這個題目跟題目5相似，但是不能是首位相接，如何才能保證第一間房屋和最后一間房屋不同時偷竊呢？如果偷竊了第一間房屋，則不能偷竊最后一間房屋，因此偷竊房屋的范圍是第一間房屋到最后第二間房屋；如果偷竊了最后一間房屋，則不能偷竊第一間房屋，因此偷竊房屋的范圍是第二間房屋到最后一間房屋。
數(shù)組nums的長度為n。如果不偷竊最后一間房屋，則偷竊房屋的下標范圍是[0,n-2]；如果不偷竊第一間房屋，則偷竊房屋的下標范圍是[1,n-1]。
下面是我實現(xiàn)的代碼：
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
7. 最長等差子序列 ：
這個類型的題目是一個擴展動態(tài)規(guī)劃，動態(tài)轉移方程結果使用哈希表來存儲。 先看原始簡單第一題：
https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/
該題目，要找存在的最長等差子序列，并且給了固定長度的“等差” 。 那么使用一個HashMap來保存狀態(tài)，Key就是原始數(shù)組里的值，value就是截止到dp[i]為止，最大的等差子序列的長度。這里是實現(xiàn)用Put時候，如果有比該值小于固定等差的key時，其value就加1，否則重新從1開始。代碼如下：
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int len = arr.length ;
if(len == 1) return 1;
Map<Integer,Integer> dp = new HashMap<>() ;
int maxDp = 0;
for (int vd : arr){
int gsp = dp.getOrDefault(vd - difference , 0) +1 ;
dp.put(vd, gsp);
maxDp = Integer.max(gsp,maxDp) ;
}
return maxDp ;
}
}
那下邊的非定長等差數(shù)列就是上邊題目的一個升級了，沒有提供出定長的“等差”。
https://leetcode-cn.com/problems/longest-arithmetic-subsequence/
這里的方法也比較巧妙，我先用一個Set枚舉出所有可能的“等差”(longestArithSeqLength函數(shù)中定義)， 再每一個等差帶入上邊的函數(shù)中，再從每個輸出結果中選出最大的，雖然感覺這種方法較笨，但是也能解決問題。代碼如下：
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int len = arr.length ;
if(len == 1) return 1;
Map<Integer,Integer> dp = new HashMap<>() ;
int maxDp = 0;
for (int vd : arr){
int gsp = dp.getOrDefault(vd - difference , 0) +1 ;
dp.put(vd, gsp);
maxDp = Integer.max(gsp,maxDp) ;
}
return maxDp ;
}
public int longestArithSeqLength(int[] nums) {
int len = nums.length ;
//保存可能出現(xiàn)的等差
Set<Integer> allDis = new HashSet<>() ;
int i=0 ,j=0 ;
for (i=0 ;i<len ;i++){
for (j=i+1 ; j<len ;j++){
allDis.add(nums[j] - nums[i]) ;
}
}
int ans = 0 ;
for(int dis : allDis){
ans = Integer.max(ans,longestSubsequence(nums,dis)) ;
}
return ans ;
}
}
8. N叉樹的遍歷問題（深度優(yōu)先遍歷DFS） ：
關于樹的遍歷，我們很快就想到了DFS，這也是深度優(yōu)先遍歷的典型題目。 下面摘取了Leetcode上關于DFS的一些知識的介紹，可以先做掃盲吧。
深度優(yōu)先遍歷
1.只要前面有可以走的路，就會一直向前走，直到無路可走才會回頭；
2.「無路可走」有兩種情況：① 遇到了墻；② 遇到了已經走過的路；
3.在「無路可走」的時候，沿著原路返回，直到回到了還有未走過的路的路口，嘗試繼續(xù)走沒有走過的路徑；
4.有一些路徑沒有走到，這是因為找到了出口，程序就停止了；
5.「深度優(yōu)先遍歷」也叫「深度優(yōu)先搜索」，遍歷是行為的描述，搜索是目的（用途）；
遍歷不是很深奧的事情，把 所有 可能的情況都看一遍，才能說「找到了目標元素」或者「沒找到目標元素」。遍歷也稱為 窮舉，窮舉的思想在人類看來雖然很不起眼，但借助 計算機強大的計算能力，窮舉可以幫助我們解決很多專業(yè)領域知識不能解決的問題。
「遍歷」和「搜索」可以看作是兩個的等價概念，通過遍歷 所有 的可能的情況達到搜索的目的。遍歷是手段，搜索是目的。因此「深度優(yōu)先遍歷」也叫「深度優(yōu)先搜索」。
leetcode 上的dfs問題，直接想到遞歸解決就行了。下面列舉了一道N叉樹的前序遍歷題目，我也是按照遞歸來解決的。
https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
class Solution {
private void traverse(Node root, List<Integer> mylist){
mylist.add(root.val) ;
if (root.children.size() > 0){
for (Node c : root.children){
traverse(c,mylist);
}
}
}
public List<Integer> preorder(Node root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
traverse(root,ans) ;
return ans ;
}
}
那么同樣地，還有N叉樹的后續(xù)遍歷的一道題目，也一起做了。
https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
class Solution {
private void traverse(Node root, List<Integer> mylist){
if (root.children.size() > 0){
for (Node c : root.children){
traverse(c,mylist);
}
}
mylist.add(root.val) ;
}
public List<Integer> postorder(Node root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
traverse(root,ans) ;
return ans ;
}
}
9.二叉樹的層序遍歷（廣度優(yōu)先搜索BFS）
廣度優(yōu)先搜索的算法，一般都借助隊列來完成。 在圖論，樹的遍歷，最短路徑等方向都有著廣泛的應用，這種題目一般有固定的套路，多練一些題目還是很有必要的 。
首先，先來看一道樹的層級遍歷題目（leetcode這2道都是一樣的） ：
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
這道題目，借助隊列，把樹的每一層單獨處理，代碼還是不難寫出的，這里不贅述了，代碼很簡單：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//輔助隊列
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
//輸出結果
List<List<Integer>> ans = new ArrayList<>() ;
if(root == null) return ans ;
while (!queue.isEmpty()){
List<Integer> ansOne = new ArrayList<>() ;
List<TreeNode> ansTree = new ArrayList<>() ;
//把本層節(jié)點加入到一個List中
while(!queue.isEmpty()){
TreeNode curNode = queue.poll() ;
ansOne.add(curNode.val) ;
ansTree.add(curNode) ;
}
//本層的子節(jié)點入隊
for(TreeNode c : ansTree){
if(c.left != null) queue.add(c.left) ;
if(c.right != null) queue.add(c.right) ;
}
ans.add(ansOne) ;
}
return ans ;
}
}
這道題和上邊題目一模一樣，只修改了最終輸出結果的數(shù)據(jù)類型。
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
這道題的輸出變成了Int[]，其余和原來的程序并沒有太大差別，這里將ArrayList轉 int[]就用最low的for循環(huán)來完成 ：
class Solution {
public int[] levelOrder(TreeNode root) {
//輔助隊列
Queue<TreeNode> queue = new LinkedList<>() ;
queue.add(root) ;
//輸出結果
List<Integer> ans = new ArrayList<>() ;
if(root == null) return new int[0] ;
while (!queue.isEmpty()){
List<TreeNode> ansTree = new ArrayList<>() ;
//把本層節(jié)點加入到一個List中
while(!queue.isEmpty()){
TreeNode curNode = queue.poll() ;
ansTree.add(curNode);
ans.add(curNode.val);
}
//本層的子節(jié)點入隊
for(TreeNode c : ansTree){
if(c.left != null) queue.add(c.left) ;
if(c.right != null) queue.add(c.right) ;
}
}
int[] c = new int[ans.size()] ;
for(int i= 0 ;i<c.length ;i++){
c[i] = ans.get(i) ;
}
return c ;
}
}
下面這道題也是層級打印的一個變體：
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
這里需要注意2點：（1）在偶數(shù)層級（例如2，4層級）逆序List輸出值。（2）子節(jié)點入隊的順序并不能改變，還按照原來順序。下邊是我實現(xiàn)的代碼
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>() ;
Queue<TreeNode> queue = new LinkedList<>() ;
if(root == null) return ans ;
queue.add(root);
int level = 0 ;
while(!queue.isEmpty()){
List<Integer> ansOne = new ArrayList<>() ;
List<Integer> ansOneReverse = new ArrayList<>() ;
List<TreeNode> ansTreeNode = new ArrayList<>() ;
//本層節(jié)點入隊
while(!queue.isEmpty()){
TreeNode curNode = queue.poll() ;
ansTreeNode.add(curNode) ;
ansOne.add(curNode.val);
}
level ++ ; //控制奇偶層級，偶數(shù)層級逆序打印
//子節(jié)點入隊的順序還是按照從左到右
for(TreeNode d : ansTreeNode){
if(d.left != null) queue.add(d.left) ;
if(d.right != null) queue.add(d.right) ;
}
if(level%2==0){
//打印結果到輸出List中
int i = ansOne.size() ;
while(i>0){
ansOneReverse.add(ansOne.get(i-1));
--i;
}
ans.add(ansOneReverse) ;
}
else{
ans.add(ansOne) ;
}
}
return ans ;
}
}
通過閱讀題解，發(fā)現(xiàn)逆序一個ArrayList，提供了現(xiàn)成的方法，不用再循環(huán)遍歷了，這里學習一下吧（未注釋的2行可以替代注釋的所有）。另外，也可以使用雙端隊列繼續(xù)優(yōu)化，Deque （Double End Queue）, LinkedList<Integer> listDemo = new Linked<>() , Deque<Integer> dequeDemo = new Linked<>()
// if(level%2==0){
// //打印結果到輸出List中
// int i = ansOne.size() ;
// while(i>0){
// ansOneReverse.add(ansOne.get(i-1));
// --i;
// }
// ans.add(ansOneReverse) ;
// }
// else{
// ans.add(ansOne) ;
// }
if(level%2==0) Collections.reverse(ansOne) ;
ans.add(ansOne);
