演算法刷題之三一維列表
列表
列表和字元串是演算法中最常見的數據結構，在列表中又分為一維列表和二維列表。一維列表的數據結構即使很簡單也會有很多複雜的演算法思想。
一維列表
- 刪除排序數組中的重複項
- 移動非0元素到頭部
- 盛最多水的容器
- 三數之和
- 長度最小的子數組
- 無重複字元的最長子串
- 前綴和
- 合併區間
二維列表
- 二維矩陣最大子矩陣和
- 旋轉影像
- 楊輝三角
- 對角線遍歷
- 矩陣元素查找
- 容器盛水
刪除排序數組中的重複項
題目：
給定一個排序數組，你需要在 原地 刪除重複出現的元素，使得每個元素只出現一次，返回移除後數組的新長度。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 並在使用 O(1) 額外空間的條件下完成。
鏈接：//leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
方法：只要將不同的數字全部集中到前面就可以了。設置雙指針，慢指針用來指向列表前部分里不重複的下標，快指針向後遍歷找不重複的數字。找到一個就讓慢指針加1，然後將快指針指向的不重複的值賦值給慢指針。
雙指針：一種常用的，好用的數據處理方式。在快速排序中，將一個數組分成大小兩個部分，用的就是雙指針。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
#時間複雜度為O(n),空間O(1)
# 慢指針
i = 1
# 快指針
for j in range(1, len(nums)):
if nums[j] != nums[j - 1]:
nums[i] = nums[j]
i += 1
nums[:] = nums[:i]
return
地道的寫法：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
return i + 1
移動非0元素到頭部
題目：
給定一個數組 nums，編寫一個函數將所有 0 移動到數組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:
必須在原數組上操作，不能拷貝額外的數組。
盡量減少操作次數。
鏈接：//leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2ba4i/
方法：將0全部集中到列表尾部，換一個思路就是將所有非0保持順序，移動到列表前部。和上一題思想類似，使用雙指針，慢指針指向0的下標，快指針向後尋找數值不為0的元素，交換快慢指針的數值，將所有0全部移動到尾部
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 慢指針
i = 0
# 快指針
j = 0
while j < len(nums):
# 不等於快慢指針交換，慢指針遇到0時會停下來，等待快指針指向非0時的交換
if nums[j] != 0:
nums[i],nums[j] = nums[j],nums[i]
i += 1
j += 1
思想：j遇到0元素不管，i遇到0元素停下。當j再遇到0元素時，和i的元素互相交換，最終完成將非零元素向前移動的目的
def func(arr):
i = 0
length = len(arr)
for j in range(len(arr)):
if arr[j] != 0:
arr[i],arr[j] = arr[j],arr[i]
i = i + 1
arr = [0,1,0,3,12]
func(arr)
print(arr)
盛最多水的容器
提示：
給你 n 個非負整數 a1，a2，…，an，每個數代表坐標中的一個點 (i, ai) 。在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
說明：你不能傾斜容器。
鏈接：//leetcode-cn.com/problems/container-with-most-water
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
方法：
首先想到的是暴力解法，兩層循環能夠找到任意兩個柱子之間的距離，乘以高度，取最大值即可。時間複雜度為O(2),
然後使用雙指針也能解決這個問題。以左右兩邊為邊界向中間進發，比較兩個柱子中較小的一個，並向中間移動，一直到兩個柱子相遇。在這個過程中能夠找到面積最大的那一對。
class Solution:
def maxArea(self, height: List[int]) -> int:
if not height:
return 0
n = len(height)
max_ares = 0
l = 0
r = n - 1
while l < r:
max_ares = max(max_ares, min(height[l], height[r]) * (r-l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return max_ares
三數之和
題目：
給一個數組[4,2,6,7,4,6]，找到其中三個數的和為14的所有組合
方法：
三數之和是使用雙指針完成遍歷，固定住第一個，然後使用雙指針一頭一尾向中間逼近
因為我們要同時找三個數，所以採取固定一個數，同時用雙指針來查找另外兩個數的方式。所以初始化時，我們選擇固定第一個元素（當然，這一輪走完了，這個藍框框我們就要也往前移動），同時將下一個元素和末尾元素分別設上 left 和 right 指針。畫出圖來就是下面這個樣子：
當三個數的和大於0時，表明right需要左移以減少和，當小於0時，left需要右移，以增大和。
知識點： 雙指針配合循環
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
length = len(nums)
arr = []
nums.sort()
for i in range(length - 2):
if nums[i] > 0:
continue
if i > 0 and nums[i] == nums[i-1]:
continue
L = i + 1
R = length - 1
while L < R:
s = nums[i] + nums[L] + nums[R]
if s == 0:
arr.append([nums[i],nums[L],nums[R]])
L += 1
R -= 1
while L < R and nums[L] == nums[L-1]:L += 1
while L < R and nums[R] == nums[R+1]:R -= 1
elif s > 0:
R -= 1
while L < R and nums[R] == nums[R+1]:R -= 1
else:
L += 1
while L < R and nums[L] == nums[L-1]:L += 1
return arr
雙指針小結
以上題目能力體現雙指針的使用技巧，通常使用雙指針，可以用在如下場景中：
- 從兩端向中間迭代數組。
這時你可以使用雙指針技巧：一個指針從頭部開始，而另一個指針從尾部開始。這種技巧經常在排序數組中使用。
- 同時有一個慢指針和一個快指針。
確定兩個指針的移動策略。與前一個場景類似，你有時可能需要在使用雙指針技巧之前對數組進行排序，也可能需要運用貪心法則來決定你的運動策略。
長度最小的子數組
題目：
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的 連續 子數組，並返回其長度。如果不存在符合條件的子數組，返回 0。
示例：
輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。
方法：使用滑動窗戶能夠完美解決這個問題。窗口右端加入元素，判斷窗口中元素總和是否大於target，如果大於計算長度，然後再左端縮小窗口，元素總和小於target，這是右端會繼續向下滑動。
知識點：變長滑動窗口
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
left = 0
res = float("inf")
cur = 0
for right in range(len(nums)):
cur += nums[right]
while cur >= s:
print('cur：%d -left: %d' % (cur,nums[left]))
res = min(res, right-left+1)
cur = cur - nums[left]
left += 1
if res != float("inf"):
return res
else:
return 0
無重複字元的最長子串
題目：
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
示例 1:
輸入: “abcabcbb”
輸出: 3
解釋: 因為無重複字元的最長子串是 “abc”，所以其長度為 3。
示例 2:
輸入: “bbbbb”
輸出: 1
解釋: 因為無重複字元的最長子串是 “b”，所以其長度為 1。
示例 3:
輸入: “pwwkew”
輸出: 3
解釋: 因為無重複字元的最長子串是 “wke”，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，”pwke” 是一個子序列，不是子串。
方法：判斷一個子數組中是否有重複有很多種辦法：
- 使用暴力雙層遍歷
- 使用字典，判斷某元素是否在字典中
- 使用數組，判斷元素是否在數組中
方法：使用滑動窗解決：窗口左側不斷加入元素，判斷元素是否存在於窗口中，不在則繼續加入，在則將重複的元素去掉，繼續添加。在這個過程中會有一個最大值出現。
知識點： 變長滑動窗口
class Solution(object):
def lengthOfLongestSubstring(self, s: str) -> int:
# 字元串為空則返回零
if not s:
return 0
window = [] # 滑動窗口數組
max_length = 0 # 最長串長度
# 遍歷字元串
for c in s:
# 如果字元不在滑動窗口中，則直接擴展窗口
if c not in window:
# 使用當前字元擴展窗口
window.append(c)
# 如果字元在滑動窗口中，則
# 1. 從窗口中移除重複字元及之前的字元串部分
# 2. 再擴展窗口
else:
# 從窗口中移除重複字元及之前的字元串部分，新字元串即為無重複字元的字元串
window[:] = window[window.index(c) + 1:]
# 擴展窗口
window.append(c)
# 更新最大長度
max_length = max(len(window), max_length)
return max_length if max_length != 0 else len(s)
這一道題目還有更精彩的解法，滑動窗口不是只能用列表實現，還可以用字元串，雙指針，字典等實現。
//leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/python-hua-dong-chuang-kou-xun-xu-jian-jin-de-3ge-/
滑動窗口小結：
滑動窗口顧名思義就是對於序列取一段子序列，通常就是有一個大小可變的窗口，左右兩端方向一致的向前滑動，右端固定，左端滑動；左端固定，右端滑動。
可以想像成隊列，一端在push元素，另一端在pop元素，如下所示：
假設有數組[a b c d e f g h]
一個大小為3的滑動窗口在其上滑動，則有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
適用範圍
1、一般是字元串或者列表
2、一般是要求最值（最大長度，最短長度等等）或者子序列
演算法思想
1、在序列中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引閉區間 [left, right] 稱為一個窗口。
2、先不斷地增加 right 指針擴大窗口 [left, right]，直到窗口中的序列符合要求。
3、此時，停止增加 right，轉而不斷增加 left 指針縮小窗口 [left, right]，直到窗口中的序列不再符合要求。同時，每次增加 left前，都要更新一輪結果。
4、重複第 2 和第 3 步，直到 right 到達序列的盡頭。
思路其實很簡單：第 2 步相當於在尋找一個可行解，然後第 3 步在優化這個可行解，最終找到最優解。左右指針輪流前進，窗口大小增增減減，窗口不斷向右滑動。
前綴和
給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。
示例 1 :
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。
輸入：nums = [1,3,7,2,8]
輸出：2，, [3,7] [2,8]
方法：
想要獲取列表中一段子列表，使用雙層循環就可以做到。能夠獲取到任意一段子列表，然後再將這一段nums[1:j]列表的和求解出來，這樣時間複雜度會很高是O3，所以使用前綴和每一次內層循環時能夠直接算出nums[i:j]的值。
知識點：前綴和
def subarraySum(self, nums: List[int], k: int) -> int:
num_times = 0
for i in range(len(nums)):
presum = 0
for j in range(i,len(nums)):
presum += nums[j]
if presum == k:
num_times += 1
return num_times
其中的presum += nums[j]就是前綴和，每次內層循環的和都記錄下來，避免了計算nums[i:j]
但這種方式還不是最優，時間複雜度為O2，如果想要將時間複雜度降低到O，還需要使用字典這種方式。類似的解法是兩數之和
使用一個字典維護前綴和與其出現的次數。
前3項的和為11，k=11。第一項和+sum(3,7) = sum(1,3,7),即sum(1) + 10 = sum(1,3,7),如果存在子數組sum=10，那麼sum(1,3,7) – 10 就等於sum(1)。
即：sum(n) – k 在字典中，那麼就說明有一個子數組=k
將兩個數相加等於固定值，變成使用固定值-其中一個數=差值，判斷差值在不在列表中
def subarraySum(self, nums: List[int], k: int) -> int:
sum_dict = {0:1}
pre_sum = 0
num_times = 0
for i in range(len(nums)):
pre_sum += nums[i]
if pre_sum - k in sum_dict:
num_times += sum_dict[pre_sum-k]
if pre_sum in sum_dict:
sum_dict[pre_sum] += 1
else:
sum_dict[pre_sum] = 1
return num_times
合併區間
題目：
給出一組區間，請合併所有重疊的區間。
請保證合併後的區間按區間起點升序排列。
示例1
複製
[[10,30],[20,60],[80,100],[150,180]]
返回值
[[10,60],[80,100],[150,180]]
方法：區間問題兩邊都是極限，解決這一類問題需要固定住一端，然後對另一端判斷並處理
知識點：區間處理思想
class Solution:
def merge(self , intervals ):
if not intervals:
return []
intervals.sort(key=lambda x: x.start)
res = [intervals[0]]
for i in intervals[1:]:
if res[-1].end < i.start:
res.append(i)
elif res[-1].end <= i.end:
res[-1].end = i.end
return res
一維列表小結
對於一維列表的演算法求解有很多中技巧，像上面提到的雙指針，滑動窗口等。在這些技巧之下，需要對一維列表的最基礎操作有深刻認識，那就是循環。下面來總結一下一維列表的循環有什麼需要掌握的。
單層循環：單層循環能取到列表中每一個值，這沒什麼特別的。
arr = [5,2,9,6,10,6]
for i in range(len(arr)):
print(arr[i])
5 2 9 6 10 6
雙層循環：雙層循環能對列表任意兩個元素操作，比如兩個元素之和，兩個元素之積，甚至是兩個元素中間元素的和。
arr = [5,2,9,6]
length = len(arr)
for i in range(length):
for j in range(i, length):
print('{}--{}'.format(arr[i], arr[j]))
5–5
5–2
5–9
5–6
2–2
2–9
2–6
9–9
9–6
6–6
雙層循環使用的比較多，記住一點，雙層循環能獲取任意兩個元素的組合。在這個最基礎的操作之上再去看到一些技巧，技巧是對最基礎解法的優化，所以對於一道題如果知道套路就上套路，不知道套路先用最暴力的解法，然後再往套路上靠。
