?

文章目錄

• 前言
• 一.排序算法
• 二.查找算法
• • 2.1 哈希查找
  • • 2.1.1 兩數(shù)之和
    • 2.1.2 兩個(gè)數(shù)組的交集
    • 2.1.3 日志速率限制器
  • 2.2 最長(zhǎng)公共前綴
  • 2.3 KMP
  • • 2.3.1 實(shí)現(xiàn) strStr()
  • 2.4 二分查找
  • 前言
  • • 2.4.1 搜索插入位置
    • 2.4.2 Sqrt(x)
    • 2.4.2 有效的完全平方數(shù)
    • 2.4.3 第一個(gè)錯(cuò)誤的版本
  • 2.5 存在重復(fù)元素2
• 三.數(shù)論相關(guān)
• 前言
• • 3.1 快速冪
  • 3.3 反轉(zhuǎn)
  • • 3.3.1 整數(shù)反轉(zhuǎn)（非常重要，涉及溢出）
    • 3.3.2 回文數(shù)
    • 3.3.3 回文排列
  • 3.4 映射規(guī)則
  • • 3.4.1 羅馬字符轉(zhuǎn)數(shù)字
    • 3.4.2 同構(gòu)字符串
    • 3.4.3 單詞規(guī)律
  • 3.5 大數(shù)運(yùn)算
  • • 3.5.1 加1
    • 3.5.2 二進(jìn)制求和
    • 3.5.3 階乘后的零
  • 3.6 快樂數(shù)
  • 3.7 素?cái)?shù)
  • • 3.7.1 計(jì)數(shù)素?cái)?shù)
  • 3.8 各位相加
  • 3.9 丑數(shù)
• 四.棧
• • 4.1 有效的括號(hào)
• 五.線性表和鏈表
• 前言
• • 5.1 指針
  • • 5.1.1 合并兩個(gè)有序鏈表
    • 5.1.1 合并兩個(gè)有序數(shù)組
    • 5.1.2 刪除排序數(shù)組中的重復(fù)項(xiàng)
    • 5.1.2 刪除排序鏈表中的重復(fù)元素
    • 5.1.3 移除元素
    • 5.1.4 驗(yàn)證回文串
    • 5.1.5 環(huán)形鏈表
    • 5.1.6 回文鏈表
    • 5.1.7 刪除鏈表中的節(jié)點(diǎn)
  • 5.2 最后一個(gè)單詞的長(zhǎng)度
  • 5.3 雙指針
  • • 5.3.1 相交鏈表
    • 5.3.2 反轉(zhuǎn)鏈表
    • 5.3.3 匯總區(qū)間
    • 5.3.4 會(huì)議室
    • 5.3.5 移動(dòng)零
  • 5.4 棧和隊(duì)列
  • • 5.4.1 用隊(duì)列實(shí)現(xiàn)棧
    • 5.4.3 用棧實(shí)現(xiàn)隊(duì)列
  • 5.5 區(qū)域和檢索 - 數(shù)組不可變
• 六.動(dòng)態(tài)規(guī)劃
• • 6.1 最大子序列和
  • 6.2 爬樓梯
  • 6.3 楊輝三角
  • 6.4 楊輝三角2
  • 6.5 買賣股票的最佳時(shí)機(jī)
  • 6.6 買賣股票的最佳時(shí)機(jī)2
  • 6.7 比特位計(jì)數(shù)
• 七. 樹
• • 前言
  • 7.1 樹的遍歷
  • • 7.1.1 二叉樹的中序遍歷
    • 7.1.2 相同的樹
    • 7.1.3 對(duì)稱二叉樹
    • 7.1.4 二叉樹的最大深度
    • 7.1.5 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹
    • 7.1.6 平衡二叉樹
    • 7.1.7 二叉樹的最小深度
    • 7.1.8 路徑總和
    • 7.1.8 二叉樹的所有路徑
    • 7.1.9 翻轉(zhuǎn)二叉樹
  • 7.2 二叉搜索樹的最近公共祖先
  • 7.3 最接近的二叉搜索樹值
• 八. 位運(yùn)算
• • 8.1 只出現(xiàn)一次的數(shù)字
  • 8.2 Excel表列名稱
  • 8.3 顛倒二進(jìn)制位
  • 8.4 2的冪
  • 8.4 3的冪
  • 8.5 丟失的數(shù)字
• 九. 字符串
• • 9.1 最短單詞距離
• 十. 博弈論
• • 10.1 nim游戲

前言

此篇文章的目的是在于建立一個(gè)可以協(xié)同配合的工作流，我希望對(duì)于一個(gè)算法的理解包含以下內(nèi)容：詳盡的分析，程序的結(jié)構(gòu)，代碼。文章中包含前兩個(gè)部分，然后在本地完成代碼。編寫代碼是否需要再附上結(jié)構(gòu)，很難說，我現(xiàn)在想的是只加上主干，再附上一個(gè)鏈接即可

一.排序算法

二.查找算法

2.1 哈希查找

2.1.1 兩數(shù)之和

題目：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個(gè) 整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

暴力解法：兩層循環(huán)遍歷所有的下標(biāo)組合

優(yōu)化：對(duì)于時(shí)空復(fù)雜度分別為n方和1的問題，優(yōu)先考慮空間換時(shí)間
-在遍歷的同時(shí)，記錄一些信息，以省去一層循環(huán)，這是“以空間換時(shí)間"的想法
-需要記錄已經(jīng)遍歷過的數(shù)值和它所對(duì)應(yīng)的下標(biāo)，可以借助查找表實(shí)現(xiàn)
-查找表有兩個(gè)常用的實(shí)現(xiàn):
·哈希表
·平衡二叉搜索樹

因?yàn)椴恍枰S護(hù)結(jié)果的順序，因此使用哈希表

本質(zhì)上，此問題是尋找target - x是否存在于數(shù)組中，暴力解法的問題就在于尋找target-x的時(shí)間復(fù)雜度太高，剛好哈希表查找的復(fù)雜度是o(1)

我犯了一個(gè)錯(cuò)誤，雖然是找target-x, 但不是將target-x存到哈希表中，而是將數(shù)組中的元素逐個(gè)存到哈希表中。極端一點(diǎn)，我可以先將數(shù)組的元素使用哈希表存儲(chǔ)，再遍歷數(shù)組尋找target-x

程序上需要注意的是需要使用高級(jí)程序語言提供的哈希表，不需要自己構(gòu)建哈希表
哈希表的使用
簡(jiǎn)單介紹哈希表：
哈希表是基于鍵、值對(duì)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，底層一般采用的是列表(數(shù)組)
使用除留余數(shù)法確定數(shù)據(jù)在哈希表中的位置，需要選擇一個(gè)p，對(duì)P取余。P還決定了哈希表的長(zhǎng)度，P要盡可能的原理2的冪
使用線性探測(cè)法處理沖突，比如兩個(gè)數(shù)的哈希值相等，a占據(jù)位置之后，b以1為單位向后順延

對(duì)于python，字典就是哈希表
enumerate()返回的是一個(gè)引用類型的變量，打印出來是這個(gè)變量的地址，屬于enumerate類，需要類型轉(zhuǎn)換為list.每個(gè)元素的順序是，(下標(biāo)，元素)

2.1.2 兩個(gè)數(shù)組的交集

分析：很容易得出，目標(biāo)是求出同時(shí)在兩個(gè)數(shù)組的元素，且這個(gè)元素唯一

我最開始認(rèn)為只需要將一個(gè)數(shù)組哈希化，但這樣處理重復(fù)元素就很麻煩了。除非把a(bǔ)ns數(shù)組也給哈希化，這樣在推入一個(gè)新的交集元素之前才能以O(shè)(1)的性能判斷該交集元素是否已經(jīng)存在于ans. 哈希化的過程除了統(tǒng)計(jì)元素之外，也同時(shí)可以去除重復(fù)元素

2.1.3 日志速率限制器

又重新想了一下什么叫每x秒一次，從數(shù)值上來說，如果t發(fā)生了，那么下一次發(fā)生在t+x，這就是每x秒一次

2.2 最長(zhǎng)公共前綴

編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。

如果不存在公共前綴，返回空字符串 “”。

法一：橫向掃描
依次遍歷字符串?dāng)?shù)組中的每個(gè)字符串，對(duì)于每個(gè)遍歷到的字符串，更新最長(zhǎng)公共前綴，當(dāng)遍歷完所有的字符串以后，即可得到字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。

第一個(gè)字符串就作為最長(zhǎng)公共前綴，再去遍歷下一個(gè)字符串，更新最長(zhǎng)公共前綴。一直迭代下去
時(shí)間：0(mn)

