第一：暴力法

往往是for循環(huán)，因?yàn)槲覀冏龅念}目絕大多數(shù)都是查找問題。
技巧：下一層for循環(huán)從哪里開始查找，從哪里開始停止

//雙層或者多層for循環(huán)for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {System.out.println(i+""+j);}

第二：雙指針

技巧：for循環(huán)變while，滿足題目中的一些條件時(shí)候，while里面中條件用判斷是否跳出循環(huán)
一：很典型的是二分查找，這里的條件就是遞增序列
https://leetcode-cn.com/problems/binary-search/

public int search(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target) return mid;else if(nums[mid] > target) right = mid - 1;else if(nums[mid] < target) left = mid + 1;}return -1;}

二：很典型的滑動(dòng)窗口（滑動(dòng)窗口也屬于雙指針的一種），這里的條件是什么呢？就是和《=target，并且有范圍
自己可以嘗試使用暴力for循環(huán)求解一下。
https://leetcode-cn.com/problems/minimum-size-subarray-sum/

public int minSubArrayLen(int target, int[] nums) {int l=0 ,r=0;int count = Integer.MAX_VALUE;while (r<nums.length){target -= nums[r];while (target<=0){count = Math.min(count,r-l+1);target +=nums[l];l++;}r++;}// 注意邊界值的鎖定return count== Integer.MAX_VALUE ? 0 : count;}

三、回溯法

回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯。
那么先練習(xí)遞歸：遞歸要去理解的話，真的是不好理解
面試題：求x的n次方

int function(int x, int n) {int result = 1; // 注意 任何數(shù)的0次方等于1for (int i = 0; i < n; i++) {result = result * x;}return result; }

如果用遞歸實(shí)現(xiàn)呢？這個(gè)比較好理解，因?yàn)槊看蔚姆祷刂刀紩?huì)乘以x，那么累計(jì)下來就是x的n次方了

int function(int x, int n) {if (n == 0) {return 1; // return 1 同樣是因?yàn)?次方是等于1的}return function(x, n - 1) * x; }

.遞歸就是有去（遞去）有回（歸來）
有去：是指把問題分解成無(wú)數(shù)的小問題，一層一層地解決，最終到達(dá)臨界點(diǎn)之后，即解決完最后一個(gè)需要調(diào)用自身函數(shù)處理的問題之后，有回：將解決的結(jié)果原路返回到原點(diǎn)，原問題解決。
實(shí)驗(yàn)一下一下的代碼

static int a;static int function(int x, int n) {if (n == 0) {return 1; // return 1 同樣是因?yàn)?次方是等于1的}System.out.println("遞歸前的值"+a);int c = 0;a = function(x, n - 1) * x;c=c+1;System.out.println("c的值"+c);System.out.println("遞歸后a的值"+a);return a;}public static void main(String[] args) {function(3,3);}

你會(huì)發(fā)現(xiàn)每次遞歸之前a都是0，而當(dāng)return 1之后，c每次都是1，也就是每次c都是從0開始+1，遞歸后a的值一次是3，9，27.
每次打印a，都是遞的過程，這個(gè)過程只產(chǎn)生了一個(gè)個(gè)子函數(shù)的棧，每次打印c都是歸的過程，為什么c的值每次都是從0開始+1呢，因?yàn)闅w的c，還是曾經(jīng)那個(gè)沒有+1的c，在剛剛結(jié)束的函數(shù)的棧里面。

組合問題
https://leetcode-cn.com/problems/combinations/
接下里我們來看一個(gè)真正的回溯問題：

List<List<Integer>> res=new ArrayList<>();List<Integer> list=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {backTrace( 1,n,k);return res;}void backTrace(int index,int n,int k){if(list.size()==k){res.add(new ArrayList<>(list));return;}for (int i = index; i <= n; i++){list.add(i);backTrace(i+1,n,k);list.remove(list.size()-1);}}

仔細(xì)體會(huì)一下遞和歸的過程，本地debug一下，特別是第一次return后，從哪里開始執(zhí)行。

回溯法，一般可以解決如下幾種問題：
組合問題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合
切割問題：一個(gè)字符串按一定規(guī)則有幾種切割方式
子集問題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集
排列問題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式
棋盤問題：N皇后，解數(shù)獨(dú)等等
組合是不強(qiáng)調(diào)元素順序的，排列是強(qiáng)調(diào)元素順序。
回溯算法模板框架如下：

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {處理節(jié)點(diǎn);backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果} }

關(guān)于回溯法的總結(jié)這篇文章已經(jīng)很地道了：https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%9B%9E%E6%BA%AF%E6%B3%95%E8%A7%A3%E5%86%B3%E7%9A%84%E9%97%AE%E9%A2%98

四、搜索

深度優(yōu)先搜索

了解遞歸之后，我們要知道遞歸的一種重要的應(yīng)用算法，深度優(yōu)先，深度優(yōu)先一般都是采用遞歸棧的形式來實(shí)現(xiàn)
深度優(yōu)先搜索屬于圖算法的一種，是一個(gè)針對(duì)圖和樹的遍歷算法，英文縮寫為DFS即Depth First Search。深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?#xff0c;利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題，如最大路徑問題等等。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)DFS算法。其過程簡(jiǎn)要來說是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次。
關(guān)于深度優(yōu)先搜索，這并不是一個(gè)很好的例子，因?yàn)闆]有if（）+return，那么什么時(shí)候return呢，自然是代碼跑完后return
https://leetcode-cn.com/problems/number-of-provinces/

