c++贪心系列

各位小伙伴们新年好呀，这是年后的第一篇文章，那么还是一样，我们继续学习这个贪心算法。

第一题

题目链接

2418. 按身高排序 - 力扣（LeetCode）

题目解析

代码原理

方法一

1.先创建一个下标数组，将两个数组所对应的数据的下标创建成一个数组

2.对下标数组进行排序，依靠升高的数据对下标数组进行排序

3.通过重新排序后的下标数组进行重新尾插names数组的数据

方法二

1.使用哈希表存映射关系

2.对身高数组进行排序

3.根据排序后的结果，往哈希表里找名字

代码编写

方法一

class Solution {

public:

    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

        int n = names.size();

        vector<int> index(n);

        for(int i = 0; i < n; i++)

        {

            index[i] = i;

        }//先创建一个下标数组

        sort(index.begin(), index.end(), [&](const int i, const int j)

        {

            return heights[i] > heights[j];

        });//排序

        vector<string> ret;

        for(auto cur: index)

        {

            ret.push_back(names[cur]);

        }//重新尾插

        return ret;

    }

};

方法二

class Solution {

public:

    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {

        int n = names.size();

        unordered_map<int, string> hash(n);

        for(int i = 0; i < n; i++)

        {

            hash[heights[i]] = names[i];

        }

        sort(heights.begin(), heights.end(), greater<int>());

        vector<string> ret;

        for(int i = 0; i < n; i++)

        {

            ret.push_back(hash[heights[i]]);

        }

        return ret;

    }

};

本题总结

如何想到

出现两组数据，且是可以一一对应的关系

方法&思路

1.哈希表，类型是unorder_map<数据类型一， 数据类型二>，然后重新插入另一个数组的数据

2.将两个数组所对应的数据的下标创建成一个数组，先根据一个数组的数据大小进行排序，再重新插入另一个数组的数据

第二题

在讲解这题之前，如果小伙伴们感兴趣可以先去了解一下田忌赛马这个故事，当然，博主也给大家准备了一个类似田忌赛马故事的小视频

日常分享

题目链接

870. 优势洗牌 - 力扣（LeetCode）

题目解析

根据视频中的田忌赛马原理，先用一组数据中的最小值与另一组的最小值进行比较，若比不过则拖走对面的最大值

代码原理

原理大家都已经清楚了，就是田忌赛马，但是如何把它转化成代码呢？利用指针即可当第一组中的最小值小于第二组的最小值时，直接将其从右边插入到结果的数组中，反之，则从左边插入

其次这里也用到了上一题我们总结过的下标数组，先将第一组的数据进行排序，并取它们的下标作为数组，之后再根据下标数组对第二个数组进行排序

代码编写

class Solution {

public:

    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {

        //将第一数组进行排序

        sort(nums1.begin(), nums1.end());

        //创建下标数组

        int n = nums1.size();

        vector<int> index(n);

        for(int i = 0; i < n; i++)

        {

            index[i] = i;

        }

        //对第二个数组进行排序

        sort(index.begin(), index.end(), [&](const int& i, const int& j){

            return nums2[i] < nums2[j];

            //nums2[i] > nums2[j] 这是降序

        });

        //小圣贤庄比武

        vector<int> ret(n);

        int left = 0, right = n - 1;

        for(auto cur: nums1)

        {

            if(cur > nums2[index[left]]) ret[index[left++]] = cur;

            else ret[index[right--]] = cur;

        }

        return ret;

    }

};

本题总结

方法总结

题型特征

类似田忌赛马

方法&思路

思路：田忌赛马的思路、下标数组、根据下标数组进行排序

方法：利用指针即可当第一组中的最小值小于第二组的最小值时，直接将其从右边插入到结果的数组中，反之，则从左边插入

第三题

题目链接

409. 最长回文串 - 力扣（LeetCode）

题目解析

回文数组：以某一个字母为对称轴，对称轴两边的字母要保持一模一样

上图中的回文数组的长度要从第一个d开始算起

注意：只有一个字母时也是回文数组

代码原理

1. 如果字符的个数偶数个，那么全部都可以⽤来构造回⽂串；

2. 如果字符的个数奇数个，减去⼀个之后，剩下的字符能够全部⽤来构造回⽂串；

3. 最后再判断⼀下，如果有字符出现奇数个，就把它单独拿出来放在中间。

那么如何统计字符个数，我们使用哈希表即可（如何写，见代码编写部分）

