今天独立完成的题目达到一半了，欣慰。

1. K 次取反后最大化的数组和

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

看着写着都挺简单，无意识中使用的方法其实就是贪心。看来说的挺对，贪心有时候就是看着是“常识性”的东西，但有时候又非常精巧。

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::sort;
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size()&&nums[i]<0&&k>0;++i) {
            nums[i]*=-1;
            --k;
        }
        sort(nums.begin(),nums.end());
        if (k%2==0) return Sum(nums);
        else {
            nums[0]*=-1;
            return Sum(nums);
        }

    }
    int Sum(vector<int>& nums) {
        int sum=0;
        for (int i=0;i<nums.size();++i) {
            sum+=nums[i];
        }
        return sum;
    }
};

2. 加油站

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

暴力解法过不了一个特定用例。

本题是从全局最优的角度思考问题。

for循环适合模拟从头到尾的遍历，⽽while循环适合模拟环形遍历。

代码

#include <vector>
#include <algorithm>
using std::vector;
using std::min;
class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int minSur=INT_MAX;
        int curSum=0;
        for (int i=0;i<gas.size();++i) {
            int rest=gas[i]-cost[i];
            curSum+=rest;
            minSur=min(minSur,curSum);
        }
        if (curSum<0) return -1;
        if (minSur>=0) return 0;
        for (int i=gas.size()-1;i>=0;--i) {
            minSur+=gas[i]-cost[i];
            if (minSur>=0) return i;
        }
        return -1;
    }
};

3. 最长公共子序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

和最长公共子序列类似，但不要求连续，所以递推公式有所变化。

如果要求连续，则当前元素不等时不必做任何动作，值默认为0，也就是清零了。

如果不要求连续，则当前元素不相等时，需要取一个最大值，在dp两个维度中选一个退一步，两者间的最大值。

代码

#include <vector>
#include <string>
using std::string;
using std::vector;
using std::max;
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int res=0;
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for (int i=1;i<=text1.size();++i) {
            for (int j=1;j<=text2.size();++j) {
                if (text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                res=max(res,dp[i][j]);
            }
        }
        return res;
    }
};

4. 不相交的线

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

其实只要序列顺序不变即可，所以实际上是求最长公共子序列（非连续）。

代码

#include <vector>

using std::vector;
using std::max;

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        for (int i=1;i<=nums1.size();++i) {
            for (int j=1;j<=nums2.size();++j) {
                if (nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

5. 柠檬水找零

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

凭直觉即可做出来。可以说是模拟，也可以说是贪心算法。

代码算法录说：

这道题⽬可以告诉⼤家，遇到感觉没有思路的题⽬，可以静下⼼来把能遇到的情况分析⼀
下，只要分析到具体情况了，⼀下⼦就豁然开朗了。

代码

#include <vector>
#include <map>
using std::map;
using std::vector;
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        map<int,int> box;
        box[5]=0;box[10]=0;box[20]=0;
        for (int i=0;i<bills.size();++i) {
            if (bills[i]==5) ++box[5];
            else if (bills[i]==10) {
                ++box[10];
                --box[5];
                if (box[5]<0) return false;
            } else {
                ++box[20];
                if (box[10]>0&&box[5]>0) {
                    --box[10];
                    --box[5];
                } else if (box[10]<=0&&box[5]>=3) {
                    box[5]-=3;
                } else return false;
            }
        }
        return true;
    }
};

6. 根据身高重建队列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

原来sort可以这样用的……

排序准则有两维的时候，要考虑先固定一维，再做另一维。

这里定义cmp函数时要用static。

代码

#include <vector>
#include <algorithm>
using std::sort;
using std::vector;
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> queue;
        for (int i=0;i<people.size();++i) {
            queue.insert(queue.begin()+people[i][1],people[i]);
        }
        return queue;
    }
    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];
    }
};

7. 分发糖果

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