// n個(gè)城市的連通性問題，dfs的深度即省份的個(gè)數(shù);這道題由于是nn矩陣那么我們可以按照?qǐng)D的深度優(yōu)先搜索來做這道題// 從模版里面看棧里面要存什么？存周圍未訪問的節(jié)點(diǎn) 怎么保證已訪問的節(jié)點(diǎn)不再訪問？我們用一個(gè)boolean數(shù)組來保證//if （周邊都沒有相連的） return 換個(gè)方向繼續(xù)試public int findCircleNum(int[][] isConnected) {int n = isConnected.length;Boolean visited[] = new Boolean[n];int circle = 0;// 每個(gè)未訪問的節(jié)點(diǎn)都需要進(jìn)行深搜for (int i = 0; i < n; i++) {if (!visited[i]){circle++; //加次數(shù)dfs(isConnected,visited,i,n);}}return circle;}private void dfs(int[][] isConnected,Boolean [] visited, int i, int n) {// 對(duì)當(dāng)前頂點(diǎn) i 進(jìn)行訪問標(biāo)記visited[i] =true;//一個(gè)節(jié)點(diǎn)與其他的周邊9個(gè)節(jié)點(diǎn)全部遍歷一遍，這是用圖的方式來做for (int j = 0; j <n ; j++) {if (isConnected[i][j] ==1 && visited[j]!=true){dfs(isConnected,visited,j,n);}//如果沒有就繼續(xù)for循環(huán)對(duì)另外一個(gè)做不撞南墻不回頭，如果所有都遍歷完了，那么從這個(gè)節(jié)點(diǎn)的深度遍歷結(jié)束}// 這里其實(shí)隱藏著return}

深度優(yōu)先除了處理圖問題（圖問題又可以用臨接矩陣來代替，本質(zhì)上是遍歷矩陣）
如果不是nXn矩陣那么純的便利矩陣深度優(yōu)先搜索又該怎么做呢？那么就變成了深度搜索mXn個(gè)單元格，來試試島嶼的個(gè)數(shù)這道題。
https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/

public int numIslands(char[][] grid) {int m =grid.length;int n =grid[0].length;int count = 0;for (int i = 0; i <m ; i++) {for (int j = 0; j < n; j++) {if (grid[i][j]=='1'){count++;dfs(grid,i,j,m,n);}}}return count;}private void dfs(char[][] grid, int i, int j,int m,int n) {if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == '0') {return;}grid[i][j] ='0';dfs(grid,i-1,j,m,n);dfs(grid,i+1,j,m,n);dfs(grid,i,j-1,m,n);dfs(grid,i,j+1,m,n);}

還可以處理樹問題，比較典型的先序、中序、后序遍歷
貼一道簡(jiǎn)單題：https://leetcode-cn.com/problems/path-sum/

//判斷什么時(shí)候終止遞歸？怎么存已經(jīng)訪問過的節(jié)點(diǎn)？ 葉子節(jié)點(diǎn)終止遞歸，訪問過的我們的tagetsum就會(huì)剪掉，算作訪問過了public boolean hasPathSum(TreeNode root, int targetSum) {return dfs(root.right,targetSum);}private boolean dfs(TreeNode root, int targetSum) {if (root==null){return false;}if (root.right==null && root.left==null){return targetSum == root.val;}return dfs(root.right,targetSum-root.val) || dfs(root.left,targetSum-root.val);}

