替換一個(gè)數(shù)字后的最大差值

【貪心】O(log n) 做法，找到左邊第一個(gè)不是9的數(shù)位，把他換成9，這樣一定是最大的。最小值是最左邊的數(shù)直接替換成0.

修改兩個(gè)元素的最小分?jǐn)?shù)

【腦筋急轉(zhuǎn)彎】從小到大排序后，三種情況可能達(dá)到最大得分：修改最大的兩個(gè)數(shù)、修改最小的兩個(gè)數(shù)，修改最小數(shù)的和最大的數(shù)。

最小無(wú)法得到的或值

【哈希表 + 枚舉】直接暴力枚舉，但不是枚舉所有數(shù)，而只需要枚舉2的冪次，因?yàn)榛蜻\(yùn)算只能把二進(jìn)制位的0變成1而1沒(méi)法變成0，所以如果2^k是“可表達(dá)”的，那么2^k一定在nums中。對(duì)于所有0≤i＜k，2^i都在nums中存在，那么1到2^k - 1都是“可表達(dá)”的，答案就是最小的，不存在于nums中的2的冪次。

壓行版

進(jìn)階版：Lowbit優(yōu)化，不用哈希表，用一個(gè)數(shù)mask記錄nums中是2的冪次的數(shù)。判斷一個(gè)數(shù)是2的冪次 x & (x - 1) = 0；找一個(gè)二進(jìn)制數(shù)最右的1： x & (~x + 1) 即 x & (-x)

常用lowbit算法 x >> k & 1 求x的第k位數(shù)字 x & -x = x & (~x + 1) 保留x最右邊的1，其余位置置0 x & (x - 1) 消除x最右邊的1（最右邊0變1），其余不變 x | (x + 1) 消除x最右邊的0（最右邊1變0），其余不變

更新數(shù)組后處理求和查詢

【暴力】純暴力會(huì)超時(shí)，用java的BitSet優(yōu)化常數(shù).

【線段樹(shù)】線段樹(shù)的用途：一個(gè)數(shù)組，更新一個(gè)子數(shù)組的值（都加上一個(gè)數(shù)，把子數(shù)組內(nèi)元素取反……）；查詢一個(gè)子數(shù)組的值（求和、求最大值）。線段樹(shù)兩大思想：挑選O(n)個(gè)特殊區(qū)間，是的任意一個(gè)區(qū)間可拆分為O(logn)個(gè)特殊區(qū)間，O(n) ≤ 4n；lazy（延遲）更新：用一個(gè)數(shù)組維護(hù)每個(gè)區(qū)間需要更新的值，如果這個(gè)值=0表示不需要更新，!=0表示需要更新。如果后面又來(lái)了一個(gè)更新破壞了有l(wèi)azy tag的區(qū)間，那么這個(gè)區(qū)間就得繼續(xù)遞歸更新。

【位運(yùn)算】