LeetCode刷题记录

发表于   |   更新于 | 分类于

想养成刷题的习惯，之前刷过一点，但校招之后就断了，现在想捡起来，定个小目标，从头开始刷题吧，看能坚持多久。

1. Two Sum

2019/4/16，易。

这题以前做过，记得第一次做的时候应该是用的最蠢的两重遍历方法相加求解，毫无疑问超时了，隐约记得可以使用查找目标值-某个值是否存在该vector中来反向求解，简单写了一下，通过了。其实是一个反向思维的题，正面求解超时，则反向来求。仍然属于蛮力法的范畴，n2时间复杂度，1空间复杂度，LeetCode平台耗时136ms。

尝试降低时间复杂度，想到以空间换时间，在查找目标值-某个值的时候，上述蛮力法使用std::find方法，说白了也是一层遍历，这层遍历目的是为了查找差值是否存在于vector中并返回下标，自然可以想到用哈希表来代替这一层遍历。当然，事先需要遍历一次原数组构建哈希表。如此时间复杂度n，空间复杂度n。

最终代码如下，本版本耗时仅16ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> map;//哈希表
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            map[nums[i]]=i;
        }
        for(auto it=nums.begin();it!=nums.end();it++){
            auto com=map.find(target-*it);
            if(com!=map.end()&&com->second!=it-nums.begin()){
                res.push_back(it-nums.begin());
                res.push_back(com->second);
                return res;
            }
        }
        return res;
    }
};

2. Add Two Numbers（again）

2019/4/19，中。

平心而论是个比较简单的链表题了，但是太久不做题竟然觉得很难理清楚，这也说明了常做题保持手感很重要。

本题也没啥特别的方法，注意循环进位即可，另外链表的题往往一开始会定义两个变量，一个用于最后返回，一个用来遍历处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res=new ListNode(-1);
        ListNode* p=res;
        int carry=0;//进位
        while(l1||l2){
            int sum = (l1?l1->val:0) + (l2?l2->val:0) + carry;
            carry=sum/10; 
            p->next = new ListNode(sum%10);
            p=p->next;
            if(l1)
            {
                l1=l1->next;
            }
            if(l2)
            {
                l2=l2->next;
            }
        }
        if(carry==1)
            p->next = new ListNode(carry);
        return res->next;
    }
};

3. Longest Substring Without Repeating Characters（again）

2019/4/21，中。

一道经典dp题，准备找工作的时候刷过，以为很简单，但写的时候却发现细节又已经遗忘了，虽然最后还是一遍过了，但还是感慨得要经常刷题保持手感啊，忘性太大了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int lengthOfLongestSubstring(string s) {
        if(s.size()<=0)
            return 0;
        vector<int> dp(s.size(),0);
        dp[0]=1;
        map<char,int> m;
        m[s[0]]=0;
        for(int i=1;i<s.size();i++){
            auto it=m.find(s[i]);
            if(it==m.end()){
                dp[i]=dp[i-1]+1;
            }else{
                if(i-it->second>dp[i-1]){
                    dp[i]=dp[i-1]+1;
                }else{
                    dp[i]=i-m[s[i]];
                }
            }
            m[s[i]]=i;
        }
        int max=dp[0];
        for(int i=1;i<dp.size();i++){
            if(dp[i]>max)
                max=dp[i];
        }
        return max;       
    }

4.Median of Two Sorted Arrays（again）

2019/4/22，难。

想法一开始就很明确，将两个有序数组Merge成一个新的有序数组就是了，然后直接返回中间值即可。后来稍微改进了下代码，因为Merge其实只需要Merge到中间数即可，后面的数并不需要处理了，所以去除了冗余排序，感觉时间复杂度是n+m，空间复杂度也是n+m。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        int i=0,j=0;
        int length1=nums1.size(),length2=nums2.size();
        int sumLen=length1+length2;
        int midIndex=(length1+length2)/2;
        while(res.size()<midIndex+1){
            if (j == length2 || (i < nums1.size() && nums1[i] < nums2[j])) {
			    res.push_back(nums1[i]);
			    i++;
		    }
		    else if (i == length1 || (j<nums2.size() && nums1[i] >= nums2[j])) {
			    res.push_back(nums2[j]);
			    j++;
		    }
        }
        if(sumLen%2==1){
            return res.back();
        }else{
            double r=(res[res.size()-1]+res[res.size()-2])/2.0;
            return r;
        }
    }

但后来发现题目要求的时间复杂度是log(n+m)，才感觉到为什么这道题目难度级别是hard，不过我习惯从这个要求的时间复杂度就得到该题应该要使用二分查找或者是二分查找的变形，看了网上的解答，应该是查找第K小数字的变体，最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int length1=nums1.size(),length2=nums2.size();
        int sumLen=length1+length2;
        if(sumLen%2==1){
            return FindKth(nums1,length1,nums2,length2,sumLen/2+1);
        }else{
            return (FindKth(nums1,length1,nums2,length2,sumLen/2)+
                    FindKth(nums1,length1,nums2,length2,sumLen/2+1))/2.0;
        }
    }
private:
    double FindKth(vector<int>& nums1,int length1,vector<int>& nums2,int length2,int k){
        if(length1>length2)
            return FindKth(nums2,length2,nums1,length1,k);
        if(length1==0)
            return nums2[k-1];
        if(k==1)
            return min(nums1[0],nums2[0]);
        int pa=min(k/2,length1),pb=k-pa;
        if(nums1[pa-1]<nums2[pb-1]){
            vector<int> tmp(nums1.begin()+pa,nums1.end());
            return FindKth(tmp,length1-pa,nums2,length2,k-pa);
        }else if(nums1[pa-1]>nums2[pb-1]){
            vector<int> tmp(nums2.begin()+pb,nums2.end());
            return FindKth(nums1,length1,tmp,length2-pb,k-pb);
        }else{
            return nums1[pa-1];
        }
    }
};