法二：縱向掃描
同上
這種方法最符合我的思考習(xí)慣

法三：分治法
法四：二分查找

2.3 KMP

2.3.1 實(shí)現(xiàn) strStr()

題目：實(shí)現(xiàn) strStr() 函數(shù)。

給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開始）。如果不存在，則返回 -1 。

法一：暴力解法
思路很明確，雙層循環(huán)。遍歷主串的每一位，每訪問到某一位時(shí)，遍歷副串的每一位。只要有一個(gè)不對(duì)，退出內(nèi)層循環(huán)

法二：KMP
以后再說

2.4 二分查找

前言

終止條件while l<=r, 為什么是小于等于？？？
A：
（1）對(duì)于偶數(shù)長(zhǎng)度序列，當(dāng)查找第一或者倒數(shù)第一個(gè)元素時(shí)，會(huì)出現(xiàn)l=r的情況，此時(shí)l或者r指向的元素就是target
（2）對(duì)于奇數(shù)長(zhǎng)度序列，當(dāng)查找第二個(gè)或者倒數(shù)第二個(gè)元素時(shí)，同上
由此需要將中止條件設(shè)為while l<=r

2.4.1 搜索插入位置

題目：給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。

請(qǐng)必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

在一個(gè)有序數(shù)組中進(jìn)行按值查找

這二分查找做下來，感覺處理邊界不是很清晰

比如說退出循環(huán)的條件是left <= right,為什么后面返回left的值就可以了，left的值表示的是索引，不是數(shù)組下標(biāo)

在不同情況下，究竟是在target<nums[mid]返回left,還是target>nums[mid]返回left
這些問題都需要解決

2.4.2 Sqrt(x)

題目：給你一個(gè)非負(fù)整數(shù) x ，計(jì)算并返回 x 的 算術(shù)平方根 。

由于返回類型是整數(shù)，結(jié)果只保留 整數(shù)部分 ，小數(shù)部分將被 舍去 。

注意：不允許使用任何內(nèi)置指數(shù)函數(shù)和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

由于 xx 平方根的整數(shù)部分 \textit{ans}ans 是滿足 k^2 \leq xk
2
≤x 的最大 kk 值，因此我們可以對(duì) kk 進(jìn)行二分查找，從而得到答案。

二分查找的下界為 0，上界可以粗略地設(shè)定為 xx。在二分查找的每一步中，我們只需要比較中間元素 mid 的平方與 xx 的大小關(guān)系，并通過比較的結(jié)果調(diào)整上下界的范圍。由于我們所有的運(yùn)算都是整數(shù)運(yùn)算，不會(huì)存在誤差，因此在得到最終的答案 ans 后，也就不需要再去嘗試ans + 1

一般來說，二分查找的結(jié)果由mid來表示，之前找插入位置那個(gè)問題返回left是因?yàn)椴迦氲奈恢貌皇莔id的位置，而是left的位置

2.4.2 有效的完全平方數(shù)

一開始還沒有意識(shí)到這是個(gè)查找問題，只是想到將原來的乘法問題轉(zhuǎn)換成乘法問題，但本質(zhì)上還是要找出一個(gè)符合條件的結(jié)果

一直以來對(duì)于二分查找不是特別熟悉

left <= right???
A：這是因?yàn)樾蛄虚L(zhǎng)度可能是奇數(shù)或者偶數(shù)，當(dāng)left > right，對(duì)上述兩種情況，循環(huán)都應(yīng)該結(jié)束

mid的更新方式？？？
A：有兩種。一般使用的是left + (right - low) / 2, 但實(shí)際上稍微合并一下就是第二種形式，(left + right) / 2

結(jié)果在哪里？？？？
A：一般情況下，left指針表示最終的結(jié)果

2.4.3 第一個(gè)錯(cuò)誤的版本

題目：你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。

假設(shè)你有 n 個(gè)版本 [1, 2, …, n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。

你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。

分析：
第一時(shí)間想到了二分查找，同時(shí)更新指針的依據(jù)要調(diào)整。就兩句話：

正確版本之前的版本全部正確

錯(cuò)誤版本之后的版本全部錯(cuò)誤

不過，mid的值的計(jì)算我不太熟悉，又搞錯(cuò)了,以low指針的值作為base
mid = (high - low) // 2 + low

2.5 存在重復(fù)元素2

題目：給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 絕對(duì)值 至多為 k。

分析：
下標(biāo)之差在K以內(nèi)的重復(fù)元素。等價(jià)于在長(zhǎng)度為K+1的數(shù)組里存在重復(fù)元素。但是是否需要

原理很簡(jiǎn)單，但寫成程序卻很巧妙不容易想到

我之前的想法是每次向字典加入長(zhǎng)度為K+1的元素，但是這里采用了一種類似于滾動(dòng)的效果，先逐步加入元素，每次加入都要進(jìn)行一次比較
當(dāng)i <= k時(shí)，字典的長(zhǎng)度從0 增長(zhǎng)到k+1，每次增加元素都要判斷是否存在重復(fù)

當(dāng)i = k+1時(shí)，字典長(zhǎng)度變?yōu)?k + 2, 為了維持窗口的長(zhǎng)度，移除一個(gè)元素，移除元素的key對(duì)應(yīng)于原數(shù)組的小標(biāo) i-k-1，然后比較此時(shí)的i是否存在重復(fù)。除i以外的元素前面已經(jīng)比較過了，一定不存在重復(fù)。

三.數(shù)論相關(guān)

前言

對(duì)于一個(gè)大數(shù)，直接處理往往是很復(fù)雜的。通常，使用因式分解對(duì)大數(shù)進(jìn)行拆分，對(duì)每一個(gè)質(zhì)因數(shù)進(jìn)行處理

自然數(shù)通常可以寫成質(zhì)因數(shù)相乘的形式

3.1 快速冪

https://blog.csdn.net/qq_19782019/article/details/85621386

這篇文章有非常詳細(xì)地推導(dǎo)過程，最終給出了一個(gè)非常簡(jiǎn)單的結(jié)論：

最后求出的冪結(jié)果實(shí)際上就是在變化過程中所有當(dāng)指數(shù)為奇數(shù)時(shí)底數(shù)的乘積

PS：需要注意的一點(diǎn)是，為了能夠統(tǒng)一算法，也就是核心思想就是每一步都把指數(shù)分成兩半，而相應(yīng)的底數(shù)做平方運(yùn)算，分兩種情況處理：

當(dāng)指數(shù)為偶數(shù)時(shí)，指數(shù)減半，底數(shù)平方

當(dāng)指數(shù)為奇數(shù)時(shí)，抽出一個(gè)底數(shù)的一次方，另外一部分按照情況1處理

3.3 反轉(zhuǎn)

3.3.1 整數(shù)反轉(zhuǎn)（非常重要，涉及溢出）

題目：給你一個(gè) 32 位的有符號(hào)整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。如果反轉(zhuǎn)后整數(shù)超過 32 位的有符號(hào)整數(shù)的范圍 [?$2^{31}$, $2^{31}$ ? 1] ，就返回 0。假設(shè)環(huán)境不允許存儲(chǔ) 64 位整數(shù)（有符號(hào)或無符號(hào)）

像反轉(zhuǎn)類的問題，可以馬上想到使用棧來存儲(chǔ)整數(shù)的每一位。當(dāng)然也可以不增加棧這一額外的空間，無論怎樣，反轉(zhuǎn)問題都涉及到兩個(gè)專業(yè)名詞，【彈出】， 【推入】

即將整數(shù)當(dāng)前的最后一位彈出整數(shù)，再推入反轉(zhuǎn)數(shù)
其表達(dá)式也非常熟悉了：

取模的時(shí)候涉及到另外一個(gè)問題，負(fù)數(shù)的取模和取余
我熟悉的是兩個(gè)整數(shù)，取模和取余的結(jié)果是一樣的，余數(shù)是在除數(shù)范圍內(nèi)，比較符合直覺。兩個(gè)負(fù)數(shù)，符號(hào)約掉了

當(dāng)符號(hào)不一致的時(shí)候，高級(jí)程序語言就有一些設(shè)定，求模運(yùn)算c = -2(向負(fù)無窮方向舍入)，求余運(yùn)算則c = -1(向0方向舍入)a = -7；b = 4， 求模時(shí)r = 1，求余時(shí)r = -3
當(dāng)符號(hào)不一致時(shí)，結(jié)果不一樣。求模運(yùn)算結(jié)果的符號(hào)和b（除數(shù)）一致，求余運(yùn)算結(jié)果的符號(hào)和a（被除數(shù)）一致
經(jīng)過測(cè)試，在C/C++, C#, JAVA, PHP這幾門主流語言中，%運(yùn)算符都是做取余運(yùn)算，而在python中的%是做取模運(yùn)算

