算法工程师的日常
0%

贪心算法

发表于 更新于 分类于 ，

贪心算法

跳跃游戏[55]

1
2
3
4
5
6
7
8
9
class Solution:
    def canJump(self, nums):
        max_can_reach = 0
        for i in range(len(nums)): #注意
            if i <= max_can_reach:
                max_can_reach = max(nums[i] + i, max_can_reach)
                if max_can_reach >= len(nums) - 1:
                    return True
        return False

跳跃游戏II[45]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def jump(self, nums: List[int]) -> int:
        step = 0
        end = 0
        max_can_reach = 0
        for i in range(len(nums)-1):
            max_can_reach = max(nums[i]+i, max_can_reach)
            if i == end:
                end = max_can_reach
                step+=1
        return step
# 和上面一致
class Solution:
    def jump(self, nums: List[int]) -> int:
        step = 0
        end = 0
        max_can_reach = 0
        for i in range(len(nums)-1):#注意
            if i<= max_can_reach:
                max_can_reach = max(nums[i]+i, max_can_reach)
                if i == end:
                    end = max_can_reach
                    step+=1
        return step

摆动序列[376]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
            if len(nums)==1:
                return 1
            direction = None
            res = 0 
            for i in range(1, len(nums)):
                if nums[i] == nums[i-1]:
                    continue
                elif nums[i] > nums[i-1]:
                    if direction == 0:
                        continue
                    direction = 0
                    res += 1
                elif nums[i] < nums[i-1]:
                    if direction == 1:
                        continue
                    direction = 1
                    res += 1
            return res + 1

分发饼干[455]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 将胃口和饼干排序
        g.sort()
        s.sort()
        # 孩子的数量
        n = len(g)
        # 饼干的数量
        m = len(s)
        # 记录结果
        res = 0 
        for i in range(m):
            # 从胃口小的开始喂
            if res < n and g[res] <= s[i]:
                res += 1
        return res

最大子序和[53]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums):
        result = float('-inf')  # 初始化结果为负无穷大
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > result:  # 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count
            if count <= 0:  # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                count = 0
        return result

K 次取反后最大化的数组和[1005]

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
# 题解1
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x))
        for i in range(len(nums) - 1, -1, -1):
            if k > 0 and nums[i] < 0:
                nums[i] = -nums[i]
                k = k - 1
        if k % 2 == 0:
            return sum(nums)
        else:
            return sum(nums) - 2*nums[0]
# 错误解法
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i]==0:
                return sum(nums)
            elif k>0 and nums[i]<0:
                nums[i] = -nums[i]
                k = k-1
            elif k>=0 and nums[i]>0:
                nums[i] = nums[i] if k%2==0 else -nums[i]
                return sum(nums)

必须对nums按照abs来排序，不然出错
还要一种基于heapq的方法

1
2
3
4
5
6
7
8
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        import heapq
        heapq.heapify(nums)
        while k>0:
            heapq.heappush(nums, -heapq.heappop(nums))
            k-=1
        return sum(nums)

加油站[134]

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 canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for i in range(len(cost)):
            index = (i + 1)%len(cost)
            rest = gas[i] - cost[i]
            while rest>=0 and index!=i:
                rest += gas[index] - cost[index]
                index = (index+1)%len(cost)
            if rest>=0 and index==i:
                return i
        return -1
# 贪心
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0
        totalSum = 0
        idx = 0
        for i in range(len(cost)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            if curSum<0:
                idx = i + 1
                curSum = 0
        if totalSum <0:
            return -1
        return idx

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

分发糖果[135]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 正常解法
class Solution:
    def candy(self, ratings: List[int]) -> int:
        left = [1] * len(ratings)
        right = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]: #注意
                right[i] = right[i+1] + 1
        s = 0
        for i in range(len(left)):
            s = s + max(left[i], right[i])
        return s