参考https://blog.csdn.net/lis_12/article/details/53128594

5.Longest Palindromic Substring（again）

2019/4/23，中。

求最长回文子串，看到题目之后我感觉这是一道dp题，但是太菜了，还是写不出来，查了解析后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<=0)
            return "";
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),true));
        
        int max=1;
        int start=0;
        for(int i=2;i<=s.size();i++){//i表示子串长度
            for(int leftIdx=0;leftIdx<=s.size()-i;leftIdx++){//j表示子串起始坐标
                int rightIdx=leftIdx+i-1;
                if(s[leftIdx]==s[rightIdx]&&dp[leftIdx+1][rightIdx-1]){
                    dp[leftIdx][rightIdx]=true;
                    max=i;
                    start=leftIdx;
                }else{
                    dp[leftIdx][rightIdx]=false;
                }
            }
        }
        return s.substr(start,max);
    }
};

时间复杂度n2，空间复杂度n2。

利用中心扩展法可以将空间复杂度降低到1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<=1)
            return s;
        int start=0,end=0;
        for(int i=0;i<s.size();i++){
            int len1=expandAroundCenter(s,i,i);//奇数
            int len2=expandAroundCenter(s,i,i+1);//偶数
            int len=max(len1,len2);
            if(len>end-start){
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        return s.substr(start,end-start+1);
    }
private:
    int expandAroundCenter(string& s,int left,int right){
        int len = s.size();
	    while (left>=0 && right<len && s[left] == s[right]) 
	    {
		    left--;
		    right++;
	    }
	    return right-left-1;//返回长度
    }
};

最后还有一种Manacher方法，能将时间复杂度降到n，同时空间复杂度也是n，没看得太明白，以后再说。http://www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html

6.ZigZag Conversion

2019/4/24，中。

之字形排列字符串然后按行打印。

刚看到时候第一种办法就是自己定义一个二维数组排一下然后按行输出得了，蛮力法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    //蛮力法
    string convert(string s, int numRows) {
        if(numRows==1)
            return s;
        //构建一个二维字符数组存数组
        vector<vector<string>> array(numRows,vector<string>(s.size()/2+1,"null"));
        int i=0,j=0;
        bool direction=true;//记录方向，ture表示向下，false向上
        for(int idx=0;idx<s.size();idx++){
            array[i][j]=s[idx];
            if(direction){
                i++;
                if(i==numRows){
                    j++;
                    i=i-2;
                    direction=false;
                }
            }else{
                i--;
                j++;
                if(i==-1){
                    i=i+2;
                    j--;
                    direction=true;
                }
            }
        }
        string res;
        for(int p=0;p<numRows;p++){
            for(int q=0;q<s.size()/2+1;q++){
                if(array[p][q]!="null"){
                   res+=array[p][q]; 
                }
            }
        }
        return res;       
    }
};

提交后虽然通过了，但花费时间560ms，空间占有400MB，感觉效率太低了，于是尝试另一种方法。

另一种方法也很好想到，既然是按某种规律排列并输出，那自然把规律找出来就好了，多在草稿纸上排了几个用例后发现每一行的间隔都是有规律的，主要规律是2*numRows-2，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    //找规律直接输出
    string convert(string s, int numRows) {
        if(numRows==1)
            return s;
        int maxInterval=2*numRows-2;//最大间隔
        string res="";
        for(int i=0;i<numRows;i++){
            int startIdx=i;
            int interval=maxInterval-2*i;
            if(i==numRows-1)
                interval=maxInterval;
            while(startIdx<s.size()){
                res+=s[startIdx];
                startIdx+=interval;
                interval=(maxInterval-interval!=0)?maxInterval-interval:interval;
            }
        }
        return res;
    }
};

提交后时间降到16ms，空间占有降低到10MB，效率提升还是很明显的。

这道题算是这几天做的比较顺利的题了，阿弥陀佛。

7.Reverse Integer

2019/4/25，易。

反转一个整数，本来以为挺简单的，但是却没有注意大数越界，又琢磨了一会儿，要注意大数问题啊。

两种差不多的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int reverse(int x) {
        //注意要转换类型，否则大数会出错
	    long long int absX = abs((long long int)x);
	    string tmp = to_string(absX);
	    for (int i = 0; i < tmp.size() / 2; i++) {
		    char a = tmp[i];
		    tmp[i] = tmp[tmp.size() - 1 - i];
		    tmp[tmp.size() - 1 - i] = a;
	    }
	    long long int res = 0;
	    for (int i = 0; i < tmp.size(); i++) {
		    res = res * 10 + (tmp[i]-'0');
            if(res>INT_MAX)//注意要比较是否越界，因为这里已经是绝对值了，所以只需和INT_MAX比较
                return 0;
	    }
	    return (x < 0) ? (-1 * res) : res;
}
};

//查了下其他人的方法，可以有第二种写法，更为简单，如下：
class Solution {
public:
    int reverse(int x) {
        long long int res=0;
        while(x!=0){
            res=res*10+x%10;
            x=x/10;
            if(res> INT_MAX)
                return 0;
            if(res<INT_MIN)
                return 0;
        }
        return res;
    }
};

两种代码耗时都是4ms，空间占有也差不多，整体效率相仿。

8. String to Integer (atoi)

2019/4/26，中。

