0. Tips

1. 位運算

如何枚舉一個二進制狀態數字k的子集, 方法就是針對中的二進制為1的位開始進行減法，判斷數字k的二進制子集, 像枚舉(2^k-1) ~ 0一樣枚舉其子集；

int sub = k;do {sub = (sub - 1) & k;} while(sub != k);

比如k = 10101的二進制子集有:
10101
10100
10001
10000
00101
00100
00001
00000

00000再-1為11111，&k后就等于k；

求1的個數 #include <cstdio> int main(){int n, cnt;cnt = 0;scanf("%d", &n);while (n) {cnt += (n & 1);n >>= 1;}printf("%d\n", cnt); }或者 int BitCount(unsigned int n) {unsigned int c =0 ;for (c =0; n; ++c){n &= (n -1) ; // 清除最低位的1}return c ; }

2. 快速冪

算法學習筆記(4)：快速冪 - 知乎

//遞歸快速冪 int qpow(int a, int n) {if (n == 0)return 1;else if (n % 2 == 1)return qpow(a, n - 1) * a;else{int temp = qpow(a, n / 2);return temp * temp;} }//遞歸快速冪（對大素數取模） #define MOD 1000000007 typedef long long ll; ll qpow(ll a, ll n) {if (n == 0)return 1;else if (n % 2 == 1)return qpow(a, n - 1) * a % MOD;else{ll temp = qpow(a, n / 2) % MOD;return temp * temp % MOD;} }//非遞歸快速冪 int qpow(int a, int n){int ans = 1;while(n){if(n&1) //如果n的當前末位為1ans *= a; //ans乘上當前的aa *= a; //a自乘n >>= 1; //n往右移一位}return ans; } //泛型的非遞歸快速冪 template <typename T> T qpow(T a, ll n) {T ans = 1; // 賦值為乘法單位元，可能要根據構造函數修改while (n){if (n & 1)ans = ans * a; // 這里就最好別用自乘了，不然重載完*還要重載*=，有點麻煩。n >>= 1;a = a * a;}return ans; }

3. 字符串

匹配算法1

Rabin-Karp算法

Rabin-Karp算法：尋找字符串S中字符串T出現的位置或次數的問題屬于字符串匹配問題

Rabin–Karp 把字符串轉化為一個hash值 不斷滑動窗口進出的思想，如何構造這一個hash值？

1044. 最長重復子串

// 1044. 最長重復子串// 二分法 + 字符串匹配算法 -- Rabin–Karp 把字符串轉化為一個hash值 不斷滑動窗口// 子串長度[0,n) 在這個范圍內枚舉當前值mid 若存在mid長的重復子串 則更新l=mid+1 否則r=mid-1// https://www.cnblogs.com/grandyang/p/14497723.htmlstring longestDupSubstring(string S) {int n = S.size();int l = 0, r = n, mod = 1e7 + 7;string res;// power 記錄每個位置的階數vector<int> power(n,1);for (int i = 1; i < n; i++) {power[i] = (power[i-1]*26) % mod;}while (l < r) {int mid = l + (r-l)/2;// rabinKarp 檢查是否存在長度為mid的重復子串string cur = rabinKarp(mid, S, power);if (cur.size() > res.size()) {res = cur;l = mid + 1;} else {// 注意二分的邊界 r取不到,所以r=midr = mid;}}return res;}string rabinKarp(int len, string s, vector<int> power) {if (len == 0) return "";unordered_map<int, vector<int>> hash;int cur = 0, mod = 1e7 + 7;for (int i = 0; i < len; ++i) {cur = (cur * 26 + s[i]-'a') % mod;}hash[cur] = {0};for (int i = len; i < s.size(); ++i) {// 此處不加mod的話，%后可能小于modcur = ((cur - (s[i-len]-'a') * power[len-1]) % mod + mod) % mod;cur = (cur * 26 + (s[i]-'a')) % mod;if (hash.count(cur)) {for (int t : hash[cur]) {if (s.substr(i - len + 1, len) == s.substr(t, len)) {return s.substr(t, len);}}hash[cur].push_back(i - len + 1);} else {hash[cur] = {i- len + 1};}}return "";}

