leetcode 刷题总结

发表于 | 更新于 | 评论数： | 阅读次数：

leetcode 刷题总结

开始刷 leetcode 和剑指 offer 大概一周多了吧，从最开始最简单的代码也要敲 30 mins，各种 bug 不断，到现在简单的可以10 mins 敲完（当然也有些没有思路的），还是有些进步的，另外发现还是需要把一些题解记录下来，总结一下，因为目前按 tags 和难度分开刷的，题目编号可能不连续，打算长期更新，加油吧！

进度更新（6月4日）：跌跌撞撞也做了80+题，从开始只做简单到现在开始做些中等题，也算有些进步吧，不足的是代码bug太多，总体接受率才28%，加油，接下来想办法提升接受率，不要一直改bug！

更新（6月26号）：最近一段时间没怎么刷题，开始刷题一个多月了，现在leetcode上才刷97题，blog上才更了不到70题，不知道为什么有些题没有记录上来。另外做了一下牛客网的校招编程题，感觉还是不会做。

1. Two Sum

  • 题目描述：Given an array of integers, return indices of the two numbers such that they add up to a specific target.
  • 解题思路：虽说是第一题简单难度，但是我就是不会做5555，评论区有哈希表解法，即将 target 与当前元素做差，在哈希表中查找有无此元素。

2. Add Two Numbers

  • You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.
  • 这题我写的超级麻烦，因为我是在原链表上改（因为我不会新建链表），所以我多了很多判断，比方说l1比l2长的话后面就在l1上改，最后还要返回l1，完后基础用例还是过了，但[5][5]得用例一直报错，内存错误，不知道哪里出现野指针还是这么回事，最后还是参考了讨论区解法。以后需要注意，新建指针方式：ListNode* l0=new ListNode(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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = NULL, *prev = NULL;
        int carry = 0;
        while (l1 || l2) {
            int v1 = l1? l1->val: 0;
            int v2 = l2? l2->val: 0;
            int tmp = v1 + v2 + carry;
            carry = tmp / 10;
            int val = tmp % 10;
            ListNode* cur = new ListNode(val);
            if (!head) head = cur;
            if (prev) prev->next = cur;
            prev = cur;
            l1 = l1? l1->next: NULL;
            l2 = l2? l2->next: NULL;
        }
        if (carry > 0) {
            ListNode* l = new ListNode(carry);
            prev->next = l;
        }
        return head;
    }
};

3. Longest Substring Without Repeating Characters

  • Given a string, find the length of the longest substring without repeating characters.
  • 我想到的只有暴力搜索了，讨论区有动态规划的解法，又写了一遍，用的python的dict方法，在dict中查找仅要$O(1)$复杂度，相当于hash表。思路是建立2个指针，第一个指针遍历后将所读取的字符放入dict，如果出现重复字符，则移动第二个指针并把读取的字符从dict中删除，相当于dict中仅有不重复的字串。
1
2
3
4
5
6
7
8
9
10
11
int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }
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:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        a={}
        if len(s)==0:
            return 0
        maxlen=1
        i=0
        j=0
        while(j!=len(s)):
            if s[j] not in a:
                a[s[j]]=1
                j+=1
            else:
                maxlen=max(len(a),maxlen)
                while(s[i]!=s[j]):
                    a.pop(s[i])
                    i+=1
                i+=1
                j+=1
        maxlen=max(len(a),maxlen)
        return maxlen

5. Longest Palindromic Substring

  • 寻找最长回文字串
  • 思路，我能想到得只有最简单的，从头到尾遍历数组，以该字符为中心向两边搜索，网上还有$O(N)$的解法，可以见详解：王大咩的图书馆、bitzhuwei。

6. ZigZag Conversion

  • The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
  • 思路：简单暴力，用 vector分别保存 zigzag 每一行的字符串，然后拼接起来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> str(numRows);
        if(s.size()<=numRows||numRows==1) return s;
        int x=1,j=0;
        for(int i=0;i<s.size();i++)
        {
            str[j].push_back(s[i]);
            if(j==0)
                x=1;
            else if(j==numRows-1)
                x=-1;
            j+=x;
        }
        string cov=str[0];
        for(auto i=str.begin()+1;i!=str.end();i++)
            cov.append(*i);
        return cov;
    }
};

7. Reverse Integer

  • 反转整数
  • 挺简单的，需要特别注意不要溢出了，int范围是：$[-2^{31},2^{31}-1] $ or [INT_MIN,INT_MAX]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int reverse(int x) {
        int a=1,res=0,z=0;
        if(x<0){a=-1;x*=-1;}
        while(x)
        {
            res=res*10+x%10;
            z=x;
            x/=10;
        }
        if(res%10!=z) return 0;
        return a*res;
    }
};

8. String to Integer (atoi)

  • Implement atoi which converts a string to an integer.
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:
    int myAtoi(string str) {
        int res=0,x=1,k=1;
        for(int i=0;i<str.size();){
            int num=str[i]-'0';
            if(str[i]-' '==0&&k)
                i++;
            else if(num<=9&&num>=0){
                if((res*10+((num)))/10!=res){
                    return x==1?INT_MAX:INT_MIN;
                }
                res=res*10+((num));
                i++;
                k=0;
            }
            else if(k&&(str[i]-'-'==0||str[i]-'+'==0))
            {
                if(str[i]-'-'==0)
                    x*=(-1);
                i++;
                k=0;
            }
            else
                break;
        }
        return res*x;
    }
};

9. Palindrome Number

  • 判断回文数
  • 最简单想到的就是把每位的数都保存到数组里，然后依次比较数组的头与尾，但这样时间效率确实不高，之后参考大神解法（见代码二），直接用一个快指针一个慢指针，找到数的中间位置，找中间位置时顺便把数的一半反转了，然后比较反转的与剩下的一半是否相等。
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:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        vector<int> num;
        while(x)
        {
            num.push_back(x%10);
            x/=10;
        }
        int b=0,e=num.size()-1;
        while(b<e)
        {
            if(num[b]==num[e])
            {
                b++;
                e--;
            }
            else
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int revhalf = 0, slow = x, fast = x;
        while(fast){ 
            revhalf = revhalf * 10 + slow % 10;
            slow /= 10;
            fast /= 100;
        }
        return slow == revhalf || slow == revhalf / 10;
    }
};

10. Regular Expression Matching

  • 模拟正则表达式

    '.' Matches any single character.
'*' Matches zero or more of the preceding element.
  • 思路：’‘可以表示0个或多个前面一个元素，因此想到用递归的方式不断搜索答案，另外’‘是后置的运算符，因此采用2个指针从后向前搜索答案。搜索时有以下几种情况：
    1. p的指针搜索到任意字母：与s中的指针比较，不同则返回false，否则p与s的指针向前移动一位，继续搜索。
    2. p的指针搜索到’.’：p与s的指针向前移动一位，继续搜索。
    3. p的指针搜索到’‘：如果p指针前一位元素为i，则统计s指针前方有n个i，然后依次’‘前的元素依次重复0~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
      43
      44
      class Solution {
      public:
          bool isMatch(string s, string p) {
              int ends=s.size()-1,endp=p.size()-1;
              return matchOrNot(s, p, ends,endp);
          }
          bool matchOrNot(string &s, string &p,int ends,int endp){
              if(ends<0&&endp<0) return true;
              if(endp<0||(ends<0 && p[endp]!='*')) return false;
              if(p[endp]=='*'){
                  if(ends<0){
                      return matchOrNot(s, p, ends,endp-2);
                  }
                  int count=0;//统计s指针前方p[endp-1]个数
                  if(p[endp-1]!='.')
                  {
                      for(int i=ends;i>=0;i--){
                          if(s[i]==p[endp-1]){
                              count++;
                          }
                          else
                              break;
                      }
                  }
                  else
                      count=ends+1;
                  bool judge=false;//递归搜索
                  for(int i=0;i<=count;i++){
                      judge=judge||matchOrNot(s, p, ends-i,endp-2);
                      if(judge)
                          return judge;
                  }
              }
              else if(p[endp]=='.'){
                  return matchOrNot(s, p, ends-1,endp-1);
              }
              else{
                  if(p[endp]==s[ends]){
                      return matchOrNot(s, p, ends-1,endp-1);
                  }
              }
              return false;
          }
      };

11. Container With Most Water

  • Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
  • 思路：见https://segmentfault.com/a/1190000008824222
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 maxArea(vector<int> &h) {  
        int res=0;  
        int n = h.size();  
        int l=0,r=n-1;  
        while(l<r)  
        {  
            res=max(res,min(h[l],h[r])*(r-l));  
            if (h[l]<h[r])  
            {  
                int k=l;  
                while(k<r&&h[k]<=h[l])  
                    k++;  
                l=k;  
                }  
            else  
            {  
                int k=r;  
                while(k>l&&h[k]<=h[r])  
                    k--;  
                r=k;  
             }  
        }  
        return res;  
    }  
};

12. Integer to Roman

  • 数字转化为罗马字
  • 这题我不会，自定义了一个转化方法，最后结果也不对，可能对转化方法不太熟吧。下面程序方法来源网络，这方法确实不错，把每一种情况都考虑到了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {  
public:  
    string intToRoman(int num) {  
        string str;    
        string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};    
        int value[]=    {1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1};   
        for(int i=0;num!=0;++i)  
        {  
            while(num>=value[i])  
            {  
                num-=value[i];  
                str+=symbol[i];  
            }  
        }  
        return str;  
    }  
};

