【算法专题】贪心算法

贪心算法介绍

什么是贪心算法呢?

首先,我们需要知道贪心策略,即解决问题的策略,将局部最优转变为全局最优;

  • 把解决问题的过程分为若干步;
  • 解决每一步的时候,都选择当前看起来"最优的"解法;
  • "希望"得到全局最优解

贪心算法的特点:

  1. 提出贪心策略,但是贪心策略的提出是没有标准和模板的,可能每一道题的贪心策略都是不同的;
  2. 贪心策略的正确性没有保障,因为我们提出的"贪心策略"有可能是错误的,正确的贪心策略是需要"证明的";常用的证明方法是我们学过的数学中见过的证明方法。

下面我们结合题目进行分析。

1. 柠檬水找零

题目链接 -> Leetcode -860.柠檬水找零

Leetcode -860.柠檬水找零

题目:在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

示例 1:
输入:bills = [5, 5, 5, 10, 20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。

示例 2:
输入:bills = [5, 5, 10, 10, 20]
输出:false
解释:
前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零,所以答案是 false。

提示:

  • 1 <= bills.length <= 10^5
  • bills[i] 不是 5 就是 10 或是 20

贪⼼策略:分情况讨论:

  • 遇到 5 元钱,直接收下;
  • 遇到 10 元钱,找零 5 元钱之后,收下;
  • 遇到 20 元钱:
    • 先尝试凑 10 + 5 的组合;
    • 如果凑不出来,拼凑 5 + 5 + 5 的组合;

代码如下:

		class Solution {
		public:
		    bool lemonadeChange(vector<int>& bills)
		    {
		        int five = 0, ten = 0;
		        for(int i = 0; i < bills.size(); i++)
		        {
		            // 5 元
		            if(bills[i] == 5)
		            {
		                five++;
		            }
		
		            // 10元
		            else if(bills[i] == 10)
		            {
		                ten++;
		
		                if(five == 0) return false;
		
		                five--;
		            }
		
		            // 20 元
		            else
		            {
		                // 5 块和 10 块都有的时候优先找5+10
		                if(five && ten) 
		                {
		                    ten--;
		                    five--;
		                }
		                
		                else if(five >= 3)
		                {
		                    five -= 3;
		                }
		                                                  
		                else
		                {
		                    return false;
		                }
		            }
		        }
		        return true;
		    }
		};

2. 将数组和减半的最少操作次数

题目链接 -> Leetcode -2208.将数组和减半的最少操作次数

Leetcode -2208.将数组和减半的最少操作次数

题目:给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。(注意,在后续操作中你可以对减半过的数继续执行操作)

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

示例 1:
输入:nums = [5, 19, 8, 1]
输出:3
解释:初始 nums 的和为 5 + 19 + 8 + 1 = 33 。
以下是将数组和减少至少一半的一种方法:
选择数字 19 并减小为 9.5 。
选择数字 9.5 并减小为 4.75 。
选择数字 8 并减小为 4 。
最终数组为[5, 4.75, 4, 1] ,和为 5 + 4.75 + 4 + 1 = 14.75 。
nums 的和减小了 33 - 14.75 = 18.25 ,减小的部分超过了初始数组和的一半,18.25 >= 33 / 2 = 16.5 。
我们需要 3 个操作实现题目要求,所以返回 3 。
可以证明,无法通过少于 3 个操作使数组和减少至少一半。

示例 2:
输入:nums = [3, 8, 20]
输出:3
解释:初始 nums 的和为 3 + 8 + 20 = 31 。
以下是将数组和减少至少一半的一种方法:
选择数字 20 并减小为 10 。
选择数字 10 并减小为 5 。
选择数字 3 并减小为 1.5 。
最终数组为[1.5, 8, 5] ,和为 1.5 + 8 + 5 = 14.5 。
nums 的和减小了 31 - 14.5 = 16.5 ,减小的部分超过了初始数组和的一半, 16.5 >= 31 / 2 = 15.5 。
我们需要 3 个操作实现题目要求,所以返回 3 。
可以证明,无法通过少于 3 个操作使数组和减少至少一半。

提示:

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

贪心策略:

  • 每次挑选出「当前」数组中「最大」的数,然后「减半」;
  • 直到数组和减少到至少一半为止。

为了「快速」挑选出数组中最大的数,我们可以利用「堆」这个数据结构。

代码如下:

		class Solution {
		public:
		    int halveArray(vector<int>& nums) 
		    {
		        int ret = 0;
		        double sum = 0;
		        priority_queue<double> pq;
		
		        // 统计数组总和,并将元素放入大堆中
		        for(auto& num : nums) 
		        {
		            sum += num;
		            pq.push(num);
		        }
		
		        // sum 取一半,每次取当前数组中最大的元素减少一半,sum 并减去这个数,然后更新大堆,统计操作次数
		        sum /= 2.0;
		        while(sum > 0)
		        {
		            double num = pq.top() / 2.0;
		            pq.pop();
		            sum -= num;
		            pq.push(num);
		            ret++;
		        }
		
		        return ret;      
		    }
		};

3. 最大数

题目链接 -> Leetcode -179.最大数

Leetcode -179.最大数

题目:给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:
输入:nums = [10, 2]
输出:“210”

示例 2:
输入:nums = [3, 30, 34, 5, 9]
输出:“9534330”

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 10^9

思路:贪心,可以先优化,将所有的数字当成字符串处理,那么两个数字之间的拼接操作以及比较操作就会很方便。

贪心策略:按照题目的要求,重新定义一个新的排序规则,然后排序即可。

我们定义的排序规则:

  • 「A 拼接 B」 大于 「B 拼接 A」,那么 A 在前,B 在后;
  • 「A 拼接 B」 等于 「B 拼接 A」,那么 A B 的顺序无所谓;
  • 「A 拼接 B」 小于 「B 拼接 A」,那么 B 在前,A 在后;

例如 [“10”, “2”] 两个数,“10” 和 “2” 拼接为 “102”;“2” 和 “10” 拼接为 “210”;因为按字典序比较 “210” 大于 “102”,所以 “210” 在前面。

代码如下:

		class mysort
		{
		public:
		    bool operator()(const string& x, const string& y)
		    {
		        return x + y > y + x;
		    }
		};
		
		class Solution {
		public:
		    string largestNumber(vector<int>& nums) 
		    {
		        // 先将数字转为字符串放入 strs 中
		        vector<string> strs;
		        for(auto& num : nums) strs.push_back(to_string(num));
		
		        // 按仿函数的方法排序
		        sort(strs.begin(), strs.end(), mysort());
		
		        // 将排好序的字符串拼接起来放入 ret 中
		        string ret;
		        for(auto& str : strs) ret += str;
		
		        // 如果第一位为 0 就返回 0
		        if(ret[0] == '0') return "0";
		        
		        return ret;
		    }
		};

4. 摆动序列(贪心思路)

题目链接 -> Leetcode -376.摆动序列

Leetcode -376.摆动序列(贪心思路)

题目:如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如,[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值(6, -3, 5, -7, 3) 是正负交替出现的。

相反,[1, 4, 7, 2, 5] 和[1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1:
输入:nums = [1, 7, 4, 9, 2, 5]
输出:6
解释:整个序列均为摆动序列,各元素之间的差值为(6, -3, 5, -7, 3) 。

示例 2:
输入:nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
输出:7
解释:这个序列包含几个长度为 7 摆动序列。
其中一个是[1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为(16, -7, 3, -3, 6, -8) 。

示例 3:
输入:nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
输出:2

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

思路:贪心算法,其中这道题我们在动态规划专题也做过。这道题的贪心策略:对于某一个位置来说:

  • 如果接下来呈现上升趋势的话,我们让其上升到波峰的位置;
  • 如果接下来呈现下降趋势的话,我们让其下降到波谷的位置。

因此,如果把整个数组放在「折线图」中,我们统计出所有的波峰以及波谷的个数即可。

在这里插入图片描述

代码如下:

		class Solution {
		public:
		    int wiggleMaxLength(vector<int>& nums) 
		    {
		        if(nums.size() < 2) return nums.size();
		
		        // right 代表后一个数减去当前这个数的差,正数代表上升趋势,负数代表下降趋势,即当前这个数右边数的趋势
		        // left 代表当前这个数左边数的趋势,0代表不确定,因为首尾位置必选,所以初始化的时候给 left 初始化为0
		        int left = 0, right = 0, ret = 0;
		        for(int i = 0; i < nums.size() - 1; i++)
		        {
		            right = nums[i + 1] - nums[i];
		            if(right == 0) continue; // 忽略掉相同的数
		
		            if(right * left <= 0) ret++;
		            left = right;
		        }
		        // 加上最后一个位置
		        return ++ret;
		    }
		};

5. 最长递增子序列(贪心算法)

题目链接 -> Leetcode -300.最长递增子序列

Leetcode -300.最长递增子序列

题目:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。
例如,[3, 6, 2, 7] 是数组[0, 3, 1, 6, 2, 2, 7] 的子序列。

示例 1:
输入:nums = [10, 9, 2, 5, 3, 7, 101, 18]
输出:4
解释:最长递增子序列是[2, 3, 7, 101],因此长度为 4 。

示例 2:
输入:nums = [0, 1, 0, 3, 2, 3]
输出:4

示例 3:
输入:nums = [7, 7, 7, 7, 7, 7, 7]
输出:1

提示:

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

贪心策略:我们在考虑最长递增子序列的长度的时候,其实并不关心这个序列长什么样子,我们只是关心最后一个元素是谁。这样新来一个元素之后,我们就可以判断是否可以拼接到它的后面。

因此,我们可以创建一个数组,统计长度为 x 的递增子序列中,最后一个元素是谁。为了尽可能的让这个序列更长,我们仅需统计长度为 x 的所有递增序列中最后一个元素的「最小值」。

统计的过程中发现,数组中的数呈现「递增」趋势,因此可以使用「二分」来查找插入位置。

代码如下:

		class Solution 
		{
		public:
		    int lengthOfLIS(vector<int>& nums)
		    {
		        int n = nums.size();
		        vector<int> ret;
		        ret.push_back(nums[0]);
		        for(int i = 1; i < n; i++)
		        {
		            // 因为我们的思路是会让数组有序的,所以当 nums[i ]大于 ret 数组最后一个元素就直接尾插
		            if(nums[i] > ret.back())
		            {
		                ret.push_back(nums[i]);
		            }
		
		            else
		            {
		                // 利用二分插入(ret数组已经有序)
		                // 找出第一次大于等于 nums[i] 的元素,使 nums[i] 替代它的位置
		                int left = 0, right = ret.size() - 1;
		                while(left < right)
		                {
		                    int mid = left + (right - left) / 2;
		                    if(ret[mid] >= nums[i]) right = mid;
		                    else left = mid + 1;
		                }
		                ret[left] = nums[i];
		            }
		        }
		        return ret.size();
		    }
		};

6. 递增的三元子序列

题目链接 -> Leetcode -334.递增的三元子序列

Leetcode -334.递增的三元子序列

题目:给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标(i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false 。

示例 1:
输入:nums = [1, 2, 3, 4, 5]
输出:true
解释:任何 i < j < k 的三元组都满足题意

示例 2:
输入:nums = [5, 4, 3, 2, 1]
输出:false
解释:不存在满足题意的三元组

示例 3:
输入:nums = [2, 1, 5, 0, 4, 6]
输出:true
解释:三元组(3, 4, 5) 满足题意,因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

提示:

  • 1 <= nums.length <= 5 * 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

贪心策略:最长递增子序列的简化版。不用一个数组存数据,仅需两个变量即可。也不用二分插入位置,仅需两次比较就可以找到插入位置。

代码如下:

		class Solution {
		public:
		    bool increasingTriplet(vector<int>& nums) 
		    {
		        int n = nums.size();
		        int x = nums[0], y = INT_MAX;
		        for(int i = 1; i < n; i++)
		        {
		            if(nums[i] > y) return true; // 如果 nums[i] 大于 y,说明它可以放在 y 后面,这时候长度为3,直接返回 true
		            else if(nums[i] > x) y = nums[i]; // 如果nums[i]大于x,说明它的大小位于 x 和 y 之间,所以可以替代 y
		            else x = nums[i]; // 否则,就是比 x 小,可以替代x
		        }
		        return false;
		    }
		};

7. 最长连续递增序列

题目链接 -> Leetcode -674.最长连续递增序列

Leetcode -674.最长连续递增序列

题目:给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列[nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1:
输入:nums = [1, 3, 5, 4, 7]
输出:3
解释:最长连续递增序列是[1, 3, 5], 长度为3。
尽管[1, 3, 5, 7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。

示例 2:
输入:nums = [2, 2, 2, 2, 2]
输出:1
解释:最长连续递增序列是[2], 长度为1。

提示:

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

思路:思路与 第五题 类似,区别在于本题是要找连续的区间,所以当我们找到开始不连续的元素时,将 ret 数组清空,重新插入;每次判断结束判断找到最长递增序列。

代码如下:

			class Solution {
			public:
			    int findLengthOfLCIS(vector<int>& nums) 
			    {
			        int ans = 1;
			        vector<int> ret; 
			        ret.push_back(nums[0]);
			        for(int i = 1; i < nums.size(); i++)
			        {
			            if(nums[i] > ret.back()) 
			            {
			                ret.push_back(nums[i]);
			            }
			
			            else
			            {
			                ret.clear();
			                ret.push_back(nums[i]);
			            }
			            ans = fmax(ans, ret.size());
			        }
			        return ans;
			    }
			}; 

8. 买卖股票的最佳时机

题目链接 -> Leetcode -121.买卖股票的最佳时机

Leetcode -121.买卖股票的最佳时机

题目:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例 1:
输入:[7, 1, 5, 3, 6, 4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6 - 1 = 5 。
注意利润不能是 7 - 1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:
输入:prices = [7, 6, 4, 3, 1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

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

思路:由于只能交易一次,所以对于某一个位置 i ,要想获得最大利润,仅需知道前⾯所有元素的最小值。然后在最小值的位置「买入」股票,在当前位置「卖出」股票即可。

代码如下:

			class Solution {
			public:
			    int maxProfit(vector<int>& prices)
			    {
			        int prevMin = INT_MAX, ret = 0;
			        for (auto& p : prices)
			        {
			            ret = max(ret, p - prevMin); // 记录最大利润
			            prevMin = min(prevMin, p);  // 记录最小买入价格
			        }
			        return ret;
			    }
			};

9. 买卖股票的最佳时机Ⅱ(贪心算法)

题目链接 -> Leetcode -122.买卖股票的最佳时机Ⅱ

Leetcode -122.买卖股票的最佳时机Ⅱ

题目:给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和 / 或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1:
输入:prices = [7, 1, 5, 3, 6, 4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2:
输入:prices = [1, 2, 3, 4, 5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3:
输入:prices = [7, 6, 4, 3, 1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。

提示:

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

贪心策略:由于可以进行无限次交易,所以只要是一个「上升区域」,我们就把利润拿到手就好了,即需要找到一个区间上升的末端,所以我们可以是使用双指针来寻找。

代码如下:

			class Solution 
			{
			public:
			    int maxProfit(vector<int>& prices) 
			    {
			        // 贪心 + 双指针
			        int ret = 0;
			        for(int start = 0; start < prices.size();)
			        {
			            int end = start + 1;
			
			            // 找到上升的末端
			            while(end < prices.size() && prices[end] > prices[end - 1]) end++;
			
			            // 利润等于上升的末端 - 上升区间的起始,如果不是上升的区间,即是自己减去自己,不影响
			            ret += prices[end - 1] - prices[start];
			            start = end;
			        }
			        return ret;
			    }
			};

10. K 次取反后最大化的数组和

题目链接 -> Leetcode -1005.K 次取反后最大化的数组和

Leetcode -1005.K 次取反后最大化的数组和

题目:给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组:

选择某个下标 i 并将 nums[i] 替换为 - nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后,返回数组 可能的最大和 。

示例 1:
输入:nums = [4, 2, 3], k = 1
输出:5
解释:选择下标 1 ,nums 变为[4, -2, 3] 。

示例 2:
输入:nums = [3, -1, 0, 2], k = 3
输出:6
解释:选择下标(1, 2, 2) ,nums 变为[3, 1, 0, 2] 。

示例 3:
输入:nums = [2, -3, -1, 5, -4], k = 2
输出:13
解释:选择下标(1, 4) ,nums 变为[2, 3, -1, 5, 4] 。

提示:

  • 1 <= nums.length <= 10^4
  • -100 <= nums[i] <= 100
  • 1 <= k <= 10^4

贪心策略:每次只需把最小的改变符号即可,所以我们可以借助优先级队列完成。

代码如下:

			class Solution {
			public:
			
			    void GetTopToOpNum(priority_queue<int, vector<int>, greater<int>>& pq)
			    {
			        int num = pq.top();
			        pq.pop();
			        num = -num;
			        pq.push(num);
			    }
			
			    int largestSumAfterKNegations(vector<int>& nums, int k) 
			    {
			        int ret = 0;
			        priority_queue<int, vector<int>, greater<int>> pq;
			        for(auto& num : nums)
			            pq.push(num);
			
			        // 每次取最小的变正数
			        while(k--) GetTopToOpNum(pq);
			
			        while(!pq.empty())
			        {
			            ret += pq.top();
			            pq.pop();
			        }
			        
			        return ret;
			    }
			};

11. 按身高排序

注意:本题没有用到贪心的思想,是为了下一题田忌赛马做准备。

题目链接 -> Leetcode -2418.按身高排序

Leetcode -2418.按身高排序

题目:给你一个字符串数组 names ,和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i,names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高 降序 顺序返回对应的名字数组 names 。

示例 1:
输入:names = [“Mary”, “John”, “Emma”], heights = [180, 165, 170]
输出:[“Mary”, “Emma”, “John”]
解释:Mary 最高,接着是 Emma 和 John 。

示例 2:
输入:names = [“Alice”, “Bob”, “Bob”], heights = [155, 185, 150]
输出:[“Bob”, “Alice”, “Bob”]
解释:第一个 Bob 最高,然后是 Alice 和第二个 Bob 。

提示:

  • n == names.length == heights.length
  • 1 <= n <= 10^3
  • 1 <= names[i].length <= 20
  • 1 <= heights[i] <= 10^5
  • names[i] 由大小写英文字母组成
  • heights 中的所有值互不相同

思路:我们不能直接按照 i 位置对应的 heights 来排序,因为排序过程是会移动元素的,但是 names 内的元素是不会移动的。由题意可知,names 数组和 heights 数组的下标是一一对应的,因此我们可以重新创建出来一个下标数组,将这个下标数组按照 heights[i] 的大小排序。那么,当下标数组排完序之后,里面的顺序就相当于 heights 这个数组排完序之后的下标。之后通过排序后的下标,依次找到原来的 name ,完成对名字的排序。

代码如下:

			class Solution {
			public:
			    vector<string> sortPeople(vector<string>& names, vector<int>& heights) 
			    {
			        int n = heights.size();
			
			        // 创建一个下标数组,用这个数组重写排序方法,按照身高排序,再利用这个下标数组找到对应的身高和名字
			        vector<int> index;
			        for(int i = 0; i < n; i++) index.push_back(i);
			
			        // 对下标进行排序
			        sort(index.begin(), index.end(),  [&](int i, int j)
			        {
			            return heights[i] > heights[j];
			        });
			
			        vector<string> ret;
			        for(int i = 0; i < n; i++)
			            ret.push_back(names[index[i]]);
			        
			        return ret;
			    }
			};

12. 优势洗牌

题目链接 -> Leetcode -870.优势洗牌

Leetcode -870.优势洗牌

题目:给定两个长度相等的数组 nums1 和 nums2,nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。

返回 nums1 的任意排列,使其相对于 nums2 的优势最大化。

示例 1:
输入:nums1 = [2, 7, 11, 15], nums2 = [1, 10, 4, 11]
输出:[2, 11, 7, 15]

示例 2:
输入:nums1 = [12, 24, 8, 32], nums2 = [13, 25, 32, 11]
输出:[24, 32, 8, 12]

提示:

  • 1 <= nums1.length <= 10^5
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 10^9

思路:在做此题之前我们需要了解一个故事:田忌赛马。由田忌赛马的故事我们可以得出一个最优的决策方式:

  • 当己方此时最差的比不过对面最差的时候,让我方最差的去换取掉对面最好的(反正都要输,不如去拖掉对面一个最强的);
  • 当己方此时最差的能比得上对面最差的时候,就让两者比对下去(最差的都能获胜,为什么还要输呢?)。

由此我们每次的决策,都会使我方处于优势。

代码如下:

			class Solution {
			public:
			    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) 
			    {
			        int n = nums2.size();
			        vector<int> index(n);
			        for(int i = 0; i < n; i++) index[i] = i;
			
			        sort(nums1.begin(), nums1.end());  // 对nums1排序
			        sort(index.begin(), index.end(), [&](int x, int y) 
			        {
			            return nums2[x] < nums2[y];
			        });   //对nums2的下标数组重写排序方法
			
			        vector<int> ret(n);
			        int left = 0, right = n - 1; // left 和 right 指向index数组的下标
			
			        // 田忌赛马(贪心)
			        // 遍历 nums1 数组,用nums1的下等马(最小数)跟nums2的下等马(最小数)比较,如果比nums2中的马大,就直接放入ret数组中以 index[left] 为下标的位置,然后 left 迭代往后走;否则用 nums1 的下等马(最小数) 换取 nums2 的上等马(最大数),然后 right 迭代往前走
			        for(auto& num : nums1)
			        {
			            if(num > nums2[index[left]]) ret[index[left++]] = num;
			            else ret[index[right--]] = num;
			        }
			        return ret;
			    }
			};

13. 最长回文串

题目链接 -> Leetcode -409.最长回文串

Leetcode -409.最长回文串

题目:给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。

在构造过程中,请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

示例 1:
输入:s = “abccccdd”
输出 : 7
解释 :
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2 :
输入 : s = “a”
输出 : 1

示例 3:
输入 : s = “aaaaaccc”
输出 : 7

提示 :

  • 1 <= s.length <= 2000
  • s 只由小写 和 / 或 大写英文字母组成

贪心策略:用尽可能多的字符去构造回文串:

  • 如果字符出现偶数个,那么全部都可以用来构造回文串;
  • 如果字符出现奇数个,减去一个之后,剩下的字符能够全部用来构造回文串;
  • 最后再判断一下,如果有字符出现奇数个,就把它单独拿出来放在中间;

代码如下:

			class Solution 
			{
			public:
			    int longestPalindrome(string s) 
			    {
			        vector<int> arr(128);
			        for(auto& ch : s) arr[ch - 'A']++;
			
			        bool flag = true;
			        int ret = 0;
			        for(int i = 0; i < 128; i++)
			        {
			        	// 偶数个
			            if(arr[i] % 2 == 0) 
			            {
			                ret += arr[i];
			            }
			            // 奇数个
			            else
			            {
			                if(flag)
			                {
			                    ret += arr[i];
			                    flag = false;
			                }
			                else
			                {
			                    ret += arr[i] - 1;
			                }
			            }
			        }
			        return ret;
			    }
			};

14. 增减字符串匹配

题目链接 -> Leetcode -942.增减字符串匹配

Leetcode -942.增减字符串匹配

题目:由范围[0, n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中 :

如果 perm[i] < perm[i + 1] ,那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ,那么 s[i] == ‘D’
给定一个字符串 s ,重构排列 perm 并返回它。如果有多个有效排列perm,则返回其中 任何一个 。

示例 1:
输入:s = “IDID”
输出:[0, 4, 1, 3, 2]

示例 2:
输入:s = “III”
输出:[0, 1, 2, 3]

示例 3:
输入:s = “DDI”
输出:[3, 2, 0, 1]

提示:

  • 1 <= s.length <= 10^5
  • s 只包含字符 “I” 或 “D”

贪心策略:

  • 当遇到 ‘I’ 的时候,为了让下一个上升的数可选择的「范围更多」,当前选择「最小」的那个数;

  • 当遇到 ‘D’ 的时候,为了让下一个下降的数可选择的「范围更多」,选择当前「最大」的那个数。

      		class Solution {
      		public:
      		    vector<int> diStringMatch(string s) 
      		    {
      		        vector<int> ret;
      		        
      		        // left 和 right 分别标记最大值和最小值
      		        int left = 0, right = s.size();
      		        for(auto& ch : s)
      		        {
      		            if(ch == 'I') ret.push_back(left++);
      		            else ret.push_back(right--);
      		        }
      		
      		        // 把最后一个数放进去
      		        ret.push_back(left);
      		
      		        return ret;
      		    }
      		};
    

15. 分发饼干

题目链接 -> Leetcode -455.分发饼干

Leetcode -455.分发饼干

题目:假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。
如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1:
输入: g = [1, 2, 3], s = [1, 1]
输出 : 1
解释 :
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1, 2, 3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2 :
输入 : g = [1, 2], s = [1, 2, 3]
输出 : 2
解释 :
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1, 2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示:

  • 1 <= g.length <= 3 * 10^4
  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 - 1

贪心策略:先将两个数组排序。针对胃口较小的孩子,从小到大挑选饼干:

  • 如果当前饼干能满足,直接喂给这个孩子(最小的饼干都能满足,不要浪费大饼干);
  • 如果当前饼干不能满足,放弃这个饼干,去检测下一个饼干(这个饼干连最小胃口的孩子都无法满足,其它的孩子也不能满足)。

代码如下:

			class Solution {
			public:
			    int findContentChildren(vector<int>& g, vector<int>& s) 
			    {   
			        // 排序
			        sort(g.begin(), g.end());
			        sort(s.begin(), s.end());
			
			        int kids = 0, mine = 0, ret = 0;
			        while(kids < g.size() && mine < s.size())
			        {
			            // 如果能够满足当前孩子,就把饼干分给这个孩子
			            if(g[kids] <= s[mine])
			            {
			                kids++;
			                ret++;
			            }
			            // 无论满不满足当前孩子,都要往下遍历饼干
			            mine++;
			        }
			        return ret;
			    }
			};

16. 最优除法

题目链接 -> Leetcode -553.最优除法

Leetcode -553.最优除法

题目:给定一正整数数组 nums,nums 中的相邻整数将进行浮点除法。例如,[2, 3, 4] -> 2 / 3 / 4 。

例如,nums = [2, 3, 4],我们将求表达式的值 “2/3/4”。
但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。你需要找出怎么添加括号,以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意:你的表达式不应该包含多余的括号。

示例 1:
输入 : [1000, 100, 10, 2]
输出 : “1000/(100/10/2)”
解释 : 1000 / (100 / 10 / 2) = 1000 / ((100 / 10) / 2) = 200
但是,以下加粗的括号 “1000/((100/10)/2)” 是冗余的,
因为他们并不影响操作的优先级,所以你需要返回 “1000/(100/10/2)”。
其他用例 :
1000 / (100 / 10) / 2 = 50
1000 / (100 / (10 / 2)) = 50
1000 / 100 / 10 / 2 = 0.5
1000 / 100 / (10 / 2) = 2

示例 2:
输入: nums = [2, 3, 4]
输出 : “2/(3/4)”
解释 : (2 / (3 / 4)) = 8 / 3 = 2.667
可以看出,在尝试了所有的可能性之后,我们无法得到一个结果大于 2.667 的表达式。

说明 :

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000

对于给定的输入只有一种最优除法。

贪心策略:在最终的结果中,前两个数的位置是无法改变的。
因为每一个数的都是大于等于 2 的,为了让结果更大,我们应该尽可能的把剩下的数全都放在「分子」上。

代码如下:

			class Solution {
			public:
			    string optimalDivision(vector<int>& nums) 
			    {
			        //在最终的结果中,前两个数的位置是无法改变的。
			        //因为每⼀个数都是大于等于 2 的,为了让结果更大,我们应该尽可能的把剩下的数全都放在分⼦上
			        if(nums.size() == 1) return to_string(nums[0]);
			        if(nums.size() == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
			
			        string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
			
			        for(int i = 2; i < nums.size(); i++)
			        {
			            ret += "/" + to_string(nums[i]);
			        }
			
			        ret += ")";
			        return ret;
			    }
			};

17. 跳跃游戏Ⅱ

题目链接 -> Leetcode -45.跳跃游戏Ⅱ

Leetcode -45.跳跃游戏Ⅱ

题目:给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

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

示例 2 :
输入 : nums = [2, 3, 0, 1, 4]
输出 : 2

提示 :

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

题目保证可以到达 nums[n - 1]

思路:类似层序遍历的过程:用类似层序遍历的过程,将第 i 次跳跃的「起始位置」和「结束位置」找出来,用这次跳跃的情况,更新出下一次跳跃的「起始位置」和「终止位置」。这样「循环往复」,就能更新出到达 n - 1 位置的最小跳跃步数。

代码如下:

			class Solution {
			public:
			    int jump(vector<int>& nums) 
			    {
			        //⽤类似层序遍历的过程,将第 i 次跳跃的「起始位置」和「结束位置」找出来,⽤这次跳跃的情况,更新出下⼀次跳跃的「起始位置」和「终⽌位置」
			        int left = 0, right = 0, maxPos = 0, ret = 0;
			        while(left <= right)  // 以防跳不到 n - 1位置
			        {
			            // 先判断⼀下是否已经能跳到最后⼀个位置
			            if(maxPos >= nums.size() - 1) return ret;
			
			            for(int i = left; i <= right; i++)
			            {
			                maxPos = max(i + nums[i], maxPos);
			            }
			            left = right + 1;
			            right = maxPos;
			            ret++;
			        }
			        return -1; // 跳不到的情况
			    }
			};

18. 跳跃游戏

题目链接 -> Leetcode -55.跳跃游戏

Leetcode -55.跳跃游戏

题目:给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

示例 1:
输入:nums = [2, 3, 1, 1, 4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:
输入:nums = [3, 2, 1, 0, 4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

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

思路:和 跳跃游戏II 一样,仅需修改一下返回值即可。

代码如下:

			class Solution {
			public:
			    bool canJump(vector<int>& nums) 
			    {
			        // 和跳跃游戏Ⅱ的思路一样
			        int left = 0, right = 0, maxPos = 0, n = nums.size();
			        while(left <= right)
			        {
			            if(maxPos >= n - 1) return true;
			
			            for(int i = left; i <= right; i++)
			            {
			                maxPos = max(maxPos, nums[i] + i);
			            }
			            left = right + 1;
			            right = maxPos;
			        }
			        return false;
			    }
			};

19. 加油站

题目链接 -> Leetcode -134.加油站

Leetcode -134.加油站

题目:在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。

示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

思路:依次枚举所有的起点;从起点开始,模拟⼀遍加油的流程;使用贪⼼优化:我们发现,当从 i 位置出发,⾛了 step 步之后,如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点,都不可能环绕⼀圈。因此我们枚举的下⼀个起点,应该是 i + step + 1.

代码如下:

			class Solution {
			public:
			    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
			    {
			        int n = gas.size();
			        
			        // 暴力枚举每一个位置,模拟从每个位置开始出发,能不能回到原位,使用step 变量标记走了多少步
			        for(int i = 0; i < n; i++)
			        {
			            int rest = 0, step = 0; // step 记录走的步数,判断是否已经走了一圈
			            for(; step < n; step++)
			            {
			                int index = (i + step) % n;  // 使下标呈环状,当越界时继续返回数组的起始位置
			                rest = rest + gas[index] - cost[index];
			                if(rest < 0) break;
			            }
			            if(rest >= 0) return i;
			
			            // 优化,不加这句会超时;这句话的原理就是假设我们从a位置开始枚举到d位置,发现不行,那么从b、c位置开始枚举到d也是不行的,所以我们直接让i跳过step步,从它的下一步开始枚举(循环内会++)
			            i += step;  
			        }
			        return -1;
			    }
			};

20. 单调递增的数字

题目链接 -> Leetcode -738.单调递增的数字

Leetcode -738.单调递增的数字

题目:当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:
输入: n = 10
输出: 9

示例 2:
输入: n = 1234
输出: 1234

示例 3:
输入: n = 332
输出: 299

提示:

  • 0 <= n <= 10^9

思路:

  1. 将整数 n 转换为字符串形式,以便于对其进⾏修改操作,并将其存储在字符串变量 str 中。
  2. 初始化⼀个变量 pos,⽤于记录从⾼位到低位第⼀个不满⾜单调递增的数字的位置。初始值为 -1,表示在第⼀位之前。
  3. 从⾼位到低位遍历字符串 str,寻找第⼀个不满⾜单调递增的数字的位置。当遇到⼀个数字⼩于前⼀个数字时,记录这个位置为 pos,并退出循环。
  4. 如果 pos 被更新,说明存在需要修改的数字,执⾏以下操作:

a. 将 pos 位置后的所有数字修改为 9,这样可以保证修改后的数字是最⼤的。

b. 将 pos 位置的数字减⼀,因为这是最⼩的减少量,同时也能够保证修改后的数字仍然⼩于原数字 n.

c. 检查 pos 前⼀位数字是否⼩于减⼀后的 pos 位置数字,如果⼩于,则说明在 pos 位置之前还有相同的数字,需要将 pos 前⼀位数字减⼀,并将 pos 位置修改为 9。

d.重复这个操作,直到 pos 前⼀位数字⼤于等于减⼀后的 pos 位置数字或 pos 已经移动到了第⼀位。

  1. 将修改后的字符串 str 转换为整型数字并返回。

代码如下:

			class Solution {
			public:
			    int monotoneIncreasingDigits(int n) 
			    {
			        string str = to_string(n);
			        int index = 0;
			
			        // 找到第一个递减的位置
			        while(index + 1 < str.size() && str[index] <= str[index + 1]) index++;
			        
			        if(index + 1 == str.size()) return n; // 全是递增的情况
			
			        // 回推,如果第一个递减的位置的数字相同,找到最高位的那个
			        while(index - 1 >= 0 && str[index] == str[index - 1]) index--;
			        str[index]--; // 找到后减一
			        
			        // 后面的全变9
			        for(int i = index + 1; i < str.size(); i++)
			            str[i] = '9';
			
			        return stoi(str);
			    }
			};

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>