標籤：

慢學演算法 / Leetcode (Python3) - 第四周

03-12

這周開始加大強度，開始想針對一些演算法專題來進行整理了。直到今天也堅持了這個專欄一個月了，已經感覺到了明顯的提升，雖說是慢學，但也盡量多的去挖掘多種解法和多面的思考，還是有收穫的。這周是2道有難度的DP題，一些簡單的字元串問題，和K-sum問題的總結（從2sum，3sum，4sum到通用解法）。代碼基於Python3書寫，結果可以直接運行在Leetcode平台上，解法也同步更新到個人博客中Leetcode刷題記錄。

四周，一個月的刷題歷程??

Leetcode-763 Partition Labels 分割字元 Link

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1: Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8]

Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

這題有點懵逼的，一開始沒什麼思路，然後大致讀懂了題意之後，腦子裡又變得很亂，各種時間複雜度很高的演算法都涌了出來，其實都沒什麼用。然後看到了這個題屬於雙指針和貪心，似乎給了我一點提示。藉助一個字典來存儲每個字母最後出現的索引，採用start和end雙指針切割的思想，一旦end指針達到切割點便將數組切割，然後更新start節點以便下一次循環遍歷得到。代碼如下

import collections
class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
last_pos = {}
for idx, item in enumerate(list(S)):
last_pos[item] = idx

res = []
start, end = 0, 0

for index, item in enumerate(S):
if last_pos[item] > end:
end = last_pos[item]
# 到達切割點
if index == end:
res.append(end - start + 1)
start = end + 1
return res

這題復盤的時候，我在想怎麼自己第一遍就不會想到這個思路呢，這題的關鍵無非就是了解題意之後。自己之前想用count來直接計數，然後發現邊界條件很難寫好，語句也不是很容易讀，多了很多ifelse判斷，但是用雙指針以擴充範圍的思想來看，就立馬寫的很順了。

Leetcode-232 Implement Queue using Stacks 用堆棧實現隊列 Link

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);

queue.push(2);

queue.peek(); // returns 1

queue.pop(); // returns 1

queue.empty(); // returns false

這是一道用棧來實現隊列的問題，作為兩種比較基本的數據結構，棧的特性是後進先出（LIFO），隊列的特性是先進先出（FIFO）。因此這道題要實現的操作中，主要就是要實現push和pop不同數據結構之間的操作轉化。

這裡區別最大的一點就是push操作，堆棧只能放在頂部，因此pop時會出錯，於是我們需要將push的元素放到頭部，這樣就和隊列的數據結構保持一致了。這裡藉助另一個數組來實現這個功能，參考圖：

代碼：

class MyQueue:
def __init__(self):
self.s1 = []
self.s2 = []

def push(self, x):
while self.s1:
self.s2.append(self.s1.pop())
self.s1.append(x)
while self.s2:
self.s1.append(self.s2.pop())

def pop(self):
return self.s1.pop()

def peek(self):
return self.s1[-1]

def empty(self):
return not self.s1

Leetcode-975 Odd Even Jump 奇偶跳 Link

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way: During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j. During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j. (It may be the case that for some index i, there are no legal jumps.) A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

作死做了一道這麼難的題，題目我都懶得摘下來了，太長了，有點 ACM的感覺。最近發現其實難題之所以難，一般是結合了2個以上的知識點，也可以說是一道題考察多個方面，代碼層面也需要構建多個模塊。我這裡參考了花花醬的視頻講解 Link。

給定一個整數數組 A，你可以從某一起始索引出發，跳躍一定次數。在你跳躍的過程中，第 1、3、5… 次跳躍稱為奇數跳躍，而第 2、4、6… 次跳躍稱為偶數跳躍。

你可以按以下方式從索引 i 向後跳轉到索引 j（其中 i < j）：

在進行奇數跳躍時（如，第 1，3，5… 次跳躍），你將會跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。

如果存在多個這樣的索引 j，你只能跳到滿足要求的最小索引 j 上。 在進行偶數跳躍時（如，第 2，4，6… 次跳躍），你將會跳到索引 j，使得 A[i] => A[j]，A[j] 是可能的最大值。如果存在多個這樣的索引 j，你只能跳到滿足要求的最小索引 j 上。 （對於某些索引 i，可能無法進行合乎要求的跳躍。） 如果從某一索引開始跳躍一定次數（可能是 0 次或多次），就可以到達數組的末尾（索引 A.length - 1），那麼該索引就會被認為是好的起始索引。

輸入：[2,3,1,1,4]