取模：商向負(fù)無窮方向，余數(shù)符號(hào)和除數(shù)一致
取余：商向0方向，余數(shù)符號(hào)和被除數(shù)一致

python確實(shí)特別，尤其是在本題的場(chǎng)景下，如果x<0，那么余數(shù)為正，顯然是無法反映x的最后一位數(shù)字，需要利用算式新余數(shù) = 余數(shù) - 除數(shù) 來計(jì)算新的余數(shù)。負(fù)數(shù)取余真的反直覺
python負(fù)數(shù)的取模和整除都需要特別注意，取模不像正數(shù)可以直接得到最后一位，整除會(huì)向下取整

還有一點(diǎn)就是負(fù)數(shù)的反轉(zhuǎn)，每次取最后一位都是取的負(fù)數(shù)，把推入的公式走一遍就清楚了

題目限制了反轉(zhuǎn)數(shù)字的上下限，推入操作可能會(huì)造成溢出問題。一方面是x10造成的溢出，一方面是加上彈出的那一個(gè)數(shù)字造成的溢出
因此，在進(jìn)行推入之前，需要進(jìn)行兩方面的判斷，只要有一個(gè)部分造成溢出，那么就return
通過推導(dǎo)得到判斷是否溢出的條件：

3.3.2 回文數(shù)

題目：給你一個(gè)整數(shù) x ，如果 x 是一個(gè)回文整數(shù)，返回 true ；否則，返回 false 。

回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。例如，121 是回文，而 123 不是。

解法一：將整數(shù)轉(zhuǎn)為字符串
只需要比較字符串的前半段和后半段是否一致即可，但是需要額外的存儲(chǔ)空間

解法二：將數(shù)字本身反轉(zhuǎn)
和之前反轉(zhuǎn)數(shù)字一樣，需要考慮溢出的問題

如果直接進(jìn)行反轉(zhuǎn)，很明顯會(huì)遇到溢出
于是可以通過只反轉(zhuǎn)一半的數(shù)字來規(guī)避這個(gè)問題，反轉(zhuǎn)問題是有序的，存在彈出和推入兩個(gè)操作，從數(shù)字的末端開始操作

迭代終止條件的選擇：
對(duì)于回文數(shù)而言，迭代過程中，右邊一半是一定小于左邊的，當(dāng)中間數(shù)字被推入右邊，那么右邊就會(huì)大于等于左邊，此時(shí)就可以終止
回文數(shù)一定是要等到處理中間位置的數(shù)字時(shí)才可以進(jìn)行判斷

相較于整數(shù)反轉(zhuǎn)，不需要處理負(fù)數(shù)取模確實(shí)簡(jiǎn)單了不少

3.3.3 回文排列

題目：給定一個(gè)字符串，判斷該字符串中是否可以通過重新排列組合，形成一個(gè)回文字符串。

分析：需要分析回文序列的特點(diǎn)，在本問題上也就是單詞頻率
奇數(shù)序列：頻率中只有一個(gè)是奇數(shù)頻率
偶數(shù)序列：頻率中全部是偶數(shù)頻率

3.4 映射規(guī)則

3.4.1 羅馬字符轉(zhuǎn)數(shù)字

需要建立一張轉(zhuǎn)換表
其次，因?yàn)榇嬖?,9等特殊情況，從左到右掃描字符串，判斷當(dāng)前字符和下一位字符代表數(shù)字的大小關(guān)系
其他情況，從左到右相加即可

3.4.2 同構(gòu)字符串

題目：給定兩個(gè)字符串 s 和 t，判斷它們是否是同構(gòu)的。

如果 s 中的字符可以按某種映射關(guān)系替換得到 t ，那么這兩個(gè)字符串是同構(gòu)的。

每個(gè)出現(xiàn)的字符都應(yīng)當(dāng)映射到另一個(gè)字符，同時(shí)不改變字符的順序。不同字符不能映射到同一個(gè)字符上，相同字符只能映射到同一個(gè)字符上，字符可以映射到自己本身。

解法：使用兩個(gè)哈希表維護(hù)兩個(gè)字符串的雙射關(guān)系

3.4.3 單詞規(guī)律

題目：給定一種規(guī)律 pattern 和一個(gè)字符串 str ，判斷 str 是否遵循相同的規(guī)律。

這里的 遵循 指完全匹配，例如， pattern 里的每個(gè)字母和字符串 str 中的每個(gè)非空單詞之間存在著雙向連接的對(duì)應(yīng)規(guī)律。

分析：
這題干真抽象。不給示例根本看不懂。其實(shí)就是判斷字符與字符串之間是否恰好對(duì)應(yīng)
簡(jiǎn)單說就是在兩個(gè)哈希表中需要形成這樣的關(guān)系，a:b, b:a, 必須同時(shí)滿足

3.5 大數(shù)運(yùn)算

3.5.1 加1

題目：給定一個(gè)由 整數(shù) 組成的 非空 數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。

最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)單個(gè)數(shù)字。

你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開頭。

需要注意的是，此問題只進(jìn)行加1操作，因此發(fā)生進(jìn)位的情況很有限
1.全為9，那么最前面進(jìn)一位，后面全改0
2.找到9之前第一個(gè)非9元素，進(jìn)一位，非9元素后面全改0。此時(shí)，非9元素后面一定是全為9的

情況2涵蓋了9零散或者連續(xù)分布的情況

3.5.2 二進(jìn)制求和

題目：給你兩個(gè)二進(jìn)制字符串，返回它們的和（用二進(jìn)制表示）。

輸入為 非空 字符串且只包含數(shù)字 1 和 0。

主要是實(shí)現(xiàn)加法的機(jī)制：
carry表示進(jìn)位的值，比如說十進(jìn)制里邊，9+1進(jìn)位為1，那么carry = 1.
對(duì)齊末位，每一位的計(jì)算結(jié)果為carry + a[i] + b[i] % 2，這個(gè)2表示進(jìn)行的2進(jìn)制運(yùn)算。每一位計(jì)算的進(jìn)位為carry + a[i] + b[i] // 2.這就是加法運(yùn)算的核心

另外有兩點(diǎn)，對(duì)齊末位，在程序中通過反轉(zhuǎn)實(shí)現(xiàn)
兩個(gè)加數(shù)不一定同樣長(zhǎng)，采取高位補(bǔ)0

3.5.3 階乘后的零

題目：給定一個(gè)整數(shù) n ，返回 n! 結(jié)果中尾隨零的數(shù)量。

提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

解法：
對(duì)于任意一個(gè) n! 而言，其尾隨零的個(gè)數(shù)取決于展開式中 1010 的個(gè)數(shù)，而 10可由質(zhì)因數(shù) 2 * 5 而來，因此 n!的尾隨零個(gè)數(shù)為展開式中各項(xiàng)分解質(zhì)因數(shù)后「2的數(shù)量」和「5的數(shù)量」中的較小值。

3.6 快樂數(shù)

題目：編寫一個(gè)算法來判斷一個(gè)數(shù) n 是不是快樂數(shù)。

「快樂數(shù)」定義為：

對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和。
然后重復(fù)這個(gè)過程直到這個(gè)數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
如果 可以變?yōu)?1，那么這個(gè)數(shù)就是快樂數(shù)。
如果 n 是快樂數(shù)就返回 true ；不是，則返回 false 。

解法：這個(gè)題很有意思
據(jù)分析，有三種可能的情況：

通過上面的表格可以看出，4位及以上的數(shù)字通過操作會(huì)變回三位數(shù)，再操作一次就落到243以內(nèi)，也就是說最壞的情況下，算法可能會(huì)在 243 以下的所有數(shù)字上循環(huán)，然后回到它已經(jīng)到過的一個(gè)循環(huán)或者回到 1，不會(huì)無止境的變大

也就是說序列不是成環(huán)就是變成1的循環(huán)

之前我們做過循環(huán)鏈表的判定，可以使用雙指針法（快慢）來判斷是否成環(huán)。區(qū)別在于，循環(huán)鏈表在判斷之前已經(jīng)存在，本題需要在生成序列的過程中判斷是否成環(huán)
或者說本題不需要生成序列，因?yàn)楹竺娴墓?jié)點(diǎn)由前面的節(jié)點(diǎn)生成，只需要更新雙指針的值即可。

3.7 素?cái)?shù)

3.7.1 計(jì)數(shù)素?cái)?shù)

經(jīng)典的素?cái)?shù)篩問題哈