字符串转整数，需要注意大数问题、正负号、空格，题目里已经写得很清楚了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int myAtoi(string str) {
       //去除前面的空格
	    str.erase(0, str.find_first_not_of(" "));
	    //处理返回0的情况
	    if (str == "")
		    return 0;
	    if (!isdigit(str[0]) && str[0] != '-'&&str[0] != '+')
		    return 0;
	    if (str[0] == '-' || str[0] == '+') {
		    if (str.size() <= 1 || !isdigit(str[1]))
			    return 0;
	    }
	    //非0
	    bool positive = str[0] == '-' ? false : true;
	    if (str[0] == '-' || str[0] == '+')
		    str = str.substr(1);
	    long long int res = 0;
	    int i = 0;
	    while (i<str.size() && isdigit(str[i])) {
		    if (positive)
			    res = res * 10 + (str[i] - '0');
		    else 
			    res = res * 10 - (str[i] - '0');
		    if (res > INT_MAX)
			    return INT_MAX;
		    if (res < INT_MIN)
			    return INT_MIN;
		    i++;
	    }
	    return res;
    }
};

看了下其他提交，方法都大同小异，只不过大佬们写的C++代码要简洁一些，不像我写的那么臃肿，大佬们的代码就是在原字符串的基础上往后遍历处理，而我的代码里还用erase/substr方法把原字符串改来改去，导致时间上慢了几ms，慢慢练吧~

9.Palindrome Number

2019/4/27，易。

判断一个整数是否是回文数，最简单的方法就是转化成字符然后前后循环判断，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        string str=to_string(x);
        if(str.size()==1)
            return true;
        for(int i=0;i<str.size()/2;i++){
            if(str[i]!=str[str.size()-1-i])
                return false;
        }
        return true;
    }
};

运行时间32ms，内存8.4MB。

后来看到题目里的扩展，如何不转换成string进行判断？

想到回文数字其实就是前后读相同，那么将该数字对半分后应该能分成两个相同数字，比如1221，就分成12和12（后一个12从右往左读），而131就可以同样分成13和13（3用两次），根据这种想法写出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        //1、算出整数位数
        int len=0;
        int t=x;
        while(t!=0){
            len++;
            t/=10;
        }
        //2、拆分数字
        t=x;
        int tmp=0;
        int i=0;
        while(i<len/2){
            tmp=tmp*10+t%10;
            t/=10;
            i++;
        }
        //3、注意如果是奇数位数的整数，还需要将中间数重复利用一次
        if(len%2==1){
            tmp=tmp*10+t%10;
        }
        if(tmp==t)
            return true;
        return false;
    }
};

同样是32ms，内存8.2MB。

后来看了下大佬们的提交，大致思路和上述第二种方法相似，但大佬的代码更加精炼，把我代码中很多直白的部分都进一步浓缩了，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0|| (x!=0 &&x%10==0)) return false;
        int sum=0;
        //这里精炼后不需要再计算整数位数，直接用x>sum来循环
        while(x>sum)
        {
            sum = sum*10+x%10;
            x = x/10;
        }
        return (x==sum)||(x==sum/10);//位数是偶数，则x==sum；位数是奇数，则x==sum/10，不需
        						    //要像我代码中奇数位数的整数多进行一次处理，实在高呀~
    }
};

10.Regular Expression Matching（again)

2019/4/29，难。

一开始以为这道题和《剑指offer》上的某道题一样，遂用那道题的解法来进行求解，后发现有点问题，经过修补后写下如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    bool isMatch(string s, string p) {
        if(s!=""&&p=="")
            return false;
        //先进行一下简单的检查，这部分代码就是修补，很丑
        for(int i=0;i<p.size();i++){
            if(p[i]!='.'&&p[i]!='*'){
                if(s.find(p[i])==string::npos){
                    if(i==p.size()-1)
                        return false;
                    else{
                        if(p[i+1]!='*')
                            return false;
                    }
                }
            }
        }
        return matchCore(s,p);
    }
    
private:
    bool matchCore(string s,string p){
        if(s==""&&p=="")
            return true;
        if(s!=""&&p=="")
            return false;
        
        if(p[1]=='*'){
            if(s[0]==p[0]||(p[0]=='.'&&s!="")){
                return matchCore(s.substr(1),p)//*表示多个
                    ||matchCore(s.substr(1),p.substr(2))//*表示1个
                    ||matchCore(s,p.substr(2));//*表示0个
            }
            else{//不等，则*只能表示0个还有机会
                return matchCore(s,p.substr(2));
            }
        }
        else{
            if(s[0]==p[0]||(p[0]=='.'&&s!="")){
                return matchCore(s.substr(1),p.substr(1));
            }
        }
        return false;
    }
};

最终通过了，但是代码很丑，效率很低，整体用了五百多毫秒，内存占用17.5MB左右，效率太差了。

然后发现可以用DP来求解，研究后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    bool isMatch(string s, string p) {
        //代码中因为定义dp数组的时候默认值就是false，所以代码中对数组元素赋值false的语句都可删除，
        //但这里仍然写出来，是为了便于理解。
        //1、定义dp数组
        vector<vector<bool>> dp(s.size()+1,vector<bool>(p.size()+1,false));
        //2、赋值初始状态
        dp[0][0]=true;
        for(int i=1;i<=s.size();i++)//空模式不会匹配非空字符串
            dp[i][0]=false;
        //非空模式想要匹配空字符串，最后一个字符必须是*
        dp[0][1]=false;
        for(int i=2;i<=p.size();i++){
            if(p[i-1]=='*'&&dp[0][i-2])
                dp[0][i]=true;
            else
                dp[0][i]=false;
        }
        //3、计算
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=p.size();j++){
                if(s[i-1]==p[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='.')
                    dp[i][j]=dp[i-1][j-1];
                else if(p[j-1]=='*'){
                    if(j>=2){
                        if(s[i-1]!=p[j-2]&&p[j-2]!='.')//不匹配，*只能表示0次
                            dp[i][j]=dp[i][j-2];
                        else//匹配，*表示0/1/多次
                            dp[i][j]=dp[i][j-2]||dp[i-1][j]||dp[i-1][j-2];
                    }else{
                        dp[i][j]=false;
                    }
                }else
                    dp[i][j]=false;
            }
        }
        return dp[s.size()][p.size()];
    }
};