輸出：3

解釋： 從起始索引 i=0 出發，我們依次可以跳到 i = 1，i = 2，i = 3：

在我們的第一次跳躍（奇數）中，我們先跳到 i = 1，因為 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大於或等於 A[0] 的最小值。 在我們的第二次跳躍（偶數）中，我們從 i = 1 跳到 i = 2，因為 A[2] 是（A[2]，A[3]，A[4]）中小於或等於 A[1] 的最大值。A[3] 也是最大的值，但 2 是一個較小的索引，所以我們只能跳到 i = 2，而不能跳到 i = 3。

在我們的第三次跳躍（奇數）中，我們從 i = 2 跳到 i = 3，因為 A[3] 是（A[3]，A[4]）中大於或等於 A[2] 的最小值。 我們不能從 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。 類似地，我們可以推斷： 從起始索引 i = 1 出發， 我們跳到 i = 4，這樣我們就到達數組末尾。 從起始索引 i = 2 出發， 我們跳到 i = 3，然後我們就不能再跳了。 從起始索引 i = 3 出發， 我們跳到 i = 4，這樣我們就到達數組末尾。 從起始索引 i = 4 出發，我們已經到達數組末尾。 總之，我們可以從 3 個不同的起始索引（i = 1, i = 3, i = 4）出發，通過一定數量的跳躍到達數組末尾。

這道題，第一步重在列出遞推公式。我們從後向前遍歷： 如果第i個節點可以上升跳到隊尾，那麼只要前序的節點j能下降跳到i節點就算是成功True。 如果第i個節點可以下降跳到隊尾，那麼只要前序的節點j能上升跳到i節點就算是成功True。 所以遞推公式可以得到一個間隔的形式： $$odd[i] = even[j], even[i] = odd[j]$$

因為要反應出遞推的關係，所以我們加上另一個替代j的關係式： odd[i] = even[odd_next[i]] even[i] = odd[even_next[i]] 這裡的odd_next和even_next反應那個odd和even的跳躍尋找符合條件的關係。其實能想到現在這一步，不算太難，但是在尋找奇偶分別條件上卡了很久，我只能想到一般的掃描，寫的也不是很好看，說到底還是不熟。最後參考了大神的寫法，發現小技巧其實很多，從倒序用reserved，到負數排序滿足降序，再到用stack的退棧。最後，由於我們只能算odd的總和，因為每一個數都是從第一步開始跳算起的。 貼一下代碼：

class Solution:
def oddEvenJumps(self, A):
"""
:type A: List[int]
:rtype: int
"""
odd = [False] * len(A)
even = [False] * len(A)

# 最後一個元素一定是滿足的
odd[-1], even[-1] = True, True

oddNext = [None] * len(A)
evenNext = [None] * len(A)

# 用一個stack來存儲最優值（最大或者最小）
# 返回出對應原數組的index, stack也是裝的index
stack = []
for item, index in sorted([[item, index] for index, item in enumerate(A)]):
while stack and index > stack[-1]:
oddNext[stack.pop()] = index
stack.append(index)

stack = []
for item, index in sorted([[-item, index] for index, item in enumerate(A)]):
while stack and index > stack[-1]:
evenNext[stack.pop()] = index
stack.append(index)

for i in reversed(range(len(A) - 1)):
if oddNext[i] is not None:
odd[i] = even[oddNext[i]]
if evenNext[i] is not None:
even[i] = odd[evenNext[i]]
return sum(odd)

Leetcode-486 Predict the Winner 預測勝者 Link

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1: Input: [1, 5, 2]

Output: False

Explanation: Initially, player 1 can choose between 1 and 2. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. Hence, player 1 will never be the winner and you need to return False.

Example 2:

Input: [1, 5, 233, 7]

Output: True

Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233. Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

這道題，剛看有點沒有太get到題意，這道題是一道有點博弈論背景的minmax的題，我也是看了花花醬的講解有了一點認識。這裡不能直接去拿最優的解，而是要轉化成player1和player2的差來解決，因為題目只要求出player1可否勝利，因此，如果存在player1 - player2的差值大於0的話，就代表player1能成功。這裡有一個坑，就是兩個隊員都要去盡量拿最優的結果，而不是只是那存在的結果，換句話說就是不能作弊。我剛開始看這道題的時候，也在想比如[1, 5, 2]中player1拿2，player2拿1，player1再拿5，這樣player1也能贏。但是題設里有提到每個人都要盡量使得分數最大化。