代码编写

class Solution {

public:

    int longestPalindrome(string s) {

        int hash[2010];

        //计数

        for(auto cur: s)

        {

            hash[cur]++;

        }

        //统计结果

        int ret = 0;

        for(auto cur: hash)

        {

            ret += cur / 2 * 2;//这里只统计了偶数部分

        }

        return ret < s.size()? ret + 1: ret;

    }

};

本题总结

思路&方法

哈希表计数：hash[cur]++

cur/2*2的思路

第四题

题目链接

942. 增减字符串匹配 - 力扣（LeetCode）

题目解析

代码原理

遇到‘I’则prem[i]这个位置的数此时是最小的

遇到‘D’则prem[i]这个位置的数此时是最大的

代码编写

class Solution {

public:

    vector<int> diStringMatch(string s) {

        int n = s.size();

        vector<int> ret;

        int left = 0,  right = n;

        for(auto cur: s)

        {

            if(cur == 'I') ret.push_back(left++);

            else ret.push_back(right--);

        }

        ret.push_back(left);//把最后一个数放进去

        return ret;

    }

};

第五题

题目链接

455. 分发饼干 - 力扣（LeetCode）

题目解析

代码原理

优先满足胃口小的小朋友

代码编写

class Solution {

public:

    int findContentChildren(vector<int>& g, vector<int>& s) {

        sort(g.begin(), g.end());

        sort(s.begin(), s.end());

        int ret = 0,  m = g.size(), n = s.size();

        for(int i = 0, j = 0; i < m && j < n; i++, j++)

        {

            while(j < n && s[j] < g[i])

            {

                j++;

            }

            if(j < n) ret++;

        }

        return ret;

    }

};

第六题

题目链接

 553. 最优除法 - 力扣（LeetCode）

题目解析

代码原理

a * c * d / b

代码编写

class Solution {

public:

    string optimalDivision(vector<int>& nums) {

        int n = nums.size();

        if(n == 1)

        {

            return to_string(nums[0]);

        }

        if(n == 2)

        {

            return to_string(nums[0]) + "/" + to_string(nums[1]);

        }

        string ret;

        ret = to_string(nums[0]) + "/(" + to_string(nums[1]);

        for(int i = 2; i < n; i++)

        {

            ret += "/" + to_string(nums[i]);

        }

        ret += ")";

        return ret;

    }

};

本题总结

方法&思路

思路：a * c * d / b

方法：to_string(元素)//用于转换数据类型

第七题

题目链接

45. 跳跃游戏 II - 力扣（LeetCode）

题目解析

代码原理

代码编写

class Solution {

public:

    int jump(vector<int>& nums) {

        int n = nums.size();

        int left = 0, right = 0, ret = 0, max_position = 0;

        while(left <= right)

        {

            if(max_position >= n - 1) return ret;

            for(int i = left; i <= right; i++)

            {

                max_position = max(max_position, nums[i] + i);

            }

            left = right + 1;

            right = max_position;

            ret++;

        }

        return -1;

    }

};

思路总结：
先模拟走一遍，拿到最大长度后，先更新left和right，再判断是否能够到达最后一个位置，若能达到则返回次数，反之则返回-1。其中更新left和right时先更新left,再更新right，并且right要为往后的最大长度。

变式题

题目链接

55. 跳跃游戏 - 力扣（LeetCode）

代码编写

class Solution {

public:

    bool canJump(vector<int>& nums) {

        int ret = 0, left = 0, right = 0, maxPos = 0;

        int n = nums.size();

        while(left <= right)

        {

            if(right >= n - 1) return true;

            for(int i = left; i <= right; i++)

            {

                maxPos = max(maxPos, nums[i] + i);

            }

            left = right + 1;

            right = maxPos;

        }

        return false;

    }

};

第九题

题目链接

题目解析

代码原理

规律怎么来？

代码编写

class Solution {

public:

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        int n = gas.size();

        for(int i = 0; i < n; i++)

        {

            int ret = 0, step = 0, index = 0;

            for(; step < n; step++)

            {

                index = (i + step) % n;

                ret += gas[index] - cost[index];

                if(ret < 0) break;

            }

            if(ret >= 0) return i;

            i += index;

        }

        return -1;

    }

};

本题总结

如何提取规律

结合题意，借用仅有的例子，列举一些符合题意和不合题意的例子，从中总结一些规律

本篇文章的内容就先到这里，我们下期文章再见！！！