首先是素?cái)?shù)的定義，在正整數(shù)范圍內(nèi)，大于1并且只能被1和自身整除的數(shù)

法一：遍歷 2-n-1的所有數(shù)，看n是否能被整除
法二：對(duì)法一的范圍進(jìn)行優(yōu)化，優(yōu)化到 2-sqrt(n)的范圍

PS：從法三開始，需要準(zhǔn)備一個(gè)數(shù)組，保存i是否為素?cái)?shù)的結(jié)果，默認(rèn)全為素?cái)?shù)。從法三開始，將法一法二的除法問題，變成了從小至大的乘法問題

官方解釋
法三：埃氏篩
前兩種方法求解每個(gè)數(shù)是否是質(zhì)數(shù)的操作都是獨(dú)立的，存在大量重復(fù)計(jì)算。該問題的基本開銷在于判斷一個(gè)數(shù)是否是質(zhì)數(shù)，時(shí)間復(fù)雜度基于總共需要做多少次這樣的操作
埃氏篩基于這樣一個(gè)事實(shí)，如果 x是質(zhì)數(shù)，那么大于 x的 x的倍數(shù) 2x,3x, 一定不是質(zhì)數(shù)。
介紹什么是合數(shù)：

因此，我們?cè)O(shè)isPrime[i]表示數(shù) i 是不是質(zhì)數(shù)，如果是質(zhì)數(shù)則為1，否則為0。從小到大遍歷每個(gè)數(shù)，如果這個(gè)數(shù)為質(zhì)數(shù)，則將其所有的倍數(shù)都標(biāo)記為合數(shù)(除了該質(zhì)數(shù)本身)，即0，這樣在運(yùn)行結(jié)束的時(shí)候我們即能知道質(zhì)數(shù)的個(gè)數(shù)。

法四：優(yōu)化了法三標(biāo)記合數(shù)的起點(diǎn)，法三從2x開始，實(shí)際上應(yīng)該從xx開始標(biāo)記合數(shù)。因?yàn)楸葂小的因數(shù)一定在之前就標(biāo)記過了。比如74，這一看47是不存在的，因?yàn)?不是質(zhì)數(shù)，但是4是合數(shù)，可變形為2*14，這就肯定標(biāo)記過了

法五：線性篩\歐拉篩
按照法三的方法，45可以寫成315或者59，他們顯然是相等的，符合法三要求的在x*x之后，但是這屬于冗余的操作

在邏輯上有很大的改動(dòng)：
（1）單獨(dú)維護(hù)一個(gè)數(shù)組，只存儲(chǔ)已經(jīng)篩出的素?cái)?shù)
（2）標(biāo)記合數(shù)要針對(duì)每一個(gè)數(shù)，只標(biāo)記質(zhì)數(shù)集合中每個(gè)元素與 x相乘的結(jié)果，

說實(shí)話，這個(gè)流程一走下來，我立馬就想到了DP，果然可以使用dp的思想

基于DP
法六：

3.8 各位相加

題目：給定一個(gè)非負(fù)整數(shù) num，反復(fù)將各個(gè)位上的數(shù)字相加，直到結(jié)果為一位數(shù)。

分析：這是之前數(shù)字反轉(zhuǎn)問題的進(jìn)階版，數(shù)字反轉(zhuǎn)需要掌握每一位的推入和彈出。

官方給了一種魔法般地?cái)?shù)學(xué)解釋，只能說牛逼

3.9 丑數(shù)

題目：丑數(shù) 就是只包含質(zhì)因數(shù) 2、3 和 5 的正整數(shù)。

給你一個(gè)整數(shù) n ，請(qǐng)你判斷 n 是否為 丑數(shù) 。如果是，返回 true ；否則，返回 false 。

分析：

首先，在大數(shù)運(yùn)算上，將大數(shù)表示成冪的乘積的形式非常普遍，這是一個(gè)重要思路。另外，在程序上，n反復(fù)除以2,3，5是我一開始沒想到的
while n % factor == 0:
n //= factor

四.棧

4.1 有效的括號(hào)

題目：給定一個(gè)只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。

特殊情況：空字符串在題干要求下為真

觀察字符串，左右括號(hào)是不會(huì)混亂排列的，最右邊的左括號(hào)最先匹配，最左邊的右括號(hào)最先匹配。后入先出的這種模式就可以使用棧這種數(shù)據(jù)結(jié)構(gòu)

五.線性表和鏈表

前言

模式識(shí)別：需要移動(dòng)左右兩頭的問題可以考慮雙指針

5.1 指針

前言：雙指針問題需要考慮清楚兩個(gè)指針分別在什么情況下移動(dòng)，怎樣移動(dòng)。fast指針會(huì)將每個(gè)元素都遍歷到，因此就不要考慮slow指針是否也要判斷元素，不需要，slow指針只表示位置

5.1.1 合并兩個(gè)有序鏈表

題目：將兩個(gè)升序鏈表合并為一個(gè)新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

很容易想到，使用雙指針法來解決，但不想線性表，鏈表要求不增加額外的存儲(chǔ)空間

特殊情況：一個(gè)鏈表為空的情況

在處理鏈表問題時(shí)，總是增加一個(gè)頭結(jié)點(diǎn)來統(tǒng)一插入、刪除等操作，這樣在處理邊界的時(shí)候可以更方便，不需要額外的代碼

這里需要自己定義鏈表結(jié)點(diǎn)這一數(shù)據(jù)機(jī)構(gòu)

雙指針法的核心思路是：永遠(yuǎn)只比較兩個(gè)指針?biāo)赶虻脑?#xff0c;結(jié)果符合要求的那個(gè)指針向后移動(dòng)

5.1.1 合并兩個(gè)有序數(shù)組

題目：給你兩個(gè)按 非遞減順序 排列的整數(shù)數(shù)組 nums1 和 nums2，另有兩個(gè)整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素?cái)?shù)目。

請(qǐng)你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲(chǔ)在數(shù)組 nums1 中。為了應(yīng)對(duì)這種情況，nums1 的初始長(zhǎng)度為 m + n，其中前 m 個(gè)元素表示應(yīng)合并的元素，后 n 個(gè)元素為 0 ，應(yīng)忽略。nums2 的長(zhǎng)度為 n 。

在解法上，雙指針法已經(jīng)非常熟悉了。針對(duì)本題，因?yàn)閿?shù)組1預(yù)留了包函數(shù)組2的存儲(chǔ)空間，所以采用從后往前掃描的雙指針法可以不增加額外的存儲(chǔ)空間

注意，雙指針法那個(gè)指針符合條件，那個(gè)指針才移動(dòng)

嚴(yán)格來說，上述反向進(jìn)行的遍歷需要3個(gè)指針

5.1.2 刪除排序數(shù)組中的重復(fù)項(xiàng)

題目：給你一個(gè)有序數(shù)組 nums ，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長(zhǎng)度。

不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。

法一：
對(duì)于有序數(shù)組，如果允許額外存儲(chǔ)，那么可以直接遍歷數(shù)組，只通過相鄰兩個(gè)元素的比較結(jié)果進(jìn)行操作，不同則記錄，相同則跳過

但不允許額外存儲(chǔ)的條件下呢？

設(shè)置快慢指針，慢指針負(fù)責(zé)指出可覆蓋位置，快指針負(fù)責(zé)遍歷數(shù)組

從下標(biāo)為1的位置開始比較是因?yàn)?#xff0c;如果重復(fù)，至少是從下標(biāo)為1的位置開始覆蓋。另外，比較相鄰元素取的是通過后一個(gè)元素與前一個(gè)元素比較，也就是fast 和 fast-1比較

同時(shí)，這樣的設(shè)計(jì)背景下，慢指針是可以充當(dāng)新數(shù)組的長(zhǎng)度，也就是遍歷原數(shù)組slow長(zhǎng)度即是沒有重復(fù)元素的新數(shù)組

特殊的，需要考慮數(shù)組長(zhǎng)度為0的情況

5.1.2 刪除排序鏈表中的重復(fù)元素

題目：存在一個(gè)按升序排列的鏈表，給你這個(gè)鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你刪除所有重復(fù)的元素，使每個(gè)元素 只出現(xiàn)一次 。

返回同樣按升序排列的結(jié)果鏈表。

相較于數(shù)組，刪除重復(fù)元素之后需要覆蓋，對(duì)于鏈表只需要重新鏈接即可，也不需要頭結(jié)點(diǎn)來統(tǒng)一操作

不要怕鏈表的這些操作

5.1.3 移除元素

題目：給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長(zhǎng)度。

不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

法一：
還是使用5.1.2的方法，由fast指針遍歷數(shù)組，如果該元素不是目標(biāo)，則寫到slow的位置，slow和fast都向前移動(dòng)
否則，fast向前移動(dòng)