柠檬水找零[860]

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
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0
        twenty = 0
        for i in bills:
            if i==5:
                five += 1
            elif i==10:
                if five>0:
                    five -=1
                    ten += 1
                else:
                    return False
            elif i==20:
                if ten>0 and five>0:
                    ten -= 1
                    five -=1
                    twenty += 1
                elif five>=3:
                    five -= 3
                    twenty += 1
                else:
                    return False
        return True

根据身高重建队列[406]

1
2
3
4
5
6
7
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x:(-x[0],x[1]))
        res = []
        for i in people:
            res.insert(i[1], i)
        return res

这里解释的详细 https://leetcode.cn/problems/queue-reconstruction-by-height/discussion/comments/1809851

用最少数量的箭引爆气球

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        result = 1
        points.sort(key =  lambda x: x[0])
        for i in range(1, len(points)):
            if points[i][0] > points[i-1][1]:
                result = result + 1
            else:
                points[i][1] = min(points[i][1], points[i-1][1])
        return result

无重叠区间[435]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序
        
        result = 1  # 不重叠区间数量，初始化为1，因为至少有一个不重叠的区间
        
        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[i - 1][1]:  # 没有重叠
                result += 1
            else:  # 重叠情况
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界
        
        return len(intervals) - result

划分字母区间[763]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        from collections import defaultdict
        d = defaultdict(int)
        for index, value in enumerate(s):
            d[value] = index
        end = 0
        results = []
        start = 0
        for index, value in enumerate(s):
            end = max(end, d[value])
            if index == end:
                results.append(index-start+1)
                start = index+1
        return results

合并区间[56]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        stack = []
        for i in intervals:
            if stack and i[0] <= stack[-1][1]:
                v = stack.pop()
                stack.append([min(v[0],i[0]), max(v[1],i[1])])
            else:
                stack.append(i)
        return stack

单调递增的数字[738]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = [int(i) for i in str(n)]
        max_idx = 0 
        for i in range(1, len(s)):
            if s[i] > s[i-1]:
                max_idx = i
            elif s[i] == s[i-1]:
                continue
            elif s[i] < s[i-1]:
                s[max_idx] = s[max_idx] - 1
                for j in range(max_idx+1, len(s)):
                    s[j] = 9
                break
        return int("".join([str(k) for k in s]))

来自 https://leetcode.cn/problems/monotone-increasing-digits/solutions/521966/jian-dan-tan-xin-shou-ba-shou-jiao-xue-k-a0mp/
按照自己的写法来的

分割数组为连续子序列[659]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        counter = Counter(nums)
        tail = Counter()
        for i in nums:
            if counter[i] and tail[i - 1]:  # 可以衔接
                counter[i] -= 1
                tail[i - 1] -= 1
                tail[i] += 1
                continue #注意这里
            if counter[i] and counter[i + 1] and counter[i + 2]:  # 可以生成新序列
                tail[i + 2] += 1
                counter[i] -= 1
                counter[i + 1] -= 1
                counter[i + 2] -= 1
                continue #注意这里
        for k, v in counter.items():
            if v > 0:
                return False
        return True

来自 https://leetcode.cn/problems/split-array-into-consecutive-subsequences/description/ 还有一个方法说的很好 https://leetcode.cn/problems/split-array-into-consecutive-subsequences/solutions/376129/zui-jian-dan-de-pythonban-ben-by-semirondo/ 这个方法的思路很清晰，代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        res = []
        for n in nums:
            for v in res:
                if n == v[-1] + 1:
                    v.append(n)
                    break
            else:
                res.insert(0,[n])
        return all([len(v)>=3 for v in res])

例如 2， 3， 4， 4， 5， 5， 6
顺序如下
[[2]]
[[2, 3]]
[[2, 3, 4]]
4不能后接，前插一行
[[4], [2, 3, 4]]
[[4, 5], [2, 3, 4]]
[[4, 5], [2, 3, 4, 5]]
[[4, 5, 6], [2, 3, 4, 5]]
最后比较是否所有序列长度大于等于3就可以了。