??一鼓作氣，再而衰氮发，三而竭渴肉，第三篇走起！
- 目錄：
算法：附錄
算法（1）：遞歸
算法（2）：鏈表
算法（3）：數(shù)組
算法（4）：字符串
算法（5）：二叉樹
算法（6）：二叉查找樹
算法（7）：隊(duì)列和堆棧（附贈(zèng)BFS和DFS）
算法（8）：動(dòng)態(tài)規(guī)劃
算法（9）：哈希表
算法（10）：排序
算法（11）：回溯法
算法（12）：位操作
數(shù)組（Array）
??數(shù)組是大家再熟悉不過(guò)的東西了爽冕，但是這里還是簡(jiǎn)單說(shuō)一下仇祭，數(shù)組是連續(xù)存放一系列元素的數(shù)據(jù)結(jié)構(gòu)，我們可以方便的通過(guò)索引訪問(wèn)數(shù)組當(dāng)中的任何一個(gè)元素颈畸。通常乌奇，數(shù)組在定義時(shí)是固定大小的，但是也有一種動(dòng)態(tài)數(shù)組眯娱，它在初始化時(shí)不需要定義數(shù)組大小礁苗，也就意味著可以無(wú)限裝數(shù)據(jù)，我們稱之為動(dòng)態(tài)數(shù)組徙缴，如C++當(dāng)中的Vector（曾經(jīng)是我最喜歡的一個(gè)數(shù)據(jù)結(jié)構(gòu)试伙，當(dāng)然，在我遇到python當(dāng)中的List之前）和Java當(dāng)中的ArrayList 于样。
安利一波問(wèn)題4疏叨，大家一定要看一看。
問(wèn)題1：找到一個(gè)一維數(shù)組的“中樞”元素的索引穿剖。如果有很多中樞元素考廉，則只需返回最左側(cè)的即可。中樞在此處意味著該索引左側(cè)元素和等于該索引右側(cè)元素和携御。
輸入: [1, 2, 8, 4, 5, 6]
輸出: 3（1+2+8 = 5+6）
代碼，那是異常的簡(jiǎn)單啊既绕。小編不禁想起了有一次面試啄刹，面試官讓我寫一個(gè)找數(shù)組中最大最小值的算法，啊凄贩，那時(shí)的時(shí)光是多么美好誓军！如下代碼的時(shí)間復(fù)雜度，空間復(fù)雜度
疲扎。
def pivotIndex(nums) -> int:
ts, cs = sum(nums), 0
for idx, num in enumerate(nums):
ls, rs = cs, ts - cs - num
if ls == rs:
return idx
cs += num
return -1
if __name__ == '__main__':
ans = pivotIndex([1, 2, 8, 4, 5, 6])
print(ans)
問(wèn)題2：加1操作昵时。將輸入數(shù)組當(dāng)成一個(gè)整數(shù)捷雕，然后執(zhí)行加1操作
例子：
輸入: [1,2,3] 輸出: [1,2,4]
輸入: [9,9,9] 輸出: [1,0,0,0]
我的方法是直接在數(shù)組里面執(zhí)行操作，當(dāng)然你也可以換種方法壹甥，如把數(shù)組里元素按位讀出來(lái)變成int救巷，然后加一，然后在按位存放到數(shù)組中句柠。
def plusOne(digits: list) -> list:
digits = [0] + digits
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
break
return (digits, digits[1:])[0 if digits[0] != 0 else 1]
if __name__ == '__main__':
ans = plusOne([1, 2, 8, 4, 5, 6])
print(ans)
問(wèn)題3：對(duì)角線遍歷二維數(shù)組(Diagonal Traverse)浦译。
一維數(shù)組一般都很簡(jiǎn)單，但是到了二維數(shù)組溯职，難度就會(huì)上升一個(gè)臺(tái)階精盅，畢竟，問(wèn)題的花樣變多了嘛~
輸入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
輸出: [1,2,4,7,5,3,6,8,9]
如果看不懂的話谜酒，可以配上下面這張圖看叹俏，保證一眼就明白~
代碼具體思路分為兩步：
step1：根據(jù)對(duì)角線將矩陣分組（可以發(fā)現(xiàn)，同一對(duì)角線的矩陣row和col坐標(biāo)相加為定值）僻族，如上圖粘驰，可以分為5組，得到[1] , [2,4]鹰贵，[3,5,7]晴氨，[6,8]，[9]碉输。
step2：按照（row + col）的大小順序?qū)?shù)據(jù)依次添加到結(jié)果列表當(dāng)中籽前。根據(jù)代碼定義，在（row + col ）為偶數(shù)時(shí)敷钾，需要翻轉(zhuǎn)一下該組元素枝哄。即[3,5,7]（此時(shí)row + col = 2）需要變?yōu)閇7,5,3]再添加到結(jié)果中。
import collections
def findDiagonalOrder(matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
result = []
dd = collections.defaultdict(list)
if not matrix: return result
# Step 1: Numbers are grouped by the diagonals.
# Numbers in same diagonal have same value of row+col
for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
dd[i + j].append(matrix[i][j]) # starting indices from 1, hence i+j+1.
# Step 2: Place diagonals in the result list.
# But remember to reverse numbers in odd diagonals.
for k in sorted(dd.keys()):
if k % 2 == 0: dd[k].reverse()
result += dd[k]
return result
if __name__ == '__main__':
arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
ans = findDiagonalOrder(arr)
print(ans)
問(wèn)題4：旋轉(zhuǎn)矩陣（Spiral Matrix）阻荒，即返回一個(gè)矩陣順時(shí)針旋轉(zhuǎn)的結(jié)果挠锥。
輸入：
[ [ 1, 2, 3 ],
?[ 4, 5, 6 ],
?[ 7, 8, 9 ] ]
輸出：[1,2,3,6,9,8,7,4,5]
下面這個(gè)答案是我在網(wǎng)上找的，看到這個(gè)代碼之后的好久時(shí)間里侨赡，我的嘴巴只能發(fā)出“wo cao”這兩個(gè)音蓖租。。羊壹”突拢看到這段代碼，我仿佛戀愛(ài)了油猫。
def spiralOrder(matrix: list) -> list:
return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1])
if __name__ == '__main__':
arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
ans = spiralOrder(arr)
print(ans)
問(wèn)題5：數(shù)組求和稠茂。給定一個(gè)升序排列的數(shù)組，找出兩個(gè)數(shù)情妖，其和等于輸入‘target’睬关，結(jié)果返回這兩個(gè)數(shù)的索引诱担。
輸入: numbers = [2,7,11,15], target = 9
輸出: [1,2]
我們?nèi)绻褂帽┝Ψǖ脑挘Y(jié)果有種电爹，時(shí)間復(fù)雜度為
蔫仙。那么大家還記不記得
有一招從天而降的掌法... 上一章講解的雙指針技術(shù)呢？這里便用到了藐不！兩個(gè)指針?lè)謩e從左和右開始向中間走匀哄，兩個(gè)數(shù)的和大了，右指針左移雏蛮，和偏小涎嚼，左指針右移......
# 四個(gè)問(wèn)題不吉利，小編拍胸脯保證挑秉，馬上（百年之內(nèi)）把第五個(gè)問(wèn)題補(bǔ)起來(lái)法梯！
def twoSum(numbers: list, target: int) -> list:
i, j = 0, len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] == target:
return [i, j]
elif numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return []
if __name__ == '__main__':
numbers = [2, 7, 11, 15]
target = 9
ans = twoSum(numbers,target)
print(ans)
問(wèn)題6：移除特定值（寫五道已經(jīng)達(dá)到我的標(biāo)準(zhǔn)了，奈何又看到一個(gè)較為經(jīng)典的案例犀概，那就......再來(lái)個(gè)雙指針教學(xué)吧~）立哑，將數(shù)組當(dāng)中等于’target'的值移除掉，空間復(fù)雜度限定為姻灶，最后結(jié)果返回新數(shù)組長(zhǎng)度铛绰。
例子：
輸入：[1,2,7,4,4,5],target = 4
輸出：4 （新數(shù)組為[1,2,7,5]，所以長(zhǎng)度為4）
快指針遍歷數(shù)組产喉，慢指針則作為新數(shù)組的尾部捂掰。只有當(dāng)快指針?biāo)傅闹岛汀畉arget’不同時(shí)，才會(huì)執(zhí)行賦值以及p+=1操作曾沈，相同時(shí)直接跳過(guò)該數(shù)这嚣。
def removeElement(numbers: list, target: int) -> int:
p = 0
for i in range(len(numbers)):
if numbers[i] != target:
numbers[p] = numbers[i]
p +=1
return p
if __name__ == '__main__':
numbers = [1,7,3,4,4,5]
target = 4
ans = removeElement(numbers,target)
print(ans)
print(numbers[:ans])
問(wèn)題7:滿足要求的最小子數(shù)組(Minimum Size Subarray Sum)。不好意思我忍不住又添了一道......該題給定n只包含正整數(shù)的數(shù)組塞俱，以及一個(gè)整數(shù)s姐帚，要求是找到一個(gè)最小長(zhǎng)度的連續(xù)子數(shù)組，該子數(shù)組的元素和≥s障涯。 如果不存在罐旗，則返回0。
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2（子數(shù)組 [4,3] 是滿足題目約束的最小數(shù)組）
運(yùn)行下面程序會(huì)輸出每步變量信息唯蝶，大家可以自己讀讀試試尤莺，看能否理解~如果不理解可以留言探討，現(xiàn)在已經(jīng)晚上11點(diǎn)了生棍，小編扛不住，這道題就不寫分析了......
def minSubArrayLen( s: int, nums: list) -> int:
total = left = 0
result = len(nums) + 1
for right, num in enumerate(nums):
total += num
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
print('total:',total,'result:',result,'left:',left,'right:',right)
return result if result <= len(nums) else 0
if __name__ == '__main__':
numbers = [2,3,1,2,4,3]
target = 7
ans = minSubArrayLen(target,numbers)
print(ans)