13. Roman to Integer

  • 将罗马数字转化为阿拉伯数字
  • 还以为自己写错了，结果一次就AC了，开心。主要就是要判断一个罗马字是前缀还是后缀，前缀需要相减，后缀则相加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        dig={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
        if(len(s)<1):
            return 0
        elif(len(s)==1):
            return dig[s]
        pre=0
        sums=0
        for i in s:
            if(dig[i]>pre):#当前罗马字比前一个罗马字大，意味着前一个字为前缀，需要减去，如IV，实际为-1+5
                sums=sums+dig[i]-2*pre
            else:#当前罗马字小于或等于前一个罗马字，意味着前一个字为后缀，需要加上，如VI，实际为5+1
                sums+=dig[i]
            pre=dig[i]
        return sums

14. Longest Common Prefix

  • Write a function to find the longest common prefix string amongst an array of strings.
  • 开始以为是最长子序列，想了半天想不出怎么做，后来发现是最长前缀子序列，一个一个比较吧。
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:
    string longestCommonPrefix(vector<string>& strs) {
        int len=strs.size();
        string str;
        if(len==0) return str;
        else if(len==1) return strs[0];
        for(int i=0;i<strs[0].size();i++){
            char c=strs[0][i];
            for(int j=1;j<strs.size();j++){
                if(strs[j].size()>i){
                    if(strs[j][i]!=c)
                    {
                        goto end;
                    }
                }
                else
                {
                    goto end;
                }
            }
            str.push_back(c);
        }
        end:
            return str;
    }
};

15. 3Sum

  • Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
  • 我的思路：首先建立哈希表，然后取2个指针a,b，在哈希表中查找-(a+b)，如果有说明和为0，但这样存在重复情况，如[-1,0,1]，a=-1,b=0与a=-1,b=1情况重复，于是新建立一个哈希表map<vector,int>，每次得到结果在哈希表中查找，时间复杂度大概为$O(n^2)$，而且没有提前停止，所以有个算例，输入n
    个0，然后我就超时了，再加上提前停止的判定，好歹AC了，但时间效率很低（其实这个思路还是能优化的，在提前停止部分优化好）。
  • 大神思路：类似2Sum，用一个指针开始遍历，另外2个指针类似于2Sum进行遍历。
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//我的初始代码
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > sum3;
        if(nums.size()<3) return sum3;
        //vector<int> sums;
        sort(nums.begin(),nums.end());
        unordered_map<int,int> set;
        map<vector<int>,int> maps;
        for(auto &i:nums){
            if(set.find(i)!=set.end()){
                set[i]+=1;
            }
            else{
                set[i]=1;
            }
        }
        vector<int> zero(3,0);
        for(int i=0;i<nums.size()-2;i++){
            for(int j=i+1;j<nums.size()-1;j++){
                if(nums[i]+nums[j]>0) break;
                else if(nums[i]==0&&nums[j]==0&&maps.find(zero)!=maps.end()) goto end;
                int k=-1*(nums[i]+nums[j]);
                if(set.find(k)!=set.end()){
                    if(k!=nums[i] && k!=nums[j]){
                        vector<int> sums={nums[i],nums[j],k};
                        sort(sums.begin(),sums.end());
                        if(maps.find(sums)==maps.end()){
                            sum3.push_back(sums);
                            maps.insert(pair<vector<int>,int>(sums,1));
                        }
                    }
                    else if(k==nums[i]&&k==nums[j]){
                        if(set[0]>=3){
                            vector<int> sums(3,0);
                            if(maps.find(sums)==maps.end()){
                                sum3.push_back(sums);
                                maps.insert(pair<vector<int>,int>(sums,1));
                            }
                        }
                    }
                    else{
                        if(set[k]>=2){
                            vector<int> sums={nums[i],nums[j],k};
                            sort(sums.begin(),sums.end());
                            if(maps.find(sums)==maps.end()){
                                sum3.push_back(sums);
                                maps.insert(pair<vector<int>,int>(sums,1));
                            }
                        }
                    }
                }
            }
        }
        end:
        return sum3;
    }
};
//大神代码
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > res;
    std::sort(num.begin(), num.end());
    for (int i = 0; i < num.size(); i++) {
        int target = -num[i];
        int front = i + 1;
        int back = num.size() - 1;
        while (front < back) {
            int sum = num[front] + num[back];
            // Finding answer which start from number num[i]
            if (sum < target)
                front++;
            else if (sum > target)
                back--;
            else {
                vector<int> triplet(3, 0);
                triplet[0] = num[i];
                triplet[1] = num[front];
                triplet[2] = num[back];
                res.push_back(triplet);
                // Processing duplicates of Number 2
                // Rolling the front pointer to the next different number forwards
                while (front < back && num[front] == triplet[1]) front++;
                // Processing duplicates of Number 3
                // Rolling the back pointer to the next different number backwards
                while (front < back && num[back] == triplet[2]) rear--;
            }
        }
        // Processing duplicates of Number 1
        while (i + 1 < num.size() && num[i + 1] == num[i]) 
            i++;
    }
    return res;
}

16. 3Sum Closest

  • Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

  • 思路：参考第15题3sum的思路，先对数组排序，然后使用3个指针遍历数组，初始化指针p0位于数组开头，p1位于p0的下一个位置，p2位于数组末尾，指针移动规则为：

    1. sum(p0,p1,p2)>target，说明sum(p0,p1,p2)应该减小，因此p2应向左移动（p2–）；
    2. sum(p0,p1,p2)<target，说明sum(p0,p1,p2)应该增大，因此p1向右移动（p1++）
    3. sum(p0,p1,p2)==target，直接return target即可；
  • 使用一个变量subs记录下最接近target的sum，每次计算完sum后与subs比较，如果sum更接近，则更新subs。
  • 提前停止条件：数组已经排过序了，因此sum(p0,p0+1,p0+2)为某个p0时对应的最小和，如果sum(p0,p0+1,p0+2)>target，不论p1p2如何移动，均有abs(sum(p0,p1,p2))>=abs(sum(p0,p0+1,p0+2))，因此可以以此作为提前停止条件。
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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size()<3) return 0;
        int res=0,subs=INT_MAX;
        sort(nums.begin(),nums.end());
        for(int p0=0;p0<nums.size()-2;p0++){
            int p1=p0+1,p2=nums.size()-1;
            int minsum=nums[p0]+nums[p1]+nums[p1+1];//p0对应最小3sum
            if((target-minsum)<=0){//提前停止判断
                if(target-minsum==0){
                    return target;
                }
                else if(abs(target-minsum)<=subs){
                    return minsum;
                }
                else if(abs(target-minsum)>subs){
                    return res;
                }
            }
            while(p1<p2){
                int sums=nums[p0]+nums[p1]+nums[p2];
                if(target-sums==0){
                    return target;
                }
                else if(target-sums>0){
                    if(abs(target-sums)<subs){
                        subs=abs(target-sums);
                        res=sums;
                    }
                    p1++;
                }
                else{
                    if(abs(target-sums)<subs){
                        subs=abs(target-sums);
                        res=sums;
                    }
                    p2--;
                }
            }
        }
        return res;
    }
};

17. Letter Combinations of a Phone Number

全排列问题，做过很多次了，递归求解。

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:
    vector<string> letterCombinations(string digits) {
        vector<string> num={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"},res;
        if(digits.size()==0) return res;
        string r;
        combine(digits,num,res,r,0);
        return res;
    }
    void combine(string &digits,vector<string> &num,vector<string> &res,string & r,int pos){
        if(digits.size()==pos||digits.size()==0)
        {
            res.push_back(r);
            return;
        }
        int i=digits[pos]-'0';
        for(auto &j:num[i]){
            r.push_back(j);
            combine(digits,num,res,r,pos+1);
            r.pop_back();
        }
    }
};

18. 4Sum

  • Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
  • 思路同3sum。
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<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        if (nums.size()<4) return res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 3; i++){
            if (i > 0 && nums[i] == nums[i-1]) continue;
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)break;
            if (nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target)continue;
            for (int j = i+1; j < nums.size() - 2; j++){
                if (j > i+1 && nums[j] == nums[j-1])continue;
                if (nums[i]+nums[j]+nums[j+1]+nums[j+2] > target)break;
                if (nums[i]+nums[j]+nums[n-2]+nums[n-1] < target)continue;
                int left = j + 1;
                int right = n - 1;
                while(left < right){
                    if (nums[i]+nums[j]+nums[left]+nums[right] < target)left++;
                    else if (nums[i]+nums[j]+nums[left]+nums[right] > target)right--;
                    else{
                        res.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(left<right && nums[left]==nums[left-1]);
                        do{right--;}while(left<right && nums[right]==nums[right+1]);
                    }
                }
            }
        }
        return res;
    }
};

19. Remove Nth Node From End of List

  • Given a linked list, remove the n-th node from the end of list and return its head.
  • 思路还是很简单，一个指针先走k步，但边界条件很难搞定，比如输入(ListNode* head, int n)分别为([1],1)、([1,2],2),这样输出phead的话就不对了。于是再链表前面新加了一个p0当head，输出p0的下一个。
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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode p0(0);
        p0.next=head;
        ListNode* ppre=&p0,*pn=&p0;
        if(n==1&&head->next==NULL) return NULL;
        for(int i=0;i<n;i++)
        {
            if(pn->next)
                pn=pn->next;
            else
                return head;
        }
        while(pn->next)
        {
            pn=pn->next;
            ppre=ppre->next;
        }
        ListNode* p=ppre->next->next;
        if(n<=0)
            return head;
        ppre->next=p;
        return p0.next;
    }
};

20. Valid Parentheses

  • Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
  • 题目很熟悉，但解法不记得了，这是根据电脑上的记录补充的，等2刷吧。
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:
    bool isValid(string s) {
        if(s.size()%2)
            return false;
        if(s.empty())
            return true;
        int pos=0,next=1;
        int len=s.size()-1;
        while(next<=len)
        {
            if(s[pos]-s[next]<=3&&s[pos]-s[next]>=-3&&s[pos]-s[next]!=0)
            {
                s.erase(s.begin()+pos,s.begin()+pos+2);
                pos=pos==0?pos:pos-1;
                next=pos+1;
            }
            else
            {
                pos+=1;
                next+=1;
            }
            len=s.size()-1;
        }
        if(len<=0)
            return true;
        return false;        
    }
};

