因为一些原因，要集中刷下LeetCode，目标半个月内每天十道Medium，加油！

1. 买卖股票的最佳时机 II

难度

• Easy
• Medium
• Hard

完成情况

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

思路

贪心算法

代码

#include <vector>

using std::vector;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size()<=1) return 0;
        int totalProfit=0;
        for (int i = 0;i<prices.size()-1;++i) {
            if (prices[i+1]>prices[i]) totalProfit+=prices[i+1]-prices[i];
        }
        return totalProfit;
    }
};

2. 三数之和

难度

• Easy
• Medium
• Hard

完成情况

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

思路

先排序，然后利用双指针。以i为三元组中第一个元素，给后续两个元素各以L和R指针指示，逐一验证。

代码

#include <vector>
#include <algorithm>

using std::vector;
using std::sort;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.size()<3) return res;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();++i) {
            if (nums[i]>0) return res;
            else if ( i>0 && nums[i]==nums[i-1]) continue;
            else {
                int L = i+1,R = nums.size()-1;
                while(L<R) {
                    if(nums[i]+nums[L]+nums[R]==0) {
                        vector<int> entry;
                        entry.push_back(nums[i]);
                        entry.push_back(nums[L]);
                        entry.push_back(nums[R]);
                        res.push_back(entry);
                        while(L<R && nums[L]==nums[L+1]) ++L;
                        while(L<R && nums[R]==nums[R-1]) --R;
                        ++L;--R;
                    }
                    else if (nums[i]+nums[L]+nums[R] >0) --R;
                    else ++L;
                }
            }
        }
        return res;
    }
};

3. 矩阵置零

难度

• Easy
• Medium
• Hard

完成情况

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

注：O(m+n)为独立完成，O(1)参考了答案。

思路

一旦一个元素为0，则其对应的行首和列首元素即变为无效信息，可利用其来存储标志。故利用第一行、第一列作为标志位。此外 ，还需先判断初始时第一行、第一列是否含0元素，如果是，则最后还应将第一行or第一列置零。

原地算法，要找到无效信息，将其作为标志位。

代码

#include <vector>

using std::vector;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool flag_row0=false,flag_col0=false;
        for (int i=0;i<matrix.size();++i) {
            if (matrix[i][0]==0) {
                flag_col0=true; 
                break;
            }
        }
        for (int j=0;j<matrix[0].size();++j) {
            if (matrix[0][j]==0) {
                flag_row0 = true; 
                break;
            }
        }
        for (int i=1;i<matrix.size();++i) {
            for (int j=1;j<matrix[0].size();++j) {
                if (matrix[i][j]==0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i=1;i<matrix.size();++i) {
            for (int j=1;j<matrix[0].size();++j) {
                if (matrix[i][0]==0 || matrix[0][j]==0) {
                    matrix[i][j]=0;
                }
            }
        }
        if (flag_row0) {
            for(int j=0;j<matrix[0].size();++j) matrix[0][j]=0;
        } 
        if (flag_col0) {
            for (int i =0;i<matrix.size();++i) matrix[i][0]=0;
        }
    }

4. 字母异位词分组

难度

• Easy
• Medium
• Hard

完成情况

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

思路

一开始想到用并查集，但实现不了。

别人的思路是使用每一个字符串排序后的字符串作为其标志，相同标志即归为一类。利用字符串到字符串数组的映射，分类这些字符串。最后返回结果。

代码

#include <vector>
#include <string>
#include <map>
#include <algorithm>

using std::vector;
using std::string;
using std::map;
using std::sort;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        if (strs.size()<=1) {
            res.push_back(strs);
            return res;
        }

        map<string,vector<string>> fa;

        for (int i=0;i<strs.size();++i) {
            string elem_sorted = strs[i];
            sort(elem_sorted.begin(),elem_sorted.end());
            fa[elem_sorted].push_back(strs[i]);
        }
        for (auto e:fa) res.push_back(e.second);
        return res;

    }
};

5. 无重复字符的最长子串

难度

• Easy
• Medium
• Hard

完成情况

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

思路

动态规划

代码

#include <string>
#include <math.h>

using std::max;
using std::string;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[128];
        for(int i=0;i<128;++i){
            last[i]=-1;
        }
        int n =s.size();
        int res=0;
        int start=0;
        for(int i=0;i<n;++i){
            int index=int(s[i]);
            start=max(start,last[index]+1);
            res=max(res,i-start+1);
            last[index]=i;
        }
        return res;
    }
};

6. 最长回文子串

难度

• Easy
• Medium
• Hard

完成情况

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

思路

二维的动态规划，用二维数组存储起点到终点是否构成回文串，在此基础上，左右每增加一个字符，即可判断是否为回文串。

遍历完毕即可得出答案。

代码

#include <string>
#include <vector>