利用DP解法耗时降到8ms，内存占用降低到9.1MB，主要思路参考https://zhuanlan.zhihu.com/p/40294596，但个人认为该链接里dp最后一种情况推导公式有误，应该是我代码中写的dp[i][j]=dp[i][j-2]||dp[i-1][j]||dp[i-1][j-2]，且该链接给出的最后代码感觉有点问题，应该不能直接用，只是个伪代码吧，不过主要思路是阐述得很清楚了。

11. Container With Most Water

2019/4/30，中。

一开始看到这道题的时候想的是用最直接的暴力法——挨个遍历，但是可以预料到耗时肯定会超出限制，所以想着改进该方法。想到在暴力遍历中其实有很多种情况是重复的，所以想到用DP数组先存前一种情况的值，再根据已知情况的值来进行当前情况的求解，能够省去一重循环，遂写出下列代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        vector<int> dp(height.size(),0);
        for(int i=1;i<height.size();i++){
            int max=dp[i-1];
            for(int j=0;j<i;j++){
                int volume=(i-j)*min(height[i],height[j]);
                if(volume>max)
                    max=volume;
            }
            dp[i]=max;
        }
        return dp[height.size()-1];
    }
};

提交，通过测试，但效率极低，耗时1300ms左右，占用内存10MB左右，仍需改进，该方法的时间复杂度是n2，所以考虑是否有时间复杂度为n的方法，看到一年前做这道题时用的是前后双指针法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<2)
            return 0;
        int i=0,j=height.size()-1;
        int maxSize=0;
        while(i<j)
        {
            int currentSize=(j-i)*min(height[i],height[j]);
            if(currentSize>maxSize)
                maxSize=currentSize;
            height[i]<height[j]?(++i):(--j);
        }
        return maxSize;
    }
};

耗时20ms，效率提升明显，主要重点在height[i]<height[j]?(++i):(--j)，即每次收缩的时候都收缩边界较小的那一侧，因为这样就可以省去很多冗余情况的判断。

12. Integer to Roman

2019/5/2，中。

整数转换成罗马数字，整数范围1~3999。

按部就班就行，首先写出的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    string intToRoman(int num) {
        map<int,string> intToString={
            {1,"I"},
            {5,"V"},
            {10,"X"},
            {50,"L"},
            {100,"C"},
            {500,"D"},
            {1000,"M"}
        };
        string res="";
        int tmp=num;
        int p=1;//表示数位
        for(;tmp!=0;tmp/=10){
            int digit=tmp%10;
            if(digit>=1&&digit<=3){
                for(int i=0;i<digit;i++){
                    res=intToString[p]+res;
                }
            }else if(digit==4){
                res=intToString[p]+intToString[5*p]+res;
            }else if(digit>=5&&digit<=8){
                string s=intToString[p*5];
                for(int i=0;i<digit-5;i++)
                    s=s+intToString[p];
                res=s+res;
            }else if(digit==9){
                res=intToString[p]+intToString[10*p]+res;
            }
            p=p*10;
        }
        return res;       
    }
};

耗时24ms，空间占用12.2MB。

提交后看了下其他人的代码，基本上思想没什么变化，只不过初始化的时候如果初始化的更具体一点，转换耗时就会更快，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string intToRoman(int num) {
    string table[4][10] = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
                           {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
                           {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
                           {"", "M", "MM", "MMM"}
                          };
    string result;
    int count = 0;
    while(num > 0){
        int temp = num % 10;
        result = table[count][temp] + result;
        num /= 10;
        count++;
    }
    return result;
}
};

耗时16ms，占用空间8.4MB。

13. Roman to Integer

2019/5/3，易。

罗马数字转整数，很笨的办法就行，if语句看起来有点乱，但能通过，耗时16ms，8.3MB内存，可以转成switch语句，我这就没有转了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    int romanToInt(string s) {
        int res=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='I'){
                if(i<s.size()-1){
                    if(s[i+1]=='V'){
                        res+=4;
                        i++;
                    }else if(s[i+1]=='X'){
                        res+=9;
                        i++;
                    }else{
                        res+=1;
                    }
                }
                else{
                    res+=1;
                }
            }else if(s[i]=='V'){
                res+=5;
            }else if(s[i]=='X'){
               if(i<s.size()-1){
                    if(s[i+1]=='L'){
                        res+=40;
                        i++;
                    }else if(s[i+1]=='C'){
                        res+=90;
                        i++;
                    }else{
                        res+=10;
                    }
                }
                else{
                    res+=10;
                } 
            }else if(s[i]=='L'){
                res+=50;
            }else if(s[i]=='C'){
                if(i<s.size()-1){
                    if(s[i+1]=='D'){
                        res+=400;
                        i++;
                    }else if(s[i+1]=='M'){
                        res+=900;
                        i++;
                    }else{
                        res+=100;
                    }
                }
                else{
                    res+=100;
                }
            }else if(s[i]=='D'){
                res+=500;
            }else if(s[i]=='M'){
                res+=1000;
            }
        }
        return res;
    }
};

14. Longest Common Prefix

2019/5/5，易。

求一组字符串的最长公共前缀，直接暴力解就行了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty())
            return "";
        
        string pre=strs[0];//最长公共前缀最长不会超过第一个元素的长度，所以先把前缀设为第一个元素
        for(int i=1;i<strs.size();i++)
        {
            for(int j=0;j<pre.size();j++)
            {
                if(pre[j]!=strs[i][j])//一旦有字符不等，表示最长前缀结束了
                {
                    pre=pre.substr(0,j);
                    break;
                }
            }
            if(pre=="")
                break;
        }
        return pre;
    }
};

15. 3Sum（again）

2019/5/8，中。

求数组中三个数和为0的子集。