21. Merge Two Sorted Lists

  • Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
  • 题目还是不难的，但是我第一遍写的代码还是超级麻烦，看了看大佬们的代码，可以从一下角度优化（简洁）代码：
    1. 随便新建一个头指针，ListNode* head = new ListNode(-1);，然后开始while循环连接链表节点，最后只需输出head-.next。这样便省去了判断l1与l2头节点哪个小，然后赋值给head的过程，使代码更简洁。
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
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head=NULL,*l3=NULL;
        while(l1&&l2)
        {
            if(l1->val<=l2->val)
            {
                if(!head)
                {
                    head=new ListNode(l1->val);
                    l3=head;
                    l1=l1->next;
                }
                else{
                    ListNode* cur =new ListNode(l1->val);
                    l3->next=cur;
                    l3=l3->next;
                    l1=l1->next;
                }
            }
            else{
                if(!head)
                {
                    head=new ListNode(l2->val);
                    l3=head;
                    l2=l2->next;
                }
                else{
                    ListNode* cur =new ListNode(l2->val);
                    l3->next=cur;
                    l3=cur;
                    l2=l2->next;
                }
            }
        }
        if(l1||l2)
        {
            ListNode *l4=l1?l1:l2;
            if(!head)
            {
                head=l4;
                return head;
            }
            else
            {
                l3->next=l4;
            }
        }
        return head;
    }
};

22. Generate Parentheses

  • 给出n个括号的排列组合，Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()”]
  • 思路：每个位置都进可以放 ( 或 ) ，但当此位置前没有单独的 ( 时，不能放置 )，建立一个变量记录没有配对的 ( 个数，然后递归求解。
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:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string p="";
        if(n==0)return res;
        getStr(res,p,n,0);
        return res;
    }
    void getStr(vector<string> &res,string &p,int n,int right)
    {
        if(n==0)
        {
            string s=p,s1(right,')');
            s+=s1;
            res.push_back(s);
        }
        else if(right==0) //right==0，此时只能添加(
        {
            p.push_back('(');
            getStr(res,p,n-1,right+1);
            p.pop_back();
        }
        else
        {
            p.push_back('(');
            getStr(res,p,n-1,right+1);
            p.pop_back();
            p.push_back(')');
            getStr(res,p,n,right-1);
            p.pop_back();
        }
    }
};

23. Merge k Sorted Lists

  • Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
  • 思路：按照合并2个list的思路，将k个list两两合并，然后继续递归合并合并后的k/2个list。
    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
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.size()==0) return NULL;
            queue<ListNode*> z;
            for(auto &i:lists){
                z.push(i);
            }
            while(z.size()!=1)
            {
                ListNode* l1=z.front();
                z.pop();
                ListNode* l2=z.front();
                z.pop();
                z.push(Merge(l1,l2));
            }
            return z.front();
        }
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        {
            if (pHead1 == NULL) return pHead2;
            if (pHead2 == NULL) return pHead1;
            ListNode *mergeList = NULL;
            if (pHead1->val < pHead2->val) {
                mergeList = pHead1;
                mergeList->next = Merge(pHead1->next, pHead2);
            }
            else {
                mergeList = pHead2;
                mergeList->next = Merge(pHead1, pHead2->next);
            }
            return mergeList;
        }
    };

24. Swap Nodes in Pairs

  • Given a linked list, swap every two adjacent nodes and return its head.
  • 开始以为2个指针就能交换完，哼哧哼哧写完发现2个指针版本算法是错的，没办法，只好修改成3指针，关键点：[1,2,3,4]交换完[2,1,4,3]，1的指针需要指向第4位，而不是原来的第3位！！交换步骤是：
    1. 2指向1
    2. 判断1应该指向第3位还是第4位还是NULL，这3种情况分别对应2指针后还有1位、2位以上以及NULL的情况
    3. 如果2指针后还有2位以上，则将1指向3，2指向3->next，3指向3->next->next继续循环
  • 看完题目还是该好好想一下，而不是觉得可以了就开始瞎写，边界条件要考虑清楚！
  • 评论区也有递归的解法
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:
    ListNode* swapPairs(ListNode* head) {
        if(!head||!(head->next)) return head;
        ListNode* p1=head,*p2=head->next,*p3=head->next->next,*p4=head->next;
        while(p2)
        {
            if(p3&&p3->next)
            {
                p1->next=p3->next;
            }
            else if(p3)
            {
                p1->next=p3;
                p2->next=p1;
                break;
            }
            else
            {
                p1->next=NULL;
                p2->next=p1;
                break;
            }
            p2->next=p1;
            p1=p3;
            p2=p3->next;
            p3=p2->next;
        }
        return p4;
    }
};

26. Remove Duplicates from Sorted Array

  • Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
  1. 要求在in-place，不能使用额外空间，首先想到很自然的解法，从后向前遍历，发现重复的元素便erase，但时间效率还是不高，只击败了30%的人。
  2. 改进：遍历数组，同时将不重复元素向前移动，覆盖掉重复元素，见解法二，改进后击败了97%+的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
//解法一：
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0)return 0;
        for(int i=nums.size()-1;i!=0;i--){
            if(nums[i]==nums[i-1]){
                nums.erase(nums.begin()+i);
            }
        }
        return nums.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//解法二：
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int p0=1,p1=1,len=nums.size();
        while(p0<len){
            if(nums[p0]==nums[p0-1])
                p0++;
            else{
                if(p0!=p1){
                    nums[p1]=nums[p0];//用后面的元素覆盖重复元素
                }
                p0++;
                p1++;
            }
        }
        return p1<len?p1:len;
    }
};

27. Remove Element

  • Given an array nums and a value val, remove all instances of that value in-place and return the new length.Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
  • 思路和上体类似啦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//解法一：
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=nums.size();
        if(i==0)return 0;
        else{
        while(i>0){
            if(nums[i-1]==val){nums.erase(nums.begin()+i-1);
            }
            i--;
        }
            return nums.size();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//解法二：
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int p0=0,p1=0,len=nums.size();
        while(p0<len){
            if(nums[p0]==val)
                p0++;
            else{
                if(p0!=p1){
                    nums[p1]=nums[p0];//用后面的元素覆盖重复元素
                }
                p0++;
                p1++;
            }
        }
        return p1;
    }
};

28. Implement strStr()

简单题，从头遍历吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strStr(string haystack, string needle) {
        int l1=haystack.size(),l2=needle.size();
        if(l2==0) return 0;
        if(l1==0||l1<l2) return -1;
        auto p1=haystack.begin(),p2=needle.begin();
        while(p1!=haystack.end()-l2+1){
            if(*p1==*p2){
                for(int i=0;i<l2;i++){
                    if(*(p1+i)!=*(p2+i)) {break;}
                    if(i==l2-1) return p1-haystack.begin();
                }
                p1++;
            }
            else p1++;
        }
        return -1;
    }
};

29. Divide Two Integers

  • Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.Return the quotient after dividing dividend by divisor.The integer division should truncate toward zero.
  • 这题很简单，主要是注意数字不要溢出
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
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        a=1
        b=1
        if(dividend<0):
            dividend=abs(dividend)
            a=-1
        if(divisor<0):
            divisor=abs(divisor)
            b=-1
        if(dividend==0 or dividend<divisor):
            return 0
        res=0
        n=1
        sums=divisor
        while(dividend>=divisor):
            if(dividend>sums):
                dividend-=sums
                res+=n
                n+=n
                sums+=sums
            elif(dividend==sums):
                res+=n
                return res*a*b if res*a*b<=2147483647 else 2147483647
            else:
                n=1
                sums=divisor
        return res*a*b if res*a*b<=2147483647 else 2147483647

30. Substring with Concatenation of All Words

  • You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
  • 这题我不会做，看了别人的题解，代码里面注释很全，字节看代码吧，类似的题目都可以使用这种划窗法来做。
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
//代码转载自：https://www.cnblogs.com/yang-xiong/p/4949285.html
class Solution {
public:
void initializeMap(map<string,int>& map, vector<string>& words){
    for(int i = 0 ;i< words.size();i++){//初始化map
        if(map.count(words[i])==0){
            map[words[i]] = 1;
        }
        else
            map[words[i]] += 1;
    }
}
vector<int> findSubstring(string s, vector<string>& words) {
    map<string, int> mapOfVec;
    int wordsLen = words.size();
    int slen = s.length();
    vector<int> result;
    if(wordsLen == 0 || slen ==0) return result;
    int singleWordLen = words[0].length();//单个字符串长度
    int i,j,count;
    bool countChanged = false;//判断是否改变过map中的值，如果没变则无需重新初始化
    count = wordsLen; //一个计数器表示还需要找到的字串个数
    initializeMap(mapOfVec,words);
    for(i = 0; i<= slen-wordsLen*singleWordLen;i++){
        string subStr = s.substr(i,singleWordLen);// 取出字串
        j = i;
        while(mapOfVec.count(subStr)!=0 && mapOfVec[subStr]!=0 && j+singleWordLen<=slen){//当该字串存在于map中且值大于0，并且j不越界的情况下
            mapOfVec[subStr] -=1; //值减1
            count--;                      
            countChanged = true;   //改变了map的值
            j=j+singleWordLen;
            subStr = s.substr(j,singleWordLen); //下一个字串
            if(mapOfVec.count(subStr)==0){ 
                break;
            }
        }
        if(count==0){
            result.push_back(i); //找齐所有字符串数组中的字串后把该索引压入；
        }
        if(countChanged){ //若未找到而且改变了map的值需要重新初始化map和count
            mapOfVec.clear();
            initializeMap(mapOfVec,words);
            count = wordsLen;
            countChanged = false;
        }
    }
    return result;
}
};

33. Search in Rotated Sorted Array

  • 旋转数组中查找
  • 要求$O(\log n)$求解，自然想到二分查找，中间也遇到了坑，比如max()函数只接受2个参数，我开始传了3个参数进去后报错，还找不出错误在哪。最后还是用的二分查找的改进版，查找n[i：j]，如果n[i]<n[j]，说明数组有序，按正常二分查找来，反之说明数组旋转了，二分之后2个数组n[i:(i+j)//2-1]和n[(i+j)//2+1：j]都要查找（不知道时间复杂度符合要求么）
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.size()<1) return -1;
        int z=-1;
        z=Bsearch(nums,target,0,nums.size()-1);
        return z;
    }
    int Bsearch(vector<int>& nums, int target,int left,int right){
        if(left>right) return -1;
        int mid=(left+right)/2;
        int res=-1;
        if(nums[left]<nums[right]){
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[left]>target||nums[right]<target)
                return -1;
            else if(nums[mid]>target){
                res=max(res,Bsearch(nums,target,left,mid-1));
            }
            else
                res=max(res,Bsearch(nums,target,mid+1,right));
        }
        else{
            if(nums[mid]==target){
                return mid;
            }
            else
                res=max(Bsearch(nums,target,mid+1,right),Bsearch(nums,target,left,mid-1));
        }
        return res;
    }
};