還有就是樹的變形，可以抽象成一顆樹的，比如說字典樹
https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/

class WordDictionary {TrieNode trieTree;public WordDictionary() {trieTree = new TrieNode();}public void addWord(String word) {if (null == word || word.length() < 1){return;}TrieNode cur = trieTree;for (int i = 0; i < word.length(); i++) {if (cur==null){cur.children.put(word.charAt(i),new TrieNode());}if (!cur.children.containsKey(word.charAt(i))){cur.children.put(word.charAt(i),new TrieNode());}cur = cur.children.get(word.charAt(i));}cur.isTail = true;}public boolean search(String word) {TrieNode cur = trieTree;if (cur==null) {return false;}return dfs(cur,0,word);}// 需要解釋下為什么只能有dfs，不能跟add一樣直接將當(dāng)前置為子節(jié)點(diǎn)，因?yàn)闉?的時(shí)候需要全遍歷private boolean dfs(TrieNode trieTree, int index, String word) {if (index>=word.length()){return trieTree.isTail;}if (trieTree.children.containsKey(word.charAt(index))){return dfs(trieTree.children.get(word.charAt(index)),index+1,word);}if (word.charAt(index)=='.'){for (Map.Entry<Character,TrieNode> child:trieTree.children.entrySet()) {if (dfs(child.getValue(),index+1,word)) {return true;}}}return false;}class TrieNode {boolean isTail;HashMap<Character,TrieNode> children;public TrieNode() {children = new HashMap<>();isTail =false;}} }

廣度優(yōu)先搜索

廣度優(yōu)先搜索（也稱寬度優(yōu)先搜索，縮寫B(tài)FS，以下采用廣度來描述）是連通圖的一種遍歷算法這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。基本過程，BFS是從根節(jié)點(diǎn)開始，沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問，則算法中止。一般用隊(duì)列數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)BFS算法。

https://leetcode-cn.com/problems/number-of-islands/

// 來看下我們需要什么？需要一個(gè)隊(duì)列來保存周圍還未訪問的節(jié)點(diǎn)，需要一個(gè)數(shù)組來保存是否訪問過，這里我們直接設(shè)置為0來標(biāo)示// 訪問過了，方向一共四個(gè)public int numIslands(char[][] grid) {int count = 0;for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(grid[i][j] == '1'){bfs(grid, i, j);count++;}}}return count;}private void bfs(char[][] grid, int i, int j) {// 想存一個(gè)Integer 就將二維數(shù)組轉(zhuǎn)成一維// 借用一個(gè)隊(duì)列 queue，判斷隊(duì)列首部節(jié)點(diǎn) (i, j) 是否未越界且為 1：//若是則置零（刪除島嶼節(jié)點(diǎn)），并將此節(jié)點(diǎn)上下左右節(jié)點(diǎn) (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入隊(duì)列；//若不是則跳過此節(jié)點(diǎn)；Deque<int[]> list = new LinkedList<>();list.add(new int[] { i, j });while(!list.isEmpty()) {int[] cur = list.remove();i = cur[0]; j = cur[1];if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {grid[i][j] = '0'; //相當(dāng)于刪除這個(gè)關(guān)系list.add(new int[] { i + 1, j }); //list.add(new int[] { i - 1, j });list.add(new int[] { i, j + 1 });list.add(new int[] { i, j - 1 });}}}``` 這是圖的，我們?cè)賮砜纯礃涞膶有虮闅v https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ ```java public class inorderTraversal {static List<List<Integer>> result;public List<List<Integer>> levelOrder(TreeNode root) {Deque<TreeNode> que = new LinkedList<>();que.offer(root);while(!que.isEmpty()) {List<Integer> level = new ArrayList<Integer>(); //記錄每一層的listint currentLevelSize = que.size(); //記錄每一層的節(jié)點(diǎn)個(gè)數(shù)for (int i = 0; i <currentLevelSize ; i++) {TreeNode node = que.poll();level.add(node.val);if (node.right!=null) {que.offer(node.right);}if (node.left!=null) {que.offer(node.left);}}result.add(level);}return result;}}

總結(jié)一下：

層序遍歷先寫個(gè)
while(que!=null)
{ 記錄一下上一層的個(gè)數(shù)，這一點(diǎn)很重要
依次出隊(duì)
處理下這個(gè)節(jié)點(diǎn)
并且把這個(gè)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)入隊(duì)
}