一开始自己用的回溯法，虽然结果能对，但是超时了，代码还是暂时列在这里，这代码里去掉了一些无用的迭代，然而还是没啥用，还是超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//超时
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        vector<int> p;
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1])
                continue;
            p.push_back(nums[i]);
            backTracking(nums,i,p,res);
            p.pop_back();
        }
        //vector<vector<int>> resVec(res.size());
        //std::copy(res.begin(), res.end(), resVec.begin());
        return res;
    }
private:
    void backTracking(vector<int>& nums,int i,vector<int>& p,vector<vector<int>>& res){
        if(p.size()==3){
            if(p[0]+p[1]+p[2]==0){
               // vector<int> tmp = p;//不能直接对p排序，会导致p发生变化，后续回溯出错
				//sort(tmp.begin(), tmp.end());				
				res.push_back(p);
                return;
            }
        }
        
        for(int j=i+1;j<nums.size();j++){
            if(j>i+1&&nums[j]==nums[j-1])
                continue;
            p.push_back(nums[j]);
            backTracking(nums,j,p,res);
            p.pop_back();
        }
    }
};

后面看了其他提交者的代码，采用的是先排序再利用前后指针的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (unsigned int i=0; i<nums.size(); i++) {
            if ((i>0) && (nums[i]==nums[i-1]))//防止重复
                continue;
            int l = i+1, r = nums.size()-1;
            while (l<r) {
                int s = nums[i]+nums[l]+nums[r];
                if (s>0) r--;
                else if (s<0) l++;
                else {
                    res.push_back(vector<int> {nums[i], nums[l], nums[r]});
                    //剔除重复
                    while (l<r&&nums[l]==nums[l+1]) l++;
                    while (l<r&&nums[r]==nums[r-1]) r--;
                    l++; r--;
                }
            }
        }
        return res;
    }
};

16.3Sum Closest

2019/5/9，中。

和15很类似，这题求的是和给定值target最近的三个数的和，方法类似，也是用两个指针从前后向中间逼近，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int min_bias = INT8_MAX;
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            int l = i + 1;
            int r = (int)nums.size() - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == target)
                    return s;
                int tmp=abs(s-target);
                if(tmp<min_bias){
                    min_bias=tmp;
                    res=s;
                }
                if(s>target)
                    r--;
                else
                    l++;
            }
        }
        return res;
    }
};

17. Letter Combinations of a Phone Number

2019/5/10，中。

一道简单的回溯题，没有啥特别的地方，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits=="")
            return res;
        vector<vector<string>> chas={{"a","b","c"},{"d","e","f"},{"g","h","i"},
                                    {"j","k","l"},{"m","n","o"},{"p","q","r","s"},
                                    {"t","u","v"},{"w","x","y","z"}};
        string tmp="";
        backTracking(digits,chas,res,tmp);
        return res;
    }
private:
    void backTracking(string& digits,const vector<vector<string>>& chas,vector<string>& res,string& tmp){
        if(tmp.size()==digits.size()){
            res.push_back(tmp);
            return;
        }
        
        for(int i=0;i<chas[digits[tmp.size()]-'0'-2].size();i++){
            tmp+=chas[digits[tmp.size()]-'0'-2][i];
            backTracking(digits,chas,res,tmp);
            tmp=tmp.substr(0,tmp.size()-1);
        }
    }
};

18. 4Sum

2019/5/11，中。

和前面的2Sum以及3Sum是一个系列的，使用和3Sum一样的思想即可，AC，耗时8ms左右。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size() < 4) 
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(i>0&&nums[i]==nums[i-1])
                continue;
            //以下两个判断可以剔除很多无效循环，没有这两个判断的话也能AC，但是耗时会在40ms左右
            if(i+3<nums.size()&&nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) 
                break;
            if(nums[i] + nums[nums.size()-1] + nums[nums.size()-2] + nums[nums.size()-3] < target) 
                continue;
            for(int j=i+1;j<nums.size();j++){
                if(j>i+1&&nums[j]==nums[j-1])
                    continue;
                int l=j+1,r=nums.size()-1;
                while(l<r){
                    int sum=nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        res.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]});
                        while(l<r&&nums[l+1]==nums[l])
                            l++;
                        while(l<r&&nums[r-1]==nums[r])
                            r--;
                        l++;r--;
                    }else if(sum>target)
                        r--;
                    else 
                        l++;
                }
            }
        }
        return res;
    }
};

19. Remove Nth Node From End of List

2019/5/12，中。

移除链表中倒数第N个元素，做过，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //只有一个节点并且要删除这个节点
        if(head->next==NULL&&n==1)
            return NULL;
        ListNode* pre=head;
        ListNode* cur=head;
        while(n--){
            pre=pre->next;
            if(!pre&&n!=0)
                return head;
        }
        while(pre){
            pre=pre->next;
            cur=cur->next;
        }
        //删除的是第一个节点
        if(cur==head){
            return head->next;
        }
        //要删除的不是最后一个节点
        if(cur->next){
            cur->val=cur->next->val;
            cur->next=cur->next->next;
        }else{//删除最后一个节点
            pre=head;
            while(pre->next!=cur)
                pre=pre->next;
            pre->next=NULL;
        }
        return head;
    }
};

20. Valid Parentheses

2019/5/13，易。

判断括号是否有效，用一个栈即可，没什么难度，自己是用ifelse写的，另外找了一个看起来清爽一些但意思一样的代码放在这里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case '(': 
                case '{': 
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};

21. Merge Two Sorted Lists

2019/5/15，易。

合并两个有序数组，简单题，最常用的方法就是循环依次比较，这里就不放这种方法的代码了，放一个递归的代码，《剑指offer》里也是这种递归代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1&&!l2)
            return NULL;
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        
        ListNode* node=NULL;
        if(l1->val<l2->val)
        {
            node=l1;
            node->next=mergeTwoLists(l1->next,l2);
        }
        else
        {
            node=l2;
            node->next=mergeTwoLists(l1,l2->next);
        }
        return node;
    }
};

