#include
#include
#include
#include
#include <string>
#include
using namespace std;
int findContentChildren(vector<int>&g,vector<int>&s)
{
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index = 0;
for(int i = 0; i < s.size(); ++i)
{
if(index < g.size() && g[index] <= s[i])
{
++index;
}
}
return index;
}
int WiggleMaxLen(const vector<int>& nums)
{
if(nums.size() <= 1)return nums.size();
int curDiff = 0, preDiff = 0, res = 1;
for(int i = 0; i < nums.size() - 1; ++i)
{
curDiff = nums[i + 1] - nums[i];
if((preDiff<=0 && curDiff > 0) || (preDiff>=0 && curDiff < 0))
{
preDiff = curDiff;
++res;
}
}
return res;
}
int maxSubArray(const vector<int>& nums)
{
int res = INT_MIN, cnt = 0;
for(int i = 0; i < nums.size(); ++i)
{
cnt += nums[i];
if(cnt > res)
{
res = cnt;
}
if(cnt < 0)
{
cnt = 0;
}
}
return res;
}
int maxProfit(const vector<int>& prices)
{
int res = 0;
for(int i = 1; i < prices.size(); ++i)
{
res += max(prices[i] - prices[i-1],0);
}
return res;
}
bool canJump(const vector<int>& nums)
{
if(nums.size() == 1)return true;
int cover = 0;
for(int i = 0; i < nums.size(); ++i)
{
cover = max(i + nums[i],cover);
if(cover >= nums.size() - 1)return true;
}
return false;
}
int jump(const vector<int>& nums)
{
if(nums.size() == 1)return 0;
int curDis = 0, nextDis = 0,res = 0;
for(int i = 0; i < nums.size(); ++i)
{
nextDis = max(nextDis, i + nums[i]);
if(i == curDis)
{
if(curDis != nums.size() - 1)
{
++res;
curDis = nextDis;
if(nextDis >= nums.size() - 1)break;
}
else break;
}
}
return res;
}
bool cmp(int a, int b)
{
return abs(a) > abs(b);
}
int largestsumAfterNegations(vector<int>& nums, int k)
{
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); ++i)
{
if(nums[i] < 0)
{
nums[i] *= -1;
--k;
}
}
while(k > 0)
{
nums[nums.size() - 1] *= -1;
--k;
}
int res = accumulate(nums.begin(),nums.end(),0);
return res;
}
int canCompleteCircle(const vector<int>& gas,const vector<int>& cost)
{
int curSum = 0,minVal = INT_MAX;
for(int i = 0; i < gas.size(); ++i)
{
int ret = gas[i] - cost[i];
curSum += ret;
if(curSum < minVal)
{
minVal = curSum;
}
}
if(curSum < 0) return -1;
if(minVal >= 0)return 0;
for(int i = gas.size() - 1; i >= 0; --i)
{
int ret = gas[i] - cost[i];
minVal += ret;
if(minVal >= 0)
{
return i;
}
}
return -1;
}
int candy(const vector<int>& rattings)
{
vector<int>candyVec(rattings.size(),1);
for(int i = 1; i < rattings.size(); ++i)
{
if(rattings[i] > rattings[i-1])candyVec[i] = 1 + candyVec[i-1];
}
for(int i = rattings.size() - 2; i >= 0; --i)
{
if(rattings[i] > rattings[i + 1])
{
candyVec[i] = max(candyVec[i], 1 + candyVec[i]);
}
}
int res = accumulate(candyVec.begin(),candyVec.end(),0);
return res;
}
bool lemonChange(const vector<int>& bills)
{
int five = 0, ten = 0, twenty = 0;
for(int bill : bills)
{
if(bill == 5) ++five;
if(bill == 10)
{
if(five <= 0)return false;
++ten;
--five;
}
if(bill == 20)
{
if(five > 0 && ten > 0)
{
--five;
--ten;
++twenty;
}
else if(five >= 3)
{
five-=3;
++twenty;
}
else return false;
}
}
return true;
}
void print(const vectorint>>& nums)
{
for(auto v:nums)
{
for(auto num : v)
{
cout << num << " ";
}
cout << endl;
}
}
vectorint>> reconstructQueue(vectorint>>& people)
{
sort(people.begin(),people.end(),[](const vector<int> &a, const vector<int>& b) {
if(a[0] == b[0]) return a[1] < b[1]; else return a[0] > b[0];});
vectorint>>q;
for(int i = 0; i < people.size(); ++i)
{
int pos = people[i][1];
q.insert(q.begin()+pos,people[i]);
}
return q;
}
int findMinArrows(vectorint>>& bubbles)
{
if(bubbles.size() == 0)return 0;
sort(bubbles.begin(),bubbles.end(),[](const vector<int>&a,const vector<int>&b){
return a[0] < b[0];
});
int res = 1;
for(int i = 1; i < bubbles.size(); ++i)
{
if(bubbles[i][0] > bubbles[i-1][1])
{
++res;
}
else
{
bubbles[i][1] = min(bubbles[i][1],bubbles[i-1][1]);
}
}
return res;
}
int eraseOverlapIntervals(vectorint>>& intervals)
{
if(intervals.size() == 0)return 0;
sort(intervals.begin(),intervals.end(), [](const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
});
int cnt = 1;
int end = intervals[0][1];
for(int i = 1; i < intervals.size(); ++i)
{
if(end <= intervals[i][0])
{
++cnt;
end = intervals[i][1];
}
}
return intervals.size() - cnt;
}
vector<int>partitionLabels(string s)
{
int hash[27] = {0};
for(int i = 0; i < s.size(); ++i)
{
hash[s[i] - 'a'] = i;
}
vector<int>res;
int left = 0, right = 0;
for(int i = 0; i < s.size(); ++i)
{
right = max(right,hash[s[i] -'a']);
if(i == right)
{
res.push_back(right - left + 1);
left = i + 1;
}
}
return res;
}
void print(const vector<int>& v)
{
for(auto num : v)
{
cout << num << " ";
}
cout << endl;
}
vectorint>>merge(vectorint>>& intervals)
{
if(intervals.size() == 0)return {};
sort(intervals.begin(),intervals.end(),[](const vector<int>& a, const vector<int>&b){
return a[0] < b[0];
});
vectorint>>res;
res.push_back(intervals[0]);
for(int i = 1; i < intervals.size(); ++i)
{
if(res.back()[1] >= intervals[i][0])
{
res.back()[1] = max(res.back()[1],intervals[i][1]);
}
else
{
res.push_back(intervals[i]);
}
}
return res;
}
int increasDigits(int n)
{
string num = to_string(n);
int flag = 0;
for(int i = num.size() - 1; i >= 0; --i)
{
if(num[i-1] > num[i])
{
flag = i;
--num[i-1];
}
}
for(int i = flag; i < num.size(); ++i)
{
num[i] = '9';
}
return stoi(num);
}
int maxProfit(vector<int>& prices,int fee)
{
int res = 0;
int minPrice = prices[0];
for(int i = 1; i < prices.size(); ++i)
{
if(prices[i] < minPrice)
{
minPrice = prices[i];
}
if(prices[i] >= minPrice && prices[i] <= minPrice + fee)
{
continue;
}
if(prices[i] > minPrice + fee)
{
res += prices[i] - minPrice - fee;
minPrice = prices[i] - fee;
}
}
return res;
}
int main()
{
//分发饼干
vector<int>g{1,2,3},s{1,1};
cout << findContentChildren(g,s) << endl;
//LeetCode376摆动序列
vector<int>nums{1,7,4,9,2,5};
cout << WiggleMaxLen(nums) << endl;
//LeetCode53 最大子序和
nums = {-2,1,-3,4,-1,2,1,-5,4};
cout << maxSubArray(nums) << endl;
//LeetCode122 买卖股票II
nums = {7,1,5,3,6,4};
cout << maxProfit(nums) << endl;
//LeetCde55 跳跃游戏
nums = {2,3,1,1,4};
cout << canJump(nums) << endl;
//LeetCode45 跳跃游戏II
cout << jump(nums) << endl;
//LeetCode1005 k次取反后最大化的数组和
nums = {3,-1,0,2};
int k = 3;
cout << largestsumAfterNegations(nums,k) << endl;
//LeetCode134 加油站
vector<int>gas{1,2,3,4,5};
vector<int>cost{3,4,5,1,2};
cout << canCompleteCircle(gas,cost) << endl;
//LeetCode135 分发糖果
vector<int>children{1,0,2};
cout << candy(children) << endl;
//LeetCode860 柠檬水换钱
vector<int>bills{5,5,5,10,20};
cout << lemonChange(bills) << endl;
//LeetCode406 根据身高重建队列
vectorint>> people{{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
print(reconstructQueue(people));
//LeetCode452 用最少量的箭引爆气球
vectorint>>bubbles{{10,16},{2,8},{1,6},{7,12}};
cout << findMinArrows(bubbles) << endl;
//LeetCode435 无重叠区间
vectorint>>buckets{{1,2},{2,3},{3,4},{1,3}};
cout << eraseOverlapIntervals(buckets) << endl;
//LeetCode763 划分字母区间 ";
string s0 = "abcbcbacadefegdehijhklij";
print(partitionLabels(s0));
//LeetCode56 合并区间
vectorint>>intervals{{1,3},{2,6},{8,10},{15,18}};
print(merge(intervals));
//LeetCode738 单调递增数字
int N = 332;
cout << increasDigits(N) << endl;
//LeetCode714 买卖股票包含手续费
vector<int>prices{1,3,2,8,4,9};
cout << maxProfit(prices,2) << endl;
return 0;
}