一、跳跃游戏I
55. 跳跃游戏 - 力扣（LeetCode）
class Solution {
public:bool canJump(vector<int>& nums) {//贪心+双指针 用left和right指向两个区间 然后maxpos表示下一层的最右端点int left=0,right=0,maxpos=0,n=nums.size();while(left<=right) //有可能会跳不到n-1的位置 比如说出现了很多个0{if(maxpos>=n-1) return true;for(int i=left;i<=right;++i) maxpos=max(maxpos,nums[i]+i);//找到之后更新区间left=right+1;right=maxpos;}return false;}
};二、跳跃游戏II
45. 跳跃游戏 II - 力扣（LeetCode）
解法1 ：动态规划
class Solution {
public:int jump(vector<int>& nums) {//动态规划的思想 dp[i]表示以i位置为结尾时的最小步数int n=nums.size();vector<int> dp(n,INT_MAX);dp[0]=0;for(int i=1;i<n;++i)for(int j=0;j<i;++j)if(nums[j]+j>=i) dp[i]=min(dp[i],dp[j]+1);return dp[n-1];}
};解法2：贪心 +双指针
class Solution {
public:int jump(vector<int>& nums) {//贪心+双指针 用left和right指向两个区间 然后maxpos表示下一层的最右端点int left=0,right=0,maxpos=0,ret=0,n=nums.size();while(left<=right) //有可能会跳不到n-1的位置 比如说出现了很多个0{if(maxpos>=n-1) return ret;for(int i=left;i<=right;++i) maxpos=max(maxpos,nums[i]+i);//找到之后更新区间left=right+1;right=maxpos;++ret;}return -1;}
};三、加油站
134. 加油站 - 力扣（LeetCode）
四、距离相等的条形码
1054. 距离相等的条形码 - 力扣（LeetCode）
class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& nums) {//贪心 隔一个放一个 要顺便统计最多的那个int n=nums.size();unordered_map<int,int> hash;int maxval=0,maxcount=0;for(auto&e:nums)if(maxcount<++hash[e]){maxcount=hash[e];maxval=e;}//开始先放最大的数vector<int> ret(n);int index=0;for(int i=0;i<maxcount;++i){ret[index]=maxval;index+=2;}hash.erase(maxval);//开始放后面的数字for(auto&[x,y]:hash)for(int i=0;i<y;++i){if(index>=n) index=1;ret[index]=x;index+=2;}return ret;}
};五、合并区间
56. 合并区间 - 力扣（LeetCode）
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& nums) {//区间问题 按照左端点排序sort(nums.begin(),nums.end());int n=nums.size();//合并区间//用left和right来标记两个区间//如果left right a b 如果重叠了a<=right right=max(right,b)//如果没有重叠 将left和right丢到ret中 然后更新int left=nums[0][0],right=nums[0][1];vector<vector<int>> ret;for(int i=1;i<n;++i){int a=nums[i][0],b=nums[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;}
};六、无重叠区间
435. 无重叠区间 - 力扣（LeetCode）
class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& nums) {sort(nums.begin(),nums.end());int n=nums.size();int ret=0;int left=nums[0][0],right=nums[0][1];for(int i=1;i<n;++i){int a=nums[i][0],b=nums[i][1];if(a<right) {right=min(right,b);++ret;} //移除右端点较大的区间 更新右区间else right=b;}return ret;}
};七、用最少数量的箭引爆气球
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
class Solution {
public:int findMinArrowShots(vector<vector<int>>& nums) {//只要出现重叠区间，就可以用一只箭射穿sort(nums.begin(),nums.end());int n =nums.size();int left=nums[0][0],right=nums[0][1]; //保留的是交集int ret=1;for(int i=1;i<n;++i){int a=nums[i][0],b=nums[i][1];if(a<=right)//如果有交集 {right=min(right,b);}else //说明没有交集{right=b;++ret;}}return ret;}
};八、俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题 - 力扣（LeetCode）
class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {//重写排序+贪心+二分int n=e.size();sort(e.begin(),e.end(),[&e](const vector<int>&v1, const vector<int>&v2){return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];});vector<int> ret;ret.emplace_back(e[0][1]);for(int i=1;i<n;++i){int b=e[i][1];//如果我比最后一个都大 我直接尾插if(b>ret.back()) ret.emplace_back(b);else //否则就二分{int left=0,right=ret.size()-1;while(left<right){int mid=(left+right)>>1;if(ret[mid]<b) left=mid+1;else right=mid;}ret[left]=b;}}return ret.size();}
};九、堆箱子
面试题 08.13. 堆箱子 - 力扣（LeetCode）
class Solution {
public:int pileBox(vector<vector<int>>& nums) {sort(nums.begin(),nums.end());int n=nums.size();//23 54 64 67//dp[i]表示以i位置为结尾的最长递增子序列的长度vector<int> dp(n);for(int i=0;i<n;++i) dp[i]=nums[i][2];for(int i=1;i<n;++i)//开始往前找for(int j=0;j<i;++j) if(nums[i][0]>nums[j][0]&&nums[i][1]>nums[j][1]&&nums[i][2]>nums[j][2])dp[i]=max(dp[i],dp[j]+nums[i][2]);return *max_element(dp.begin(),dp.end()); }
};