https://blog.csdn.net/qq_35789269/article/details/118686761

拓?fù)渑判?/h1>

給定一個(gè)包含 nn 個(gè)節(jié)點(diǎn)的有向圖 GG，我們給出它的節(jié)點(diǎn)編號(hào)的一種排列，如果滿足：
對(duì)于圖 GG 中的任意一條有向邊 (u, v)(u,v)，u 在排列中都出現(xiàn)在 v的前面。

來通過一道題來實(shí)戰(zhàn)拓?fù)渑判?#xff1a;
https://leetcode-cn.com/problems/course-schedule/
1、判斷是否有環(huán)來打破拓?fù)?#xff08;對(duì)應(yīng)深度優(yōu)先搜索算法）
記住這三個(gè)標(biāo)志位對(duì)應(yīng)的狀態(tài)
i == 0 ： 干凈的，未被 DFS 訪問
i == -1：其他節(jié)點(diǎn)啟動(dòng)的 DFS 訪問過了，路徑?jīng)]問題，不需要再訪問了
i == 1 ：本節(jié)點(diǎn)啟動(dòng)的 DFS 訪問過了，一旦遇到了也說明有環(huán)了

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> adjacency = new ArrayList<>();for(int i = 0; i < numCourses; i++)adjacency.add(new ArrayList<>());int[] flags = new int[numCourses];for(int[] cp : prerequisites)adjacency.get(cp[1]).add(cp[0]);for(int i = 0; i < numCourses; i++)if(!dfs(adjacency, flags, i)) return false;return true;}private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {if(flags[i] == 1) return false;if(flags[i] == -1) return true;flags[i] = 1;for(Integer j : adjacency.get(i))if(!dfs(adjacency, flags, j)) return false;flags[i] = -1;return true;} }

2、通過入度表來打破（對(duì)應(yīng)廣度優(yōu)先搜索算法）

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegrees = new int[numCourses];List<List<Integer>> adjacency = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++)adjacency.add(new ArrayList<>());// Get the indegree and adjacency of every course.for(int[] cp : prerequisites) {indegrees[cp[0]]++;adjacency.get(cp[1]).add(cp[0]);}// Get all the courses with the indegree of 0.for(int i = 0; i < numCourses; i++)if(indegrees[i] == 0) queue.add(i);// BFS TopSort.while(!queue.isEmpty()) {int pre = queue.poll();numCourses--;for(int cur : adjacency.get(pre))if(--indegrees[cur] == 0) queue.add(cur);}return numCourses == 0;} }

最短路徑問題

最短路徑用bfs處理是最好的
787. K 站中轉(zhuǎn)內(nèi)最便宜的航班
https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/