22. Generate Parentheses（again）

2019/5/16，中。

生成括号，用递归解法。

总结出来三点，就是选择、限制、结束条件是这种递归和回溯的主要部分，本题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        recursion(res,"",n,0);
        return res;
    }
private:
    void recursion(vector<string>& res,string s,int left,int right){
        if(left==0&&right==0){
            res.push_back(s);
            return;
        }
        if(left>0)
            recursion(res,s+"(",left-1,right+1);
        if(right>0)
            recursion(res,s+")",left,right-1);
    }
};

23. Merge k Sorted Lists

2019/5/17，难。

第21题的升级版，最容易想到的方法就是循环调用第21题的代码，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)
            return NULL;
        ListNode* res;
        res=lists[0];
        //循环调用21题的方法
        for(int i=1;i<lists.size();i++){
            res=mergeTwoLists(res,lists[i]);
        }
        return res;
    }
private:
    ListNode* mergeTwoLists(ListNode*& l1, ListNode* l2) {
        if(!l1&&!l2)
            return NULL;
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        ListNode* tmp;
        if(l1->val<l2->val){
            tmp=l1;
            tmp->next=mergeTwoLists(l1->next,l2);
        }else{
            tmp=l2;
            tmp->next=mergeTwoLists(l1,l2->next);
        }
        return tmp;
    }
};

最后提交发现该方法可以AC，但耗时240ms，占内存11MB左右，效率不是特别好。

为提高效率，采用分治法的思想，两两合并再合并，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)
            return NULL;
        ListNode* res;
        int n=lists.size();
        while(n>1){
            int k=(n+1)/2;
            for(int i=0;i<n/2;i++)
                lists[i]=mergeTwoLists(lists[i],lists[i+k]);
            n=k;
        }
        return lists[0];
    }
private:
    ListNode* mergeTwoLists(ListNode*& l1, ListNode* l2) {
        //...此函数相同
    }
};

该方法耗时24ms，效率提升很多。

24. Swap Nodes in Pairs

2019/5/21，中。

链表题，主要就是搞清楚指针的变换和空指针的情况，循环遍历下去即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head)
            return NULL;
        if(!head->next)
            return head;
        ListNode* cur=head,*next=head->next;
        ListNode* newHead=next;//记录新的头结点
        ListNode* pre=NULL;
        while(next){
            if(pre==NULL)
                pre=cur;
            else
                pre->next=next;
            cur->next=next->next;
            next->next=cur;
            
            pre=cur;
            cur=cur->next;
            if(cur)
                next=cur->next;
            else
                next=NULL;
            
        }
        return newHead;
    }
};

25. Reverse Nodes in k-Group

2019/5/26，难。

最近等毕业论文审核通知，心烦意乱，没有什么心情，所以做题耽搁了些。

这是题24的升级版，题24是两两反转，而本题是按数字k来反转，变成了更一般的情况，我的想法是按段分割整个链表，对每一段链表分别进行反转，注意好节点指针，还是比较容易漏的，测试了好久，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head)
            return NULL;
        //1 计算链表长度
        int len=0;
        ListNode* cur=head;
        ListNode* res=NULL;//记录最后返回的头结点
        while(cur){
            len++;
            cur=cur->next;
        }
        if(k>len||k==1)
            return head;
        int i=len/k;//2 计算反转链表的循环次数
        cur=head;
        bool first=true;//记录是否是第一次，用来保存调整后的头结点
        ListNode* last=NULL;//记录上一次调整的最后一个节点
        while(i--){
            int n=k;
            ListNode* tail=cur;
            //得到本次需要调整的最后一个节点
            while(n>1){
                tail=tail->next;
                n--;
            }
            ListNode* tmp=tail->next,*tmp1=cur;//tmp记录下一次调整的头结点，tmp1记录本次调整的头结点，也就是本次调整完的最后一个节点
            if(first)//如果是第一次调整则记录最终头结点
            {
                res=reverseList(last,cur,tail,k);
                first=false;
            }
            else
                reverseList(last,cur,tail,k);
            last=tmp1;
            cur=tmp;
        }
        return res;
    }
private:
    //反转部分链表
    ListNode* reverseList(ListNode*& last,ListNode*& head,ListNode*& tail,int k){
        ListNode* pre=tail->next;
        ListNode* next=NULL;
        while(k--){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
            if(k==1&&last)
            {
                last->next=head;
            }
        }
        return pre;
    }
};

最后耗时20ms，内存9.7MB左右。

26. Remove Duplicates from Sorted Array

2019/5/27，易。

去除排序数组中的重复数组。

本题本来以为是需要将重复数字删掉，但题目的意思其实是只需要让单独的数字出现在前面，超出单独数字长度后的数字可以不用删除，因为不用删除所有可以省很多时间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int index=0;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]!=nums[index])
            {
                index++;
                nums[index]=nums[i];
            }
        }
        return index+1;
    }
};

不过一开始我以为是需要删除元素，所以用了迭代器来删除数组元素，最后也可以跑通，只是耗时会比较多，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        //检查的过程中删除元素，改变了原数组的长度，耗时较长
        int cur=nums[0];
        for(auto it=nums.begin()+1;it!=nums.end();)
        {
            if(*it==cur)
            {
                it=nums.erase(it);
            }
            else
            {
                cur=*it;
                it++;
            }
        }
        return nums.size();
    }
};

27. Remove Element

2019/5/31，易。

删除数组中指定元素，很简单的一道题，可以用vector的erase方法来删除，但联想到上一题，觉得题目要求应该只需要将非指定值的元素放在数组前面部分即可，所以最后写出的代码也没删除，只是替换了一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()==0)
            return 0;
        int end=nums.size()-1;
        while(end>=0&&nums[end]==val)
            end--;
        for(int i=0;i<end;i++){
            if(nums[i]==val)
            {
                int tmp=nums[i];
                nums[i]=nums[end];
                nums[end]=tmp;
                while(end>=0&&nums[end]==val)
                    end--;
            }
        }
        return end+1;
    }
};

