455. 分发饼干
饼干从大的开始利用，优先满足胃口大的；
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res=0;
int index=s.size()-1;
for(int i=g.size()-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]) {//注意index不要越界,index的范围
res+=1;
index-=1;
}
}
return res;
}
};另一种方法：
饼干从小的开始利用，优先满足胃口小的；
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int index=0;
int res=0;
for(int i=0;i<s.size();i++){
if(index<g.size()&&g[index]<=s[i]){
res+=1;
index+=1;
}
}
return res;
}
};376. 摆动序列
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int res=1;
if(nums.size()<=1) return nums.size();
int pre=0;
int cur=0;
for(int i=0;i<nums.size()-1;i++){
cur=nums[i+1]-nums[i];
if((pre>=0&&cur<0)||(pre<=0&&cur>0)){
res++;
pre=cur;
}
}
return res;
}
};53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=INT_MIN;
int count=0;
for(int i=0;i<nums.size();i++){
count+=nums[i];
if(count>res)res=count;
if(count<0) count=0;
}
return res;
}
};122. 买卖股票的最佳时机 II
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res=0;
for(int i=0;i<prices.size()-1;i++){
res+=max(prices[i+1]-prices[i],0);
}
return res;
}
};55. 跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover=0;
for(int i=0;i<=cover;i++){
cover=max(i+nums[i],cover);
if(cover>=nums.size()-1) return true;
}
return false;
}
};45. 跳跃游戏 II
class Solution {
public:
int jump(vector<int>& nums) {
int res=0;
int cur=0;
int next=0;
if(nums.size()==1)return 0;
for(int i=0;i<nums.size();i++){
next=max(i+nums[i],next);
if(i==cur){
res++;
cur=next;
if(cur>=nums.size()-1){
break;
}
}
}
return res;
}
};1005. K 次取反后最大化的数组和
class Solution {
public:
static bool cmp(int a,int b){
return abs(a)>abs(b);
}
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(),cmp);
for(int i=0;i<nums.size();i++){
if(nums[i]<0&&k>0){
nums[i]*=-1;
k--;
}
}
if(k%2==1){
nums[nums.size()-1]*=-1;
}
int res=0;
for(int i=0;i<nums.size();i++){
res+=nums[i];
}
return res;
}
};134. 加油站
感觉加油站这题做的很晕
class Solution {
public:
//1.从0遍历结束之后，rest>=0，就返回0
//2.从0遍历结束之后，rest<0，返回-1
//3.从0遍历，发现中间有rest<0,但整体>=0，那就从后遍历找rest累计能补掉这个漏洞的
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum=0;
int min=INT_MAX;
for(int i=0;i<cost.size();i++){
int rest=gas[i]-cost[i];
curSum+=rest;
if(curSum<min){
min=curSum;
}
}
if(min>=0)return 0;
if(curSum<0)return -1;
for(int i=cost.size()-1;i>=0;i--){
int rest=gas[i]-cost[i];
min+=rest;
if(min>=0)return i;
}
return -1;
}
};方法2：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum=0;
int totalSum=0;
int start=0;
for(int i=0;i<gas.size();i++){
curSum+=gas[i]-cost[i];
totalSum+=gas[i]-cost[i];
if(curSum<0){
start=i+1;
curSum=0;
}
}
if(totalSum<0) return -1;
return start;
}
};135. 分发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int>candyVec(ratings.size(),1);
for(int i=1;i<ratings.size();i++){
if(ratings[i]>ratings[i-1]) candyVec[i]=candyVec[i-1]+1;
}
//从后往前遍历
for(int i=ratings.size()-2;i>=0;i--){
if(ratings[i]>ratings[i+1]) candyVec[i]=max(candyVec[i],candyVec[i+1]+1);
}
int res=0;
for(int i=0;i<ratings.size();i++){
res+=candyVec[i];
}
return res;
}
};860. 柠檬水找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0,ten=0,twenty=0;
for(int i=0;i<bills.size();i++){
if(bills[i]==5) five++;
if(bills[i]==10){
if(five==0)return false;
else {
five--;
ten++;
}
}
if(bills[i]==20){
if(ten>0&&five>0){
ten--;
five--;
twenty++;
}
else if(five>=3){
five-=3;
twenty++;
}
else return false;
}
}
return true;
}
};406. 根据身高重建队列
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
if(a[0]==b[0])return a[1]<b[1];
return a[0]>b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
vector<vector<int>>que;
for(int i=0;i<people.size();i++){
int position=people[i][1];
que.insert(que.begin()+position,people[i]);
}
return que;
}
};改进：容器使用了list,list底层是链表实现的，比起vector能减少时间复杂度
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
if(a[0]==b[0])return a[1]<b[1];
return a[0]>b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
list<vector<int>>que;
for(int i=0;i<people.size();i++){
int position=people[i][1];
auto it=que.begin();
while(position--){
it++;
}
que.insert(it,people[i]);
}
return vector<vector<int>>(que.begin(),que.end());
}
};452. 用最少数量的箭引爆气球
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>&b){
return a[0]<b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int res=1;
for(int i=1;i<points.size();i++){
if(points[i][0]>points[i-1][1]){
res++;
}
else{
points[i][1]=min(points[i-1][1],points[i][1]);
}
}
return res;
}
};435. 无重叠区间
按照区间末端进行排序
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
return a[1]<b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int count=1;
int end=intervals[0][1];
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>=end){
count++;
end=intervals[i][1];
}
else continue;
}
return intervals.size()-count;
}
};按照区间前段进行排序：
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
return a[0]<b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int count=0;
int end=intervals[0][1];
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]>=end){
end=intervals[i][1];
}
else {
count++;
end=min(end,intervals[i][1]);
}
}
return count;
}
};763. 划分字母区间
class Solution {
public:
vector<int> partitionLabels(string s) {
//初始化每个字符的最远位置
int hash[26]={0};
//遍历 初始化
for(int i=0;i<s.size();i++){
hash[s[i]-'a']=i;
}
//遍历，寻找最远距离
vector<int>res;
int left=0;
int right=0;
for(int i=0;i<s.size();i++){
right=max(right,hash[s[i]-'a']);
if(right==i){
res.push_back(right-left+1);
left=right+1;
}
}
return res;
}
};56. 合并区间
class Solution {
public:
static bool cmp(const vector<int>& a,const vector<int>& b){
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
vector<vector<int>>res;
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
if(intervals[i][0]<=res.back()[1]){
res.back()[1]=max(res.back()[1],intervals[i][1]);
}
else {
res.push_back(intervals[i]);
}
}
return res;
}
};738. 单调递增的数字
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum=to_string(n);
//flag标记从哪里开始被赋值成9
int flag=strNum.size();
for(int i=strNum.size()-1;i>0;i--){
if(strNum[i]<strNum[i-1]){
flag=i;
strNum[i-1]--;
}
}
for(int i=flag;i<strNum.size();i++){
strNum[i]='9';
}
return stoi(strNum);
}
};
![[C++] C++11详解 (一)](https://i-blog.csdnimg.cn/direct/162083f688e54458963640439ee57f22.png)