class Solution {public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {List<int[]>[] edges = new List[n];// 從src到i到價(jià)格int[] price = new int [n];Deque<int[]> queue = new LinkedList<>();for (int i = 0; i <n ; i++) {edges[i] = new ArrayList<>();price[i] = Integer.MAX_VALUE;}for (int i = 0; i < flights.length; i++) {edges[flights[i][0]].add(new int[]{flights[i][1],flights[i][2]});}price[src] = 0;// 這里設(shè)計(jì)很重要，必須跟個(gè)次數(shù)，因?yàn)橛衚到限制,src到i的次數(shù)和費(fèi)用queue.offer(new int[]{src,0,price[src]});while (!queue.isEmpty()) {int [] poll = queue.poll();if (poll[1]>k) break;for(int[] next :edges[poll[0]]){if (next[1]+poll[2]<price[next[0]]){price[next[0]] = next[1]+poll[2];//更新費(fèi)用queue.add(new int[]{next[0],poll[1]+1,price[next[0]]});}}}return price[dst]==Integer.MAX_VALUE?-1:price[dst];} }

涉及到幾種，邊是否帶權(quán)重，是否有關(guān)系？
List<int[]>[] edges = new List[n];
List<List> adjacency = new ArrayList<>();
還有就是隊(duì)列的設(shè)計(jì)，要包含些什么信息比較好

五、動(dòng)態(tài)規(guī)劃

對(duì)于迭代搜索求結(jié)果，多少種方法的還有一種常用的方法，那就是動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃，英文：Dynamic Programming，簡(jiǎn)稱DP，如果某一問題有很多重疊子問題，使用動(dòng)態(tài)規(guī)劃是最有效的。所以動(dòng)態(tài)規(guī)劃中每一個(gè)狀態(tài)一定是由上一個(gè)狀態(tài)推導(dǎo)出來的。
對(duì)于動(dòng)態(tài)規(guī)劃問題，有人將拆解為如下五步曲，這五步都搞清楚了，才能說把動(dòng)態(tài)規(guī)劃真的掌握了！

確定dp數(shù)組（dp table）以及下標(biāo)的含義

確定遞推公式

dp數(shù)組如何初始化

確定遍歷順序

舉例推導(dǎo)dp數(shù)組
來個(gè)最簡(jiǎn)單的：
斐波拉契
https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

//這個(gè)就很簡(jiǎn)單了，都給出來了//dp數(shù)組就是f（n），遍歷順序從前到后了// F(0) = 0，F(1) = 1// F(n) = F(n - 1) + F(n - 2)public int fib(int n) {int [] dp = new int[n+1];dp[0] =0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i-2]+dp[i-1];}return dp[n];}

這道題也可以做遞歸，當(dāng)然也并不需要維護(hù)這么長(zhǎng)的dp數(shù)組的。
動(dòng)態(tài)規(guī)劃要不是從小到大，一次遞推，要么是做選擇max、min等。
打家劫舍：
https://leetcode-cn.com/problems/house-robber/

//第i家偷還是不偷//如果偷dp[i] =dp[i-2]+i//不偷dp[i] =dp[i-1]//最佳就是取他們之間最大的public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int n = nums.length;int dp[] = new int[n+1];dp[0] = nums[0];dp[1] =Math.max(dp[0],nums[1]);for (int i = 2; i <n ; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[n-1];}

零錢兌換
https://leetcode-cn.com/problems/coin-change/

public static int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount + 1];//初始化dp數(shù)組為最大值for (int j = 0; j < dp.length; j++) {dp[j] = max;}//當(dāng)金額為0時(shí)需要的硬幣數(shù)目為0dp[0] = 0;for (int i = 0; i < coins.length; i++) {//正序遍歷：完全背包每個(gè)硬幣可以選擇多次for (int j = coins[i]; j <= amount; j++) {//只有dp[j-coins[i]]不是初始最大值時(shí)，該位才有選擇的必要,第一次j=coins[i],肯定是0，j再++//就把缺少coins[i]并且小雨amount的dp[amout]求出來了if (dp[j - coins[i]] != max) {//選擇硬幣數(shù)目最小的情況，這里的dp[i]實(shí)際上上一輪的最小值，所以這里需要做更新dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];}public static void main(String[] args) {coinChange(new int[]{1,2,3},6);}

六、前綴和（一般用來求子數(shù)組的和或者滿足什么條件的子數(shù)組等）

前綴和有個(gè)非常神奇的定理：
以數(shù)組為例
for循環(huán)求完前綴和之后+再雙for循環(huán)遍歷前綴和的差值（就是子數(shù)組的和）還是以上一道題為例子，體會(huì)一下這個(gè)過程
雖然對(duì)于上道題，除了二分優(yōu)化了點(diǎn)（下面注釋掉的那一部分），其實(shí)沒有什么優(yōu)勢(shì)

public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int count = Integer.MAX_VALUE;int sum[] = new int[n+1];// 為了方便計(jì)算，令 size = n + 1// sums[0] = 0 意味著前 0 個(gè)元素的前綴和為 0// sums[1] = A[0] 前 1 個(gè)元素的前綴和為 A[0]// 以此類推,不要小看這個(gè)假設(shè)，和鏈表設(shè)置頭節(jié)點(diǎn)一樣，這for (int i = 1; i <= n; i++) {sum[i] = sum[i-1]+nums[i];}for (int i = 1; i <= n ; i++) {int sumMax = target +sum[i-1];// 返回// int bound = Arrays.binarySearch(sum, sumMax); 下面那個(gè)for循環(huán)可以用這個(gè)代替int bound = 0;for (int j = 1; j <=n ; j++) {if (sumMax ==sum[j]){bound = j;}}count = Math.min(count,bound-i+1);}return count == Integer.MAX_VALUE ? 0 : count;}

前綴和對(duì)應(yīng)有個(gè)很相似的思想叫差分思想

差分思想：
1）對(duì)于原始數(shù)組arr[a, b, c, d]，其差分?jǐn)?shù)組為：diff[a, b-a, c-b, d-c]
2）差分?jǐn)?shù)組的前綴和數(shù)組 == 原始數(shù)組，即：求差分?jǐn)?shù)組的前綴和數(shù)組，即可還原回去。[a, a + b-a, a+b-a + c-b, …]
3）對(duì)原始數(shù)組的區(qū)間增加，可以轉(zhuǎn)化為對(duì)其差分?jǐn)?shù)組的兩點(diǎn)增加（ O(n) -> O(1) ）：
假設(shè)對(duì)arr[i … j]區(qū)間每個(gè)元素全部增加delta，則等價(jià)于：diff[i] += delta，diff[j+1] -= delta
//對(duì)于數(shù)組 [1,2,2,4]，其差分?jǐn)?shù)組為 [1,1,0,2]，
對(duì)于原數(shù)組，下標(biāo)1，2的都加一【1，3，3，4】，其差分?jǐn)?shù)組【1，2，0，1】