既然兩個選手都是比較聰明的，那我們也聰明一點。在這裡的問題中，如果數字的個數是偶數個的化，player1一定可以贏，因為數字是可見的，player1有先手的優勢，因此他完全可以找到預先找到最大的值安排順序，換句話說就是他可以預知結果，比如[1, 5, 233, 7]，player1可以知道233是最大值，因此他可以預先讓自己能最終拿到這個數字，那麼他為了保證一定能拿到233，那麼他第一次就一定要拿1，這樣player2隻能從5和7中選擇，如此就可以順利成為贏家，其他偶數數字更大的情況也是一樣適用的。而奇數就會存在不確定性，這個不確定性和player1多拿的數字有關。同之前的例子，如果這裡數字變成了5個，那麼也就是說player1會多取一個數字，剩下4個數字先手是player2，所以player2在偶數個的情況下是絕對可以保證自己贏的，那麼player1到底能否最終成為贏家取決於，player1多取一個數字能否贏過偶數個情況下player2最優的情況。

這裡的遞推公式，可以寫成 $$ solve(nums) = max(nums[0] - solve(nums[1:]), nums[-1] - solve(nums[:-1])) $$

解釋一下，solve(nums)是每次最優的情況，而nums[0]和nums[-1]代表前一次取值的可能，而player1要贏，那麼最後的solve的結果一定要大於等於0，才能贏。採用記憶化遞歸的方式，代碼如下：

class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums)%2 == 0 or len(nums) == 1:
return True

cache = dict()

def solve(nums):

tnums = tuple(nums)
if tnums in cache:
return cache[tnums]
cache[tnums] = max(
nums[0] - solve(nums[1:]),
nums[-1] - solve(nums[:-1])
)
return cache[tnums]
return solve(nums) >= 0

這麼看代碼不難，但是這個思路很難獲得，也有用bottom-up做的，我沒太看懂。。。感覺也有點複雜，列表格數組，就是不太容易想，直觀是挺直觀的。有時間再研究。

Leetcode-551 Student Attendance Record I 學生出席率 Link

