【算法专题】贪心算法

guduadmin201月前

贪心算法

贪心算法介绍
- 1. 柠檬水找零
- 2. 将数组和减半的最少操作次数
- 3. 最大数
- 4. 摆动序列(贪心思路)
- 5. 最长递增子序列(贪心算法)
- 6. 递增的三元子序列
- 7. 最长连续递增序列
- 8. 买卖股票的最佳时机
- 9. 买卖股票的最佳时机Ⅱ(贪心算法)
- 10. K 次取反后最大化的数组和
- 11. 按身高排序
- 12. 优势洗牌
- 13. 最长回文串
- 14. 增减字符串匹配
- 15. 分发饼干
- 16. 最优除法
- 17. 跳跃游戏Ⅱ
- 18. 跳跃游戏
- 19. 加油站
- 20. 单调递增的数字
  贪心算法介绍
  
  什么是贪心算法呢？
  
  首先，我们需要知道贪心策略，即解决问题的策略，将局部最优转变为全局最优；
  - 把解决问题的过程分为若干步；
  - 解决每一步的时候，都选择当前看起来"最优的"解法；
  - "希望"得到全局最优解
    贪心算法的特点：
    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& 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& nums) { int ret = 0; double sum = 0; priority_queue 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& nums) { // 先将数字转为字符串放入 strs 中 vector 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& 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& nums) { int n = nums.size(); vector 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& 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& nums) { int ans = 1; vector 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& 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& 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, greater>& pq) { int num = pq.top(); pq.pop(); num = -num; pq.push(num); } int largestSumAfterKNegations(vector& nums, int k) { int ret = 0; priority_queue, greater> 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 sortPeople(vector& names, vector& heights) { int n = heights.size(); // 创建一个下标数组，用这个数组重写排序方法，按照身高排序，再利用这个下标数组找到对应的身高和名字 vector 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 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 advantageCount(vector& nums1, vector& nums2) { int n = nums2.size(); vector 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 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 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 diStringMatch(string s) { vector 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& g, vector& 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& 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& 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& 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& gas, vector& 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
        思路：
        
        将整数 n 转换为字符串形式，以便于对其进⾏修改操作，并将其存储在字符串变量 str 中。
        初始化⼀个变量 pos，⽤于记录从⾼位到低位第⼀个不满⾜单调递增的数字的位置。初始值为 -1，表示在第⼀位之前。
        从⾼位到低位遍历字符串 str，寻找第⼀个不满⾜单调递增的数字的位置。当遇到⼀个数字⼩于前⼀个数字时，记录这个位置为 pos，并退出循环。
        如果 pos 被更新，说明存在需要修改的数字，执⾏以下操作：
        
        a. 将 pos 位置后的所有数字修改为 9，这样可以保证修改后的数字是最⼤的。
        
        b. 将 pos 位置的数字减⼀，因为这是最⼩的减少量，同时也能够保证修改后的数字仍然⼩于原数字 n.
        
        c. 检查 pos 前⼀位数字是否⼩于减⼀后的 pos 位置数字，如果⼩于，则说明在 pos 位置之前还有相同的数字，需要将 pos 前⼀位数字减⼀，并将 pos 位置修改为 9。
        
        d.重复这个操作，直到 pos 前⼀位数字⼤于等于减⼀后的 pos 位置数字或 pos 已经移动到了第⼀位。
        
        将修改后的字符串 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); } };

db标签

网友评论

搜索: Search

最新文章

热门文章

【算法专题】贪心算法

贪心算法

贪心算法介绍

1. 柠檬水找零

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

3. 最大数

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

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

6. 递增的三元子序列

7. 最长连续递增序列

8. 买卖股票的最佳时机

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

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

11. 按身高排序

12. 优势洗牌

13. 最长回文串

14. 增减字符串匹配

15. 分发饼干

16. 最优除法

17. 跳跃游戏Ⅱ

18. 跳跃游戏

19. 加油站

20. 单调递增的数字

猜你喜欢

网友评论