鏈接：https://leetcode-cn.com/problems/corporate-flight-bookings

public class corpFlightBookings {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums = new int[n];for (int[] booking : bookings) {//先需要將差分?jǐn)?shù)組d[l]位置加 inc,這樣下標(biāo) >= l 位置的元素都獲得inc增量//其次,為了不影響原數(shù)組中下標(biāo)大于 r 的元素,需要在d[r + 1]處減去inc,使得原數(shù)組下標(biāo) > r 的元素值不變.//對(duì)于這段話不理解的//對(duì)于數(shù)組 [1,2,2,4]，其差分?jǐn)?shù)組為 [1,1,0,2]，//【1,12,12,4】其差分?jǐn)?shù)組為【1，11，0，-8】nums[booking[0]-1] = booking[2];if (booking[1]<n){nums[booking[1]] -= booking[2];}}for (int i = 0; i < n; i++) {nums[i]+=nums[i-1];}return nums;}

更多前綴和都題目到這篇文章中看
https://blog.csdn.net/qq_35789269/article/details/120051335?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164070565316780271591421%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=164070565316780271591421&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_ecpm_v1~rank_v31_ecpm-2-120051335.nonecase&utm_term=%E5%B7%AE%E5%88%86&spm=1018.2226.3001.4450

七、單調(diào)棧

通常是一維數(shù)組，要尋找任一個(gè)元素的右邊或者左邊第一個(gè)比自己大或者小的元素的位置，此時(shí)我們就要想到可以用單調(diào)棧了
每日溫度
https://leetcode-cn.com/problems/daily-temperatures/

// 這里的關(guān)鍵是棧里面要存下標(biāo)public int[] dailyTemperatures(int[] temperatures) {Deque<Integer> stack = new LinkedList<>();int n = temperatures.length;int []result = new int[n];for (int i = 0; i < n; i++) {//int temp0 = temperatures[i];while(!stack.isEmpty() && temp0>temperatures[stack.peek()]){//int temp = ;int prevIndex = stack.pop();result[prevIndex] = i-prevIndex;}//只要沒有大的就繼續(xù)入棧stack.push(i);}return result;}

八、樹

對(duì)于樹，我們得知道如何構(gòu)建一顆比較常見的樹，比如最常見的完全二叉樹，如何遍歷一棵樹
https://blog.csdn.net/qq_35789269/article/details/116426945?ops_request_misc=%7B%22request%5Fid%22%3A%22163811878116780271558685%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fblog.%22%7D&request_id=163811878116780271558685&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_v2~rank_v29-1-116426945.pc_v2_rank_blog_default&utm_term=樹&spm=1018.2226.3001.4450
首先我們來知道如何從一個(gè)數(shù)組來生成一顆完全二叉樹
如果此時(shí)給我們一個(gè)順序存儲(chǔ)的數(shù)組，叫我們構(gòu)建一顆二叉樹
給定二叉樹 [3,9,20,null,null,15,7]，

// Definition for a binary tree node.public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }} public static TreeNode createBT(int[] arr, int i) // 初始時(shí),傳入的i==0 {TreeNode root = null; // 定義根節(jié)點(diǎn)if (i >= arr.length) // i >= arr.length 時(shí),表示已經(jīng)到達(dá)了根節(jié)點(diǎn)return null;root = new TreeNode(arr[i]); // 根節(jié)點(diǎn)// 這里其實(shí)很不好理解，理解的關(guān)鍵在于i值在遞和歸的時(shí)候的變化root.left = createBT(arr, 2*i+1); // 遞歸建立左孩子結(jié)點(diǎn)root.right = createBT(arr, 2*i+2); // 遞歸建立右孩子結(jié)點(diǎn)return root; }public class Main {public static void main(String[] args) {int[] arr = {3,9,20,null,null,15,7};TreeNode root = createBT(arr, 0);System.out.println("先序遍歷：");PreOrder(root);System.out.println("\n中序遍歷：");InOrder(root);System.out.println("\n后序遍歷：");PostOrder簡(jiǎn)單題(root);} // 這里只寫preOrder，中序和后序自己寫下public static void preOrder(TreeNode root){if (root==null){return;}System.out.println(root.val);preOrder(root.left) ;preOrder(root.right);}

再來處理一道關(guān)于樹的題目：
翻轉(zhuǎn)二叉樹：
https://leetcode-cn.com/problems/invert-binary-tree/
先分析一下：如果只有一層的二叉樹我們會(huì)怎么寫代碼？

TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
我相信每個(gè)人應(yīng)該都會(huì)寫出這樣的代碼。
這個(gè)時(shí)候我們回想下遞歸，如果我們從根節(jié)點(diǎn)開始，遞歸地對(duì)樹進(jìn)行遍歷，并從葉子節(jié)點(diǎn)先開始翻轉(zhuǎn)，那么不是就把整棵樹整完了嗎？
不難寫出這樣的代碼

public TreeNode invertTree(TreeNode root) {if (root==null){return null;}invertTree(root.right); invertTree(root.left);// 第一輪這里的root一定是倒數(shù)第二層的root，就可以交換其左孩子和右孩子了TreeNode temp = root.right;root.right = root.left;root.left = temp;return root;}``` # 并查集https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/ ```java package org.ling.offer.project01;public class MakeCon {static int fa[];static int count;public static int makeConnected(int n, int[][] connections) {init(n);count = n-1;// fa =new int[n];//如果初始布線數(shù)小于 n - 1，那么一定不能使所有計(jì)算機(jī)連通if (connections.length < n - 1) {return -1;}for (int i = 0; i < connections.length ; i++) {if (uoin(connections[i][0],connections[i][1])){count--;}}return count;}public static boolean uoin(int x,int y ){int xn = find(x);int yn = find(y);if (xn!=yn){fa[xn] = yn;return true;}return false;}public static void init(int n) {fa = new int[n];for (int i = 0; i <n ; i++) {fa[i] = i;}}// 這個(gè)梗方便理解，但實(shí)際上還是會(huì)超時(shí)static int find(int x){int r = x;while (fa[r] != r){r = fa[r]; // 找到根}// 這是x的值為x的根，讓那個(gè)我們把將 x → p 路徑上的所有節(jié)點(diǎn)的 fa 更新為 pwhile(fa[x]!=x){int t = fa[x];fa[x] = r;x =t ;}return x;}// 使用方法2利用遞歸棧來解決會(huì)好很多，因?yàn)榍罢邥?huì)跑兩次static int find2(int x){if(fa[x]==x){return x;}return fa[x]=find(fa[x]);}public static void main(String[] args) {int[][] c ={{0,1},{0,2},{1,2}};makeConnected(4,c);} }

這道題也可以用dfs做，不妨復(fù)習(xí)下dfs，但是和島嶼那道題不太一樣的是，這道題的邊才是我們要找的鄰接關(guān)系。

public class makeCon {static List<Integer>[] edges;static boolean[] used;public static int makeConnected(int n, int[][] connections) {if (connections.length < n - 1) {return -1;}edges = new List[n];for (int i = 0; i < n; i++) {edges[i] = new ArrayList<Integer>();}// 先要構(gòu)建鄰接矩陣for (int[] con : connections) {edges[con[0]].add(con[1]);edges[con[1]].add(con[0]);}used = new boolean[n];int ans = 0;for (int i = 0; i < n; i++) {if (!used[i]) {dfs(i);++ans;}}return ans-1;}private static void dfs(int u) {used[u] =true;for (int v:edges[u]) {if (!used[v]){dfs(v);}}}public static void main(String[] args) {int[][] c ={{0,1},{0,2},{1,2}};makeConnected(4,c);}

鳴謝：
https://blog.csdn.net/lxzxmm/article/details/81305039

總結(jié)

以上是生活随笔為你收集整理的力扣刷题系列总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。