正常AC了，后来看别人的提交，其实连替换都不用，若有指定数字直接覆盖就行了，不过大同小异，不去深究。

28. Implement strStr()

2019/6/1，易。

判断是否是子串，由于这道题难度是简单，所以用最简单的遍历查找即可，至于KMP算法可以参见另一篇文章《剑指Offer+常用手写算法(C++)》。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//最简单的遍历比较法
class Solution {
public:
    int strStr(string haystack, string needle) {
        int m=haystack.size(),n=needle.size();
        if(!n)
            return 0;
        for(int i=0;i<m-n+1;i++)
        {
            int j=0;
            for(;j<n;j++)
            {
                if(haystack[i+j]!=needle[j])
                    break;
            }
            if(j==n)
                return i;
        }
        return -1;
    }
};

29. Divide Two Integers(again)

2019/6/3，中。

不用乘法、除法以及模运算完成两个整数的除法，主要想法是使用移位运算，每次双倍，再做操作和累加，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor==0||(dividend == INT_MIN && divisor == -1))
            return INT_MAX;
        if(divisor==1)
            return dividend;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1 ;
        long long dvd = labs(dividend);
        long long dvs = labs(divisor);
        int res = 0;
        while(dvd >= dvs){
            long long tmp = dvs , m = 1;
            while (dvd >= (tmp << 1)) {
                tmp <<= 1;
                m <<= 1;
            }
            dvd -= tmp;
            res += m;
        }
        return sign==1 ? res : -res;
        
    }
};

30. Substring with Concatenation of All Words（again）

2019/6/5，难。

有点难度的一道题，不过基本方法很好想，就依次遍历n*len的子串，针对每个子串进行验证是否成立，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        //主要步骤，先找出所有n*len长度的子串，再一一验证
        vector<int> res;
        if(s==""||words.size()==0)
            return res;
        int len=0;
        if(words.size()>0)
            len=words[0].size();
        int lenOfSubstr=len*words.size();
        if(s.size()<lenOfSubstr)
            return res;
        unordered_map<string, int> wordCnt;
        for (auto &word : words) 
            ++wordCnt[word];
        for(int i=0;i<=s.size()-lenOfSubstr;i++){
            unordered_map<string, int> strCnt;
            int j = 0; 
            for (j = 0; j < words.size(); ++j) {
                string t = s.substr(i + j * len, len);
                if (!wordCnt.count(t)) break;
                ++strCnt[t];
                if (strCnt[t] > wordCnt[t]) break;
            }
            if (j == words.size()) 
                res.push_back(i);
        }
        return res;
    }
};

能够通过，只是效率比较低，看网上还有一种利用滑动窗口的方法，能够提高效率，可以百度看看。

31. Next Permutation

2019/6/10，中。

求字符数组按照字典序的下一个排列。

研究了几个排列后发现了一些规律，写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //尝试思路：从右往左找第一个逆序对（idx1,idx2），交换位置，对idx1后面的数字重新排序，若没有逆序对则说明是最后一个排列，返回第一个排序即可
        if(nums.size()<=1)
            return ;
        //1 从右往左找第一个逆序对
        int idx1=-1,idx2=-1;
        for(int i=nums.size()-1;i>=1;i--){
            if(nums[i]>nums[i-1])
            {
                idx1=i-1;
                idx2=i;
                break;
            }
        }
        //2 往右寻找比该数大的最小值
        if(idx1!=-1){
            for(int j=idx1+1;j<nums.size();j++){
                if(nums[j]>nums[idx1]&&nums[j]<nums[idx2])
                    idx2=j;
            }
        }
        //3 交换排序或者直接排序
        if(idx1!=-1){
            int tmp=nums[idx1];
            nums[idx1]=nums[idx2];
            nums[idx2]=tmp;
            sort(nums.begin()+idx1+1,nums.end());
        }else{
            sort(nums.begin(),nums.end());
        }
    }
};

提交通过了。

当然，C++本身还有一个next_permutation函数，直接用的话本题也能通过：

1
2
3
4
5
6
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation( nums.begin(), nums.end() ); 
    }
};

32. Longest Valid Parentheses（again）

2019/6/13，难。

求最长有效括号子串，一开始就想到应该用动态规划或者栈的方法来做，但自己编程水平还是太菜，写了半天没写出来，看了网上的解答后觉得自己很蠢，虽然难度是难，但本题其实感觉并不难，给出代码吧，头疼。

不过这题有个技巧，栈的话会先在栈里放一个-1，动态规划的话则会在原字符串前加一个)，都是为了使处理更加方便，可能这就是自己没想到的地方吧，值得重视。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//栈
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.length() == 0)
            return 0;
        int res = 0;
        stack<int> st;
        st.push(-1);
        for(int i=0; i<s.length(); ++i){
            if(s[i] == '('){
                st.push(i);
            }
            else{
                st.pop();
                if(!st.empty()){
                    res = max(res, i-st.top());
                }
                else{
                    st.push(i);
                }
            }
        }

        return res;
    }
};
//dp
class Solution {
public:
    int longestValidParentheses(string s) 
    {
        int result=0;
        s=')'+s;
        vector<int> dp(s.length(),0);
        for(int i=1;i<s.length();i++)
        {
            if(s[i]==')')
            {
                if(s[i-1-dp[i-1]]=='(') dp[i]=dp[i-1]+2;//累加本次的长度
                dp[i]+=dp[i-dp[i]];//和前面已经计算过的长度再做一次累加得到最后的数字
            }
            result=max(result,dp[i]);
        }
        return result;
    }
};

33. Search in Rotated Sorted Array(again)

