LeetCode解题记录(贪心算法)(二)

2021年7月19日 1点热度 0条评论 来源: 进击的汪sir

1. 前言

由于后面还有很多题型要写,贪心算法目前可能就到此为止了,上一篇博客的地址为
LeetCode解题记录(贪心算法)(一)
下面正式开始我们的刷题之旅

2. 贪心

763. 划分字母区间(中等)

题目链接

思路

想切割,要有首尾两个指针,确定了结尾指针,就能确定下一个切割的开始指针。
遍历字符串,如果已扫描部分的所有字符,都只出现在已扫描的范围内,即可做切割。
注意 : 贪心的思想为,只要是扫描过的字符,都出现在我扫描的范围之类,我就切割,不去考虑其他的条件,这样能保证切割的数量最多

代码实现思路

  • result 用来保存结果
  • start end,片断的首尾指针
  • map 存放每一个字符的最远位置

首先通过一个map,记录了每个字符的最远的位置,接下来遍历字符串,end是用来记录,当前已经扫描的字符串的最远的出现的位置,如果当前的位置,等于扫描的字符串的最远位置,则,可以证明,到达了切割的条件,然后切割,存到result里

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> result;
        unordered_map<char, int> map; //记录char c 和其最后出现位置的 map
        int start = 0, end = 0;
        // 初始化map,记录每一个字符的最后位置
        for (int i = 0; i < S.size(); i ++) {
            map[S[i]] = i;
        }
        for (int i = 0; i < S.size(); i ++) {
            end = max(end, map[S[i]]);//记录已扫描字符的最后一次出现的位置
            if (i == end) {//说明后面的片段没有出现重复的字母了
                result.push_back(end - start + 1);//记录结果
                start = i + 1;
            }
        }
        return result;
    }
};

406. 根据身高重建队列(中等)

解题思路

贪心算法:按照身高从高到低进行排序,矮的放后面,因为矮的即使放在了高的前面,也不会对之前高的产生影响;但高的放在前面,对矮的结果就会产生影响了。

重写 compare() 方法:身高相同,按照个数升序排序;身高不同,按照身高降序排序。

public int compare(int[] o1, int[] o2) {

    // 先按身高降序,若身高相同则按 k 值升序。
    return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
}

第二个数字作为索引位置,把数组放在目标索引位置上,如果原来有数了,会往后移。(在一个 ListList 中的指定位置插入一个元素,当前指定位置的元素会往后面移动一个位置。)
遍历排序后的数组,根据 K 插入到 K 的位置上。

class Solution {

    public int[][] reconstructQueue(int[][] people) {

        int n = people.length;
        int m = people[0].length;
        if (n == 0 || m == 0) return new int[0][0];

        Arrays.sort(people, new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {

                // 先按身高降序,若身高相同则按 k 值升序。
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });

        // 遍历排序后的数组,根据 K 插入到 K 的位置上。
        List<int[]> list = new ArrayList<>();
        for (int[] i : people) {

            list.add(i[1], i);
        }
        return list.toArray(new int[list.size()][2]);
    }
}

665. 非递减数列

题目链接

给你一个长度为 n 的整数数组,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示:

1 <= n <= 10 ^ 4
10 ^ 5 <= nums[i] <= 10 ^ 5

题解:

贪心算法

本题是要维持一个非递减的数列,所以遇到递减的情况时(nums[i] > nums[i + 1]),要么将前面的元素缩小,要么将后面的元素放大。

但是本题唯一的易错点就在这,

如果将nums[i]缩小,可能会导致其无法融入前面已经遍历过的非递减子数列;
如果将nums[i + 1]放大,可能会导致其后续的继续出现递减;
所以要采取贪心的策略,在遍历时,每次需要看连续的三个元素,也就是瞻前顾后,遵循以下两个原则:

需要尽可能不放大nums[i + 1],这样会让后续非递减更困难;
就是能不放大就不放大,尽量与前面持平

如果缩小nums[i],但不破坏前面的子序列的非递减性;

算法步骤:

遍历数组,如果遇到递减:
还能修改:
修改方案1:将nums[i]缩小至nums[i + 1];
这个方案是,用i-1,i,i+1,来表示三个数的位置,其中i是我们发现大于i+1的数,那么当i+1大于i-1的时候,我们应该将i缩小至i+1,为什么呢,你想啊,你右边的数比你小,你左边的数比你小,但是呢,你右边的数比你左边的数高,你是不是只需要和你右边的一样高,就能保持非递减?如果你不这样,你让右边的数增加,这就违反了上面的第一条原则:需要尽可能不放大nums[i + 1],这样会让后续非递减更困难,因为这种情况,我们的选择是缩小i

修改方案2:将nums[i + 1]放大至nums[i];
这种情况是什么呢,与上一种相反,你左边右边的数都比你小,但是你右边的数比你左边的数要小,这个时候我们就应该将右边的数放大,放大至nums[i],也就是你的大小,这种情况下是没有争论的,只能将右边的数放大,不明白的同学可以自己在纸上画一画

如果不能修改了:直接返回false;
这个代码需要修改两个地方,显然不符合题目要求,返回false

代码如下

flag 代表修改机会,因为只有一次,所以用掉了,flag就变成false

class Solution {
public:
    bool checkPossibility(vector<int>& nums) 
    {
        if (nums.size() == 1)   return true;
        bool flag = nums[0] <= nums[1] ? true : false; // 标识是否还能修改
        // 遍历时,每次需要看连续的三个元素
        for (int i = 1; i < nums.size() - 1; i++)
        {
            if (nums[i] > nums[i + 1])  // 出现递减
            {
                if (flag)   // 如果还有修改机会,进行修改
                {
                    if (nums[i + 1] >= nums[ i - 1])// 修改方案1
                        nums[i] = nums[i + 1];
                    else                            // 修改方案2
                        nums[i + 1] = nums[i];      
                    flag = false;                   // 用掉唯一的修改机会
                }   
                else        // 没有修改机会,直接结束
                    return false;
            }
        }
        return true;
    }
};

执行结果

3. 总结

对不起各位,我算法这块更新的实在是太慢了,不过最近真的很忙很忙,当然有时候我也会娱乐一下,没有做到自律,下个星期我还准备开始写计算机网络和操作系统的专栏,所以算法这块,我尽量多写(其实我就是懒,有时候晚上回家真的好累,不想写算法题,,,,)

总之,下个星期,继续努力,与昨天的自己比较!

    原文作者:进击的汪sir
    原文地址: https://www.cnblogs.com/wanghongyang/p/15027551.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。