Leetcode【392、870、881、1090】
Leetcode【392、870、881、1090】
问题描述：【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腾讯云开发者