這一方法我覺得別扭的地方在于，假設(shè)有連續(xù)的元素都不是目標(biāo)，但是還是需要寫一遍。可以這樣，判斷fast和slow是否相等，實(shí)際上只要出現(xiàn)一次目標(biāo),fast和slow必發(fā)生錯(cuò)位

法二:
產(chǎn)生的背景是，如果要移除的元素恰好在數(shù)組的開頭，可以直接將最后一個(gè)元素 55 移動(dòng)到序列開頭，取代元素 1
這個(gè)優(yōu)化在序列中val 元素的數(shù)量較少時(shí)非常有效

此方法，雙指針在一次循環(huán)中只有一個(gè)指針會(huì)發(fā)生移動(dòng)，由left遍歷數(shù)組，如果發(fā)現(xiàn)目標(biāo)，right向左移動(dòng)，left不動(dòng)
否則，沒發(fā)現(xiàn)目標(biāo)，left向右移動(dòng)

這樣感覺就消除了前面非目標(biāo)連續(xù)元素的問題

5.1.4 驗(yàn)證回文串

題目：給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。

說明：本題中，我們將空字符串定義為有效的回文串。

法一：反轉(zhuǎn)字符串

字符串里面可能有空格，標(biāo)點(diǎn)符號(hào)，他并不是簡(jiǎn)單地abba這種形式

因?yàn)樯婕暗絻蓚€(gè)指針的移動(dòng)，極端情況下指針會(huì)移動(dòng)到串尾，因此每次移動(dòng)完之后都需要判斷指針位置是否符合條件

5.1.5 環(huán)形鏈表

題目：給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán)，則返回 true 。 否則，返回 false 。

解法：雙指針法
利用快慢指針，慢指針一次走一步，快指針一次走兩步
比較反直覺的一點(diǎn)是，快指針有可能會(huì)超過慢指針，但總會(huì)相遇在同一個(gè)位置

如果說不存在環(huán)，則快指針一定先到達(dá)鏈表尾部，要么本身為空，要么next為空

5.1.6 回文鏈表

分析：我選擇最簡(jiǎn)單的一種方式，把節(jié)點(diǎn)的值取出來，就等價(jià)于處理回文數(shù)組了，經(jīng)典的雙指針法

實(shí)際上，可以直接使用快慢指針法，但是要麻煩許多
1.通過快慢指針的慢指針將鏈表后半段反轉(zhuǎn)
2.判斷是否回文
3.通過快指針恢復(fù)鏈表

5.1.7 刪除鏈表中的節(jié)點(diǎn)

題目：請(qǐng)編寫一個(gè)函數(shù)，用于 刪除單鏈表中某個(gè)特定節(jié)點(diǎn) 。在設(shè)計(jì)函數(shù)時(shí)需要注意，你無法訪問鏈表的頭節(jié)點(diǎn) head ，只能直接訪問 要被刪除的節(jié)點(diǎn) 。

題目數(shù)據(jù)保證需要?jiǎng)h除的節(jié)點(diǎn) 不是末尾節(jié)點(diǎn) 。

分析：可惜，沒有注意到待刪除節(jié)點(diǎn)不是末尾結(jié)點(diǎn)
先將待刪除節(jié)點(diǎn)的val變成下一個(gè)節(jié)點(diǎn)的val，再刪除下一個(gè)節(jié)點(diǎn)。鏈表節(jié)點(diǎn)的信息也就兩個(gè)嘛，val和next

5.2 最后一個(gè)單詞的長(zhǎng)度

題目：給你一個(gè)字符串 s，由若干單詞組成，單詞前后用一些空格字符隔開。返回字符串中最后一個(gè)單詞的長(zhǎng)度。

單詞 是指僅由字母組成、不包含任何空格字符的最大子字符串。

反向遍歷即可

因?yàn)轭}干已經(jīng)說明，字符串至少含有一個(gè)單詞，也就不需要考慮沒有單詞的情況

5.3 雙指針

5.3.1 相交鏈表

題目：給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 null 。

圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開始相交：

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。

解法：雙指針

雙指針的更新策略非常巧妙，如果能讓兩個(gè)指針齊頭并進(jìn)，那么他們一定能同時(shí)到達(dá)相交點(diǎn)。但是兩個(gè)單鏈表的長(zhǎng)度不一樣

但是，兩個(gè)鏈表共享其中一段，只有交點(diǎn)前面一段不一樣。如果說一個(gè)指針走過自己這一段，再走另一個(gè)指針走的那一段，以交點(diǎn)為界，那么總體來講，兩個(gè)指針就走過了相等的長(zhǎng)度

5.3.2 反轉(zhuǎn)鏈表

題目：給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

解析：嚴(yán)格來說應(yīng)該是3個(gè)指針，需要同時(shí)記錄當(dāng)前節(jié)點(diǎn)，前一節(jié)點(diǎn)，后一節(jié)點(diǎn)的地址，也就是鏈表操作中的“先連后斷”, 連接之后再更新指針

5.3.3 匯總區(qū)間

題目：給定一個(gè)無重復(fù)元素的有序整數(shù)數(shù)組 nums 。

返回 恰好覆蓋數(shù)組中所有數(shù)字 的 最小有序 區(qū)間范圍列表。

nums = [0,1,2,4,5,7]
[“0->2”,“4->5”,“7”]

分析：經(jīng)典的雙指針法。重點(diǎn)是找到high的位置。判斷條件在題干中分析可以得出。low和high分別指向區(qū)間的左右。

5.3.4 會(huì)議室

題目：給定一個(gè)會(huì)議時(shí)間安排的數(shù)組 intervals ，每個(gè)會(huì)議時(shí)間都會(huì)包括開始和結(jié)束的時(shí)間 intervals[i] = [starti, endi] ，請(qǐng)你判斷一個(gè)人是否能夠參加這里面的全部會(huì)議。

分析：核心在于判斷區(qū)間是否有重疊。重點(diǎn)是要先進(jìn)行排序，笑死

5.3.5 移動(dòng)零

題目：給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序。

分析：數(shù)組要進(jìn)行元素的按值移動(dòng)還是比較困難的。使用雙指針法處理，要對(duì)兩個(gè)指針的功能和操作定義清楚
left: 左邊為非零數(shù)，一直指向已處理好的序列的尾部
right: 左邊直至left為止，為0，一直指向待處理序列的頭部

什么是處理好的？？不含0
什么是待處理的？？含0

總的來說，就是將left的0與right的非0進(jìn)行交換，left找0，right找非0

這樣說還是挺抽象的，具象一點(diǎn)：

遇到非0，兩個(gè)指針均向前移動(dòng)。很好理解，因?yàn)閘eft沒有找到0，所以就沒有和right交換的需要

遇到0，right右移。這就說明，left找到了0，right需要去找下面第一個(gè)非0

經(jīng)過情況2之后，如果right找到了非0，此時(shí)就應(yīng)該交換left和right的值

我一直覺得別扭的地方在于，如果從一開始直接遇到情況1，不就意味著left和right都指向同一個(gè)元素嗎？？他們有必要進(jìn)行交換嗎？？
A：這是一種必要的開銷。只要進(jìn)行過一次0的移動(dòng)，left和right必然會(huì)錯(cuò)開。當(dāng)然，如果從開頭就是連續(xù)的非0，那么left和right的確會(huì)發(fā)生看起來沒必要的交換

5.4 棧和隊(duì)列

5.4.1 用隊(duì)列實(shí)現(xiàn)棧

題目：請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

分析：假設(shè)使用兩個(gè)隊(duì)列來模擬棧
入棧：隊(duì)列1存儲(chǔ)當(dāng)前的棧內(nèi)元素，并是指指針指向隊(duì)首元素；隊(duì)列2存儲(chǔ)即將入棧的元素
將隊(duì)列1的元素出隊(duì)列1，入隊(duì)列2，并交換兩個(gè)隊(duì)列以維持上述的定義，更新指針
其他操作基于隊(duì)列1完成即可，主要就是通過兩個(gè)隊(duì)列實(shí)現(xiàn)入棧操作

5.4.3 用棧實(shí)現(xiàn)隊(duì)列

分析：同樣的序列分別推入棧和隊(duì)列，彈出序列恰好相反，那么將棧的彈出序列再推入另一個(gè)棧，再彈出，不就和隊(duì)列的彈出序列相同了嗎

基于這一點(diǎn)，可以維護(hù)兩個(gè)棧倆實(shí)現(xiàn)隊(duì)列的效果。棧1負(fù)責(zé)彈出，棧2負(fù)責(zé)推入。
出棧：如果棧1不空，則彈出棧頂元素；如果棧1為空，將棧2元素全部彈出并推入棧1，再彈出棧頂元素

