最近有些浮躁,所以我决定从现在开始,就一件事我要坚持到底的去做。5月份就是:

  1. 将 LeetCode 上的算法题每种类型都做明白
  2. 减肥健身,天天坚持
  3. 不玩游戏

分发饼干

假设在某次选择中,贪心策略选择给第 i 个孩子分配第 m 个饼干,并且第 i 个孩子满足度最小,第 m 个饼干为可以满足第 i 个孩子的最小饼干。假设最优策略在这次选择中给 i 个孩子分配第 n 个饼干,并且这个饼干大于第 m 个饼干。我们发现使用第 m 个饼干去替代第 n 个饼干完全不影响后续的结果,因此不存在比贪心策略更优的策略,即贪心策略就是最优策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
g.sort()
s.sort()
gindex = sindex = 0
while gindex < len(g) and sindex < len(s):
if g[gindex] <= s[sindex]:
gindex += 1
sindex += 1
return gindex

买卖股票的最佳时机 II

对于 [a, b, c, d],如果有 a <= b <= c <= d ,那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ,因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0,那么就把 prices[i] - prices[i-1] 添加到收益中,从而在局部最优的情况下也保证全局最优。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
ans = 0
for idx, p in enumerate(prices[1:], 1):
if prices[idx] > prices[idx-1]:
ans += (prices[idx]-prices[idx-1])
return ans

判断子序列

贪心算法的思想,通过判断s中每一个字符串在t中是否会出现,若出现,继续下一个字符,并且将t中的指针后移,再进行判断,否则返回False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
tidx = 0
for sitem in s:
tidx = t.find(sitem, tidx)
if tidx == -1:
return False
else:
tidx += 1
return True

用最少数量的箭引爆气球

按照最后的位置排序,然后进行判断是否刺破,最后得到最少的箭的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def findMinArrowShots(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if not points:
return 0
points = sorted(points, key=lambda x: x[1])
cur_pos = points[0][1]
shot = 1
for idx, point in enumerate(points):
if idx == 0:
continue
if point[0] <= cur_pos:
continue
else:
cur_pos = point[1]
shot += 1
return shot

划分字母区间

同样,首先要理解题目,要将字符串划分为尽可能多的片段,那么首先要知道同一个字母最后出现的位置,有了这个就能确定一个子串会在哪个地方停止,比如 ababc 其中 a 最后一次出现的位置是 2,那么子串至少长度是3,但是继续遍历这个子串时候发现 b 最后一次出现的位置是3,因此子串就需要更新,长度至少为4,继续遍历剩下的a,b,不需要更新,因此就可以将字符串分为 abab 和 c

这就是一种贪心算法,只要满足当前字母的最后一次出现的位置即可,不断更新最优解,最后得到整体解

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
# 找到每个字母最后一次出现的位置
last_indexes = {}
for index, ele in enumerate(S):
last_indexes[ele] = index
ret = []
first_index = 0
while first_index < len(S):
# 确定每个子串真正的last_index
idx = last_index = first_index
# 遍历每个字母,可以找到这个字母的最后一次出现的位置,idx开始就是first_index的位置
# 也就是说遍历这么长的子串,并且不断的动态更新真正最后的位置
while idx < len(S) and idx <= last_index:
dynamic_last_indexes = last_indexes[S[idx]]
if dynamic_last_indexes > last_index:
last_index = dynamic_last_indexes
idx += 1
# 遍历完成之后,就找到了一个子串,其结尾位置就是last_index
ret.append(last_index - first_index + 1)
first_index = last_index + 1
return ret

根据身高重建队列

这道题主要理解了要在h相同的情况下先插入身高高的元素,这样身高矮的元素就是正确的位置,否则身高矮的元素就会被挤到后面,从而错误。

按照身高降序,然后h升序,这样h就是它应该被插入的位置了。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reconstructQueue(self, people):
"""
:type people: List[List[int]]
:rtype: List[List[int]]
"""
# 按照身高降序,h升序的方式进行,然后按照h插入,先插大的
people.sort(key=lambda x: (-x[0], x[1]))
ret = []
for p in people:
ret.insert(p[1], p)
return ret

任务调度器

对tasks按照任务进行计数,记数目最多的任务为t,其个数为tmax

问题转化为在tmax个任务之间的“槽”内尽可能安插别的任务,使idle最小化

例如输入tasks = ['A' * 5, 'B' * 5, 'C' * 4, 'D' * 2, 'E' * 1], n = 5

本例中,数目最多的任务t为’A’,其个数tmax = 5

A o o o o o A o o o o o A o o o o o A o o o o o A x x x x x

标记为‘o’的部分需要填充任务或者idle,‘o’安排完毕后,剩余任务放置在标记为‘x’的部分

调度结果如下,答案为26:

A B C D E i A B C D i i A B C i i i A B C i i i A B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def leastInterval(self, tasks, n):
"""
:type tasks: List[str]
:type n: int
:rtype: int
"""
# 找到最多的那个任务,其他就是往这个任务中间填其他任务或者idle
# 最后时间是所有任务的长度加上idle的时间
cnt = collections.Counter(tasks)
tmax = max(cnt.values())
slots = (tmax - 1) * n
tsum = len(tasks)
print(cnt.values())
# 这里 n - (n == tmax) 是存在几个相同个数task的时候,这些任务会排在后面,而不会产生idle
# 所以就是总长度排除掉最后面的任务,减去运行的任务,就是idle的长度
return tsum + max(0, slots + tmax - 1 - sum(n - (n == tmax) for n in cnt.values()))