#34. Search for a Range

  • Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.Your algorithm’s runtime complexity must be in the order of O(log n).If the target is not found in the array, return [-1, -1].
  • 看见$O(logn)$就该想到二分查找了。
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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int p1=0,p2=nums.size()-1,p0=(nums.size()-1)/2,p=0;
        vector<int> res={-1,-1};
        if(nums.size()==0||target>nums[p2]||target<nums[0]) return res;
        while(p1<=p2)
        {
            p0=(p1+p2)/2;
            if(nums[p0]>target){
                p2=p0-1;
            }
            else if(nums[p0]<target)
            {
                p1=p0+1;
            }
            else
                break;
        }
        if(nums[p0]==target){
            int b=p0,e=p0;
            if(b>0){
                while(nums[b-1]==target){
                    if(b==1)
                    {
                        b=0;
                        break;
                    }
                    b--;
                }
            }
            if(e<nums.size()-1)
            {
                while(nums[e+1]==target){
                    if(e==nums.size()-2)
                    {
                        e=nums.size()-1;
                        break;
                    }
                    e++;
                }
            }
            res[0]=b;
            res[1]=e;
            return res;
        }
        return res;
    }
};

36. Valid Sudoku

  • Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
  • 每行每列每个box地检查吧，另外这题没有什么必要用递归的（感觉）。改进方式：将每行、每列数字保存在set中，可以在$O(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
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        return valid(board,0,0);
    }
    bool valid(vector<vector<char>>& board,int i,int j) {
        if(board[i][j]!='.'){
            for(int k=0;k<9;k++){// check clomn & line &box
                if(board[i][k]==board[i][j]&&k!=j) return false;
                else if(board[k][j]==board[i][j]&&k!=i) return false;
                else{
                    for(int i0=i/3*3;i0<i/3*3+3;i0++){
                        for(int j0=j/3*3;j0<j/3*3+3;j0++){
                            if(board[i0][j0]==board[i][j]&&(i!=i0&&j!=j0)) return false;
                        }
                    }
                }
            }
        }
        if(i==8&&j==8) return true;
        if(j==8){j=0;i+=1;}
        else
            j+=1;
        return valid(board,i,j);
    }
};

39. Combination Sum

  • Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.The same repeated number may be chosen from candidates unlimited number of times.
  • 此类问题的关键是若满足条件，则将解保存，否则需正确回溯到上一步空间状态，我的思路是：对于第i个元素，有放与不放2种状态，则用递归方式依次搜索着2种状态，另外将数组预先排序，可以降低搜索时间。需要吐槽的是，自己的代码功力还是太弱鸡，开始以为递归的话，sums数组在函数中会被修改，好像就递归不起来了，于是传了个虚参，后来发现可以用实参。然后刚开始考虑，对于第i个元素，我居然写出3种状态来了，然后result最后也传了个虚参，submit后，输出空结果，检查了半天，发现result前面少写了个&。最后总共花了一个多小时，效率太慢了。
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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> sums;
        if(candidates.size()==0) return result;
        int begin=0;
        sort(candidates.begin(), candidates.end());
        getSum(candidates,target,begin,sums,result);
        return result;
    }
    void getSum(vector<int>& candidates, int target,int begin,vector<int> &sums,vector<vector<int>>& result)
    {
        if(candidates[begin]<target)
        {
            sums.push_back(candidates[begin]);
            getSum(candidates,target-candidates[begin],begin,sums,result);//将第i个元素放入解数组并搜索
            sums.pop_back();
            if(begin+1<candidates.size())
            {
                getSum(candidates,target,begin+1,sums,result);//第i个元素不放，并开始考虑i+1元素
            }
        }
        else if(candidates[begin]==target)
        {
            sums.push_back(candidates[begin]);
            result.push_back(sums);
            sums.pop_back();
        }
        else
        {
            return;
        }
    }
};

40. Combination Sum II

  • Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.Each number in candidates may only be used once in the combination.
  • 大体思路与上题一样，感觉没什么区别，就是一个元素只能用1次了，然后我啪啪啪一会就写完，一运行发现结果错了，仔细检查发现，重复的元素会造成干扰，如[1,1,2,3,4]，target=3，我的结果是[[1,2],[1,2]]，这两个1分别是第一、第二个1，然后想到，要么输出结果后对res数组去重，但这样复杂度太高了，于是第二步想用哈希表，将结果插入res数组时先在哈希表中搜索一下，但我哈希表用的不熟悉，写了一会，用的unordered_map<vector,int>，结果还是报错了，不知道是不是vector不能做键值，于是用了第三种方法，思路是：对于第i个元素，有放与不放2种状态，但对于重复元素而言（比较candidates[i]==candidates[i+1]），仅对如果放，按以前一样递归搜索，不放则递归搜索下一个不重复元素。还是以[1,1,2,3,4]为例，如果第一个1放，则考虑第二个1放不放，如果第一个1不放，则考虑第三个元素2放不放，这样便不会出现2个一放第一个和放第二个重复的情况。
    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:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> res;
            vector<int> vec1;
            if(candidates.size()==0) return res;
            sort(candidates.begin(),candidates.end());
            getSum(candidates, target,res,vec1,0);
            return res;
        }
        void getSum(vector<int>& candidates, int target,vector<vector<int>> &res,vector<int> &vec1,int begin)
        {
            if(candidates[begin]<target&&begin<candidates.size()-1)
            {
                vec1.push_back(candidates[begin]);
                getSum(candidates, target-candidates[begin],res,vec1,begin+1);
                vec1.pop_back();
                int i=1;
                while(begin+i<candidates.size()-1)
                {
                    if(candidates[begin]<candidates[begin+i])
                        break;
                    i++;
                }
                getSum(candidates, target,res,vec1,begin+i);
            }
            else if(candidates[begin]==target)
            {
                vec1.push_back(candidates[begin]);
                res.push_back(vec1);
                vec1.pop_back();
            }
        }
    };

41. First Missing Positive

43. Multiply Strings

  • 字符串乘法
  • 不能直接相乘，就位与位相乘吧，这种题用C++麻烦得很，还要考虑大数相乘。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n1,n2=[int(i) for i in num1],[int(i) for i in num2]
        for i in range(len(n1)):
            n1[i]=n1[i]*10**(len(n1)-i-1)
        for i in range(len(n2)):
            n2[i]=n2[i]*10**(len(n2)-i-1)
        res=[]
        for i in n1:
            for j in n2:
                res.append(i*j)
        r=sum(res)
        return str(r)

44. Wildcard Matching

  • Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.
  • 字符串匹配，改了一晚上bug，最后还是TL，麻痹，解法放下面吧，看了别人的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
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
#我的TL解法,看了大神解法，发现了自己TL的原因，很多无意义的搜索，而且递归方式还比较难修改，就这样了，GG
class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if(len(s)==0 and len(p)==0):
            return True      
        elif(len(s)==0):
            if(p.count('*')==len(p)):
                return True
            else:
                return False
        elif(len(p)==0):
            return False
        return self.match(0,0,s,p)
    def match(self,pleft,sleft,s,p):
        if(pleft==len(p) and sleft==len(s)):
            return True
        elif(pleft>=len(p)-1 and p[-1]=='*'):
            return True
        elif(pleft>=len(p)):
            return False
        elif(sleft>=len(s)):
            if(p[pleft:].count('*')==len(p[pleft:])):
                return True
            else:
                return False
        if(p[pleft]=='?'):
            return self.match(pleft+1,sleft+1,s,p)
        elif(p[pleft]=='*'):
            s1=len(p)
            for i in range(pleft+1,len(p)):
                if(p[i]!='*'):
                    s1=i
                    break
            for i in range(sleft,len(s)):
                # 这里重复搜索了很多次！会不停返回上一个*，实际上有些不用返回！
                if(self.match(s1,i,s,p)):
                    return True
        else:
            if(p[pleft]!=s[sleft]):
                return False
            else:
                return self.match(pleft+1,sleft+1,s,p)
        return False
#大神DP解法：https://leetcode.com/problems/wildcard-matching/discuss/17845/Python-DP-solution
class Solution:
# @return a boolean
def isMatch(self, s, p):
    length = len(s)
    if len(p) - p.count('*') > length:
        return False
    dp = [True] + [False]*length
    for i in p:
        if i != '*':
            for n in reversed(range(length)):
                dp[n+1] = dp[n] and (i == s[n] or i == '?')
        else:
            for n in range(1, length+1):
                dp[n] = dp[n-1] or dp[n]
        dp[0] = dp[0] and i == '*'
    return dp[-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
//大神C++解法：https://leetcode.com/problems/wildcard-matching/discuss/17811/My-three-C++-solutions-(iterative-(16ms)-and-DP-(180ms)-and-modified-recursion-(88ms))
class Solution {
public:
    bool isMatch(string s, string p) {
        int  slen = s.size(), plen = p.size(), i, j, iStar=-1, jStar=-1;
        for(i=0,j=0 ; i<slen; ++i, ++j)
        {
            if(p[j]=='*')
            { //meet a new '*', update traceback i/j info
                iStar = i;
                jStar = j;
                --i;
            }
            else
            { 
                if(p[j]!=s[i] && p[j]!='?')
                {  // mismatch happens
                    if(iStar >=0)
                    { // met a '*' before, then do traceback
                        i = iStar++;
                        j = jStar;
                    }
                    else return false; // otherwise fail
                }
            }
        }
        while(p[j]=='*') ++j;
        return j==plen;
    }
};

45. Jump Game II

  • Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Your goal is to reach the last index in the minimum number of jumps.
  • 思路：遍历一遍数组，记录下当前位置与最大可跳跃位置，然后向后遍历，遍历时用一个变量记录下应该跳跃到的位置（即可跳跃到最大位置的位置），当遍历出了当前位置的最大跳跃位置，将当前位置移动到应该跳跃的位置。
    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
    class Solution {
    public:
        int jump(vector<int>& nums) {
            if(nums.size()<=1) return 0;
            int num=0,len=nums.size()-1;
            int pos=0,max_to_pos=nums[0],max_pos=0,pre_to_pos=nums[0];
            for(int i=0;i<=len;i++)
            {
                int to_pos=i+nums[i];
                if(to_pos>max_to_pos)
                {
                    max_to_pos=to_pos;
                    max_pos=i;
                }
                if(i>=pre_to_pos)
                {
                    pre_to_pos=max_to_pos;
                    pos=max_pos;
                    max_to_pos=pos+nums[pos];
                    num+=1;
                }
                else if(i==len) num+=1;
            }
            return num;
        }
    };

46. Permutations

  • Given a collection of distinct integers, return all possible permutations.
  • 递归问题
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:
    vector<vector<int> > permute(vector<int> &num) {
	    vector<vector<int> > result;
	    permuteRecursive(num, 0, result);
	    return result;
    }
    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
	void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
		if (begin >= num.size()) {
		    // one permutation instance
		    result.push_back(num);
		    return;
		}
		for (int i = begin; i < num.size(); i++) {
		    swap(num[begin], num[i]);
		    permuteRecursive(num, begin + 1, result);
		    // reset
		    swap(num[begin], num[i]);
		}
    }
};

