网站建设设置背景图片,wordpress小程序主题,优化营商环境心得体会2023,深圳网站设计九曲贪心算法 贪心算法介绍1. 柠檬水找零2. 将数组和减半的最少操作次数3. 最大数4. 摆动序列(贪心思路)5. 最长递增子序列(贪心算法)6. 递增的三元子序列7. 最长连续递增序列8. 买卖股票的最佳时机9. 买卖股票的最佳时机Ⅱ(贪心算法)10. K 次取反后最大化的数组和11. 按身高排序12… 贪心算法 贪心算法介绍1. 柠檬水找零2. 将数组和减半的最少操作次数3. 最大数4. 摆动序列(贪心思路)5. 最长递增子序列(贪心算法)6. 递增的三元子序列7. 最长连续递增序列8. 买卖股票的最佳时机9. 买卖股票的最佳时机Ⅱ(贪心算法)10. K 次取反后最大化的数组和11. 按身高排序12. 优势洗牌13. 最长回文串14. 增减字符串匹配15. 分发饼干16. 最优除法17. 跳跃游戏Ⅱ18. 跳跃游戏19. 加油站20. 单调递增的数字 贪心算法介绍
什么是贪心算法呢
首先我们需要知道贪心策略即解决问题的策略将局部最优转变为全局最优
把解决问题的过程分为若干步解决每一步的时候都选择当前看起来最优的解法希望得到全局最优解
贪心算法的特点
提出贪心策略但是贪心策略的提出是没有标准和模板的可能每一道题的贪心策略都是不同的贪心策略的正确性没有保障因为我们提出的贪心策略有可能是错误的正确的贪心策略是需要证明的常用的证明方法是我们学过的数学中见过的证明方法。
下面我们结合题目进行分析。
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^5bills[i] 不是 5 就是 10 或是 20
贪⼼策略分情况讨论
遇到 5 元钱直接收下遇到 10 元钱找零 5 元钱之后收下遇到 20 元钱 先尝试凑 10 5 的组合 如果凑不出来拼凑 5 5 5 的组合
代码如下 class Solution {public:bool lemonadeChange(vectorint 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 块都有的时候优先找510if(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^51 nums[i] 10^7
贪心策略
每次挑选出「当前」数组中「最大」的数然后「减半」直到数组和减少到至少一半为止。
为了「快速」挑选出数组中最大的数我们可以利用「堆」这个数据结构。
代码如下 class Solution {public:int halveArray(vectorint nums) {int ret 0;double sum 0;priority_queuedouble 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 1000 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(vectorint nums) {// 先将数字转为字符串放入 strs 中vectorstring 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 就返回 0if(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 10000 nums[i] 1000
思路贪心算法其中这道题我们在动态规划专题也做过。这道题的贪心策略对于某一个位置来说
如果接下来呈现上升趋势的话我们让其上升到波峰的位置如果接下来呈现下降趋势的话我们让其下降到波谷的位置。
因此如果把整个数组放在「折线图」中我们统计出所有的波峰以及波谷的个数即可。 代码如下 class Solution {public:int wiggleMaxLength(vectorint nums) {if(nums.size() 2) return nums.size();// right 代表后一个数减去当前这个数的差正数代表上升趋势负数代表下降趋势即当前这个数右边数的趋势// left 代表当前这个数左边数的趋势0代表不确定因为首尾位置必选所以初始化的时候给 left 初始化为0int 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(vectorint nums){int n nums.size();vectorint 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(vectorint 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直接返回 trueelse if(nums[i] x) y nums[i]; // 如果nums[i]大于x说明它的大小位于 x 和 y 之间所以可以替代 yelse x nums[i]; // 否则就是比 x 小可以替代x}return false;}};7. 最长连续递增序列
题目链接 - Leetcode -674.最长连续递增序列
Leetcode -674.最长连续递增序列
题目给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl 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(vectorint nums) {int ans 1;vectorint 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^50 prices[i] 10^4
思路由于只能交易一次所以对于某一个位置 i 要想获得最大利润仅需知道前⾯所有元素的最小值。然后在最小值的位置「买入」股票在当前位置「卖出」股票即可。
代码如下 class Solution {public:int maxProfit(vectorint 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^40 prices[i] 10^4
贪心策略由于可以进行无限次交易所以只要是一个「上升区域」我们就把利润拿到手就好了即需要找到一个区间上升的末端所以我们可以是使用双指针来寻找。
代码如下 class Solution {public:int maxProfit(vectorint 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] 1001 k 10^4
贪心策略每次只需把最小的改变符号即可所以我们可以借助优先级队列完成。
代码如下 class Solution {public:void GetTopToOpNum(priority_queueint, vectorint, greaterint pq){int num pq.top();pq.pop();num -num;pq.push(num);}int largestSumAfterKNegations(vectorint nums, int k) {int ret 0;priority_queueint, vectorint, greaterint 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 。
对于每个下标 inames[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.length1 n 10^31 names[i].length 201 heights[i] 10^5names[i] 由大小写英文字母组成heights 中的所有值互不相同
思路我们不能直接按照 i 位置对应的 heights 来排序因为排序过程是会移动元素的但是 names 内的元素是不会移动的。由题意可知names 数组和 heights 数组的下标是一一对应的因此我们可以重新创建出来一个下标数组将这个下标数组按照 heights[i] 的大小排序。那么当下标数组排完序之后里面的顺序就相当于 heights 这个数组排完序之后的下标。之后通过排序后的下标依次找到原来的 name 完成对名字的排序。
代码如下 class Solution {public:vectorstring sortPeople(vectorstring names, vectorint heights) {int n heights.size();// 创建一个下标数组用这个数组重写排序方法按照身高排序再利用这个下标数组找到对应的身高和名字vectorint 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];});vectorstring ret;for(int i 0; i n; i)ret.push_back(names[index[i]]);return ret;}};12. 优势洗牌
题目链接 - Leetcode -870.优势洗牌
Leetcode -870.优势洗牌
题目给定两个长度相等的数组 nums1 和 nums2nums1 相对于 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^5nums2.length nums1.length0 nums1[i], nums2[i] 10^9
思路在做此题之前我们需要了解一个故事田忌赛马。由田忌赛马的故事我们可以得出一个最优的决策方式
当己方此时最差的比不过对面最差的时候让我方最差的去换取掉对面最好的反正都要输不如去拖掉对面一个最强的当己方此时最差的能比得上对面最差的时候就让两者比对下去最差的都能获胜为什么还要输呢。
由此我们每次的决策都会使我方处于优势。
代码如下 class Solution {public:vectorint advantageCount(vectorint nums1, vectorint nums2) {int n nums2.size();vectorint 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的下标数组重写排序方法vectorint 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 2000s 只由小写 和 / 或 大写英文字母组成
贪心策略用尽可能多的字符去构造回文串
如果字符出现偶数个那么全部都可以用来构造回文串如果字符出现奇数个减去一个之后剩下的字符能够全部用来构造回文串最后再判断一下如果有字符出现奇数个就把它单独拿出来放在中间
代码如下 class Solution {public:int longestPalindrome(string s) {vectorint 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^5s 只包含字符 “I” 或 “D”
贪心策略 当遇到 ‘I’ 的时候为了让下一个上升的数可选择的「范围更多」当前选择「最小」的那个数 当遇到 ‘D’ 的时候为了让下一个下降的数可选择的「范围更多」选择当前「最大」的那个数。 class Solution {public:vectorint diStringMatch(string s) {vectorint 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^40 s.length 3 * 10^41 g[i], s[j] 2^31 - 1
贪心策略先将两个数组排序。针对胃口较小的孩子从小到大挑选饼干
如果当前饼干能满足直接喂给这个孩子最小的饼干都能满足不要浪费大饼干如果当前饼干不能满足放弃这个饼干去检测下一个饼干这个饼干连最小胃口的孩子都无法满足其它的孩子也不能满足。
代码如下 class Solution {public:int findContentChildren(vectorint g, vectorint 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.最优除法
题目给定一正整数数组 numsnums 中的相邻整数将进行浮点除法。例如[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 102 nums[i] 1000
对于给定的输入只有一种最优除法。
贪心策略在最终的结果中前两个数的位置是无法改变的。 因为每一个数的都是大于等于 2 的为了让结果更大我们应该尽可能的把剩下的数全都放在「分子」上。
代码如下 class Solution {public:string optimalDivision(vectorint 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^40 nums[i] 1000
题目保证可以到达 nums[n - 1]
思路类似层序遍历的过程用类似层序遍历的过程将第 i 次跳跃的「起始位置」和「结束位置」找出来用这次跳跃的情况更新出下一次跳跃的「起始位置」和「终止位置」。这样「循环往复」就能更新出到达 n - 1 位置的最小跳跃步数。
代码如下 class Solution {public:int jump(vectorint 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^40 nums[i] 10^5
思路和 跳跃游戏II 一样仅需修改一下返回值即可。
代码如下 class Solution {public:bool canJump(vectorint 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 个加油站开往第 i1 个加油站需要消耗汽油 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 ncost.length n1 n 10^50 gas[i], cost[i] 10^4
思路依次枚举所有的起点从起点开始模拟⼀遍加油的流程使用贪⼼优化我们发现当从 i 位置出发⾛了 step 步之后如果失败了。那么 [i, i step] 这个区间内任意⼀个位置作为起点都不可能环绕⼀圈。因此我们枚举的下⼀个起点应该是 i step 1.
代码如下 class Solution {public:int canCompleteCircuit(vectorint gas, vectorint 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]--; // 找到后减一// 后面的全变9for(int i index 1; i str.size(); i)str[i] 9;return stoi(str);}};