5.5 區(qū)域和檢索 - 數(shù)組不可變

題目：給定一個(gè)整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i、j 兩點(diǎn)。

實(shí)現(xiàn) NumArray 類：

NumArray(int[] nums) 使用數(shù)組 nums 初始化對(duì)象
int sumRange(int i, int j) 返回?cái)?shù)組 nums 從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i、j 兩點(diǎn)（也就是 sum(nums[i], nums[i + 1], … , nums[j])）

分析：當(dāng)數(shù)組確定，使用函數(shù)多次求解區(qū)間和是沒有必要的。每次求解區(qū)間和都需要遍歷，在初始化的時(shí)候可以一次性求出階梯和，階梯和通過裁切可以得到區(qū)間和

階梯和怎么求？？？
A：創(chuàng)建一個(gè)存儲(chǔ)階梯和的數(shù)組，先加入元素0，遍歷原數(shù)組，每次選擇一個(gè)元素和階梯和數(shù)組的[-1]位相加

六.動(dòng)態(tài)規(guī)劃

6.1 最大子序列和

題目：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

我的問題在于對(duì)狀態(tài)方程的定義，我的定義是：
f(i)表示到第i個(gè)元素為止的數(shù)組的最大子序和，由此寫出的狀態(tài)轉(zhuǎn)移方程是，f(i) = max( f[i-1], f[i-1] + nums[i] )

正確的定義是：
f(i) 代表以第 i 個(gè)數(shù)結(jié)尾的「連續(xù)子數(shù)組的最大和， 因此有
f(i)=max{f(i?1)+nums[i],nums[i]}

我的定義就不滿足連續(xù)子序列的連續(xù)，對(duì)于第i個(gè)元素，只有兩種狀態(tài)，要么被包含進(jìn)子序列，要么不被包含，自成一個(gè)序列。之所以只有兩種狀態(tài)，還是因?yàn)閷?duì)f(i)的定義，必須要以第i個(gè)元素結(jié)尾

這也是我最迷惑的地方，子序列的位置是不固定的，這種不固定就導(dǎo)致有些反直覺。比如說對(duì)于數(shù)組[1,2,3,-4,5,6]。按照正確的定義，f(3)的最大子序和是2，但我總感覺應(yīng)該是6

我做了這樣一個(gè)嘗試，將數(shù)組[1,2,3,-4]按照上述兩種定義方式寫出求解f(i)時(shí)涉及到的子序列，我發(fā)現(xiàn)，按照我的定義，f[i-1] + nums[i] 不一定成立，因?yàn)閒(i-1)表示的最大子序列的最后一個(gè)元素不一定是nums[i-1]
按照正確的定義，f(i?1)+nums[i] 和 nums[i] 確實(shí)能夠形成兩個(gè)連續(xù)的序列
寫出數(shù)組[1,2,3,-4]按照正確定義涉及到的連續(xù)子序列，我發(fā)現(xiàn)實(shí)際上它是包含了數(shù)組的所有連續(xù)子序列

我想應(yīng)該這樣總結(jié)，通過計(jì)算所有以第i個(gè)元素結(jié)尾的連續(xù)序列，最終我們就計(jì)算了全部的連續(xù)序列，進(jìn)而就可以求得其中和最大的連續(xù)序列

通過測(cè)試，不能將f(i-1)寫入狀態(tài)轉(zhuǎn)移方程，他的值總是最大的

6.2 爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

6.3 楊輝三角

題目：給定一個(gè)非負(fù)整數(shù) numRows，生成「楊輝三角」的前 numRows 行。

在「楊輝三角」中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。

生成楊輝三角的原理非常簡(jiǎn)單，只是說一般分析是寫成等腰三角形，但寫成程序，就寫成直角三角形，以此來確定計(jì)算關(guān)系

6.4 楊輝三角2

思路同上，理解了如何生成楊輝三角即可

6.5 買賣股票的最佳時(shí)機(jī)

題目：給定一個(gè)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 表示一支給定股票第 i 天的價(jià)格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個(gè)不同的日子 賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。

返回你可以從這筆交易中獲取的最大利潤(rùn)。如果你不能獲取任何利潤(rùn)，返回 0

解法：典型的動(dòng)態(tài)規(guī)劃，在這個(gè)問題上，注意，只進(jìn)行一次交易


如果寫出如同分析“最大子序和”那樣的數(shù)對(duì)，感覺很難判斷是否包含了所有的選擇。在上面的分析中，對(duì)f(i)的定義實(shí)際上是前i-1個(gè)數(shù)中的最小值，當(dāng)然，硬要說的話，將其定義為到第i個(gè)數(shù)的最大收益也不是不行。主要是要想清楚最大收益產(chǎn)生于什么時(shí)候

6.6 買賣股票的最佳時(shí)機(jī)2

題目：給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

解析：這一次就能進(jìn)行多次交易，但是交易不能重疊
收集所有上行區(qū)段的利潤(rùn)即可

6.7 比特位計(jì)數(shù)

題目：給你一個(gè)整數(shù) n ，對(duì)于 0 <= i <= n 中的每個(gè) i ，計(jì)算其二進(jìn)制表示中 1 的個(gè)數(shù) ，返回一個(gè)長(zhǎng)度為 n + 1 的數(shù)組 ans 作為答案。

分析：
對(duì)于2的冪，已經(jīng)知道可以通過x&(x-1)來判斷。要計(jì)算i的二進(jìn)制表示中1的個(gè)數(shù)，可以反復(fù)進(jìn)行與運(yùn)算。但是以前就知道 i 中1的個(gè)數(shù)和處于其之前的2的冪有關(guān)

那就可以使用DP的思想來處理，首先定義dp[i] 為數(shù)i的1的個(gè)數(shù)
實(shí)際上可以構(gòu)造這樣的狀態(tài)轉(zhuǎn)移方程：
dp[i] = dp[i - 當(dāng)前最大2的冪] + dp[當(dāng)前最大2的冪]
dp[2的冪] 都為1，因此可以將上式表示為：
dp[i] = dp[i - 當(dāng)前最大2的冪] + 1

七. 樹

前言

先講講dfs，這個(gè)算法我接觸的比較早，算法思想也符合我的思維方式。但是具體到代碼層面，就和我的理解出現(xiàn)了偏差。
我的理解是，棧里面存的應(yīng)該是一條可回溯的路徑，比如說對(duì)于這樣一張無向圖

我認(rèn)為最開始棧里邊存的是A C D,從A開始按照規(guī)律向相連的最深處遍歷，當(dāng)D沒有相鄰邊之后，回溯到C，看C還有沒有未訪問的相鄰邊，再回溯到A
很明顯，對(duì)于每一個(gè)節(jié)點(diǎn)我們需要訪問到相鄰節(jié)點(diǎn)，如果暫時(shí)只取一個(gè)節(jié)點(diǎn)推入棧，那么應(yīng)該以什么方式選擇呢？等到回溯至此的時(shí)候，又以同樣的方式選擇一個(gè)節(jié)點(diǎn)推入棧嗎？可想而知有多混亂

我想我產(chǎn)生這種想法的理由是，我總是認(rèn)為棧里面應(yīng)該存dfs的路徑。但是是否可以這樣，通過棧頂元素的彈出來確定dfs的路徑呢？棧里面存儲(chǔ)節(jié)點(diǎn)，每次遍歷當(dāng)前節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)，推入沒有訪問過得節(jié)點(diǎn)，同時(shí)更新訪問數(shù)組，記錄已經(jīng)訪問的節(jié)點(diǎn)。所以棧里面沒有重復(fù)元素，都是唯一的，這樣也就保證了訪問不會(huì)重復(fù)

為什么這種方法可以達(dá)到dfs的效果？通過上述方法，相當(dāng)于每彈出一個(gè)節(jié)點(diǎn)，就會(huì)推入與之相鄰的未訪問節(jié)點(diǎn)。那么，彈出元素之間的關(guān)系就是層層向深處推進(jìn)的關(guān)系,a[i-1]和a[i]相鄰，a[i]和a[i+1]相鄰

stack數(shù)組是用來達(dá)到dfs的核心，visit數(shù)組是輔助stack,保證不重復(fù)

樹的遍歷區(qū)別于圖，我們對(duì)樹的遍歷的順序做了規(guī)范，先序中序后序。
如果說使用dfs思想遍歷二叉樹，將節(jié)點(diǎn)推入stack默認(rèn)順序?yàn)橄茸笞訕湓儆易訕?#xff0c;那么遍歷順序就等價(jià)于“根右左”