47. Permutations II

  • Given a collection of numbers that might contain duplicates, return all possible unique permutations.
  • 类似上题，注意去重
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:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back(nums);
        if(nums.size()==1) return res;
        permute(nums,0,res);
        set<vector<int>> res1(res.begin(),res.end());
        res.clear();
        for(auto i=res1.begin();i!=res1.end();i++){
            res.push_back(*i);
        }
        return res;
    }
    void permute(vector<int> &nums,int begin,vector<vector<int>>& res){
        for(int i=begin;i<nums.size();i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]!=nums[j])
                {
                    nums[i]^=nums[j];
                    nums[j]^=nums[i];
                    nums[i]^=nums[j];
                    res.push_back(nums);
                    permute(nums,i+1,res);
                    nums[i]^=nums[j];
                    nums[j]^=nums[i];
                    nums[i]^=nums[j];
                }
            }
        }
    }
};

49. Group Anagrams

  • Given an array of strings, group anagrams together.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Example:
    Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
    Output:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

  • 首先自己手撸了个，建立个数组，遍历string，将每个元素个数保存在数组里，比较2个数组是否相同，得到答案。但是时间花销太大了，500+ms。代码如下:

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<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string> > res;
        if(strs.size()<1) return res;
        int a[strs.size()]={0};
        for(int i=0;i<strs.size();i++){
            if(a[i]==0){
                vector<string> subres;
                subres.push_back(strs[i]);
                int len=strs[i].size();
                int stri[27]={0};
                for(int j=0;j<len;j++){
                    stri[strs[i][j]-'a']++;
                }
                for(int k=i+1;k<strs.size();k++){
                    if(a[k]==0&&strs[k].size()==len){
                        vector<int> chars(stri,stri+27);
                        for(int j=0;j<len;j++){
                            if(chars[strs[k][j]-'a']>0)
                                chars[strs[k][j]-'a']--;
                            else
                                goto ending;
                        }
                        if(accumulate(chars.begin(),chars.end(),0)==0){
                            subres.push_back(strs[k]);
                            a[k]=1;
                        }
                        ending:
                            int z=0;
                    }
                }
                res.push_back(subres);
            }
        }
        return res;
    }
};
  • 网上别人的哈希表解法，方式是对每个string排序，在哈希表中比较有没有相同string即可。
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:  
    vector<vector<string>> groupAnagrams(vector<string>& strs) {  
        vector<vector<string>> ans;  
        int size=strs.size();  
        if(size<=0){  
            return ans;  
        }  
          
        map<string, vector<string>> hashMap;  
        for(int i=0; i<size; i++){  
            string s=strs[i];  
            string t=s;  
            sort(t.begin(), t.end());  
            map<string, vector<string>>::iterator iter=hashMap.find(t);  
            if(iter==hashMap.end()){  
                vector<string> tV;  
                tV.push_back(s);  
                hashMap.insert(pair<string, vector<string>>(t, tV));  
                #建立hash表，pair<string, vector<string>
                #第一个string为排好序的string
                #第二个vector<string>为排序等于第一个string的string的集合（好像有点绕）
            }else{  
                (iter->second).push_back(s);  
            }  
        }  
          
        for(map<string, vector<string>>::iterator iter=hashMap.begin(); iter!=hashMap.end(); ++iter){  
            vector<string> tV(iter->second);  
            sort(tV.begin(), tV.end());  
            ans.push_back(tV);  
        }  
          
        return ans;  
    }  
};