GO SDK庫的RK算法：?

// PrimeRK is the prime base used in Rabin-Karp algorithm. const PrimeRK = 16777619func HashStr(sep string) (uint32, uint32) {hash := uint32(0)for i := 0; i < len(sep); i++ {hash = hash*PrimeRK + uint32(sep[i])}var pow, sq uint32 = 1, PrimeRKfor i := len(sep); i > 0; i >>= 1 {if i&1 != 0 {pow *= sq}sq *= sq}return hash, pow }func IndexRabinKarp(s, substr string) int {// Rabin-Karp searchhashss, pow := HashStr(substr)n := len(substr)var h uint32for i := 0; i < n; i++ {h = h*PrimeRK + uint32(s[i])}if h == hashss && s[:n] == substr {return 0}for i := n; i < len(s); {h *= PrimeRKh += uint32(s[i])h -= pow * uint32(s[i-n])i++if h == hashss && s[i-n:i] == substr {return i - n}}return -1 }

匹配算法2

KMP算法

徹底理解KMP_CSDN

1.字典樹

字典樹，又稱 Trie 樹，是一種樹形結構。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串）。主要思想是利用字符串的公共前綴來節約存儲空間。?

在實際運用中，比如我們要儲存大量的單詞在一個文本中，而且還要查找某個單詞是否存在，如果存在，請輸出出現了多少次。考慮到有大量的單詞而且還要詢問出現了多少次，考慮到無法用字符串直接存儲并進行遍歷，所以就有了字典樹這種高級數據結構。字典樹的主要思想是利用字符串的公共前綴來節約存儲空間。

如上圖所示，從根節點開始到每一個紅色標記(end)的結點都是一個單詞，上圖中儲存的字符串有"abc"、"abcd" 、"abd" 、"b"、"bcd"、"efg"、"hi"。當有大量單詞是就可以利用字典樹這種高級數據結構就可以節約存儲空間。

字典樹的實現方式有兩種，1：通過結構體指針來實現，2：通過數組來實現

兩種實現方式主要區別在于，數組實現的字典樹比結構體指針實現的字典更節省內存，只要不是特別卡內存，建議用結構體指針實現，比較好寫也易于理解，下面詳細講解一下字典樹的結構體實現，以leetcode 472題為例