两维的贪心，要保证左右两侧都符合性质。先固定一侧——正序遍历，再固定另一侧——反序遍历。

代码

#include <vector>
using std::vector;
using std::max;
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<candyVec.size();++i) {
            res+=candyVec[i];
        }
        return res;
    }
};

8. 用最少数量的箭引爆气球

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

自己完成的感觉思路不错，但是性能比较差。

答案的思路跟我是一样的，但我用了麻烦一点，但更容易理解的栈去做，所以性能差近一半。

事实上每次更新右边界即可，我把两个边界都更新了。

两种都放出来。

代码

#include <vector>
#include <stack>
#include <algorithm>
using std::sort;
using std::max;
using std::min;
using std::stack;
using std::vector;
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // sort(points.begin(),points.end(),cmp);
        // stack<vector<int>> s;
        // for (int i=points.size()-1;i>=0;--i) s.push(points[i]);
        // int res=0;
        // while (!s.empty()) {
        //     vector<int> balloon=s.top();
        //     s.pop();
        //     if (!s.empty()&&s.top()[0]<=balloon[1]) {
        //         vector<int> newBalloon(2);
        //         newBalloon[0]=s.top()[0];
        //         newBalloon[1]=min(balloon[1],s.top()[1]);
        //         s.pop();
        //         s.push(newBalloon);
        //     }
        //     else ++res;
        // }
        // return res;
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);
        int result = 1;
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) { 
            result++;
            }
            else {
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }
        return result;
    }
    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];
    }
};

9. 无重叠区间

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

跟上一题有点类似。排序后遍历。

我以左边界排序，先是正序遍历，有一个用例过不了，看了下随想录的思路，说按左边界排序的话最好反向遍历，正向的话有点麻烦。改了下方向的确过了。

此外，感觉随想录删区间的方法有些麻烦，我直接把要删的区间用前一个区间覆盖掉，正常通过且更方便。

代码

#include <vector>
#include <algorithm>
using std::sort;
using std::vector;
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int res=0;
        for (int i=intervals.size()-2;i>=0;--i) {
            if (intervals[i][1]>intervals[i+1][0]) {
                intervals[i]=intervals[i+1];
                ++res;
            }
        }
        return res;
    }
    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];
    }
};

10. 划分字母区间

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

记录每个字母出现的首尾顺序，不断更新串尾直到抵达。

部分细节没处理好，写的时间长了点。

第一段代码是没优化的，第二段简单优化了下。适当优化之后时间占用降了一半。再用一维数组代替map，空间占用也优化不少。

代码

未优化

#include <vector>
#include <map>
#include <string>
using std::string;
using std::vector;
using std::map;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        map<char,int> right,left;
        for (int i=97;i<=122;++i) {
            left[char(i)] = -1;
        }
        for (int i=0;i<s.size();++i) {
            if (left[s[i]]==-1) {
                left[s[i]]=i;
                right[s[i]]=i;
            }
            right[s[i]]=i;
        }
        vector<int> res;
        int start=-1;
        int des=-1;
        for (int i=0;i<s.size();++i) {
            if (start==-1) {
                start=i;
                des=right[s[i]];
            }
            des=des>right[s[i]]?des:right[s[i]];
            if (des==i) {
                res.push_back(des-start+1);
                start=-1;
                des=-1;
            }
        }
        return res;
    }
};

优化后

#include <vector>
#include <string>
using std::string;
using std::vector;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> right(26);
        for (int i=0;i<s.size();++i) right[int(s[i])-97]=i;
        vector<int> res;
        int start=-1;
        int des=-1;
        for (int i=0;i<s.size();++i) {
            if (start==-1) {
                start=i;
                des=right[int(s[i])-97];
            }
            des=des>right[int(s[i])-97]?des:right[int(s[i])-97];
            if (des==i) {
                res.push_back(des-start+1);
                start=-1;
                des=-1;
            }
        }
        return res;
    }
};