關(guān)于遞歸回溯的理解

7.1 樹的遍歷

7.1.1 二叉樹的中序遍歷

題目：給定一個(gè)二叉樹的根節(jié)點(diǎn) root ，返回它的 中序 遍歷。

這是個(gè)老問題了，一般考慮使用遞歸，比較好理解
遞歸都可以改成迭代，也就是循環(huán)

兩種方式是等價(jià)的，區(qū)別在于遞歸的時(shí)候隱式地維護(hù)了一個(gè)棧，（一直朝左子樹的最深處,到時(shí)候要回退）而我們?cè)诘臅r(shí)候需要顯式地將這個(gè)棧模擬出來，其他都相同

以回溯為重點(diǎn)考慮的話，是否可以這樣理解
1.root不空，則一直尋找最深的左子樹為空的節(jié)點(diǎn)
2.輸出這個(gè)節(jié)點(diǎn)，將其作為新的根
3.如果root的右子樹為空則回溯，即彈出棧頂元素如果root的右子樹不為空，則重復(fù)上述過程

但是在代碼層面并不會(huì)直接去判斷root的右子樹是否為空，核心代碼會(huì)先找最深、且左子樹為空的節(jié)點(diǎn)，然后將root更新為該節(jié)點(diǎn)的右節(jié)點(diǎn)

感覺這塊有點(diǎn)亂，TNND

7.1.2 相同的樹

題目：判斷兩棵樹是否相同

既要進(jìn)行數(shù)值比較，又要進(jìn)行結(jié)構(gòu)比較

乍一看，似乎個(gè)圖算法用到bfs和dfs一樣，但是兩棵樹就需要用到兩個(gè)棧或者兩個(gè)隊(duì)列
dfs可以用遞歸來做，遞歸就需要遞歸出口和遞歸表達(dá)式
遞歸出口的范式一般是：如果…，返回…
如果兩個(gè)跟都為空則相同
如果其中一個(gè)為空則不同
如果兩個(gè)的值不等則不同
數(shù)值和結(jié)構(gòu)的比較都包含了

遞歸表達(dá)式基于樹的這種分形結(jié)構(gòu)，根比較完之后，就要確定左子樹和右子樹的情況

對(duì)于dfs的迭代版本，需要考慮循環(huán)條件，循環(huán)中何時(shí)退出。毫無疑問，只有整個(gè)迭代完成才能判斷兩棵樹相同

7.1.3 對(duì)稱二叉樹

題目：給定一個(gè)二叉樹，檢查它是否是鏡像對(duì)稱的。

總結(jié)一下，先序中序后序遍歷二叉樹通常使用遞歸來實(shí)現(xiàn)，本質(zhì)上使用的是dfs思想，遞歸隱式地維護(hù)了一個(gè)棧。之后“相同的樹”這一題也是用遞歸解決，那么實(shí)際上遞歸通過不同的結(jié)構(gòu)可以改變遍歷的順序

因此，熟悉遞歸的結(jié)構(gòu)就尤為重要

遞歸出口：考慮高度為2的二叉樹

根均為空，為真

一個(gè)根為空，為假

兩個(gè)根的值相同，樹A的左子樹和樹B的右子樹，樹A的右子樹和樹B的左子樹相等

這個(gè)問題和“相同的樹”比較類似

7.1.4 二叉樹的最大深度

題目：給定一個(gè)二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

還是可以沿用上述的dfs思想，如果我們知道了左子樹和右子樹的最大深度 l 和 r，那么該二叉樹的最大深度即為max(l,r)+1，而左子樹和右子樹的最大深度又可以以同樣的方式進(jìn)行計(jì)算。因此我們可以用「深度優(yōu)先搜索」的方法來計(jì)算二叉樹的最大深度。具體而言，在計(jì)算當(dāng)前二叉樹的最大深度時(shí)，可以先遞歸計(jì)算出其左子樹和右子樹的最大深度，然后在 O(1) 時(shí)間內(nèi)計(jì)算出當(dāng)前二叉樹的最大深度。遞歸在訪問到空節(jié)點(diǎn)時(shí)退出。

細(xì)品為何在root為空時(shí)返回0：明顯，root為空，這一層不存在，當(dāng)然返回0；但是root不為空，這一層肯定就是+1.所以總體來看它是一層一層進(jìn)行的計(jì)算

7.1.5 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

題目：給你一個(gè)整數(shù)數(shù)組 nums ，其中元素已經(jīng)按 升序 排列，請(qǐng)你將其轉(zhuǎn)換為一棵 高度平衡 二叉搜索樹。

高度平衡 二叉樹是一棵滿足「每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1 」的二叉樹。

法一：遞歸
首先是BST二叉搜索樹的定義，從節(jié)點(diǎn)的值的角度出發(fā)，根比左子樹的要大，比右子樹的要小

7.1.6 平衡二叉樹

題目：給定一個(gè)二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對(duì)值不超過 1 。

解法：不是要構(gòu)造平衡二叉樹。平衡二叉樹的定義是，任意結(jié)點(diǎn)的左右子樹的高度差不超過1
仍然是用遞歸的方式，核心在于如何判斷是否平衡

如果節(jié)點(diǎn)為空，則平衡

左右子樹的高度差不超過1，且左子樹，右子樹也都是平衡二叉樹

第二點(diǎn)不容易想到

7.1.7 二叉樹的最小深度

題目：給定一個(gè)二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

又是一個(gè)基于DFS，使用遞歸完成的問題

遞歸出口有3個(gè)：

根節(jié)點(diǎn)為空

根節(jié)點(diǎn)沒有子樹

根節(jié)點(diǎn)有子樹，返回當(dāng)前的最小深度 + 1

遞歸表達(dá)式為：
如果存在子樹，則將其作為根，返回其高度和最小深度的比較結(jié)果，取更小的那個(gè)更新最小深度

7.1.8 路徑總和

題目：
給你二叉樹的根節(jié)點(diǎn) root 和一個(gè)表示目標(biāo)和的整數(shù) targetSum ，判斷該樹中是否存在 根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 的路徑，這條路徑上所有節(jié)點(diǎn)值相加等于目標(biāo)和 targetSum 。

葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

解法：
還是一樣，使用DFS的思想，用遞歸來完成

遞歸出口有兩個(gè)：

如果根為空，返回FALSE。表示無法訪問這個(gè)節(jié)點(diǎn)

如果該節(jié)點(diǎn)為葉子結(jié)點(diǎn)，進(jìn)行值的比較

遞歸表達(dá)式：
如果根存在子樹，那么需要看左子樹或者右子樹是否存在滿足條件的情況

7.1.8 二叉樹的所有路徑

題目：給你一個(gè)二叉樹的根節(jié)點(diǎn) root ，按 任意順序 ，返回所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。

葉子節(jié)點(diǎn) 是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

分析：老辦法，DFS+遞歸實(shí)現(xiàn)。

遞歸出口要理解還是很容易的，但是在代碼上有些我感覺反直覺的東西

就是說當(dāng)開始遍歷root的右子樹的時(shí)候，為什么不會(huì)在路徑上出現(xiàn)左子樹的節(jié)點(diǎn)。在我的直覺上，我認(rèn)為會(huì)出現(xiàn)左子樹的節(jié)點(diǎn)？？？
A：其原因在于遞歸函數(shù)的參數(shù)，我們傳遞進(jìn)去的當(dāng)前額路徑path。在上述代碼中，else塊的兩個(gè)實(shí)參path是一樣的，此時(shí)意味著在進(jìn)行分叉，而分叉之前的路徑是一樣的。舉個(gè)簡(jiǎn)單的例子，形如，

通過手動(dòng)推算，開始訪問root 1的左子樹和右子樹的path都是1->，然后進(jìn)入遞歸

7.1.9 翻轉(zhuǎn)二叉樹

題目：翻轉(zhuǎn)一棵二叉樹。

分析：將一顆二叉樹進(jìn)行鏡像翻轉(zhuǎn)。二叉樹問題普遍需要遍歷，遍歷通常又是用遞歸來實(shí)現(xiàn)。

遞歸出口我總結(jié)下來，需要考慮最簡(jiǎn)單地情況：
1.根不存在
2.根存在
3.根的子樹不存在子樹了
如上，最多到高度為二的二叉樹就能把出口描述清楚，感覺還是很微妙

之前有道題，相同二叉樹，需要判斷一棵樹是否對(duì)稱，思路類似

7.2 二叉搜索樹的最近公共祖先

題目：給定一個(gè)二叉搜索樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先。

百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）。”

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]、