static class TrieNode {TrieNode[] children;boolean isWord;//還可以在這里記錄終止于此的單詞個數 int numpublic TrieNode() {children = new TrieNode[26];}}private TrieNode trie_root;public List<String> findAllConcatenatedWordsInADict_(String[] words){List<String> res = new ArrayList<>();trie_root = new TrieNode();//初始化字典樹for (String w:words) {TrieNode cur = trie_root;for(char c : w.toCharArray()){if(cur.children[c-'a']==null) cur.children[c-'a'] = new TrieNode();cur = cur.children[c-'a'];}cur.isWord = true;//cur.num++;}for (String w:words){if(find_word(w,0,0,trie_root)) res.add(w);}return res;}public boolean find_word(String word,int depth,int idx,TrieNode node){if(idx == word.length() && depth>1) return true;//記錄深度 避免是自己for (int i = idx; i < word.length(); i++) {//迭代查找樹node = node.children[word.charAt(i)-'a'];if(node == null) return false;//end 開啟新一輪遞歸if (node.isWord && find_word(word,depth+1,i+1,trie_root)) return true;}return false;}

677. 鍵值映射

class MapSum {/* 1. 使用HashMap結構Map <String,Integer>map = new HashMap<>();public MapSum() {}public void insert(String key, int val) {map.put(key,val);}public int sum(String prefix) {int res = 0;for (var t:map.entrySet()) {String key = t.getKey();if(key.indexOf(prefix)==0) res += t.getValue();}return res;}*///2. 自己構造字典前綴樹private class TrieNode{private int val;private TrieNode[] next;public TrieNode(){//this.val = val;next = new TrieNode[26];}}TrieNode root;public MapSum() {root = new TrieNode();}public void insert(String key, int val) {TrieNode cur = root;for (char c : key.toCharArray()){if(cur.next[c-'a']==null) cur.next[c-'a'] = new TrieNode();cur = cur.next[c-'a'];}cur.val = val;}public int sum(String prefix) {TrieNode cur = root;for (char c : prefix.toCharArray()){if(cur.next[c-'a']==null) return 0;cur = cur.next[c-'a'];}return getSum(cur);//前綴到此為止 下面用遞歸，迭代解決不了}public int getSum(TrieNode pre){//尋找后續的所有樹枝int res = pre.val;for (TrieNode child : pre.next) {//遍歷所有可能的子樹if(child!=null) res += getSum(child);}return res;} }

212. 單詞搜索 II

class Solution {Set<String> res = new HashSet<String>();int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};public List<String> findWords(char[][] board, String[] words) {Trie root = new Trie();for (String word : words){root.insert(word);}for (int i = 0; i < board.length; ++i) {for (int j = 0; j < board[0].length; ++j){if (root.child[board[i][j]-'a'] != null){dfs(board, i, j, root);}}}return new ArrayList<String>(res);}public void dfs(char[][] board, int i, int j, Trie cur){char c = board[i][j];if (c == '.') return;if (cur.child[c-'a']==null) return;cur = cur.child[c - 'a'];//System.out.println(cur.word);if (cur.end){res.add(cur.word);//return; 繼續搜索 bad case：oa oaa}board[i][j] = '.';for (int[] d: dir){int i2 = i + d[0], j2 = j + d[1];if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) {dfs(board, i2, j2, cur);}}board[i][j] = c;} } class Trie{Trie[] child;boolean end = false;String word;public Trie(){word = "";child = new Trie[26];}public void insert(String word){Trie cur = this;//注意這種寫法char [] chs = word.toCharArray();for (char c : chs){if(cur.child[c-'a']==null) cur.child[c-'a'] = new Trie();cur = cur.child[c-'a'];}cur.end = true;cur.word = word;} }

2.并查集

并查集主要用于解決一些元素分組的問題。它管理一系列不相交的集合，并支持兩種操作：

• 合并（Union）：把兩個不相交的集合合并為一個集合。
• 查詢（Find）：查詢兩個元素是否在同一個集合中。

先初始化

int fa[MAXN]; inline void init(int n) {for (int i = 1; i <= n; ++i)fa[i] = i; }

遍歷查詢 + 合并

//未壓縮路徑 int find(int x) {if(fa[x] == x)return x;elsereturn find(fa[x]); } inline void merge(int i, int j) {fa[find(i)] = find(j); }

以leetcode?990. 等式方程的可滿足性?為例

class Solution {int [] parent = new int[26];private void union(int a,int b){parent[find(a)] = find(b); }private int find(int x){if(x!=parent[x])parent[x] = find(parent[x]);return parent[x];}public boolean equationsPossible(String[] equations) {for(int i = 0;i<26;i++)parent[i] = i;for(String str : equations){if(str.charAt(1) == '=')union(str.charAt(0) - 'a',str.charAt(3) - 'a');}for(String str : equations){if(str.charAt(1) == '!' && find(str.charAt(0) - 'a') == find(str.charAt(3) - 'a'))return false;}return true;} }

上面已經進行過路徑壓縮?

LeetCode?721. 賬戶合并

class Solution {//721. 賬戶合并 并查集class DSU{//放到class里int [] parent;public DSU(int n){parent = new int[n];for (int i = 0;i<n;i++)parent[i] = i;}public int find(int x){if(parent[x] != x)parent[x] = find(parent[x]);return parent[x];}public void union(int x,int y){parent[find(x)] = find(y);}}public List<List<String>> accountsMerge(List<List<String>> accounts) {HashMap<String,Integer> email_id = new HashMap<>();//記錄每個郵箱地址的主人HashMap<String,String> email_name = new HashMap<>();//記錄郵箱地址的id 后面進行同類郵箱地址合并DSU dsu = new DSU(10001);//郵箱地址的最大數量int id = 0;for (var account:accounts) {String name = "";for(String email : account){if(name==""){name = account.get(0);continue;}email_name.put(email,name);if(!email_id.containsKey(email)){email_id.put(email,id++);}dsu.union(email_id.get(account.get(1)),email_id.get(email));}}Map<Integer,List<String>> res = new HashMap<>();for(String email : email_id.keySet()){//同類郵箱地址整合int idx = dsu.find(email_id.get(email));res.computeIfAbsent(idx,a->new ArrayList()).add(email);}for(var list : res.values()){//添加名字Collections.sort(list);list.add(0,email_name.get(list.get(0)));}return new ArrayList<>(res.values());} }

947. 移除最多的同行或同列石頭? “二維”并查集 每個元素有兩個屬性；

//二維并查集int parent[] = new int[20002];public int find(int x){if (parent[x] != x) parent[x] = find(parent[x]);return parent[x];}// 可以看成將x->y 這條邊加入并查集 以y為代表public void union(int x,int y){//parent[find(x)] = find(y);int px = find(x);int py = find(y);if (px == py) return;parent[px] = py;}//思路是要先把每個石頭的兩個坐標元素整合為一個集合public int removeStones(int[][] stones) {int base = 10001;for (int[] st : stones) {parent[st[0]] = st[0];parent[st[1]+base] = st[1]+base;}//把x值相同的root即y去指向同一root 還要注意上面是怎么union的//舉例(1,10);(2,10);(1,9);顯然 set里會把前兩個去掉；//第三個的話 1先指向10 union時再把1和10一起指向9；set.addd(find)時就去重了 要理解union本質for (int[] st : stones) union(st[0],st[1]+base);Set<Integer> set = new HashSet<>();for (int[] st : stones){set.add(find(st[1]+base));}return stones.length - set.size();}

3.單調棧

?單調棧就是棧里面存放的數據都是有序的,所以可以分為單調遞增棧和單調遞減棧兩種。

402. 移掉K位數字

//單調棧 從前到后遍歷 高位刪除較大的數public String removeKdigits(String num, int k) {if(num.length()==k) return "0";Deque<Character> deque = new LinkedList<>();for (char c:num.toCharArray()) {while (!deque.isEmpty() && deque.peekLast() > c && k >0){deque.pollLast();k--;}deque.offerLast(c);}while (k-- > 0) deque.pollLast();StringBuilder res = new StringBuilder();boolean frontZero = true;for (char c : deque){if (frontZero && c=='0') continue;frontZero = false;res.append(c);}return res.length()==0 ? "0" : res.toString();//避免刪除后全是0的情況}

316. 去除重復字母

class Solution {//316. 去除重復字母 與1081 same. like 321,402//azad zazd//壓棧 類似單調棧 當棧頂大于當前的c且棧頂可以被替換(即后續的s中有棧頂元素) 刪除棧頂public String removeDuplicateLetters(String s) {Stack<Character> stack = new Stack<>();for (int i = 0;i<s.length();i++) {char c = s.charAt(i);if (stack.contains(c)) continue;while (!stack.isEmpty() && stack.peek() > c && s.indexOf(stack.peek(),i)!=-1)stack.pop();stack.push(c);}StringBuilder sb = new StringBuilder();for (char c : stack) sb.append(c);return sb.toString();} }

321. 拼接最大數

//321. 拼接最大數 思路：最終的數組兩部分來源于s1和s2，而且這兩部分分別是各自s1和s2的最大值//兩部分的長度和為k 遍歷取最大值即可public int[] maxNumber(int[] nums1, int[] nums2, int k) {int[] res = new int[k];int maxI = Math.min(nums1.length,k);for (int i = Math.max(k-nums2.length,0); i <= maxI; i++) {//i表示s1的長度 k-i是s2的長度int[] cur = mergeArray(getMaxArray(nums1,i),getMaxArray(nums2,k-i));if(compareArray(cur,0,res,0)) res = cur;}return res;}//合并數組 不能按歸并那樣合并 如[7,6] [7,8] 可能產生 7 7 8 6；實際是7876public int[] mergeArray(int[] nums1, int[] nums2){int [] res = new int[nums1.length + nums2.length];int cur = 0, p1 = 0, p2 = 0;while (cur < nums1.length + nums2.length){if (compareArray(nums1, p1, nums2, p2))//如果當前值相等還需要比較后續哪個大res[cur++] = nums1[p1++];elseres[cur++] = nums2[p2++];}return res;}//獲取長度為k的最大子序列 類似于單調棧public int[] getMaxArray(int[] nums,int k){int[] res = new int[k];int n = nums.length;int pop_cnt = n - k;//表示最多彈出的數量 再多彈的話湊不夠k個數了int cur = 0;//cur-1表示棧頂，cur表示即將添加元素的位置for (int i = 0; i < n; i++) {while(cur>0 && res[cur-1] < nums[i] && pop_cnt>0){cur--;pop_cnt--;}if (cur<k) res[cur++] = nums[i];else pop_cnt--;//注意這里 要-- 不然pop_cnt偏大 會多彈導致不夠k個}return res;}public boolean compareArray(int[] nums1, int p1, int[] nums2, int p2) {if (p2 >= nums2.length) return true;if (p1 >= nums1.length) return false;if (nums1[p1] > nums2[p2]) return true;if (nums1[p1] < nums2[p2]) return false;return compareArray(nums1, p1 + 1, nums2, p2 + 1);}

題外話：在遍歷數組時，如果想獲得比當前小的最大值，由后向前遍歷；最小值，從前向后；

738. 單調遞增的數字

//倒序掃描數字，若當前數字比其右邊一位大，則把該位數字減1，最后將flag右邊的所有位改成9public int monotoneIncreasingDigits(int N) {if (N<10) return N;StringBuilder sb = new StringBuilder(String.valueOf(N));int flag = -1;//記錄for (int i = sb.length()-2;i>=0;i--){//倒著 因為-1后可能左邊又大于此處了if (sb.charAt(i)>sb.charAt(i+1)){sb.setCharAt(i,(char)(sb.charAt(i)-1));flag = i;/*while (++i< sb.length()){sb.setCharAt(i,'9');}*/}}if (flag==-1) return N;while (++flag < sb.length()) sb.setCharAt(flag,'9');return Integer.valueOf(sb.toString());}

4. 二分

二分思路梳理

34. 在排序數組中查找元素的第一個和最后一個位置?下面是二分的兩種寫法，第一種是未確定有序數組中是否含有target，尋找左邊界，第二種是確定有的情況下尋找右邊界（注意找左邊界的時候，由右側逼近；找右邊界的時候，由左側逼近）；

class Solution {public int[] searchRange(int[] nums, int target) {int l = 0,r = nums.length-1;int[] res = new int[]{-1,-1};if (nums.length==0) return res;//尋找左邊界 還沒起確定有沒有target 所以寫法不太一樣while (l<r){//結束時l==rint mid = l+(r-l)/2;if (nums[mid]>=target) r = mid;else l = mid+1;}if(nums[l]!=target) return res;//判斷res[0] = l;r = nums.length-1;//尋找右邊界，已經確定有target了while (l<=r){int mid = l+(r-l)/2;if(nums[mid]<=target) l = mid+1;else r = mid-1;}res[1] = r;return res;} }

笨蛋寫法

private int findFirstPosition(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {// ① 不可以直接返回，應該繼續向左邊找，即 [left, mid - 1] 區間里找right = mid - 1;} else if (nums[mid] < target) {// 應該繼續向右邊找，即 [mid + 1, right] 區間里找left = mid + 1;} else {// 此時 nums[mid] > target，應該繼續向左邊找，即 [left, mid - 1] 區間里找right = mid - 1;}}// 此時 left 和 right 的位置關系是 [right, left]，注意上面的 ①，此時 left 才是第 1 次元素出現的位置// 因此還需要特別做一次判斷if (left != nums.length && nums[left] == target) {return left;}return -1; }private int findLastPosition(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {// 只有這里不一樣：不可以直接返回，應該繼續向右邊找，即 [mid + 1, right] 區間里找left = mid + 1;} else if (nums[mid] < target) {// 應該繼續向右邊找，即 [mid + 1, right] 區間里找left = mid + 1;} else {// 此時 nums[mid] > target，應該繼續向左邊找，即 [left, mid - 1] 區間里找right = mid - 1;}}// 由于 findFirstPosition 方法可以返回是否找到，這里無需單獨再做判斷return right; }

5.帶標記函數dp

689. 三個無重疊子數組的最大和

? ? /* ?題目是求三個無重疊子數組的最大和
? ? 其實可以拓展到N個無重疊子數組的最大和
? ? 1，定義如下：
? ? sums[i]代表以nums[i]結尾的前k個數的和
? ? dp[i][j]代表截止到nums[i]形成的第j個無重疊子數組的最大和
? ? path[i][j]代表截止到nums[i]形成的第j個無重疊子數組以哪個下標為結尾，用來回溯路徑
? ? 2，狀態轉移方程為 dp[i][j] = max{dp[i - 1][j], sums[i] + dp[i - k][j - 1]};
? ? 對應的path[i][j] = path[i - 1][j]或i
*/

//689. 三個無重疊子數組的最大和//典型帶標記函數的動態規劃 甚至和書上的都一樣public int[] maxSumOfThreeSubarrays(int[] nums, int k){return maxSumOf_N_Subarrays(nums, k, 3);}public int[] maxSumOf_N_Subarrays(int[] nums, int k,int n) {int len = nums.length;if (k < 1 || n * k > len) return null;int sum = 0;int [] prekSum = new int[len];for (int i = 0; i < len; i++) {sum += nums[i];if (i >= k) sum -= nums[i-k];if (i >= k-1) prekSum[i] = sum;}int [][] dp = new int[len][n+1];//省去了邊界處理int [][] path = new int[len][n+1];//初始值dp[k-1][1] = prekSum[k-1];path[k-1][1] = k-1;for (int i = k; i < len; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = dp[i-1][j];path[i][j] = path[i-1][j];if (dp[i-k][j-1] + prekSum[i] > dp[i][j]){dp[i][j] = dp[i-k][j-1]+prekSum[i];path[i][j] = i;}}}int idx = n;int[] res = new int[n];int c = path[len-1][idx];res[idx-1] = c - k + 1;while (--idx>0){c = path[c-k][idx];res[idx-1] = c - k + 1;}return res;}

6.樹

450. 刪除二叉搜索樹中的節點

//450. 刪除二叉搜索樹中的節點public TreeNode deleteNode(TreeNode root, int key) {if (root==null) return null;if (key < root.val){root.left = deleteNode(root.left,key);}else if (key > root.val){root.right = deleteNode(root.right,key);}else{TreeNode left = root.left;TreeNode right = root.right;//尋找右側最小的葉子節點if (right==null) return left;if (left==null) return right;while (right!=null && right.left!=null) right = right.left;//將root的左子樹拼接到右側最小葉子節點的左子樹right.left = left;return root.right;}return root;}

7.? 圖論

Kruskal?算法

1584. 連接所有點的最小費用

class Solution {//Kruskal 算法public int minCostConnectPoints(int[][] points) {int n = points.length;int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);boolean[] added = new boolean[n];int ans = 0;for (int i = 0; i < n; i++) {int min = 0;// 1)選出最小邊;for (int j = 0; j < n; j++) {if (!added[j] && dist[j] < dist[min]) {min = j;}}// 2)最小邊加入生成樹added[min] = true;if (dist[min] != Integer.MAX_VALUE) {ans += dist[min];}// 3)更新當前生成樹到其他點的邊的權值for (int j = 0; j < n; j++) {if (!added[j]) {dist[j] = Math.min(dist[j], mdist(points[min], points[j]));}}}return ans;}int mdist(int[] x, int[] y) {return Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1]);} }

與上面相似的? 迪杰斯特拉求最短路，下面給出鄰接矩陣求法。

743. 網絡延遲時間?

// 743. 網絡延遲時間// 單源最短路徑問題public int networkDelayTime(int[][] times, int n, int k) {int inf = Integer.MAX_VALUE;int res = 0;// 1. 初始化鄰接矩陣int [][] graph = new int[n+1][n+1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {graph[i][j] = i == j ? 0 : inf;}}for (int[] edge : times) {graph[edge[0]][edge[1]] = edge[2];}// 2. 鄰接矩陣查找各個頂點的極值// 初始化 距離數組 和 visitedint[] distance = new int[n+1];Arrays.fill(distance, inf);for (int i = 1; i <= n; i++) {distance[i] = graph[k][i];}boolean[] visited = new boolean[n+1];// 初始化源點visited[k] = true;distance[k] = 0;for (int i = 1; i <= n; i++) { // 代表循環次數為節點數量(每次找到一個最近點) 無實際意義int min = inf; // 當前最短路int idx = -1; // 最短路的節點for (int j = 1; j <= n; j++) {if (!visited[j] && distance[j] < min) {min = distance[j];idx = j;}}if (idx == -1) {break;}visited[idx] = true;for (int j = 1; j <= n; j++) {// 這里要加idx能到j的判斷 不然有越界問題if (!visited[j] && graph[idx][j] != inf && distance[idx] + graph[idx][j] < distance[j]) {distance[j] = distance[idx] + graph[idx][j];}}}// 3. 取最大路徑for (int i = 1; i <= n; i++) {res = Math.max(res, distance[i]);}return res == inf ? -1 : res;}

8.全排列問題

劍指 Offer 38. 字符串的排列

dfs是得到從 idx 處開始，后面字符的全排列；

int n;vector<string> permutation(string s) {n = s.size();vector<string> res;dfs(s,res,0);return res;}void dfs(string s,vector<string> &res,int idx){if (idx == n){res.push_back(s);return;}//dfs將得到idx后的那些字符的全排列 每次只要取idx處的不同字符即可for (int i = idx;i<n;i++){bool flag = true;for (int j = idx;j<i;j++){if (s[i] == s[j]){//剪枝 此時j處字符等于i i已經被放到idx處過了flag = false;break;}}if (flag){swap(s[idx],s[i]);dfs(s,res,idx+1);swap(s[idx],s[i]);}}}

注意，上面的dfs的swap中遞歸調用函數時是從idx+1開始的，不是i+1，要理解遞歸函數的本質意義，像下面這個就是從i+1開始

39. 組合總和?允許重復

class Solution { public:vector<vector<int>> res;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> tmp;//Arrays.sort(candidates.begin(),candidates.end());help(tmp,candidates,target,0);return res;}void help(vector<int> &tmp, vector<int>& candidates,int tar,int idx){if(tar==0){res.push_back(tmp);return;}for(int i = idx;i<candidates.size();i++){if(candidates[i]<=tar){tmp.push_back(candidates[i]);help(tmp,candidates,tar-candidates[i],i);tmp.pop_back();}}} };

40. 組合總和 II?不允許重復

vector<vector<int>> res;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());vector<int> tmp;help(candidates,tmp,target,0);return res;}void help(vector<int>& candidates,vector<int>& tmp, int target,int idx){if(target==0){res.push_back(tmp);return;}if(idx==candidates.size()||candidates[idx]>target) return;for(int i = idx;i<candidates.size()&&candidates[i]<=target;i++){if(i>idx&&candidates[i]==candidates[i-1]) continue;tmp.push_back(candidates[i]);help(candidates,tmp,target-candidates[i],i+1);tmp.pop_back();}return;}

總結

以上是生活随笔為你收集整理的经典算法题：字典树、并查集、单调栈、二分、带标记函数dp、树、全排列、字符串问题等常用算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。