54. Spiral Matrix

  • 旋转数组，没有什么好解法，上右下左一个一个转吧
    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
    class Solution:
        def spiralOrder(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[int]
            """
            if(len(matrix)==0):
                return []
            elif(len(matrix)==1):
                return matrix[0]
            elif(len(matrix[0])==1):
                return [i[0] for i in matrix]
            total=min(len(matrix),len(matrix[0]))//2
            col=len(matrix[0])#lie
            row=len(matrix)#行
            res=[]
            for i in range(total):
                for j in range(i,col-i):
                    res.append(matrix[i][j])
                for j in range(i+1,row-i):
                    res.append(matrix[j][col-i-1])
                for j in range(col-2-i,i-1,-1):
                    res.append(matrix[row-1-i][j])
                for j in range(row-2-i,i,-1):
                    res.append(matrix[j][i])
            if(min(row,col)-2*total==1):
                if(col>=row):
                    for i in range(total,col-total):
                        res.append(matrix[total][i])
                else:
                    for i in range(total,row-total):
                        res.append(matrix[i][total])
            return res

55. Jump Game

  • Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Determine if you are able to reach the last index.
  • 解题思路：开始想到可能需要用动态规划法，用一个数组存放该位置可以最大跳到哪，后来想了想，只用一个int记录该位置最大可以跳到哪，最后判断该int是否大于初始数组长度就行了；
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:\\感觉代码很简洁啊，居然只击败50%的人，囧
    bool canJump(vector<int>& nums) {
        int l=nums.size(),max_index=0,index=0;
        for(int i=0;i<l;i++)
        {
            index=i+nums[i];
            if(max_index<index) max_index=index;
            if(i>=max_index) break;
        }
        return max_index>=l-1;
    }
};

56. Merge Intervals

  • Given a collection of intervals, merge all overlapping intervals.
  • 合并区间，这个题目我理解错意思了，然后就写了一个相邻区间的合并的函数，最后发现有如下输入：[[2,3][4,5],[5,6][1,10]]，答案应该输出[[1,10]]，而我因为是从第一个开始，相邻的合并，最后只能输出[[2,3][4,5],[1,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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 //代码转载自https://www.cnblogs.com/simplepaul/p/6666489.html
class Solution {
public:
    static bool comp( const Interval &a, const Interval &b)
    {
        return (a.start < b.start);
    }      // 自己定义一个comp函数(必须为静态函数)，用来对 区间的开始值 进行排序
    vector<Interval> merge(vector<Interval>& intervals)
    {
        // start typing your code below
        // if intervals are sorted, it would be easy
        vector<Interval> res;     // 存放结果区间
        if (intervals.empty())   return res; //去掉这句不能AC
        sort(intervals.begin(), intervals.end(),comp);//sort函数的用法
        res.push_back(intervals[0]);// 将第一个区间存放进结果中
        for(int i = 1; i < intervals.size(); ++i)
        {
            if (res.back().end >= intervals[i].start)
                res.back().end = max(res.back().end, intervals[i].end);// 如果区间有重叠则进行区间融合
            else
                res.push_back(intervals[i]);  // 否则将区间直接存入结果
        }
        return res;
    }
};

58. Length of Last Word

  • Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.If the last word does not exist, return 0.
  • 感觉很简单啊。。。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
        def lengthOfLastWord(self, s):
            """
            :type s: str
            :rtype: int
            """
            l=0
            b=1
            for i in s[::-1]:
                if(i!=' '):
                    l+=1
                    b=0
                elif(i==' ' and b==1):
                    continue;
                else:
                    return l;
            return l;

59. Spiral Matrix II

  • Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
    Example:

    Input: 3
    Output:
    [
    [ 1, 2, 3 ],
    [ 8, 9, 4 ],
    [ 7, 6, 5 ]
    ]

  • 在54题的基础上修改的，很快就改出来了，2233
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:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if(n==0):
            return [[]]
        elif(n==1):
            return [[1]]
        total=n//2
        col=n#lie
        row=n#行
        res=[]
        times=1
        matrix=[[0 for i in range(n)] for j in range(n)]
        for i in range(total):
            for j in range(i,col-i):
                matrix[i][j]=times
                times+=1
            for j in range(i+1,row-i):
                matrix[j][col-i-1]=times
                times+=1
            for j in range(col-2-i,i-1,-1):
                matrix[row-1-i][j]=times
                times+=1
            for j in range(row-2-i,i,-1):
                matrix[j][i]=times
                times+=1
        if(min(row,col)-2*total==1):
            if(col>=row):
                for i in range(total,col-total):
                    matrix[total][i]=times
                    times+=1
            else:
                for i in range(total,row-total):
                    matrix[i][total]=times
                    times+=1
        return matrix

61. Rotate List

  • Given a linked list, rotate the list to the right by k places, where k is non-negative.
  • 需要将最后k位旋转到开头，只需找到第k-1位，以及第末位，然后末位指向开头，第k-1位指向NULL，return 第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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head||k==0||!(head->next)) return head;
        int length=0;
        ListNode* pf=head,*pe=head;
        for(;length<k;length++){//一个指针先走k-1步
            if(pf->next){
                pf=pf->next;
            }
            else
                break;
        }
        if(length==k){
            while(pf->next){
                pf=pf->next;
                pe=pe->next;
            }
        }
        else{//链表没有k那么长，则只需旋转k%(length+1)次
            return rotateRight(head,k%(length+1));
        }
        pf->next=head;
        ListNode* res=pe->next;
        pe->next=NULL;
        return res;
        
    }
};

62. Unique Paths

  • A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).How many possible unique paths are there?
  • 思路：最开始想用递归，三两下就把代码写完了，然后提交发现运行超时（因为重复计算！！！时间复杂度$O(n^n)$），最后想了半天还是不会，看讨论区才发现用动态规划法比较好。

63. Unique Paths II

  • An obstacle and empty space is marked as 1 and 0 respectively in the grid.有障碍物。
  • 这题恶心在边界条件，居然存在[[0]]、[[1]]、[[0,1]]、[[1,0]]之类的恶心输入。话说[[1]]这样你机器人怎么落脚？[[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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row=obstacleGrid.size();
        if(row==0)
            return 0;
        int col=obstacleGrid[0].size();
        if(row==1&&col==1)
            return obstacleGrid[0][0]==1?0:1;
        obstacleGrid[0][0]=1-obstacleGrid[0][0];
        for(int i=1;i<row;i++){//第一列仅有1种走法，碰到障碍物的话就只有0种走法
            if(obstacleGrid[i][0]==0){
                obstacleGrid[i][0]=obstacleGrid[i-1][0];
            }
            else
                obstacleGrid[i][0]=0;
        }
        for(int i=1;i<col;i++){//第一行仅有1种走法，碰到障碍物的话就只有0种走法
            if(obstacleGrid[0][i]==0){
                obstacleGrid[0][i]=obstacleGrid[0][i-1];
            }
            else
                obstacleGrid[0][i]=0;
        }
        for(int i=1;i<row;i++){//动态规划过程，n[i,j]=n[i-1,j]+n[i,j-1]，如果n[i,j]有障碍物，则n[i,j]=0
            for(int j=1;j<col;j++){
                if(obstacleGrid[i][j]==0){
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
                }
                else
                    obstacleGrid[i][j]=0;
            }
        }
        return obstacleGrid[row-1][col-1];
    }
};

64. Minimum Path Sum

  • Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
  • 学会用动态规划法写题了QAQ
    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 minPathSum(vector<vector<int>>& grid) {
            vector<int> gridSum(grid[0].size(),grid[0][0]);
            for(int j=0;j<grid.size();j++)
            {
                for(int i=0;i<grid[0].size();i++)
                {
                    if(j==0)
                    {
                        if(i!=0)
                            gridSum[i]=gridSum[i-1]+grid[0][i];
                    }
                    else{
                        if(i==0)
                            gridSum[i]=gridSum[i]+grid[j][i];
                        else
                            gridSum[i]=min(gridSum[i],gridSum[i-1])+grid[j][i];
                    }
                }
            }
            return gridSum[gridSum.size()-1];
        }
    };

69. Sqrt(x)

  • Implement int sqrt(int x).
  • 类似二分搜索
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 mySqrt(int x) {
        long left=0,right=x,mid;
        if(left* left==x || right*right==x)
            return left*left==x?left:right;
        while(left<right)
        {
            mid=(left+right)/2;
            if(mid*mid>x)
                right=mid-1;
            else if(mid*mid<x)
                left=mid+1;
            else if(mid*mid==x)
                return mid;
        }
        if(left*left==x)
            return left;
        return left*left>x?left-1:left;
    }
};

70. Climbing Stairs

  • You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int climbStairs(int n) {
            if(n<=3)
                return n;
            int num1=2,num2=1,nums=3;
            int n_step=4;
            for(int i=4;i<=n;i++)
            {
                int tmp=num1;
                num1=nums;
                num2=tmp;
                nums=num1+num2;
            }
            return nums;
            
        }
    };

73. Set Matrix Zeroes

  • Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
  • 思路：首先想到的是用2个向量分别标记行与列是否需要置0，这样空间复杂度为$O(m+n)$，优化方式为使用1个向量标记某列是否为0，行则在遍历时直接替换，这样空间复杂度为$O(n)$，见解法1。
  • 继续优化：参考大神解法，原本自然而然的思路是用2个向量分别标记行与列是否需要置0，如果不适用额外空间，则可以找到数组中含0的行与列，用于充当上面提到的向量。见解法2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
[
  [0,1,2,3],
  [3,0,5,2],
  [1,3,1,5]
]
找到第一个0在[0,0]处，可用第0行与第0列记录行列是否需要置0。
找到第二个0在[1,1]处，将此0投影到0行0列，可得：
[
  [0,0,2,3],
  [0,0,5,2],
  [1,3,1,5]
]
全部遍历完数组后遍历第0行与第0列即可知道哪些行需要置换为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
//解法1
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        map<int,int> col;
        if(matrix.size()==0||matrix[0].size()==0) return ;
        int y=matrix.size(),x=matrix[0].size();
        for(int j=0;j<y;j++){
            int row=0;
            for(int i=0;i<x;i++){
                if(matrix[j][i]==0){
                    if(col.find(i)==col.end())
                        col[i]=1;
                    row=1;
                }
            }
            if(row){
                for(int i=0;i<x;i++){
                    matrix[j][i]=0;
                }
            }
        }
        auto it=col.begin();
        while(it!=col.end()){
            int j=it->first;
            for(int i=0;i<y;i++){
                matrix[i][j]=0;
            }
            it++;
        }
    }
};
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
//解法二
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col=0,row=0;
        if(matrix.size()==0||matrix[0].size()==0) return;
        int y=matrix.size(),x=matrix[0].size();
        int has0=0;
        for(int j=0;j<y;j++){
            if(!has0){//col 与 row 存储第一个0的位置，使用此行列储存是否需要将此行列置0
                for(int i=0;i<x;i++){
                    if(matrix[j][i]==0){
                        col=i;
                        row=j;
                        has0=1;
                        break;
                    }
                }
            }
            if(has0){//将0投影到 col 与 row 上
                for(int i=0;i<x;i++){
                    if(matrix[j][i]==0){
                        matrix[row][i]=0;
                        matrix[j][col]=0;
                    }
                }
            }
        }
        if((col!=0||row!=0)||(matrix[0][0]==0)){//判断数组中是否有0，没有则不需要置换
        //col与row需最后置换
            for(int j=0;j<y;j++){
                if(matrix[j][col]==0&&j!=row){
                    for(int i=0;i<x;i++){
                        matrix[j][i]=0;
                    }
                }
            }
            for(int i=0;i<x;i++){
                if(matrix[row][i]==0&&i!=col){
                    for(int j=0;j<y;j++){
                        matrix[j][i]=0;
                    }
                }
            }
            for(int j=0;j<y;j++){
                matrix[j][col]=0;
            }
            for(int i=0;i<x;i++){
                matrix[row][i]=0;
            }
        }
    }
};

74. Search a 2D Matrix

  • Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
    • Integers in each row are sorted from left to right.
    • The first integer of each row is greater than the last integer of the previous row.
  • 这题第一次做只会一行一行比较，看讨论区才知道可以二分查找，现在第二次直接就把二分查找写出来了。也不难，也没怎么调bug。
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:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0) return false;
        int row=matrix.size(),col=matrix[0].size();
        if(target<matrix[0][0]||target>matrix[row-1][col-1]) return false;
        if(target==matrix[0][0]||target==matrix[row-1][col-1]) return true;
        int begin=0,total=row*col-1;
        while(begin<=total){
            int mid=(begin+total)/2;
            if(target>getNum(mid,matrix,row,col)){
                begin=mid+1;
            }
            else if(target==getNum(mid,matrix,row,col)){
                return true;
            }
            else{
                total=mid-1;
            }
        }
        return false;
    }
    int getNum(int pos,vector<vector<int>>& matrix,int row,int col){
        int x,y;
        x=pos/col;
        y=pos%col;
        return matrix[x][y];
    }
};

75. Sort Colors

  • Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
  • 大概有2个思路：先遍历一遍，统计0，1，2出现个数，再遍历一遍并赋值（题目好像要求只能遍历一遍。。）。或者可以用2个指针交换位置的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> colorNum={0,0,0};
        for(auto &i:nums){
            colorNum[i]+=1;
        }
        int begin=0;
        for(auto &i:nums){
            while(colorNum[begin]==0)
                begin+=1;
            i=begin;
            colorNum[begin]-=1;
        }
    }
};
  • 好吧，题目不允许遍历2遍，定义2个指针pos0、pos2，pos0当作0与1的交接处，pos2当作1与2的交界处，用pos1从pos0到pos2遍历，如果是1，则pos1++，如果是0，则与pos0交换，且pos0++，如果是2，则与pos2交换，且pos2–。
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:
    void sortColors(vector<int>& nums) {
        if(nums.size()<=1) return;
        int pos0=0,pos2=nums.size()-1;
        while(true){
            if(nums[pos0]==0)
                pos0++;
            if(nums[pos2]==2)
                pos2--;
            if(pos0==pos2)
                return;
            if((nums[pos0]!=0&&nums[pos2]!=2))
                break;
        }
        auto pos1=pos0;
        while(pos1!=pos2+1){
            if(nums[pos1]==1)
                pos1++;
            else if(nums[pos1]==0)
            {
                nums[pos1]=nums[pos0];
                nums[pos0]=0;
                pos0++;
                while(nums[pos0]==0)
                    pos0++;
                pos1=max(pos1,pos0);
            }
            else{
                nums[pos1]=nums[pos2];
                nums[pos2]=2;
                pos2--;
                while(nums[pos2]==2)
                    pos2--;
            }
        }
    }
};

77. Combinations

  • Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
    Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
  • 全排列问题，递归求解
    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:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int> > res;
            if(k<=0) return res;
            vector<int> nums;
            solu(res,nums,1,n,k);
            return res;
        }
        void solu(vector<vector<int> > &res,vector<int> &nums,int begin,int n,int k){
            int len=nums.size();
            if(len==k){
                res.push_back(nums);
                return;
            }
            if(begin>n||len+n-begin+1<k) return;
            nums.push_back(begin);
            solu(res,nums,begin+1,n,k);
            nums.pop_back();
            solu(res,nums,begin+1,n,k);
        }
    };

78. Subsets

  • Given a set of distinct integers, nums, return all possible subsets (the power set).Note: The solution set must not contain duplicate subsets.
  • 递归问题
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<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> r1;
        if(nums.size()==0) return res;
        subs(nums,res,r1,0);
        return res;
    }
    void subs(vector<int>& nums,vector<vector<int>>& res,vector<int>& r1,int pos)
    {
        if(pos<nums.size()-1)
        {
            r1.push_back(nums[pos]);
            subs(nums,res,r1,pos+1);
            r1.pop_back();
            subs(nums,res,r1,pos+1);            
        }
        else
        {
            res.push_back(r1);
            r1.push_back(nums[pos]);
            res.push_back(r1);
            r1.pop_back();
        }
    }
};

79. Word Search

  • Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
  • 在网格中寻找单词，只能在相邻的字母间查找
  • 花了一个小时终于AC了，但效率超级慢，才击败10%的人。。。思路是用一个二维数组count记录原board中字母使用情况，用map记录单词的位置，然后从word开始遍历每次比较2字母位置以及字母是否已经被使用，如果都符合要求则把当前位置字母标记为已使用，并继续遍历下一个，否则回退回去继续搜索。
  • 反思：时间效率低下的原因是每次都必须先遍历数组并保存map，时间及空间的花销都很大，实际上直接遍历数组找word的第一个单词，然后再从相邻元素中找第二个单词，依次迭代即可。
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
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        map<char,vector<vector<int> > > maps;
        vector<vector<int> > count;
        if(board.size()==0||board[0].size()==0||(board.size()*board[0].size()<word.size())) return false;
        for(int i=0;i<board.size();i++){
            vector<int> x;
            for(int j=0;j<board[0].size();j++){
                x.push_back(0);
                if(maps.find(board[i][j])!=maps.end()){
                    vector<int> coor;
                    coor.push_back(i);
                    coor.push_back(j);
                    maps[board[i][j]].push_back(coor);
                }
                else{
                    vector<int> coor={i,j};
                    vector<vector<int> > coors;
                    coors.push_back(coor);
                    maps[board[i][j]]=coors;
                }
                
            }
            count.push_back(x);
        }
        vector<int> position;
        if(word.size()==1){
            return maps.find(word[0])!=maps.end();
        }
        return solu(board,word,0,maps,count,position);
    }
    bool solu(vector<vector<char>>& board, string word,int pos,map<char,vector<vector<int> > >& maps,vector<vector<int> > &count,vector<int>& position){
        if(pos>=word.size()) return true;
        if(maps.find(word[pos])==maps.end()) return false;
        int len=maps[word[pos]].size();
        for(int i=0;i<len;i++){
            if(position.size()!=0){
                if(judge(maps[word[pos-1]][position[pos-1]],maps[word[pos]][i])&&judgePosition(count,maps[word[pos]][i])){
                    position.push_back(i);
                    count[maps[word[pos]][i][0]][maps[word[pos]][i][1]]=1;
                    if(solu(board,word,pos+1,maps,count,position)){
                        return true;
                    }
                    count[maps[word[pos]][i][0]][maps[word[pos]][i][1]]=0;
                    position.pop_back();
                    if(i==len-1)
                        return false;
                }
                if(i==len-1)
                    return false;
            }
            else{
                position.push_back(i);
                count[maps[word[pos]][i][0]][maps[word[pos]][i][1]]=1;
                if(solu(board,word,pos+1,maps,count,position)){
                    return true;
                }
                count[maps[word[pos]][i][0]][maps[word[pos]][i][1]]=0;
                position.pop_back();
                if(i==len-1)
                    return false;
            }
            //return false;
        }
    }
    bool judge(vector<int> &x1,vector<int> &x2){
        int x=abs(x1[0]-x2[0]);
        int y=abs(x1[1]-x2[1]);
        return x+y==1;
    }
    bool judgePosition(vector<vector<int> > &x1,vector<int> &x2){
        return x1[x2[0]][x2[1]]==0;
    }
};

80. Remove Duplicates from Sorted Array II

  • Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
  • 遍历数组，记录下重复数字的个数，同时，记录下新数组的长度。下面为各种可能性：
    1. 开始遍历时，新数组指针与遍历指针一致，如果数字没有重复超过2个，则新数组指针与遍历指针同时向右移动一位。
    2. 如果数字重复3个以上，则仅移动遍历的指针，新数组指针所指位置代表需要替换的位置。此时新数组指针与遍历指针错开了。
    3. 当新数组指针与遍历指针错开，则需判断 1. 数字重复次数小于2时，说明此数字选哟保留，则将遍历指针数字赋值给新数组指针，并且数字重复次数+1。2. 当数字重复次数大于2时，说明此数字已经保留了2个，多余的不需要保存，仅需将遍历指针移动。
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 removeDuplicates(vector<int>& nums) {
        int len=1,sizes=nums.size();
        if(sizes<=2) return sizes;
        int times=1;
        for(int i=1;i<sizes;i++){
            if(nums[i]!=nums[i-1]){
                if(len!=i){
                    nums[len]=nums[i];
                }
                times=1;
                len++;
            }
            else {
                times+=1;
                if(len!=i){
                    if(times<3){
                        nums[len]=nums[i];
                        len++;
                    }
                }
                else if(times<3){
                    len++;
                }
            }
        }
        return len;
    }
};

81. Search in Rotated Sorted Array II

  • Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).You are given a target value to search. If found in the array return true, otherwise return false.
  • 分成2半递归着二分搜索吧。
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:
    bool search(vector<int>& nums, int target) {
        if(nums.size()==0)
            return false;
        else if(nums.size()==1)
            return target==nums[0]?true:false;
        return searchHalf(nums, target,0,nums.size()-1);
    }
    bool searchHalf(vector<int>& nums, int target,int left,int right){
        if(left>right)
            return false;
        if(nums[left]<nums[right]){
            //递增
            if(target<nums[left]||target>nums[right])
                return false;
            else if(target==nums[left]||target==nums[right])
                return true;
            else{//二分搜索
                int half=(left+right)/2;
                if(target==nums[half])
                    return true;
                if(target>nums[half]){
                    return searchHalf(nums, target,half+1,right);
                }
                if(target<nums[half])
                    return searchHalf(nums, target,left,half-1);
            }
        }
        else{
            int half=(left+right)/2;
            if(nums[half]==target)
                return true;
            return searchHalf(nums, target,half+1,right)||searchHalf(nums, target,left,half-1);
        }
    }
};

82. Remove Duplicates from Sorted List II

  • Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
  • 基础题吧。
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *newHead=new ListNode(head->val-1);
        newHead->next=head;
        ListNode *pre,*now,*next;
        pre=newHead;
        now=pre->next;
        next=now->next;
        bool isDup=false;
        while(next!=NULL)
        {
            if(next->val==now->val)
            {
                now=next;
                next=next->next;
                isDup=true;
                if(next==NULL)
                    pre->next=NULL;
            }
            else if(!isDup)
            {
                pre=now;
                now=next;
                next=next->next;
            }
            else if(isDup){
                pre->next=next;
                now=next;
                next=next->next;
                isDup=false;
            }
        }
        return newHead->next;
    }
};

83. Remove Duplicates from Sorted List

  • Given a sorted linked list, delete all duplicates such that each element appear only once.
  • 基础题
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *pre,*now,*next;
        pre=head;
        now=pre->next;
        next=now->next;
        while(now!=NULL)
        {
            if(pre->val==now->val)
            {
                pre->next=next;
                now=next;
                if(next!=NULL)
                    next=next->next;
            }
            else
            {
                pre=now;
                now=next;
                if(next!=NULL)
                    next=next->next;
            }
        }
        return head;
    }
};

88. Merge Sorted Array

  • Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
  • 基础题，但有个bug检查了很久。。。
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:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int length=m+n-1;
        --m;
        --n;
        if(n<0) return;
        while(n>=0)
        {
            if(nums1[m]>nums2[n]&&m>=0)
            {
                nums1[length]=nums1[m];
                m-=1;
            }
            else
            {
                nums1[length]=nums2[n--];
            }
            length-=1;
        }
    }
};

91. Decode Ways

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
//https://blog.csdn.net/u012501459/article/details/46550815
class Solution {
public:
    int numDecodings(string s) {
        int length=s.size();
        if(length==0)
            return 0;
            
        int current=s[0]=='0'?0:1;
        int last=1;
        for(int i=1;i<length;i++)
        {
            int tmp=current;
            if(s[i]=='0')
            {
                if(s[i-1]=='1'||s[i-1]=='2')
                     current=last;
                else 
                    return 0;
            }
            else if(s[i-1]=='1'||s[i-1]=='2'&&s[i]<='6')
                current+=last;
            else 
                current=current;
            
            last=tmp;
        }
        
        return current;
    }
};

112. Path Sum

  • Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)
            return false;
        return sums(root,sum,0);
    }
    bool sums(TreeNode* node, int sum,int n)
    {
        if(!(node->left)&&!(node->right))
            return n+node->val==sum;
        else if(!(node->left)||!(node->right))
            return !(node->left)?sums(node->right,sum,n+node->val):sums(node->left,sum,n+node->val); 
        else
            return sums(node->left,sum,n+node->val)||sums(node->right,sum,n+node->val); 
    }
};

113. Path Sum II

  • Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
  • 深度优先搜索，用python写了一个，注意list.copy()
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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        self.res=[]
        self.sum=sum
        self.path=[]
        if(root==None):
            return self.res
        self.sol(root,0)
        return self.res
        
    def sol(self,node,add):
        if(node.left==None and node.right==None):
            add+=node.val
            self.path.append(node.val)
            if(add==self.sum):
                self.res.append(self.path.copy())
        else:
            add+=node.val
            self.path.append(node.val)
            if(True):
                if(node.left):
                    self.sol(node.left,add)
                    self.path.pop()
                if(node.right):
                    self.sol(node.right,add)
                    self.path.pop()

202. Happy Number

  • 题目描述：A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
  • 解题思路：没什么思路，硬解吧（讨论区有用2个指针的方法，挺不错，即快指针追上慢指针，说明变成一个环了）
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://Runtime: 4 ms,beat 86%
    bool isHappy(int n) {
        vector<int> num={0};
        int x=n;
        bool a=true;
        while(x!=1)
        {
            x=all_sum(x);
            for(auto &i:num)
            {
                if(x==i)
                {
                    a=false;
                    goto end;
                }
            }
            num.push_back(x);
        }
        end:
            return a;
    }
    int all_sum(int n)
    {
        int sum=0;
        while(n){
            sum+=pow(n%10,2);
            n/=10;
        }
        return sum;
    }
};

204. Count Primes

  • Count the number of prime numbers less than a non-negative number, n.
  • 如此短的题目，看完后不明所以，看讨论区也看不懂，然后找到一篇博客，讲的很清楚，反正我完全不会做 QAQ。

231. Power of Two

  • 题目描述：Given an integer, write a function to determine if it is a power of two.
  • 解题思路：首先想到的是递归，然后想用位运算，看了讨论区才发现一个二的指数的特性，如果一个数n为2的指数倍的话，二进制表示为$0\times0100$，则n-1为$0\times0011$，n&(n-1)=0，可用此特性来判断。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isPowerOfTwo(int n) {
        long long i=1;
        while(n>=i)
        {
            if(i==n) return true;
            i=i<<1;
        }
        return false;
    }
};

242. Valid Anagram

  • 题目描述：Given two strings s and t , write a function to determine if t is an anagram of s.
  • 思路：哈希表或者排序之后对比，见讨论区总结
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> judge(27,0);
        if(s.size()!=t.size()) return false;
        for(auto i=s.begin(),j=t.begin();i!=s.end()&&j!=t.end();i++,j++)
        {
            judge[*i-'a']++;
            judge[*j-'a']--;
        }
        return count(judge.begin(),judge.end(),0)==27;
    }
};

326. Power of Three

  • 题目描述：Given an integer, write a function to determine if it is a power of 3.
  • 解题思路：题目要求不要用循环，就直接写了个递归，然后看了下讨论区，各种各样的解法，什么log的，最大数的，见讨论区总结)
1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n==1||n==3) return true;
        if(n%3!=0||n==0) return false;
        else return isPowerOfThree(n/3);
    }
};

367. Valid Perfect Square

  • 题目描述：Given a positive integer num, write a function which returns True if num is a perfect square else False.
  • 思路：二分搜索

NO.387 First Unique Character in a String

  • 题目描述：Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.（找到给定的string的第一个不重复的字符。）
  • 解题思路：刚看到这个题目，感觉没有什么特别好的解法，除了2个指针遍历的$O(n^2)$的解法，解法二是建立哈希表，这样只需遍历一遍 string 和一遍哈希表，解法三，建立一个包含26元素的数组，数组中每个数字代表对应的字母的个数，遍历 string 后，遍历数组，返回第一个为1的index。
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:
    int firstUniqChar(string s) {
        unordered_map<char, int> m;
        for (auto &c : s) {
            m[c]++;
        }
        for (int i = 0; i < s.size(); i++) {
            if (m[s[i]] == 1) return i;
        }
        return -1;
    }
};
//解法三
class Solution {
public:
    int firstUniqChar(string s) {
        int alphabet[26] = {0};
        for (int i = 0; i < s.size(); ++i){++alphabet[s[i] -'a'];}
        int i = 0;
        while (i < s.size() && alphabet[s[i]-'a'] > 1) ++i;
        return i == s.size() ? -1 : i;
    }
};
  • 此外还有个 Python 解法-!)，感觉很强，在此分享下：
1
2
3
4
5
6
7
8
def firstUniqChar(self, s):
    """
    :type s: str
    :rtype: int
    """
    letters='abcdefghijklmnopqrstuvwxyz'
    index=[s.index(l) for l in letters if s.count(l) == 1]
    return min(index) if len(index) > 0 else -1

NO.389. Find the Difference

  • Given two strings s and t which consist of only lowercase letters.String t is generated by random shuffling string s and then add one more letter at a random position.Find the letter that was added in t.
  • 思路：看讨论区里的，用异或解，或者字符求和后做差。
1
2
3
4
5
6
7
8
9
class Solution {
public:
    char findTheDifference(string s, string t) {
        int j=0;
        for(auto &i:s) j=j^i;
        for(auto &i:t) j=j^i;
        return j;
    }
};

NO.434. Number of Segments in a String

  • 题目描述：Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.（计算string中的单词个数）
  • 解题思路：计算单词间的空格个数。另外看到个挺新颖的解法，分享下：
1
2
3
4
5
//The stringstream >> operator will output strings separated by white spaces until exhausting all strings.
    int countSegments(string s) {
      stringstream ss(s); int res = 0;
      while (ss >> s) ++res; return res;
    }

438. Find All Anagrams in a String

  • Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
  • 思路：反正我没想到什么好思路，写了个超复杂的QAQ
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://运行时间超过3%的人QAQ
    vector<int> findAnagrams(string s, string p) {
        vector<int> sums,results;
        vector<float> times;
        int ls=s.size(),lp=p.size();
        if(lp>ls) return results;
        for(int i=0;i<=ls-lp;i++)
        {
            int sum=0,time=0;
            for(int j=i;j<=i+lp-1;j++)
            {
                sum+=s[j];
                time+=(100.0/(s[j]-'a'+1));
            }
            sums.push_back(sum);
            times.push_back(time);
        }
        int Psum=0,Ptime=0;
        for(int i=0;i<=lp-1;i++)
        {
            Psum+=p[i];
            Ptime+=100.0/(p[i]-'a'+1);
        }
        for(int i=0;i<=sums.size()-1;i++)
        {
            if(sums[i]==Psum&&times[i]==Ptime)
                results.push_back(i);
        }
        return results;
    }
};

443. String Compression

  • 题目描述：Given an array of characters, compress it in-place.
    The length after compression must always be smaller than or equal to the original array.Every element of the array should be a character (not int) of length 1.After you are done modifying the input array in-place, return the new length of the array.Follow up:Could you solve it using only O(1) extra space?（将[“a”,”a”,”b”,”b”,”c”,”c”,”c”] 缩并成 [“a”,”2”,”b”,”2”,”c”,”3”] 形式，要求：在原容器上更改）

  • 解题思路：定义3个指针，第一个指向缩并后数组末尾，负责指定下一个需替换的元素，第二、三个指针遍历数组，统计字符个数。看了下讨论区，大家思路都差不多（为什么我的才超过82% QAQ ）。

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://Runtime: 8 ms,beat 82.94%
    int compress(vector<char>& chars) {
        if(chars.size()==1) return 1;
        auto p=chars.begin(),p0=chars.begin();
        char c;
        for(;p0!=chars.end();)
        {
            int count=0;
            c=*p0;
            auto p1=p0;
            for(;p1!=chars.end();p1++)
            {
                if(*p1!=*p0)
                {
                    p0=p1;
                    break;
                }
                else
                    count++;
            }
            *p=c;
            p++;
            if(count>1)
            {
                string s1=to_string(count);
                for(auto &i:s1)
                {
                    *p=i;
                    p++;
                }
            }
            if(p1==chars.end()) break;
        }
        chars.erase(p,chars.end());
        return chars.size();
    }
};

454. 4Sum II

  • Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

    Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
  • 思路与前面的ksum类似，可以用hash，或者4指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        E = {}
        for a in A:
            for b in B:
                if a+b not in E:
                    E[a+b] = 0
                E[a+b] += 1
        ans = 0
        for c in C:
            for d in D:
                if -(c+d) in E:
                    ans += E[-(c+d)]
        return ans

520. Detect Capital

  • 题目描述：判断单词是否为Capital，单词为Capital的条件为：

    1. All letters in this word are capitals, like “USA”.
    2. All letters in this word are not capitals, like “leetcode”.
    3. Only the first letter in this word is capital if it has more than one letter, like “Google”.

  • 解题思路：统计单词中大写单词的个数。（查看讨论区发现有 count_if 函数挺好用的）

    1. std::count(first,last,value)：first是容器的首迭代器，last是容器的末迭代器，value是询问的元素，整个函数返回ｉｎｔ型。count函数的功能是：统计容器中等于value元素的个数。
    2. std::count_if(first,last,comp) (在comp为true的情况下计数）　或者　count_if(first,last,value,comp) (这个是在comp为true的情况下统计容器中等于value的元素）：first为首迭代器，last为末迭代器，value为要查询的元素，comp为比较bool函数，为true则计数，函数返回型是int。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public://runtime 15ms;beat 64%
    bool detectCapitalUse(string word) {
        int count=0;
        for(auto &i:word)
        {
            if(i>='A'&&i<='Z')
            {
                count++;
            }
        }
        if(count==word.size()||(count==1&&word[0]<='Z')||count==0) return true;
        return false;
    }
};

541. Reverse String II

  • 题目描述：Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
  • 解题思路：用 reverse 翻转吧（这里有个坑，reverse(first,end)，是反转[first,end)，左开右闭，我一开始认为2边都是闭，结果反转得不对，晕）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string reverseStr(string s, int k) {
        if(k<=1) return s;
        for(int i=0;;i+=(2*k))
        {
            if(i+k<=s.size())
                reverse(s.begin()+i,s.begin()+i+k);
            else
            {
                reverse(s.begin()+i,s.end());
                break;
            }
        }
        return s;
    }
};

551. Student Attendance Record I

  • 题目描述：Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
  • 思路：统计L、A个数而已。

557. Reverse Words in a String III

  • 题目描述：You need to return whether the student could be rewarded according to his attendance record.
  • 思路：挺简单的，找空格而已。

606. Construct String from Binary Tree

  • 题目描述：You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.（打印二叉树）
  • 思路：递归做吧，不麻烦
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://自己写的有些啰嗦，明明一个函数就可以递归了，偏偏爱写2个
    string tree2str(TreeNode* t) {
        string tree;
        if(!t) return tree;
        get_tree(t,tree);
        return tree;
    }
    void get_tree(TreeNode* t,string &tree)
    {
        tree+=(to_string(t->val));
        if(!(t->left))
        {
            if((t->right))
            {
                tree+="()(";
                get_tree(t->right,tree);
                tree+=")";
            }
        }
        else
        {
            tree+="(";
            get_tree(t->left,tree);
            tree+=")";
            if(t->right)
            {
                tree+="(";
                get_tree(t->right,tree);
                tree+=")";
            }
        }
    }
};

657. Judge Route Circle

  • 题目描述：判断机器人是否回到原点
  • 思路：通过坐标x,y，很简单。

本文标题:leetcode 刷题总结

文章作者:微石

发布时间:2018年07月13日 - 10:07

最后更新:2018年07月19日 - 11:07

原始链接:akihoo.github.io/posts/c80e95e5.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。