2019/6/21，中。

这两天奔波找房子参加毕业典礼啥的就没刷题，这道题之前做过类似的，主要使用二分法，并且在排除的过程中注意根据有序的部分数组来进行判断，以便决定去除左右哪一部分无效数据。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //使用二分法
        if(nums.empty())
            return -1;
        
        int left=0;
        int right=nums.size()-1;
        int mid=0;
        while(left<=right)
        {
            mid=left+((right-left)>>1);
            if(nums[mid]==target)
                return mid;
            
            if(nums[left]<=nums[mid])
            {
                if(target>=nums[left]&&target<nums[mid])
                    right=mid-1;
                else
                    left=mid+1;
            }
            else
            {
                if(target>nums[mid]&&target<=nums[right])
                    left=mid+1;
                else
                    right=mid-1;
            }
        }
        return -1;
    }
};

34. Find First and Last Position of Element in Sorted Array

2019/6/26，中。

《剑指Offer》上有类似的题，又复习了一遍，提交的时候发现之前在LeetCode上做过这道题，用的是比较笨的办法，但在LeetCode上的执行效率却比递归方法高，有点意思，给出下面两种代码，核心思想仍然是二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//普通方法
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res={-1,-1};
        if(nums.empty())
            return res;
        int left=0;
        int right=nums.size()-1;
        int mid=0;
        while(left<=right)
        {
            mid=left+((right-left)>>1);
            if(nums[mid]<target)
                left=mid+1;
            else if(nums[mid]>target)
                right=mid-1;
            else
            {
                int i=mid,j=mid;
                while(i>=0&&nums[i]==target)
                    i--;
                while(j<nums.size()&&nums[j]==target)
                    j++;
                res[0]=i+1;
                res[1]=j-1;
                return res;
            }
        }
        return res;
    }
};
//递归方法
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        if(nums.size()<=0)
            return res;
        //利用递归
        res[0]=getFirst(nums,0,nums.size()-1,target);
        res[1]=getLast(nums,0,nums.size()-1,target);
        return res;
    }
private:
    int getFirst(vector<int>& nums, int left, int right,int target){
        if(left>right)
            return -1;
        int mid=left+((right-left)>>1);
        if(nums[mid]==target){
            if(mid==0||(mid>0&&nums[mid-1]!=target))
                return mid;
            else
                right=mid-1;
        }else if(nums[mid]<target)
            left=mid+1;
        else
            right=mid-1;
        return getFirst(nums,left,right,target);
        
    }
    int getLast(vector<int>& nums, int left, int right,int target){
        if(left>right)
            return -1;
        int mid=left+((right-left)>>1);
        if(nums[mid]==target){
            if((mid<nums.size()-1&&nums[mid+1]!=target)||mid==nums.size()-1)
                return mid;
            else
                left=mid+1;
        }else if(nums[mid]<target)
            left=mid+1;
        else
            right=mid-1;
        return getLast(nums,left,right,target);        
    }
};

35. Search Insert Position

2019/7/6，易。

本题相对简单，写的时候也一次通过了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.size() <= 0){
            return 0;
        }
        int left = 0, right = nums.size()-1;
        int res = 0;
        while(left<=right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] == target)
                return mid;
            //不等
            if(mid == 0 && nums[mid] > target)
                return 0;
            if(mid == nums.size()-1 && nums[mid] < target)
                return nums.size();
            if(nums[mid] > target && nums[mid-1] < target)
                return mid;
            if(nums[mid] < target && nums[mid+1] > target)
                return mid+1;
            
            if(nums[mid] < target)
                left = mid + 1;
            if(nums[mid] > target)
                right = mid - 1;
        }
        return res;
    }
};

但是后来看别人提交的代码的时候发现自己又把问题复杂化了，根本就不是二分查找的变种，而是最基本的二分法！要说变化也就是最后返回的值变成了left！还是对问题的理解程度太弱了，所谓寻找插入的下标，说白了原来就是返回left就行了，试验几次就会看出这个规律了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size()-1;
        while (l <= r) {
            int middle = (l + r) / 2;
            if (nums[middle] > target) r = middle - 1;
            else if (nums[middle] < target) l = middle + 1;
            else return middle;
        }
        return l;
    }
};

36. Valid Sudoku

2019/7/7，中。

这道题我还记得之前第一次做的时候以为要把整个数独都填完呢，后来发现自己还是把问题复杂化了（似乎我的思维有这个毛病，得改），本题的意思其实只是判断input里每一行每一列每个九宫格有没有重复数字而已，并不用填充整个数独。

所以最简单的办法就是遍历判断好了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //即检查每一行每一列每一个九宫格内是否有重复数字
        for(int i = 0; i < 9; i ++)
        {
            unordered_map<char, bool> m1;   //负责检查行
            unordered_map<char, bool> m2;   //负责检查列
            unordered_map<char, bool> m3;   //负责检查九宫格
            for(int j = 0; j < 9; j ++)
            {
                //分别检查第i行，第i列，第i个九宫格中的九个数，j表示第j个数
                
                //每一行的坐标，不需要转换
                if(board[i][j] != '.')
                {
                    if(m1[board[i][j]] == true)
                        return false;
                    m1[board[i][j]] = true;
                }
                //每一列的坐标，横纵坐标互换即可
                if(board[j][i] != '.')
                {
                    if(m2[board[j][i]] == true)
                        return false;
                    m2[board[j][i]] = true;
                }
                //九宫格内坐标转换
                if(board[i/3*3+j/3][i%3*3+j%3] != '.')
                {
                    if(m3[board[i/3*3+j/3][i%3*3+j%3]] == true)
                        return false;
                    m3[board[i/3*3+j/3][i%3*3+j%3]] = true;
                }
            }
        }
        return true;
    }
};

查看别人的代码后发现有很精简的代码，但逻辑内核不变，这里也就不贴了。