贪心题目

Posted on | Post modified: | In |
Words count in article: 776

跳跃游戏||

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

1
2
3
4
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

以$[2,3,1,1,4]$为例，初始能跳的最远位置为2，然后看从1到2这段路上能跳最远的点，1位置能跳到4,而2位置只能跳到3，因此第一步跳到位置1。更新现在的最远距离为4，这已经跳到最后了，因此需要跳两次。

  • 代码细节
  1. 在遍历时，需要一个变量保存当前能到的最远位置。
  2. 在遍历过程中，最远位置是可能会变动的，因此需要一个变量记录上一次跳跃的位置，如果遍历到上一次跳跃的位置，那么就需要增加一步跳跃。
  3. 最后一个位置不需要访问。因为每个位置$ i $都是在$i <= maxPos$ 的条件下访问的，因此在访问最后一个位置时，最远位置应该是大于等于它的，说明前面已经能够跳到最远了。这时如果再访问就可能造成一次多余的跳跃(在maxPos恰等于最后位置时)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++ i) {
            maxPos = max(maxPos, i + nums[i]); // 贪心最远位置
            if (i == end) { // 如果遍历到上一步能跳到的最远位置
                end = maxPos;
                ++ step;
            }
        }
        return step;
    }
};

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
  • 贪心+二分

维护一个f数组，它的下标表示上升子序列的长度，对应位置的值表示该子序列的最后一个数。该序列一定是单增的，因此在遍历原序列的时候可以二分查找当前位置所能插入的最长子序列(f[x] < nums[i]) 。然后贪心的选取该位置，更新比找到的子序列数量大一个的子序列的最后一个数为它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lengthOfLIS(vector<int>& nums) {
    int n = size(nums);
    int f[n+1];
    memset(f, 0, sizeof f);
    f[0] = -1e9; 
    int len = 0;
    for (int i = 0; i < n; ++ i) {
        // 遍历整个序列
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1>> 1;
            // 在f中找比当前数小的最大的数
            if (f[mid] < nums[i]) l = mid ;
            else r = mid - 1;
        }
        f[l + 1] = nums[i];
        len = max(len, l + 1);
    }
    return len;
}