分析：
首先是二叉搜索樹的定義，也叫二叉排序樹。我們通過遞歸定義二叉排序樹，先構(gòu)造新的節(jié)點(diǎn)，若root為空，則直接插入；否則，若val小于根的val，則插入左子樹，否則插入右子樹

一次遍歷真的很秀，很優(yōu)雅
（1）p, q不存在咋辦？
不可能。題干說了，樹中指定的兩個(gè)節(jié)點(diǎn)，找就完事了
（2）p,q在什么時(shí)候分叉？
首先，他們一定會(huì)分叉。根據(jù)bst的性質(zhì)，分叉的節(jié)點(diǎn)一個(gè)比直接雙親大，一個(gè)小。這也就意味著，當(dāng)root不能同時(shí)大于或者小于兩點(diǎn)，則該root為最近的公共祖先。從此刻開始，兩個(gè)節(jié)點(diǎn)分道揚(yáng)鑣

7.3 最接近的二叉搜索樹值

題目：給定一個(gè)不為空的二叉搜索樹和一個(gè)目標(biāo)值 target，請(qǐng)?jiān)谠摱嫠阉鳂渲姓业阶罱咏繕?biāo)值 target 的數(shù)值。

注意：

給定的目標(biāo)值 target 是一個(gè)浮點(diǎn)數(shù)
題目保證在該二叉搜索樹中只會(huì)存在一個(gè)最接近目標(biāo)值的數(shù)

分析：
我最開始只有一點(diǎn)不確定，是否需要遍歷所有節(jié)點(diǎn)？？？？
A：不需要。通過數(shù)軸可以確定。如果target < root.val， 那么最接近的值一定在root的左子樹。
反證法證明：如果在右子樹，那么這個(gè)值一定大于root.val，而root.val才是最接近的值。矛盾

八. 位運(yùn)算

8.1 只出現(xiàn)一次的數(shù)字

題目：給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

利用了異或運(yùn)算的交換律。異或運(yùn)算，相同為0，不同為1，另外，a^a = 0
0 ^ a = a。0就相當(dāng)于與乘法運(yùn)算中的1

8.2 Excel表列名稱

題目：給你一個(gè)整數(shù) columnNumber ，返回它在 Excel 表中相對(duì)應(yīng)的列名稱。

例如：

A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28

解法：應(yīng)該想到他的模式，每26位要進(jìn)一位。進(jìn)一步想到考察進(jìn)位機(jī)制
本質(zhì)上就是10進(jìn)制轉(zhuǎn)26進(jìn)制，那就是 ：除進(jìn)制取余倒排

有點(diǎn)反直覺的地方在于實(shí)現(xiàn)數(shù)字和字符串的轉(zhuǎn)換，其實(shí)使用純數(shù)字來表示可能更好理解，這也就意味著莫以為可以是（26），所以某個(gè)數(shù)字就成了
(26)(26),由此看看怎么實(shí)現(xiàn)轉(zhuǎn)換

有點(diǎn)麻煩的是這個(gè)0，不管是10進(jìn)制還是二進(jìn)制都有0,10進(jìn)制轉(zhuǎn)二進(jìn)制，余數(shù)為0是不用特殊處理的。

8.3 顛倒二進(jìn)制位

題目：顛倒給定的 32 位無符號(hào)整數(shù)的二進(jìn)制位。

提示：

請(qǐng)注意，在某些語言（如 Java）中，沒有無符號(hào)整數(shù)類型。在這種情況下，輸入和輸出都將被指定為有符號(hào)整數(shù)類型，并且不應(yīng)影響您的實(shí)現(xiàn)，因?yàn)闊o論整數(shù)是有符號(hào)的還是無符號(hào)的，其內(nèi)部的二進(jìn)制表示形式都是相同的。
在 Java 中，編譯器使用二進(jìn)制補(bǔ)碼記法來表示有符號(hào)整數(shù)。因此，在 示例 2 中，輸入表示有符號(hào)整數(shù) -3，輸出表示有符號(hào)整數(shù) -1073741825。

解析：輸入是一個(gè)二進(jìn)制數(shù)，只是要注意一點(diǎn)，當(dāng)他作為二進(jìn)制數(shù)時(shí)，高位的0會(huì)被省去，比如000111，在實(shí)際使用的時(shí)候就變成111

8.4 2的冪

題目：給你一個(gè)整數(shù) n，請(qǐng)你判斷該整數(shù)是否是 2 的冪次方。如果是，返回 true ；否則，返回 false 。

如果存在一個(gè)整數(shù) x 使得 n == 2x ，則認(rèn)為 n 是 2 的冪次方。

分析：
我一直對(duì)位運(yùn)算不熟悉，沒怎么用過。之前只是用過運(yùn)算的相關(guān)性質(zhì)，0相當(dāng)于乘法中的1
n & (n - 1)用于移除最低位的1
實(shí)際上只有兩種情況：（1）不需要借位時(shí)，最低位的1必然是在末位，那么n和n-1的其他位相同，與運(yùn)算之后n的其他位不變，末位變0；（2）需要借位時(shí)，必然從最低位的1借出，那么從最低位的1開始直至末尾，n和n-1不同，與運(yùn)算之后，這些為全為0，也移除了最低位的1

在本題中，2的冪的二進(jìn)制表示必然只有一個(gè)1，那么移除最低位的1之后此數(shù)必然變?yōu)?

8.4 3的冪

沒有辦法像求解2的冪那樣直接使用位運(yùn)算，但是x的冪的特點(diǎn)是，（1）首先是正整數(shù) （2）一直除3都能整除

8.5 丟失的數(shù)字

題目：給定一個(gè)包含 [0, n] 中 n 個(gè)數(shù)的數(shù)組 nums ，找出 [0, n] 這個(gè)范圍內(nèi)沒有出現(xiàn)在數(shù)組中的那個(gè)數(shù)。

分析：首先是這個(gè)題目看得人有點(diǎn)懵逼。[0,n]有n+1個(gè)數(shù)字，但是只包含了n個(gè)，范圍在[0,n+1]，找出缺的那一個(gè)

我選擇了位運(yùn)算的解法，比較喜歡異或運(yùn)算，核心就這兩個(gè)：x^x = 0
x^0 = x
如果在原序列后面再補(bǔ)上[0,n+1]這n+1個(gè)數(shù)，依次進(jìn)行異或，因?yàn)槿笔У臄?shù)字只出現(xiàn)了一次，那么最后的結(jié)果就是這個(gè)確實(shí)的數(shù)字

巧妙地地方在于，并不需要真的往數(shù)組補(bǔ)上n+1個(gè)數(shù)，因?yàn)閿?shù)字范圍和下標(biāo)是一致的，因此讓數(shù)組下標(biāo)參與異或即可，最后再補(bǔ)上len(nums)即可。真的非常優(yōu)雅

九. 字符串

9.1 最短單詞距離

題目：給定一個(gè)單詞列表和兩個(gè)單詞 word1 和 word2，返回列表中這兩個(gè)單詞之間的最短距離。

分析：
我最初的想法是，先找第一個(gè)，再找第二個(gè)，然后計(jì)算距離，但是處理不了這種情況
a…a…b…b
此問題的關(guān)鍵在于，必須要在遍歷的過程中同時(shí)找兩個(gè)目標(biāo)，實(shí)時(shí)更新他們的位置

如上例，前面有重復(fù)的單詞1，一直沒有找到單詞2,那么處于后位的單詞1肯定離單詞2更近

十. 博弈論

10.1 nim游戲

題目：你和你的朋友，兩個(gè)人一起玩 Nim 游戲：

桌子上有一堆石頭。
你們輪流進(jìn)行自己的回合，你作為先手。
每一回合，輪到的人拿掉 1 - 3 塊石頭。
拿掉最后一塊石頭的人就是獲勝者。
假設(shè)你們每一步都是最優(yōu)解。請(qǐng)編寫一個(gè)函數(shù)，來判斷你是否可以在給定石頭數(shù)量為 n 的情況下贏得游戲。如果可以贏，返回 true；否則，返回 false 。

分析：

推廣開來，將整個(gè)游戲進(jìn)程視作k個(gè)回合，每回合各抓一次。
后手要贏就得保證在最后一個(gè)回合開始前石子總數(shù)是4的倍數(shù)。
先手要贏就得破壞這個(gè)條件，在先手抓后，使總的石子數(shù)變成4的倍數(shù)。也就是把超過4n的那部分抓掉

進(jìn)一步講，從一開始結(jié)局就是肯定的

當(dāng)規(guī)則形成，游戲中只有最精明的玩家時(shí)，結(jié)局是注定的

總結(jié)

以上是生活随笔為你收集整理的每天一个算法（简单）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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