從兩個(gè)數(shù)字?jǐn)?shù)組里生成最小數(shù)字

【模擬 + 哈希表】觀察如果nums1和nums2有交集，那么答案是1位數(shù)，即交集的最小值。否則nums1和nums2中各取一個(gè)最小值x和y，答案是min(10x+y，10y+x)。

【模擬 + 位運(yùn)算】二進(jìn)制位上的1表示集合存在該元素（向集合中添加元素就是|上1<<x），&運(yùn)算可以求交集，達(dá)到O(1)的空間復(fù)雜度。（c++的__builtin_ctz能返回二進(jìn)制下末尾0的個(gè)數(shù)，java是Integer.numberOfTrailingZeros，go是bits.TrailingZeros）

找到最大開(kāi)銷(xiāo)的子字符串

【DP】根據(jù)題意，生成一個(gè)字母和價(jià)值的映射，題目轉(zhuǎn)換為求價(jià)值數(shù)組的最大子數(shù)組和（允許子數(shù)組為空）。定義f[i]為以a[i]結(jié)尾的最大子數(shù)組和，f[i] = max(f[i -1], 0) + a[i]，答案為max(f)。

使子數(shù)組元素和相等

【中位數(shù)貪心 + 裴蜀定理】如果arr不是循環(huán)數(shù)組，則有arr[i] + arr[i+1] + ... arr[i + k - 1] = arr[i + 1] + arr[i + 2] + ... + arr[i + k]，約掉得arr[i] = arr[i + k]，則可以按i mod k的結(jié)果將arr分組，對(duì)每一組，計(jì)算所有元素相等的最少運(yùn)算次數(shù)。根據(jù)中位數(shù)貪心，將b的所有元素變成b的中位數(shù)（m/2）是最優(yōu)的。觀察到arr[0]和arr[1]不管如何循環(huán)都不在同一組，得到一個(gè)循環(huán)數(shù)組如果既有周期n和周期k，那么也有周期gcd(n,k)，根據(jù)裴蜀定理，arr[i] = arr[i + nx + ky] = arr[i + gcd(n, k)]。

圖中的最短環(huán)

【BFS】枚舉，對(duì)每個(gè)start跑bfs，維護(hù)0到每個(gè)start到i的最短路dis，同時(shí)入隊(duì)node和father。