問題描述：【Greedy】392. Is Subsequence
解題思路：
這道題是給兩個字元串 s 和 t，判斷 s 是否是 t 的子序列。
簡單題。雙指針 i 和 j 分别指向 t 和 s，對于 t 的每一個位置周遊，如果 t[i] 和 s[j] 相同，那麼 j 也想後移動找下一個相同的字元。當 j 達到 s 的長度，傳回 True，否則 s 不是 t 的子序列，傳回 False。
時間複雜度為 O(n)，空間複雜度為 O(1)。
Python3 實作：
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if s == "":
return True
i = j = 0
for i in range(len(t)):
if t[i] == s[j]:
j += 1
if j == len(s):
return True
return False 複制
問題描述：【Greedy】870. Advantage Shuffle
解題思路：
這道題是給兩個大小相等的數組 A 和 B，A 相對于 B 的優勢可以用滿足 A[i] > B[i] 的索引 i 的數目來描述。傳回 A 的任意排列，使其相對于 B 的優勢最大化。
這道題使用貪婪的思想，即對 A 和 B 都先進行升序排列，用 A 的最小值去滿足 B 的最小值，如果不能滿足，就讓 A 的最小值去滿足 B 的最大值。是不是有種“田忌賽馬”的感覺？哈哈哈~
時間複雜度來自于排序花銷的 O(n*logn)，空間複雜度為 O(n)，用來儲存結果。
Python3 實作：
class Solution:
def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
N = len(A)
A.sort()
B = sorted(zip(B, range(N))) # 同時記錄B的索引，便于構造結果
ans = [0] * N
i, j = 0, N-1 # i指向B的最小值，j指向B的最大值
for a in A:
if a > B[i][0]: # 用A的較小值滿足B的較小值
ans[B[i][1]] = a
i += 1
else: # 否則，就讓A的較小值滿足B的較大值
ans[B[j][1]] = a
j -= 1
return ans 複制
問題描述：【Two Pointers】881. Boats to Save People
解題思路：
救生艇問題。給一個重量數組和船容量，一次隻能運輸兩個人，求所需最少船數。
這道題屬于裝箱問題 貪心算法 之 裝箱問題，使用貪婪的思想先滿足最重的人上船，是以要對數組進行降序排序。
因為這道題中，一艘船最多隻能搭載兩個人，是以讓最重的捎上一個最輕的，這樣做的原因是如果最輕的人可以與任何人配對，那麼就讓他與最重的人配對（貪心）。如果兩個人超過 limit，那麼最重的人單獨上船。是以，我們還需要使用雙指針分别指向數組兩端最重和最輕的人往中間滑動，就能得到所需的最少船數。
Python3 實作：
class Solution:
def numRescueBoats(self, people: List[int], limit: int) -> int:
people.sort(reverse=True) # 按重量降序排序
ans = 0
low, high = 0, len(people) - 1 # low指向最重的，high指向最輕的
while low <= high:
if people[low] + people[high] <= limit: # 最重的捎上最輕的
low += 1
high -= 1
else: # 最重的單獨上船
low += 1
ans += 1 # 每次船數加1
return ans 複制
問題描述：【Sort、Heap】1090. Largest Values From Labels
解題思路：
這道題是給兩個對應的數組 values 和 labels，從 values 中選一個子集 S 滿足 |S| <= num_wanted，并且子集 S 中各個标簽的數目總滿足 <= use_limit，求傳回子集 S 的最大可能的和。
方法1（Sort）：
要得到最大可能的子集和，很明顯要對 values 按照降序排列（labels 也要對應 values 的值參與排序），先挑最大的數字裝入子集 S 中（貪心）。
對于排序後的每個 values[i]，依次加入到 S 中，并且用一個字典記錄 values[i] 的标簽 labels[i] 出現的次數，如果滿足限制兩個限制條件，則 num_wanted 減小 1，該标簽次數加 1，同時累加和。如果 num_wanted 減為 0，直接傳回累加結果即為答案。否則，周遊完 values 後，傳回累加的答案即可。
時間複雜度為 O(n*logn)，空間複雜度為 O(n)。
Python3 實作：
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
comb = sorted(zip(values, labels), reverse=True) # 按照values降序排列
ans = 0
label_dic = collections.defaultdict(int) # 記錄各個标簽次數
for c in comb:
if num_wanted == 0:
return ans
if label_dic[c[1]] < use_limit: # 标簽次數沒有超過use_limit
ans += c[0]
label_dic[c[1]] += 1
num_wanted -= 1
return ans 複制
方法2（Heap）：
實際上，我們也可以使用 Heap 排序，根據 values[i] 的負值建立小根堆，即 (-values[i], labels[i])。每次從堆頂彈出一個元素，按照上述方法判斷即可。時間複雜度和空間複雜度同上。
Python3 實作：
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], num_wanted: int, use_limit: int) -> int:
heap = []
for i in range(len(values)):
heapq.heappush(heap, (-values[i], labels[i])) # values[i]的負值建立小根堆
ans = 0
labels_dic = collections.defaultdict(int) # 記錄各個标簽次數
while len(heap):
v, l = heapq.heappop(heap)
if labels_dic[l] < use_limit: # 标簽次數沒有超過use_limit
ans += (-v)
labels_dic[l] += 1
num_wanted -= 1
if num_wanted == 0:
return ans
return ans 複制