按要求补齐数组
给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:
int minPatches(vector<int>& nums, int n) {
int64_t tmp=1;
int res=0;
int i=0;
while(tmp<=n){
if(i<nums.size() && nums[i]<=tmp){
tmp=tmp+nums[i++];
}
else{
tmp = tmp+tmp;
res++;
}
}
return res;
}
删除重复字母保持最小字典序
给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入: "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<int>& nums) {
int n=nums.size();
int res=0;
for(int i=0;i<n;++i){
if(i>res) return false; //res表示最远能够到达的位置，此时表示到不了i的位置，直接返回
res = max(res,nums[i]+i);
}
return true;
}
跳跃游戏2
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
int jump(vector<int>& 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;i<n;i++){
tmp=max(tmp, i+nums[i]);
if(i>res || i==res && res<n-1){ //注意这个地方的条件
step+=1;
res=tmp;
}
if(res>=n-1) break; //以res为准，而不是tmp
}
return step;
}
买卖股票的最佳时机2
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
//只要后一天的价格大于前一天的价格就加diff
int maxProfit(vector<int>& prices) {
int n=prices.size();
if (n==0) return 0;
int mn=prices[0];
int res=0;
int diff=0;
for(int i=1;i<n;i++){
diff = prices[i]-prices[i-1];
if(diff>0)
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<int>& prices) {
int n=prices.size();
if(n<=1) return 0;
int a[n]={0};
int min=prices[0];
for(int i=1;i<n;++i){
if(prices[i]<min) min= prices[i];
a[i]=max(a[i-1], prices[i]-min );
}
return a[n-1];
}
买卖股票的最佳时机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<int> &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<int>& prices) {
int n = prices.size();
int local[3]={0};
int global[3]={0};
int diff = 0;
for(int i=1;i<n;++i){
diff = prices[i]-prices[i-1];
for(int j=2;j>=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<int>& gas, vector<int>& cost) {
int n=gas.size();
int total=0,sum=0,start=0;
for(int i=0;i<n;i++){
total += gas[i]-cost[i];
sum += gas[i]-cost[i];
if(total<0){
start=i+1;
total=0;
}
}
if(sum<0) return -1;
return start;
}
分发糖果
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> tmp(n,1);
int sum=0;
for(int i=1;i<n;++i){
if(ratings[i]>ratings[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<n;i++){
sum+=tmp[i];
}
return sum;
}
柠檬水找零
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
bool lemonadeChange(vector<int>& bills) {
int money[3]={0};
int n=bills.size();
for(int i=0; i<n; i++){
if(bills[i]==5){
money[0]++;
}
else if(bills[i]==10){
if(money[0]>0){
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;
}