You are given a string representing an attendance record for a student. The record only contains the following three characters: A : Absent. L : Late. P : Present. A student could be rewarded if his attendance record doesnt contain more than one A (absent) or more than two continuous L (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1: Input: "PPALLP"

Output: True

Example 2: Input: "PPALLL"

Output: False

感覺是道送分題，隨便寫了一下就AC了，這裡需要注意的是缺席全局不能超過1次，遲到不能連續大於2次，直接就上代碼了，思路也都是比較平鋪直敘的。

class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
count_a = 0
count_l = 0
max_l = 0
for item in list(s):
if item == A:
count_a += 1
count_l = 0
elif item == L:
count_l += 1
if count_l > max_l: max_l = count_l
else:
count_l = 0
return count_a < 2 and count_l < 3

這裡可以稍微剪枝改進一下，在循環里一旦遇到缺席大於1次或者遲到連續達到3次的就直接輸出False，否則則為True，代碼如下：

class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
count_a = 0
count_l = 0
for item in list(s):
if item == A:
count_a += 1
if item == L:
count_l += 1
else: count_l = 0
if count_a > 1 or count_l > 2:
return False
return True

Leetcode-1 2SUM 2數求和 Link

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

哈哈哈，又做回了第一題，是想借這個機會把所有的k-sum類題目都過一遍，先從這個2sum開始。作為第一題實在是有點簡單，因為這裡要返回原數組的索引，所以用一個dict來保存數據，key為數字，value為索引，代碼如下：

class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mem = dict()

for index, item in enumerate(nums):
if item in mem:
return [mem[item], index]
else:
mem[target - item] = index

這裡是一個基本款，但是有一個適用於這裡sum問題所有的情況的就是雙指針，這裡也不例外，雖然是有點麻煩，但是還是很有必要寫一下的。

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
sn = sorted((num, i) for i, num in enumerate(nums))
i, j = 0, len(nums) - 1
print(sn)
while i < j:
n, k = sn[i]
m, l = sn[j]
if n + m < target:
i += 1
elif n + m > target:
j -= 1
else:
return [k, l]

這裡將原數組，轉化為(value, index)一個tuple類型。對這個tuple類型進行了排序，這樣既保留了原有的index和value，又排了順序。然後就是常規的步驟了，兩個指針各指向一頭，如果大於target就移動右指針，反之移動左指針。最近發現很多問題都有涉及對這個tuple的運用，真的是一個很高階的技能。

Leetcode-15 3SUM 3數求和 Link

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example: Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

和2Sum不同，這裡是返回滿足條件且不重複的結果，存儲在一個list of lists里，既然是3Sum問題就會涉及到3個指針 ε==(づ′▽`)づ，看來是幾sum就幾個指針啊。這裡比較棘手的是處理這個重複的問題，這裡一度讓我很頭大，不過看了一些大神的方法，大家似乎也都是差不多的解決方案，那麻煩就麻煩點吧，代碼如下：

class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
# 外層第1個指針
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
# 第2第3個指針從i往後開始
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
# 這裡判斷直到找到下一個不同於上一個的值
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1 # 這裡把最終移動放到最後
return res

這裡3個指針都需要去重，外層的i，去重判斷為nums[i] == nums[i-1]，內部的i和j，當滿足條件時，插入結果，立馬開始去重，直到找到下一個不重複的位置再繼續帶入while循環，直到 l==r 停止循環。

Leetcode-18 4SUM 4數求和 Link

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

4數求和啦，一路從2個做到4個，這裡也是一樣的意思，4數就是4個指針嘍（噗~(o?▽?)o）。一樣也是會遇到很噁心的重複問題，我這裡先自己丑陋的實現了一遍，思路是外層2個指針，內部做2SUM，去重我藉助了一個字典，因為重複的情況很多很複雜，所以藉助字典可以照顧到所有的情況，內外一旦發現重複，就啟動指針的移位，最後輸出結果中的每一個都先排了個序，再set去重，再轉成list輸出，哈哈哈，發現居然AC了。代碼如下：

class Solution:

def writeDict(self, mem, key, value):
print(value)
if key in mem:
mem[key].append(value)
else:
mem[key] = [value]

def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
mem = dict()
nums.sort()
res = []

for prior1_idx in range(len(nums)-2):
for prior2_idx in range(prior1_idx + 1, len(nums)-1):
sum_prior = nums[prior1_idx] + nums[prior2_idx]
prior = (nums[prior1_idx], nums[prior2_idx])

if sum_prior in mem and prior in mem[sum_prior]:
continue

sum_post = target - sum_prior
temp = nums.copy()
temp.remove(nums[prior1_idx])
temp.remove(nums[prior2_idx])
l, r = 0, len(temp) - 1
while l < r:
if temp[l] + temp[r] < sum_post:
l += 1
elif temp[l] + temp[r] > sum_post:
r -= 1
else:
post = (temp[l], temp[r])
if sum_post in mem and post in mem[sum_prior]:
l += 1
r -= 1
continue
else:
# 寫入字典
self.writeDict(mem, sum_prior, prior)
self.writeDict(mem, sum_post, post)
single = list(prior) + list(post)
single.sort()
res.append(single)
l += 1
r -= 1
return list(set(tuple(i) for i in res))

很長，很不好用，但是能過，好了不耍流氓了。看了一些大牛的解法，終於是時候推出普適的解法了。 先貼一下代碼：

class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
num.sort()
def ksum(num, k, target):
i = 0
result = set()
if k == 2:
j = len(num) - 1
while i < j:
if num[i] + num[j] == target:
result.add((num[i], num[j]))
i += 1
elif num[i] + num[j] > target:
j -= 1
else:
i += 1
else:
while i < len(num) - k + 1:
newtarget = target - num[i]
subresult = ksum(num[i+1:], k - 1, newtarget)
if subresult:
result = result | set( (num[i],) + nr for nr in subresult)
i += 1

return result

return [list(t) for t in ksum(num, 4, target)]

這是我看下來寫得比較清楚的一種，運用了遞歸，最小子問題就是一個普通的2sum雙指針解法，在else裡面，將外層的指針直到的數與target作差作為下一個k-1 sum的子任務目標值，進行遞歸求解。

result = result | set( (num[i],) + nr for nr in subresult)

這一行代碼是關鍵，(num[i],)是tuple特有的形式，將之後滿足的解灌入這個tuple中，外層用一個set包裹來達到去重的目的，因為雙指針是依賴於排過序的。最後用result|來對所有的set取並集得到一個set of tuples的結果。最終，再把結果轉化為list of lists就結束了。

這個辦法，我覺得可能可以記憶一下，尤其是遞歸的思想和對結果的轉化，真的不是短時間可以想到的，這裡的2個模板，一個是基本的2sum，一個是ksum的轉化，可以做一下記憶。(?′?`?)

不容易的一周，很多題都不是很容易，想上一點強度。還是要堅持！

推薦閱讀：

TAG:力扣（LeetCode） | 演算法 | Python |