using std::vector;
using std::string;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s=="" || s.size()<2) return s;

        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));

        int maxLen=1;
        int maxStart=0;
        int maxEnd=0;
        for (int r=1;r<s.size();++r) {
            for (int l=0;l<r;++l) {
                if (s[l]==s[r] && (r-l<=2 || dp[l+1][r-1]==true)) {
                    dp[l][r]=true;
                    if (r-l+1>maxLen) {
                        maxLen = r-l+1;
                        maxStart=l;
                        maxEnd=r;
                    }
                }
            }
        }
        return s.substr(maxStart,maxLen);
    }
};

7. 递增的三元子序列

难度

• Easy
• Medium
• Hard

完成情况

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

思路

先假定small是第一个元素，然后向后遍历。如果比small小，那就更新small继续遍历，如果比small大，就设为mid。

从断点继续遍历。如果比small小，更新small，如果在small和mid之间，更新mid，否则就是比mid大，成功。

代码

#include <vector>

using std::vector;

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size()<3) return false;
        int small=nums[0],mid;
        int k=1;
        while (k<nums.size()) {
            if (nums[k]<=small) small=nums[k];
            else {
                mid=nums[k];
                break;
            }
            ++k;
        }
        if (k==nums.size()-1) return false;
        for (int i=k+1;i<nums.size();++i) {
            if (nums[i]<=small) small=nums[i];
            else if (nums[i]<=mid) mid=nums[i];
            else return true;
        }
        return false;
    }
};

8. 使用最小花费爬楼梯

难度

• Easy
• Medium
• Hard

完成情况

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

思路

动态规划。也可将空间优化为O(1)。

代码

O(n)空间

#include <vector>

using std::vector;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1,0);
        for (int i=2;i<=cost.size();++i) {
            dp[i]=(dp[i-2]+cost[i-2]<dp[i-1]+cost[i-1])?(dp[i-2]+cost[i-2]):(dp[i-1]+cost[i-1]);
        }
        return dp[cost.size()];
    }
};

O(1)空间

#include <vector>
#include <algorithm>
using std::vector;
using std::min;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // vector<int> dp(cost.size()+1,0);
        // for (int i=2;i<=cost.size();++i) {
        //     dp[i]=(dp[i-2]+cost[i-2]<dp[i-1]+cost[i-1])?(dp[i-2]+cost[i-2]):(dp[i-1]+cost[i-1]);
        // }
        // return dp[cost.size()];
        vector<int> dp(2,0);
        for (int i=2;i<=cost.size();++i) {
            int sum = min(dp[0]+cost[i-2],dp[1]+cost[i-1]);
            dp[0]=dp[1];
            dp[1]=sum;
        }
        return dp[1];
    }
};

9. 不同路径

难度

• Easy
• Medium
• Hard

完成情况

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

思路

动态规划，注意dp数组初始化为1。

空间复杂度可以优化到O(n)，因为是一行一行更新，所以每次更新完一行，上一行就没用了。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,1));
        for(int r=1;r<m;++r) {
            for (int c=1;c<n;++c) {
                dp[r][c]=dp[r-1][c]+dp[r][c-1];
            }
        }
        return dp[m-1][n-1];
    }
};

10. 不同路径 II

难度

• Easy
• Medium
• Hard

完成情况

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

思路

在上一题基础上改进。初始化数组为1，正式计算dp数组前，将第一行第一列单独处理一遍，然后将障碍物所在点设为0，最后只计算不为0的点。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if(obstacleGrid[0][0]==1) return 0;
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,1));
        for (int c=0;c<n;++c) {
            if (obstacleGrid[0][c]==1) {
                for (int i=c;i<n;++i) dp[0][i]=0;
                break;
            }
        }
        for (int r=0;r<m;++r) {
            if (obstacleGrid[r][0]==1) {
                for (int i=r;i<m;++i) dp[i][0]=0;
                break;
            }
        }
        for (int r=1;r<m;++r) {
            for (int c=1;c<n;++c) {
                if (obstacleGrid[r][c]==1) dp[r][c]=0;
            }
        }
        for (int r=1;r<m;++r) {
            for (int c=1;c<n;++c) {
                if (dp[r][c]!=0) dp[r][c]=dp[r-1][c]+dp[r][c-1];
            }
        }
        return dp[m-1][n-1];
    }
};

11. 整数拆分

难度

• Easy
• Medium
• Hard

完成情况

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

思路

动态规划，先找规律，发现6以前固定，再往后拆分成3+另一个数即可。

因为从3开始 dp[3] 是小于3的。

这里误打误撞写出了O(n)时间复杂度的解法。

代码

#include <vector>

using std::vector;

class Solution {
public:
    int integerBreak(int n) {
        int m=n<7?6:n;
        vector<int> dp(m+1);
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        dp[3]=2;
        dp[4]=4;
        dp[5]=6;
        dp[6]=9;
        for (int i=7;i<m+1;++i) {
            dp[i]=3*dp[i-3];
        }
        return dp[n];
    }
};