抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-贪心算法

leetcode

发布于：2024年11月18日

字数：2.3k 字

时长：10 分钟

前言

题单LeetCode 热题 100的贪心算法部分，给出解析。

121. Best Time to Buy and Sell Stock

原题链接

题目描述

You are given an array prices where prices[i] is the price of a given stock on the $i^{th}$ day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1: 

1
2
3
4
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2: 

1
2
3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

解题方法

此问题要求在给定的价格数组中，选择某一天买入股票，并在未来的某一天卖出股票，获得最大化利润。

解题步骤：

  • 初始化最小价格：首先，我们需要一个变量来跟踪到目前为止的最小价格。这个变量表示你可以在之前的某一天以这个最低价买入股票。

  • 计算最大利润：我们还需要另一个变量来跟踪到目前为止的最大利润。对于每一天的价格，计算当天卖出时的利润（即当天价格减去之前的最低价格），然后更新最大利润。

  • 遍历价格数组：逐步遍历价格数组，对于每个价格，更新最小价格和最大利润。

  • 返回结果：遍历结束后，最大利润即为我们所求的最大收益。如果最大利润为负数或0，意味着没有任何有利可图的交易，我们返回0。

代码实现

1
2
3
4
5
6
7
8
    def maxProfit(self, prices: List[int]) -> int:
        # 最小价格与最大利润
        min_price, max_profit = float('inf'), 0
        # 遍历每天的价格
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

55. Jump Game

原题链接

题目描述

You are given an integer array nums. You are initially positioned at the array’s first index , and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1: 

1
2
3
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2: 

1
2
3
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

解题方法

这个问题是一个典型的「贪心算法」问题，可以通过贪心思想来解答。需要判断能否从数组的第一个索引跳到最后一个索引。

解题思路：

  1. 贪心策略：
    • 我们维护一个变量 farthest，表示我们当前能跳到的最远位置。
    • 每次遍历数组时，更新 farthest 为当前位置 i 能跳到的最远位置 i + nums[i]。
    • 如果在遍历过程中 farthest 超过或等于数组的最后一个位置，就可以返回 true。
    • 如果当前索引 i 超过了 farthest，说明已经无法跳到该索引之后的位置，返回 false。
  2. 步骤：
    • 从第一个位置开始遍历数组。
    • 对于每个位置，检查是否能够更新当前最远可以到达的距离。
    • 如果在遍历过程中最远的距离无法更新且到达不了最后一个位置，则返回 false。

代码实现

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        farthest = 0
        for i in range(len(nums)):
            if i > farthest:
                return False  # 如果当前索引 i 超过了最远距离，说明跳不过去了
            farthest = max(farthest, i + nums[i])  # 更新最远可到达的距离
            if farthest >= len(nums) - 1:
                return True  # 如果最远距离已经超过或等于最后一个位置，返回 True
        return False

同时也可以从尾部开始使用贪心，从最后一个位置开始往前推，看看是否可以找到一个位置能够跳到最后一个位置。如果可以找到，则将目标位置移动到这个位置，继续往前推。

步骤：

  1. 初始化 lastPos = len(nums) - 1，表示目标是到达最后一个位置。
  2. 从倒数第二个位置开始，检查当前位置是否可以跳到 lastPos，如果可以，则更新 lastPos = i。
  3. 如果最后 lastPos == 0，说明可以从第一个位置跳到最后一个位置，返回 true；否则返回 false。
1
2
3
4
5
6
7
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        lastPos = len(nums) - 1  # 目标是最后一个位置
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= lastPos:  # 如果从 i 能跳到 lastPos
                lastPos = i  # 更新目标位置
        return lastPos == 0

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

45. Jump Game II

原题链接

题目描述

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1: 

1
2
3
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2: 

1
2
Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It’s guaranteed that you can reach nums[n - 1].

解题方法

这个问题可以通过贪心算法来解决。我们需要在每一步尽可能地跳得远，以最小化跳跃次数。具体步骤如下：

思路：

  1. 初始化：

    • 我们可以使用三个变量来跟踪当前的状态：
      • jumps: 表示跳跃的次数。
      • current_end: 表示当前跳跃的最远位置。
      • farthest: 表示在当前跳跃范围内可以跳到的最远位置。

  2. 遍历数组：

    • 遍历每一个位置 i，我们可以从当前位置跳到 i + nums[i]。
    • 更新 farthest 为当前能跳到的最远位置。
    • 如果我们到达了当前跳跃范围的边界（即 i == current_end），我们需要增加一次跳跃，并将 current_end 更新为 farthest。

  3. 结束条件：

    • 当 current_end 达到或超过 n - 1（最后一个位置）时，返回跳跃次数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = 0
        current_end = 0
        farthest = 0
        
        for i in range(n - 1):  # 不需要遍历最后一个元素
            farthest = max(farthest, i + nums[i])  # 更新最远能跳到的位置
            
            if i == current_end:  # 到达当前跳跃的最远位置
                jumps += 1  # 增加跳跃次数
                current_end = farthest  # 更新跳跃的范围
                
                if current_end >= n - 1:  # 如果可以直接到达最后一个位置，结束
                    break
        
        return jumps

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组的长度，我们只需要遍历一次数组。

空间复杂度：$O(1)$，只使用了常数空间。

763. Partition Labels

原题链接

题目描述

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1: 

1
2
3
4
5
6
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.

Example 2: 

1
2
Input: s = "eccbbbbdec"
Output: [10]

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

解题方法

这个问题可以通过贪心算法来解决，思路如下：

  1. 记录每个字符的最后位置：遍历字符串 s，记录每个字符最后一次出现的位置。这可以通过一个哈希表来完成，键是字符，值是字符最后一次出现的位置。

  2. 遍历字符串：然后再遍历字符串，使用两个指针（start 和 end）来划分每个部分。start 是当前部分的开始位置，end 是当前部分中字符的最大结束位置（即该部分的右边界）。

  3. 更新边界：遍历时，更新 end 的值，确保在当前部分内出现的所有字符都能被包含。每当当前字符的位置等于 end 时，说明当前部分可以划分完毕，记录这个部分的大小，并将 start 更新为下一个部分的开始位置。

  4. 返回结果：最终返回所有部分的大小。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # Step 1: 记录每个字符最后出现的位置
        last_position = {char: idx for idx, char in enumerate(s)}
        
        partitions = []
        start, end = 0, 0
        
        # Step 2: 遍历字符串
        for idx, char in enumerate(s):
            # 更新当前部分的结束位置
            end = max(end, last_position[char])
            
            # 如果当前字符的位置等于部分的结束位置，说明这一部分可以划分完毕
            if idx == end:
                partitions.append(idx - start + 1)  # 记录当前部分的大小
                start = idx + 1  # 更新 start 为下一个部分的起始位置
                
        return partitions

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/db0c61fe/

更新于：2024年11月18日

贪心算法

评论