目录
1. 最优除法
题目展示：
题目分析：
代码实现：
class Solution {
public:
string optimalDivision(vector<int>& nums)
{
int n=nums.size();
if(n==1) return to_string(nums[0]);
if(n==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<n;i++)
{
ret+="/"+to_string(nums[i]);
}
ret+=")";
return ret;
}
};2. 加油站
题目展示：
题目分析：
代码实现：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
{
int n=gas.size();
for(int i=0;i<n;i++)//依次枚举所有起点
{
int rest=0;//标记净收益
int step=0;
for(;step<n;step++)
{
int index=(i+step)%n;
rest=rest+gas[index]-cost[index];
if(rest<0) break;
}
if(rest>=0) return i;
i=i+step;
}
return -1;
}
};3. 坏了的计算器
题目链接：991. 坏了的计算器 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
int brokenCalc(int startValue, int target)
{
int ret=0;
while(target>startValue)
{
if(target%2==0) target/=2;
else target+=1;
ret++;
}
return ret+startValue-target;
}
};4. 可被三整除的最大和
题目链接：1262. 可被三整除的最大和 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
int maxSumDivThree(vector<int>& nums)
{
const int INF=0x3f3f3f3f;
int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;
for(auto x:nums)
{
sum+=x;
if(x%3==1)
{
if(x<x1) x2=x1,x1=x;
else if(x<x2) x2=x;
}
else if(x%3==2)
{
if(x<y1) y2=y1,y1=x;
else if(x<y2) y2=x;
}
}
//分类讨论
if(sum%3==0) return sum;
else if(sum%3==1) return max(sum-x1,sum-y1-y2);
else return max(sum-y1,sum-x1-x2);
}
};5. 单调递增的数字
题目链接：738. 单调递增的数字 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
int monotoneIncreasingDigits(int n)
{
string s=to_string(n);//转化为字符串
int i=0;
int m=s.size();
//找到第一个递减的位置
while(i+1<m&&s[i]<=s[i+1]) i++;
if(i+1==m) return n;
while(i-1>=0&&s[i]==s[i-1]) i--;
s[i]--;
for(int j=i+1;j<m;j++) s[j]='9';
return stoi(s);
}
};6. 合并区间
题目展示：
题目分析：
代码实现：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
sort(intervals.begin(),intervals.end());//排序
//合并区间
int left=intervals[0][0];
int right=intervals[0][1];
vector<vector<int>> ret;
for(int i=1;i<intervals.size();i++)
{
int a=intervals[i][0];
int b=intervals[i][1];
//有重叠部分
if(a<=right)
{
right=max(right,b);//求并集
}
else
{
ret.push_back({left,right});
left=a;
right=b;
}
}
ret.push_back({left,right});
return ret;
}
};7. 无重叠区间
题目链接：435. 无重叠区间 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
sort(intervals.begin(),intervals.end());
int left=intervals[0][0];
int right=intervals[0][1];
int ret=0;
for(int i=1;i<intervals.size();i++)
{
int a=intervals[i][0];
int b=intervals[i][1];
if(a<right)
{
ret++;
right=min(b,right);
}
else
{
right=b;
}
}
return ret;
}
};8. 用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points)
{
sort(points.begin(),points.end());
int right=points[0][1];
int ret=1;
for(int i=1;i<points.size();i++)
{
int a=points[i][0];
int b=points[i][1];
if(a<=right)
{
right=min(right,b);
}
else
{
ret++;
right=b;
}
}
return ret;
}
};