锐客网

  1. 首页 > it技术 > >

贪心算法

按要求补齐数组 给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
【贪心算法】输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:

int minPatches(vector& nums, int n) { int64_t tmp=1; int res=0; int i=0; while(tmp<=n){ if(i

删除重复字母保持最小字典序 给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入: "bcabc"
输出: "abc"
string removeDuplicateLetters(string s) { int m[256] = {0}, visited[256] = {0}; string res = "0"; for (auto x : s) ++m[a]; for (auto x : s) { --m[x]; if (visited[x]) continue; while (x < res.back() && m[res.back()]) { //输入bcabc，遍历到a时，只有bc在后面还出现，才把bc弹出 visited[res.back()] = 0; res.pop_back(); } res += x; visited[x] = 1; } return res.substr(1); }

通配符匹配 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '' 的通配符匹配。
'?' 可以匹配任何单个字符。
'' 可以匹配任意字符串（包括空字符串）。
//TODO 待修改 bool isMatch(string s, string p) { int n=s.size(); int m=p.size(); if(n==0 && m==0) return true; if (n!=0 && m==0) return false; if(p[1]!='?'){ if(s[0] == p[0] || s[0]!='\0' && p[0]=='*'){ return isMatch(s.substr(1,n-1),p.substr(1,m-1)); }else return false; }else{ if(s[0]==p[0] || s[0]!='\0' && p[0]=='*'){ return isMatch(s, p.substr(2,m-2))|| isMatch(s.substr(1,n-1),p.substr(1,m-1)); }else { return isMatch(s, p.substr(2,m-2)); } }}

跳跃游戏1 输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
bool canJump(vector& nums) { int n=nums.size(); int res=0; for(int i=0; ires) return false; //res表示最远能够到达的位置，此时表示到不了i的位置，直接返回 res = max(res,nums[i]+i); } return true; }

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

贪心算法
文章图片
image.png
int jump(vector& nums) { int n=nums.size(); if(n==1) return 0; //只有一个数，返回1 int res=nums[0]; int step=1; int tmp=nums[0]; for(int i=1; ires || i==res && res=n-1) break; //以res为准，而不是tmp } return step; }

买卖股票的最佳时机2 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
//只要后一天的价格大于前一天的价格就加diff int maxProfit(vector& prices) { int n=prices.size(); if (n==0) return 0; int mn=prices[0]; int res=0; int diff=0; for(int i=1; i0) res += diff; } return res; }

买卖股票的最佳时机1-动态规划 输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
//用a[i]保存到i天的最大利润，只买卖一次 int maxProfit(vector& prices) { int n=prices.size(); if(n<=1) return 0; int a[n]={0}; int min=prices[0]; for(int i=1; i

买卖股票的最佳时机3 输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
我们其实可以求至少k次交易的最大利润，找到通解后可以设定 k = 2，即为本题的解答。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])
其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值中取较大值，而全局最优比较局部最优和前一天的全局最优。
int maxProfit(vector &prices) { if (prices.empty()) return 0; int n = prices.size(), g[n][3] = {0}, l[n][3] = {0}; for (int i = 1; i < prices.size(); ++i) { int diff = prices[i] - prices[i - 1]; for (int j = 1; j <= 2; ++j) { l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff); g[i][j] = max(l[i][j], g[i - 1][j]); } } return g[n - 1][2]; }

//可以最多买卖2次 int maxProfit(vector& prices) { int n = prices.size(); int local[3]={0}; int global[3]={0}; int diff = 0; for(int i=1; i=1; --j){ local[j]=max(global[j-1]+max(diff,0), local[j]+diff); global[j]=max(local[j], global[j]); } } return global[2]; }

加油站 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
int canCompleteCircuit(vector& gas, vector& cost) { int n=gas.size(); int total=0,sum=0,start=0; for(int i=0; i

分发糖果 输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
int candy(vector& ratings) { intn = ratings.size(); vector tmp(n,1); int sum=0; for(int i=1; iratings[i-1]){ tmp[i]=tmp[i-1]+1; } }for(int i=n-2; i>=0; --i){ if(ratings[i] > ratings[i+1]){ tmp[i]=max(tmp[i],tmp[i+1]+1); //注意这个地方是取max } }for(int i=0; i

柠檬水找零 输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
bool lemonadeChange(vector& bills) { int money[3]={0}; int n=bills.size(); for(int i=0; i0){ money[0]--; money[1]++; }else{ return false; } } else if(bills[i]==20){ if(money[1]>0 && money[0]>0){ money[0]--; money[1]--; money[2]++; } else if(money[0]>2){ money[0] -= 3; money[2]++; }else{ return false; } } } return true; }

    推荐阅读


    上一篇：穿越军~童铁旅｜军事主题夏令营|穿越军~童铁旅｜军事主题夏令营 男子汉成长 习惯养成

    下一篇：2018年10月27号