Monodyee

这个屌丝很懒，什么也没留下！

热门标签

leetcode-高频题题解

作者：Monodyee | 2024-02-19 17:22:31

踩

leetcode-高频题题解

1. Two Sum

hashmap的2-sum模板

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.size()==0){
            return res;
        }

        unordered_map<int,int> m;
        for(int i=0;i<nums.size();++i){
            int t = target-nums[i];
            if(m.count(t)){
                res.push_back(m[t]);
                res.push_back(i);
                return res;
            }
            else{
                m[nums[i]] = i;
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

8. String to Integer (atoi)

返回值是int型：

class Solution {
public:
    int myAtoi(string str) {
        int num = 0;
        int sign = 1;
        const int n = str.size();
        int i = 0;

        while (str[i] == ' ' && i < n) i++; //忽略空格

        if (str[i] == '+') i++; //判断正负号
        else if (str[i] == '-') {
            sign = -1;
            i++;
        }

        for (; i < n; i++) {
            if (str[i] == '-' || !isdigit(str[i])) //当出现非数字字符，忽略之后的数字
                break;
            if (num > INT_MAX / 10 ||(num == INT_MAX / 10 && (str[i] - '0') > INT_MAX % 10)) {
                return sign == -1 ? INT_MIN : INT_MAX;
            }
            num = num * 10 + str[i] - '0';
        }
        return num * sign;
    }
};
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

返回值是long：

int myAtoi(string str) {
    long result = 0;
    int indicator = 1;
    for(int i = 0; i<str.size();)
    {
        i = str.find_first_not_of(' ');
        if(str[i] == '-' || str[i] == '+')
            indicator = (str[i++] == '-')? -1 : 1;
        while('0'<= str[i] && str[i] <= '9')
        {
            result = result*10 + (str[i++]-'0');
            if(result*indicator >= INT_MAX) return INT_MAX;
            if(result*indicator <= INT_MIN) return INT_MIN;               
        }
        return result*indicator;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

15. 3Sum

需要去重的2-sum模板

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3){
            return res;
        }

        sort(nums.begin(),nums.end());

        for(int i=0;i<nums.size();++i){
            if(i!=0 && nums[i]==nums[i-1]){
                continue;
            }

            int target = 0-nums[i];
            int l = i+1,r=nums.size()-1;
            while(l<r){
                int sum = nums[l] + nums[r];
                if(sum == target){
                    vector<int> pair;
                    pair.push_back(nums[i]);
                    pair.push_back(nums[l]);
                    pair.push_back(nums[r]);
                    res.push_back(pair);
                    ++l;
                    --r;

                    while(l<r && nums[l] == nums[l-1]){
                        l++;
                    }

                    while(l<r && nums[r] == nums[r+1]){
                        r--;   
                    }

                }
                else if(sum>target){
                    r--;
                }
                else{
                    l++;
                }
            }
        }

        return res;
    }
};


- public class Solution {
-     public List<List<Integer>> threeSum(int[] num) {
-         List<List<Integer>> ans = new ArrayList<>();
-         if(num != null && num.length >= 3){
-             Arrays.sort(num);
-             HashMap<Integer, Integer> map = new HashMap<>();
-             HashMap<Integer, Integer> pointer = new HashMap<>();
-             for(int i = 0; i < num.length; ++i){
-                 Integer count = map.get(num[i]);
-                 if(count == null){
-                     count = 0;
-                     pointer.put(num[i], i);
-                 }
-                 map.put(num[i], count + 1);
-             }
-             // List<Integer> l = new ArrayList<>(4);
-             int zero = 0;
-             for(int i = 0, j = i + 1; i < num.length; ){
-                 j = i + 1;
-                 while(j < num.length){
-                     int remain = zero - num[i] - num[j];
-                     Integer count = map.get(remain);
-                     boolean flag = false;
-                     if(count != null){
-                         int site = pointer.get(remain);
-                         if(site > j){
-                             flag = true;
-                         }
-                         else if(site == j && count >= 2){
-                             flag = true;
-                         }
-                         if(flag){
-                             List<Integer> l = new ArrayList<>();
-                             l.add(num[i]);l.add(num[j]);l.add(remain);
-                             ans.add(l);
-                         }
-                     }
-                     while( ++j < num.length && num[j] == num[j - 1]);
-                 }
-                 while( ++i < num.length && num[i] == num[i - 1]);
-             }
-             if(map.get(0) != null && map.get(0) >= 3){
-                 List<Integer> l = new ArrayList<>();
-                 l.add(0);l.add(0);l.add(0);
-                 ans.add(l);
-             }
-
-         }
-         return ans;
-     }
- }
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
96
97
98
99
100
101
102

20. Valid Parentheses

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i=0;i<s.size();++i){
            switch(s[i]){
                case '(':
                case '{':
                case '[':st.push(s[i]);break;
                case ')':if(st.empty() || st.top() != '(') return false; else st.pop();break;
                case '}':if(st.empty() || st.top() != '{') return false; else st.pop();break;
                case ']':if(st.empty() || st.top() != '[') return false; else st.pop();break;
                default: ;
            }
        }

        return st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

21. Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while(l1 && l2){
            if(l1->val < l2->val){
                tail->next = l1;
                l1 = l1->next;
            }
            else{
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        if(l1){
            tail->next = l1;
        }

        if(l2){
            tail->next = l2;
        }

        return dummy.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
32
33
34
35
36
37

28. Implement strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(!needle.size()) return 0;
        else if(haystack.size()<needle.size()) return -1;

        for(int i=0;i<haystack.size()-needle.size()+1;++i){
            int j=0;
            for(;j<needle.size();++j){
                if(haystack[i+j]!=needle[j])
                    break;
            }
            if(j==needle.size())
                return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

50. Pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0){
            return 1.0;
        }

        if(n==INT_MIN){
            return myPow(x,-n/2) * myPow(x,-n/2);
        }

        if(n<0){
            return 1.0/myPow(x,-n);
        }

        double half = myPow(x,n/2);
        if((n & 1) == 0){
            return half*half;
        }

        return x*half*half;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

56. Merge Intervals

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        if(!intervals.size() || intervals.size()==1) return intervals;

        sort(intervals.begin(),intervals.end(),SortByM1);
        Interval t(intervals[0].start,intervals[0].end);
        for(int i=1;i<intervals.size();++i){
            if(intervals[i].start>t.end){
                res.push_back(t);
                t.start=intervals[i].start;
                t.end=intervals[i].end;
            }
            else{
                t.end=max(intervals[i].end,t.end);
            }
        }
        res.push_back(t);
        return res;
    }

    static bool SortByM1(Interval v1, Interval v2)//注意：本函数的参数的类型一定要与vector中元素的类型一致 
    { 
        if(v1.start != v2.start)
            return v1.start < v2.start;//升序排列 
        else
            return v1.end < v2.end;
    }
};
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

57. Insert Interval

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        if(!intervals.size()){
            res.push_back(newInterval);
            return res;
        }

        int index=0;
        while(index < intervals.size() && intervals[index].end < newInterval.start){
            res.push_back(intervals[index++]);
        }

        while(index < intervals.size() && intervals[index].start <= newInterval.end){
            newInterval.start = min(newInterval.start, intervals[index].start);
            newInterval.end = max(newInterval.end, intervals[index].end);
            index++;
        }

        res.push_back(newInterval);
        while(index < intervals.size()){
            res.push_back(intervals[index++]);
        }

        return res;
    }
};
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

65. Valid Number

有限状态自动机：

class Solution {
public:
    bool isNumber(string str) {
        int state=0, flag=0; // flag to judge the special case "."
        while(str[0]==' ')  str.erase(0,1);//delete the  prefix whitespace
        while(str[str.length()-1]==' ') str.erase(str.length()-1, 1);//delete the suffix whitespace
        for(int i=0; i<str.length(); i++){
            if('0'<=str[i] && str[i]<='9'){
                flag=1;
                if(state<=2) state=2;
                else state=(state<=5)?5:7;
            }
            else if('+'==str[i] || '-'==str[i]){
                if(state==0 || state==3) state++;
                else return false;
            }
            else if('.'==str[i]){
                if(state<=2) state=6;
                else return false;
            }
            else if('e'==str[i]){
                if(flag&&(state==2 || state==6 || state==7)) state=3;
                else return false;
            }
            else return false;
        }
        return (state==2 || state==5 || (flag&&state==6) || state==7);
    }
};
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

分情况讨论：

bool isNumber(string s) {       
        int i = 0;

        // skip the whilespaces
        for(; s[i] == ' '; i++) {}

        // check the significand
        if(s[i] == '+' || s[i] == '-') i++; // skip the sign if exist

        int n_nm, n_pt;
        for(n_nm=0, n_pt=0; (s[i]<='9' && s[i]>='0') || s[i]=='.'; i++)
            s[i] == '.' ? n_pt++:n_nm++;       
        if(n_pt>1 || n_nm<1) // no more than one point, at least one digit
            return false;

        // check the exponent if exist
        if(s[i] == 'e') {
            i++;
            if(s[i] == '+' || s[i] == '-') i++; // skip the sign

            int n_nm = 0;
            for(; s[i]>='0' && s[i]<='9'; i++, n_nm++) {}
            if(n_nm<1)
                return false;
        }

        // skip the trailing whitespaces
        for(; s[i] == ' '; i++) {}

        return s[i]==0;  // must reach the ending 0 of the 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

70. Climbing Stairs

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        else
        {
            int dp[n+1];
            dp[1]=1;dp[2]=2;
            for(int i=3;i<n+1;i++)
            {
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[n];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

73. Set Matrix Zeroes

void setZeroes(vector<vector<int>>& matrix) {
        bool row = false, col = false;
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == 0) {
                    if(i == 0) row = true;
                    if(j == 0) col = true;
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        for(int i = 1; i < matrix.size(); i++){
            for(int j = 1; j < matrix[0].size(); j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        if(col){
            for(int i = 0; i < matrix.size(); i++) matrix[i][0] = 0;
        }
        if(row){
            for(int j = 0; j < matrix[0].size(); j++) matrix[0][j] = 0;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

88.Merge Sorted Array

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1,j=n-1,k=m+n-1;
        while(i>=0&&j>=0){
            if(nums1[i]>nums2[j]) nums1[k--]=nums1[i--];
            else nums1[k--]=nums2[j--];
        }
        while(j>=0) nums1[k--]=nums2[j--];
    }
1
2
3
4
5
6
7
8

98.Validate Binary Search Tree

/**
 * 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:
    vector<int> list;
    bool isValidBST(TreeNode* root) {
        if(!root){
            return true;
        }

        inorder(root);
        for(int i=1;i<list.size();++i){
            if(list[i]<=list[i-1]){
                return false;
            }
        }
        return true;
    }
    void inorder(TreeNode* root){
        if(!root){
            return;
        }

        inorder(root->left);
        list.push_back(root->val);
        inorder(root->right);
    }

};

TreeNode* pre = NULL;
bool isValidBST(TreeNode* root) {
    if(root){
        if(!isValidBST(root->left)){
            return false;
        }
        if(pre && pre->val >= root->val){
            return false;
        }

        pre = root;

        return isValidBST(root->right);
    }

    return true;
}
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

125.Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        transform(s.begin(),s.end(),s.begin(),::tolower);

        int l=0,r=s.size()-1;
        while(l<r){
            if(!::isalnum(s[l])){
                l++;
            }
            else if(!::isalnum(s[r])){
                r--;
            }
            else if(s[l++] != s[r--]){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Leet Code, Valid Palindrome
// 时间复杂度 O(n)，空间复杂度 O(1)

class Solution {
public:
     bool isPalindrome(string s) {
          transform(s.begin(), s.end(), s.begin(), ::tolower);
          auto left = s.begin(), right = prev(s.end());
          while (left < right) {
               if (!::isalnum(*left)) ++left;
               else if (!::isalnum(*right)) --right;
               else if (*left++ != *right--) return false;
          }
          return true;
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

127.Word Ladder

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(beginWord.size()==0 || endWord.size()==0 || beginWord.size()!=endWord.size()){
            return 0;
        }

        int L = beginWord.size();

        int step = 1;
        unordered_set<string> s(wordList.begin(),wordList.end());
        queue<string> q;
        q.push(beginWord);
        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;++i){
                string word = q.front();
                q.pop();
                for(int j=0;j<L;++j){
                    char ch = word[j];
                    for(char c = 'a';c<='z';++c){
                        if(c == ch){
                            continue;
                        }
                        word[j] = c;
                        if(s.find(word) != s.end()){
                            q.push(word);
                            s.erase(word);
                            if(word == endWord){
                                return step+1;
                            }
                        }
                    }
                    word[j] = ch;
                }
            }
            step++;
        }

        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.Add Two Numbers

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode prehead(0),* p=&prehead;
        int extra = 0;
        while(l1 || l2 || extra){
            int sum = (l1?l1->val:0) + (l2?l2->val:0) + extra;
            extra = sum/10;
            p->next = new ListNode(sum%10);
            p = p->next;
            l1=l1?l1->next:l1;
            l2=l2?l2->next:l2;
        }
        return prehead.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

12.Integer to Roman

class Solution {
public:
    string intToRoman(int num) {
        string str="";
        string s[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int nums[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};

        for(int i=0;i<13 && num;++i){
            int c = num/nums[i];
            num %= nums[i];
            for(int j=0;j<c;++j){
                str+=s[i];
            }
        }
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

13.Roman to Integer

class Solution {
public:
    int romanToInt(string s) {
        if(s.empty()) return 0;
        int ret=charToInt(s[0]);

        int pre=ret;
        for(int i=1;i<s.size();i++){
            int t=charToInt(s[i]);
            if(t<=pre)
                ret+=t;
            else
                ret+=t-2*pre;
            pre=t;
        }
        return ret;
    }
    int charToInt(char c) { 
        int data = 0; 

        switch (c) { 
            case 'I': 
                data = 1; 
                break; 
            case 'V': 
                data = 5; 
                break; 
            case 'X': 
                data = 10; 
                break; 
            case 'L': 
                data = 50; 
                break; 
            case 'C': 
                data = 100; 
                break; 
            case 'D': 
                data = 500; 
                break; 
            case 'M': 
                data = 1000; 
                break; 
        }   
        return data; 
    } 
};
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

22.Generate Parentheses

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(res, 0, 0, n, "");
        return res;
    }
    void dfs(vector<string> &res, int left, int right, int n, string str){
        if(!n) return;
        if(left == n && right == n){
            res.push_back(str);
        }

        if(left > n || right > left)
            return;

        dfs(res, left+1, right, n, str + "(");
        dfs(res, left, right+1, n, str + ")");
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

23. k Sorted Lists

见 “九章算法” 笔记本下的笔记 “ch8 - Heap堆”

24.Swap Nodes in Pairs

ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0);
        dummy.next=head;

        ListNode* prev=&dummy;
        while(head &&head->next)
        {
            ListNode* nn=head->next->next;
            prev->next=head->next;
            head->next->next=head;
            head->next=nn;
            prev=head;
            head=nn;

        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

27.Remove Element

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()==0){
            return 0;
        }

        int i=0, j=0;
        while(j<nums.size()){
            if(nums[j] != val){
                nums[i++] = nums[j++];
            }
            else{
                j++;
            }
        }

        return i;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

46.Permutations

class Solution {
public:
    vector<vector<int> > permute(vector<int>& num) {
        sort(num.begin(), num.end());

        vector<vector<int>> result;
        vector<int> path; // 中间结果

        dfs(num, path, result);
        return result;
    }
private:
    void dfs(const vector<int>& num, vector<int> &path,
        vector<vector<int> > &result) {
        if (path.size() == num.size()) { // 收敛条件
            result.push_back(path);
            return;
        }
        // 扩展状态
        for (auto i : num) {
            // 查找 i 是否在 path 中出现过
            auto pos = find(path.begin(), path.end(), i);

            if (pos == path.end()) {
                path.push_back(i);
                dfs(num, path, result);
                path.pop_back();
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

49. Group Anagrams

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        if(strs.empty()) return ret;

        map<string,vector<string>> m;
        for(int i=0;i<strs.size();++i){
            string str=strs[i];
            sort(str.begin(),str.end()); //
            m[str].push_back(strs[i]);
        }

        for(map<string,vector<string>>::iterator it=m.begin();it!=m.end();++it){
            ret.push_back(it->second);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

67. Add Binary

class Solution {
public:
    string addBinary(string a, string b) {
        string res="";
        int c=0,s=0;
        for(int i=a.size()-1,j=b.size()-1;i>=0 || j>=0 || c==1;){
            int a1=i>=0? a[i--]-'0':0;
            int b1=j>=0? b[j--]-'0':0;
            int t=a1 + b1 + c;
            s = t%2;
            c = t/2;
            res.insert(res.begin(),s+'0');
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

69.Sqrt(x)

class Solution {
public:
    int mySqrt(int x) {
        if(x<0){
            return -1;
        }

        long long start=0, end = x/2+1;
        while(start+1 < end){
            long long mid = start + (end-start)/2;
            long long t = mid * mid;
            if(t == x){
                return (int)mid;
            }
            else if(t > x){
                end = mid;
            }
            else{
                start = mid;
            }
        }

        if(start * start <= x && end * end >x){
            return (int)start;
        }

        return (int)end;
    }
};
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

77. Combinations

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> elem;
        dfs(ret, elem, 1, n, k);
        return ret;
    }
    void dfs(vector<vector<int>> &ret, vector<int> &elem, int begin, int end,int k1){
        int s = elem.size();
        if(s==k1){
            ret.push_back(elem);
        }
        else{
            for(int i=begin;i<=end;++i){
                auto pos=find(elem.begin(),elem.end(),i);
                if(pos==elem.end()){
                    elem.push_back(i);
                    dfs(ret,elem,i+1,end, k1);
                    elem.pop_back();
                }
            }           
        }       
    }   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

78. Subsets

class Solution {
private:
    void helper(vector<vector<int> > &results,
                vector<int> &subset,
                vector<int> &nums,
                int start) {
        results.push_back(subset);

        for (int i = start; i < nums.size(); i++) {
            subset.push_back(nums[i]);
            helper(results, subset, nums, i + 1);
            subset.pop_back();
        }
    }

 public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int> > results;
        vector<int> subset;

        sort(nums.begin(), nums.end());
        helper(results, subset, nums, 0);

        return results;
    }
};
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

79. Word Search

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(!word.size()) return false;
        int m=board.size(),n=0;
        if(m){
            n=board[0].size();
        }

        int len=word.size();
        vector<vector<bool> > visit(m,vector<bool>(n,false));
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(check(visit,0,word,board,i,j)){
                    return true;
                }
            }
        }
        return false; //找不见的情况
    }

    bool check(vector<vector<bool> > &visit, int start, string word, vector<vector<char>> board, int i, int j){
        if(word[start]!=board[i][j]) return false;
        else{
            visit[i][j]=true;
            if(start==word.size()-1) return true;
            else{
                if(i-1>=0 && !visit[i-1][j] && check(visit,start+1,word,board,i-1,j)) return true;
                if(i+1<board.size() && !visit[i+1][j] && check(visit,start+1,word,board,i+1,j)) return true;
                if(j-1>=0 && !visit[i][j-1] && check(visit,start+1,word,board,i,j-1)) return true;
                if(j+1<board[0].size() && !visit[i][j+1] && check(visit,start+1,word,board,i,j+1)) return true;
            }
            visit[i][j]=false;
            return false;
        }
    }
};
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

91. Decode Ways

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1,0); //表示前i位的编码数目，即对应坐标0~i-1

        if(n==0){
            return 0;
        }           
        if(s[0] == '0'){ //注意！！！  
            return 0;
        }

        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;++i){
            if(s[i-1] >= '1'){
                dp[i] = dp[i-1];
            }
            string s2 = s.substr(i-2,2);
            int t = 0;
            stringstream ss;
            ss<<s2;
            ss>>t;

            if(t>=10 && t<=26){
                dp[i] += dp[i-2];
            }
        }           

        return dp[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

102. Binary Tree Level Order Traversal

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root){
            return res;
        }

        queue<TreeNode* > q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> level;
            for(int i=0;i<size;++i){
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
            res.push_back(level);
        }

        return res;
    }
};
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

129. Sum Root to Leaf Numbers

/**
 * 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:
    int sumNumbers(TreeNode *root) {
        return dfs(root, 0);
    }
private:
    int dfs(TreeNode *root, int sum) {
        if (root == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr)
            return sum * 10 + root->val;
        return dfs(root->left, sum * 10 + root->val) +
               dfs(root->right, sum * 10 + root->val);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

131. Palindrome Partitioning

class Solution {
public:
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    vector<vector<string>> partition(string &s) {
        // write your code here
        vector<vector<string>> res;
        vector<string> str;

        if(!s.size()){
            return res;
        }

        dfs(s, res, str, 0);
        return res;
    }

    //找到所有以str开头的是回文串的组合，放入res中
    void dfs(string &s, vector<vector<string>> &res, vector<string> &str, int startIndex){
        if(startIndex == s.size()){
            res.push_back(str);
            return;
        }

        for(int i=startIndex; i<s.size();++i){
            string substr = s.substr(startIndex, i-startIndex+1);
            if(!isPalindrome(substr)){ 
                continue;
            }

            str.push_back(substr);
            dfs(s, res, str, i+1);
            str.pop_back();
        }
    }

    bool isPalindrome(string s){
        for(int i=0,j=s.size()-1; i<j; i++,j--){
            if(s[i] != s[j]){
                return false;
            }
        }
        return true;
    }
};
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

4. Median of Two Sorted Arrays

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size(),n2=nums2.size();
        int n=n1+n2;
        if(n&1){
            return findMadian(nums1,0,nums2,0,n/2+1);
        }
        else{
            return (findMadian(nums1,0,nums2,0,n/2)+findMadian(nums1,0,nums2,0,n/2+1))/2.0;
        }
    }
    double findMadian(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k){
        int n1=nums1.size(),n2=nums2.size();
        if(n1-start1>n2-start2) return findMadian(nums2,start2,nums1,start1,k);
        if(n1-start1<=0) return nums2[start2+k-1];
        if(k==1) return min(nums1[start1],nums2[start2]);

        int k1=min(k/2,n1-start1),k2=k-k1;
        if(nums1[start1+k1-1]==nums2[start2+k2-1])
            return nums1[start1+k1-1];
        else if(nums1[start1+k1-1]>nums2[start2+k2-1])
            return findMadian(nums1,start1,nums2,start2+k2,k1);
        else
            return findMadian(nums1,start1+k1,nums2,start2,k2);
    }
};
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

7. Reverse Integer

class Solution {
public:
    int reverse(int x) {
        if (x == INT_MIN)
            return 0;
        if (x < 0)
            return -reverse(-x);

        int rx = 0; // store reversed integer
        while (x != 0) {
            // check overflow
            if (rx > INT_MAX / 10 || 10 * rx > INT_MAX - x % 10) return 0;
            rx = rx * 10 + x % 10;
            x = x / 10;
        }
        return rx;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

10.Regular Expression Matching

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();

        if(p.size()>1 && p[1]=='*'){
            return isMatch(s,p.substr(2)) || (!s.empty() && (s[0]==p[0] || p[0]=='.') && isMatch(s.substr(1),p));
        }
        else{
            return !s.empty() && (s[0]==p[0] || p[0]=='.') && isMatch(s.substr(1), p.substr(1));
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

https://www.jianshu.com/p/85f3e5a9fcda

对于第4个条件：当p的第二个字符不是星号时，如果S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)‘ . ’)，则进入下一层递归继续比较分别截取首元素的s和p；否则，返回false。

对于第5个条件：当p的第二个字符是星号时，如果S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)‘ . ’)，有两种分支需要分别判断：

1、某字符+星号不要匹配s的首字符：（因为星号之前的字符可出现可不出现，该情况不配是考虑到后面有必须匹配的。假设当前匹配并截去s的首字符，会导致后续匹配错误。）截去p的前两个元素（某字符+星号）并进入下一层递归，假如返回true，则当前递归返回true；假如返回false，进入分支2。

2、某字符+星号要匹配s的首字符：截去s首字符并继续条件5的判断。
对于第6个条件：当p的第二个字符是星号时，非【S不空且(p.charAt(0) == s.charAt(0) 或者 p.charAt(0)==‘ . ’)】，截去p的前两个元素（某字符+星号）并进入下一层递归。

17.Letter Combinations of a Phone Number

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;

        //特殊情况处理，当输入为空或者输入中包含处2-9以外的数字时。
        bool flg=0;
        for(int i=0;i<digits.empty();++i){
            if(digits[i]<'2' || digits[i]>'9'){
                flg=1;
                break;
            }               
        }
        if(digits.empty() || flg)
            return ret;

        vector<string> nums = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        string str="";
        dfs(ret, str, 0, digits, nums);
        return ret;
    }
    void dfs(vector<string> &ret, string &str, int startIndex, string digits, vector<string> nums){
        if(startIndex == digits.size()){
            ret.push_back(str);
            return;
        }

        for(int i=0;i<nums[digits[startIndex]-'0'].size();++i){
            str += nums[digits[startIndex]-'0'][i];
            dfs(ret, str, startIndex+1, digits, nums);
            str = str.substr(0,str.size()-1);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

19.Remove Nth Node From End of List

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* p1 = &dummy, *p2 = &dummy;

        for(int i=0;i<n;++i){
            p1 = p1->next;
        }

        while(p1->next){
            p1 = p1->next;
            p2 = p2->next;
        }

        p2->next = p2->next->next;

        return dummy.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

26.Remove Duplicates from Sorted Array

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }

        int i=0,j=0;
        while(j<nums.size()){
            if(nums[i] == nums[j]){
                ++j;
            }
            else{
                nums[++i] = nums[j++];
            }
        }

        return i+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

80.Remove Duplicates from Sorted List II

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }

        int idx = 0;
        int cnt = 0;
        for(int i=0;i<nums.size();++i){
            if(i>0 && nums[i] == nums[i-1]){
                cnt++;
                if(cnt>=3){
                    continue;
                }
            }
            else{
                cnt=1;
            }
            nums[idx++] = nums[i];           
        }

        return idx;
    }
};
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

29.Divide Two Integers

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor || (dividend == INT_MIN && divisor == -1)) // overflow
            return INT_MAX;

        int sign = ((dividend<0)^(divisor<0))?-1:1;
        long long dvd = labs(dividend); //陷阱1
        long long dvs = labs(divisor);

        int res = 0;
        while(dvd >= dvs){
            long long tmp = dvs, mul = 1;
            while(dvd >= (tmp<<1)){ //陷阱2
                tmp <<= 1;
                mul <<= 1;
            }
            dvd -= tmp;
            res += mul;
        }
        return sign == 1 ? res:-res;;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

33.Search in Rotated Sorted Array

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()==0){
            return -1;
        }

        int start=0,end=nums.size()-1;
        while(start+1<end){
            int mid = start+(end-start)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] > nums[start]){ // mid在上升区间
                if(target >= nums[start] && target <= nums[mid]){
                    end = mid;
                }
                else{
                    start = mid;
                }
            }
            else{ //mid在下降区间
                if(target >= nums[mid] && target <= nums[end]){
                    start = mid;
                }
                else{
                    end = mid;
                }
            }
        }

        if(nums[start] == target){
            return start;
        }
        if(nums[end] == target){
            return end;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

81.Search in Rotated Sorted Array II

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size()==0){
            return false;
        }

        int start=0,end=nums.size()-1;
        while(start+1<end){
            int mid = start+(end-start)/2;
            if(nums[mid] == target){
                return true;
            }
            if(nums[mid] > nums[start]){ // mid在上升区间
                if(target >= nums[start] && target <= nums[mid]){
                    end = mid;
                }
                else{
                    start = mid;
                }
            }
            else if(nums[mid] < nums[start]){ //mid在下降区间
                if(target >= nums[mid] && target <= nums[end]){
                    start = mid;
                }
                else{
                    end = mid;
                }
            }
            else{
                start++;
            }
        }

        if(nums[start] == target){
            return true;
        }
        if(nums[end] == target){
            return true;
        }
        return false;
    }
};
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

34.Search for a Range

class Solution {
public:
    vector<int> searchRange(vector<int>& A, int target) {
        vector<int> res(2,-1);
        int n = A.size();
        if(!n)
            return res;

        int l = 0, r=0;
        int start=0, end = n-1;
        while(start+1 < end){
            int mid = start + (end -start)/2;
            if(target <= A[mid]){
                end = mid;
            }
            else{
                start = mid;
            }
        }
        if(A[start] == target)
            l = start;
        else if(A[end] == target)
            l = end;
        else
            return res;

        start = 0;
        end = n-1;
        while(start+1 < end){
            int mid = start + (end -start)/2;
            if(target >= A[mid]){
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if(A[end] == target) // 注意此处先比较end
            r = end;
        else if(A[start] == target)
            r = start;
        else
            return res;

        res[0] = l;
        res[1] = r;

        return res;
    }
};
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

39.Combination Sum

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        if(candidates.size()==0){
            return res;
        }

        sort(candidates.begin(),candidates.end());

        vector<int> one;
        dfs(candidates, res, one, target, 0);

        return res;
    }
    void dfs(vector<int> candidates, vector<vector<int>> &res, vector<int> &one, int remain, int startIndex){
        if(remain == 0){
            res.push_back(one);
            return;
        }

        for(int i=startIndex;i<candidates.size();++i){
            /*//不需要，因为没有重复元素
            if(i>startIndex && candidates[i] == candidates[i-1]){
                continue;
            }*/
            if(candidates[i] <= remain){
                one.push_back(candidates[i]);
                dfs(candidates,res,one,remain - candidates[i], i);//可重复取多次体现在此处的startIndex没有+1
                one.pop_back();
            }
            else{
                break;
            }
        }       
    }
};
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

40.Combination Sum Ⅱ

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        if(candidates.size()==0){
            return res;
        }

        sort(candidates.begin(),candidates.end());

        vector<int> one;
        dfs(candidates, res, one, target, 0);

        return res;
    }
    void dfs(vector<int> candidates, vector<vector<int>> &res, vector<int> &one, int remain, int startIndex){
        if(remain == 0){
            res.push_back(one);
            return;
        }

        for(int i=startIndex;i<candidates.size();++i){
            if(i>startIndex && candidates[i] == candidates[i-1]){ //跳过重复元素
                continue;
            }

            if(candidates[i] <= remain){
                one.push_back(candidates[i]);
                dfs(candidates,res,one,remain - candidates[i], i+1);//每个元素只能选1次，所以此处是i+1
                one.pop_back();
            }
            else{
                break;
            }
        }       
    }   
};
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

216.Combination Sum Ⅲ

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        if(n==0 && k>0 || k>n || k==0){
            return res;
        }

        vector<int> one;
        dfs(res,one,1,k,n);

        return res;
    }
    void dfs(vector<vector<int>> &res, vector<int> &one, int startIdx, int k, int n){
        if(n==0 && k==0){
            res.push_back(one);
            return;
        }

        for(int i=startIdx;i<=9;++i){ // 无重复元素
            if(n < i){
                break;
            }
            one.push_back(i);
            dfs(res,one,i+1,k-1,n-i); //每个元素选一次
            one.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

43.Multiply Strings

class Solution {
public:
    string multiply(string num1, string num2) {
        string res(num1.size()+num2.size(), '0');

        for(int i=num1.size()-1;i>=0;--i){
            int carry = 0;
            for(int j=num2.size()-1;j>=0;--j){
                int tmp = res[i+j+1]-'0' + (num1[i]-'0') * (num2[j]-'0') +carry;
                res[i+j+1] = tmp%10 + '0';
                carry = tmp/10;
            }
            res[i] += carry;
        }

        size_t startpos=res.find_first_not_of("0");
        if(startpos != string::npos){
            return res.substr(startpos);   
        }

        return "0";
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

44.Wildcard Matching

http://blog.csdn.net/makuiyu/article/details/43698963

迭代回溯【可用】
递归回溯【时间会超】

动态规划【空间会超】

0 1 2 3 4 5 6 7 8
s: a b c d a c c c
| | \ \ \
p: a b * c d * a c c
|
失配

class Solution {
public:
bool isMatch(string s, string p) {
int sl = s.size(), pl = p.size();

      int ss = 0, pp = -1;
      int i=0, j=0;
      while(i<s.size()){
          if('?' == p[j] || s[i] == p[j]){
              ++i,++j;
          }
          else if('*' == p[j]){
              ss = i;
              pp = j++;
          }
          else if(pp != -1){
              i = ++ss;
              j = pp+1;
          }
          else{
              return false;
          }
      }

      while('*' == p[j]){
          ++j;
      }

      return j == p.size();
  }
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

};

51.N-Queens

class Solution {
public:   
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        if(n<=0){
            return res;
        }

        vector<int> one;
        dfs(res, one, n);
        return res;
    }
    void dfs(vector<vector<string>> &res, vector<int> &one, int n){
        if(one.size()==n){
            res.push_back(drawChessBoard(one));
            return;
        }
        for(int i=0;i<n;++i){
            if(!isValid(one, i+1)){
                continue;
            }
            one.push_back(i+1);
            cout<<one.size()<<endl;
            dfs(res, one, n);
            one.pop_back();
        }
    }
    vector<string> drawChessBoard(vector<int> &one){
        vector<string> res;
        for(int i=0;i<one.size();++i){
            string str(one.size(), '.');
            str[one[i]-1] = 'Q';
            res.push_back(str);
        }

        return res;
    }
    bool isValid(vector<int> one, int idx){
        for(int i=0;i<one.size();++i){
            if(one[i] == idx){
                return false;
            }
            if(one[i]-i == idx-one.size()){ // 对角线
                return false;
            }
            if(one[i]+i == idx+one.size()){ // 对角线
                return false;
            }
        }       

        return true;
    }   
};
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

52.N-Queens II

class Solution {
public:
    int totalNQueens(int n) {
        if(n<=0){
            return 0;
        }

        int res = 0;
        vector<int> one;
        dfs(res, one, n);
        return res;
    }
    void dfs(int &res, vector<int> &one, int n){
        if(one.size()==n){
            res++;
            return;
        }
        for(int i=0;i<n;++i){
            if(!isValid(one, i+1)){
                continue;
            }
            one.push_back(i+1);
            dfs(res, one, n);
            one.pop_back();
        }
    }
    bool isValid(vector<int> one, int idx){
        for(int i=0;i<one.size();++i){
            if(one[i] == idx){
                return false;
            }
            if(one[i]-i == idx-one.size()){ // 对角线
                return false;
            }
            if(one[i]+i == idx+one.size()){ // 对角线
                return false;
            }
        }       

        return true;
    }
};
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

53.Maximum Subarray

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

62.Unique Paths

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> f(n,0);
        for(int i=0;i<n;++i){
            f[i] = 1;
        }

        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                f[j] += f[j-1];
            }
        }

        return f[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

63.Unique Paths II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(); //m行n列
        if(!m){
            return 0;
        }
        int n = obstacleGrid[0].size();

        vector<int> f(n,0);
        for(int i=0;i<n;++i){
            if(obstacleGrid[0][i] == 1){
                break;   
            }
            f[i] = 1;
        }

        for(int i=1;i<m;++i){
            for(int j=0;j<n;++j){
                if(obstacleGrid[i][j] == 1){
                    f[j] = 0;
                }
                else{
                    f[j] += (j==0)?0:f[j-1];
                }               
            }
        }

        return f[n-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

64.Minimum Path Sum

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size(),n=0;
        if(m) n=grid[0].size();
        else return 0;

        vector<int> dp(n,grid[0][0]);
        for(int i=1;i<n;++i){
            dp[i] = dp[i-1]+grid[0][i];
        }

        for(int i=1;i<m;++i){
            dp[0] += grid[i][0];
            for(int j=1;j<n;++j){
                dp[j] = min(dp[j-1],dp[j]) + grid[i][j];
            }
        }

        return dp[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

72.Edit Distance

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        if(!n1 && !n2){
            return 0;
        }

        int f[n1+1][n2+1];
        for(int i=0;i<=n1;++i){
            f[i][0] = i;
        }
        for(int j=0;j<=n2;++j){
            f[0][j] = j;
        }

        for(int i=1;i<=n1;++i){
            for(int j=1;j<=n2;++j){
                if(word1[i-1] == word2[j-1]){
                    f[i][j] = min(f[i-1][j-1], f[i-1][j]+1); //匹配、删除
                    f[i][j] = min(f[i][j], f[i][j-1]+1); //插入
                }
                else{
                    f[i][j] = min(f[i-1][j-1]+1, f[i-1][j]+1); //替换，删除
                    f[i][j] = min(f[i][j], f[i][j-1]+1); //插入
                }
            }
        }

        return f[n1][n2];
    }
};
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

74.Search a 2D Matrix

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=0;
        if(m) n=matrix[0].size();
        if(!m || !n){
            return false;
        }

        int l = 0, r = m*n-1;
        while(l+1 < r){
            int mid = l+(r-l)/2;
            int t = matrix[mid/n][mid%n];
            if(target == t){
                return true;
            }
            else if(target > t){
                l = mid;
            }
            else{
                r = mid;
            }
        }

        if(target == matrix[l/n][l%n]){
            return true;
        }
        if(target == matrix[r/n][r%n]){
            return true;
        }
        return false;
    }
};
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

240. Search a 2D Matrix II

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if(m==0)
            return false;
        int n = matrix[0].size();

        int i = 0, j = n-1;
        while(i<m && j>=0){
            if(target == matrix[i][j])
                return true;
            else if(target < matrix[i][j]){
                j--;
            }
            else{
                i++;
            }
        }

        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

83.Remove Duplicates from Sorted List

/**
 * 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 || !head->next)
            return head;

        ListNode *pre=head, *cur=head->next;
        while(cur){
            if(cur->val == pre->val){
                cur = cur->next;
                pre->next = cur;
            }
            else{
                pre = cur;
                cur = cur->next;
            }
        }

        return 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

82.Remove Duplicates from Sorted List Ⅱ

/**
 * 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) {
        ListNode dummy(0);
        dummy.next = head;

        ListNode *pre = &dummy, *cur = head;
        bool isDel = false;
        while(cur){
            isDel = false;
            while(cur->next && cur->val==cur->next->val){
                isDel = true;
                cur->next = cur->next->next;
            }
            if(isDel){
                cur = cur->next;
                pre->next = cur;
                isDel = false;
            }
            else{
                pre = cur;
                cur=cur->next;
            }
        }

        return dummy.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
32
33
34
35
36

86.Partition List

ListNode* partition(ListNode* head, int x) {
        ListNode left(0), right(0);
        ListNode *l = &left, *r = &right;

        while(head){
            ListNode* & ref = head->val < x ? l : r;
            ref->next = head;
            ref = ref->next;

            head = head->next;
        }

        l->next = right.next;
        r->next = NULL;
        return left.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

93.Restore IP Addresses

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        if(s.size()<4 || s.size() > 12){
            return res;
        }

        vector<string> ip;
        dfs(res, ip, s, 0);
        return res;
    }

    void dfs(vector<string> &res, vector<string> &ip, string s, int startIndex){
        if(ip.size()==4){
            if(startIndex != s.size()){
                return;
            }

            string str = "";
            for(int i=0;i<4;++i){
                str += ip[i];
                str += ".";
            }
            str = str.substr(0,str.size()-1);
            res.push_back(str);
            return;
        }

        for(int i=startIndex;i<s.size()&&i<startIndex+3;++i){
            string str = s.substr(startIndex,i-startIndex+1);
            if(isvalid(str)){
                ip.push_back(str);
                dfs(res,ip,s,i+1);
                ip.pop_back();
            }
        }
    }

    bool isvalid(string str){
        if(str[0] == '0'){
            return str == "0";
        }
        int digit;
        stringstream ss;
        ss<<str;
        ss>>digit;

        return digit>=0 && digit<=255;
    }
};
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

94.Binary Tree Inorder Traversal

递归：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;

        if(!root){
            return ret;
        }

        vector<int> ret1 = inorderTraversal(root->left);
        vector<int> ret2 = inorderTraversal(root->right);

        ret.insert(ret.end(), ret1.begin(), ret1.end());
        ret.push_back(root->val);
        ret.insert(ret.end(), ret2.begin(), ret2.end());

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

非递归：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(!root){
            return ret;
        }

        stack<TreeNode*> s;
        TreeNode* cur = root;
        while(cur || !s.empty()){
            while(cur){
                s.push(cur);
                cur=cur->left;
            }

            cur = s.top();
            ret.push_back(cur->val);
            s.pop();
            cur = cur->right;
        }

        return ret;
    }
};
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

103.Binary Tree Zigzag Level Order Traversal

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root){
            return ret;
        }

        stack<TreeNode*> curlevel;
        stack<TreeNode*> nextlevel;
        stack<TreeNode*> tmp;

        curlevel.push(root);
        bool normalOrder = true;

        while(!curlevel.empty()){
            vector<int> cur;

            while(!curlevel.empty()){
                TreeNode* node = curlevel.top();
                curlevel.pop();
                cur.push_back(node->val);

                if(normalOrder){
                    if(node->left){
                        nextlevel.push(node->left);
                    }
                    if(node->right){
                        nextlevel.push(node->right);
                    }
                }
                else{
                    if(node->right){
                        nextlevel.push(node->right);
                    }
                    if(node->left){
                        nextlevel.push(node->left);
                    }
                }
            }

            ret.push_back(cur);
            tmp = curlevel;
            curlevel = nextlevel;
            nextlevel = tmp;
            normalOrder = !normalOrder;
        }

        return ret;
    }
};
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

105.Construct Binary Tree from Preorder and Inorder Tree

/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(!preorder.size() || !inorder.size() || preorder.size()!=inorder.size()){
            return NULL;
        }

        return mybuildTree(preorder,0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
    TreeNode* mybuildTree(vector<int>& preorder, int prestart, int preend, vector<int>& inorder, int instart, int inend){
        if (instart > inend) {
            return NULL;
        }

        TreeNode* root = new TreeNode(preorder[prestart]);
        int pos = findPosition(inorder, instart, inend, preorder[prestart]);

        root->left = mybuildTree(preorder, prestart+1, prestart+pos-instart, inorder, instart, pos-1);
        root->right = mybuildTree(preorder, prestart+pos-instart+1, preend, inorder, pos+1, inend);

        return root;
    }   
    int findPosition(vector<int> A, int start, int end,int key){
        int pos = 0;
        for(int i=start;i<=end;++i){
            if(A[i] == key){
                pos = i;
                break;
            }
        }
        return pos;
    }
};
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

106.Construct Binary Tree from Inorder and Postorder Tree

/**
 * 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(!inorder.size() || !postorder.size() || inorder.size()!=postorder.size()){
            return NULL;
        }

        return mybuildTree(postorder,0, postorder.size()-1, inorder, 0, inorder.size()-1);
    }
    TreeNode* mybuildTree(vector<int>& postorder, int poststart, int postend, vector<int>& inorder, int instart, int inend){
        if (instart > inend) {
            return NULL;
        }

        TreeNode* root = new TreeNode(postorder[postend]);
        int pos = findPosition(inorder, instart, inend, postorder[postend]);

        root->left = mybuildTree(postorder, poststart, poststart+pos-instart-1, inorder, instart, pos-1);
        root->right = mybuildTree(postorder, poststart+pos-instart, postend-1, inorder, pos+1, inend);

        return root;
    }   
    int findPosition(vector<int> A, int start, int end, int key){
        int pos = 0;
        for(int i=start;i<=end;++i){
            if(A[i] == key){
                pos = i;
                break;
            }
        }
        return pos;
    }
};
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

108.Convert Sorted Array to Binary Search Tree

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0)
            return NULL;

        return helper(nums, 0, nums.size()-1);
    }
    TreeNode* helper(vector<int> nums, int start, int end){
        if(start>end){
            return NULL;
        }

        TreeNode* root = new TreeNode(nums[start+(end-start)/2]);
        root->left = helper(nums, start, start+(end-start)/2-1);
        root->right = helper(nums, start+(end-start)/2+1, end);

        return root;
    }     
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

109.Convert Sorted List to Binary Search Tree

class Solution {
public:
    ListNode* cur;
    TreeNode* sortedListToBST(ListNode* head) {
        int size = getLen(head);
        cur = head;

        return helper(size);
    }
    TreeNode* helper(int size){
        if(size<=0){
            return NULL;
        }

        TreeNode* left = helper(size/2);
        TreeNode* root = new TreeNode(cur->val);
        cur = cur->next;
        TreeNode* right = helper(size - 1 - size/2);

        root->left = left;
        root->right = right;

        return root;
    }
    int getLen(ListNode* head){
        int size = 0;
        while(head){
            size++;
            head = head->next;
        }

        return size;
    }
};
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

path sumⅠⅡⅢ 求解：

https://segmentfault.com/a/1190000003554851

112.Path SumⅠ

bool hasPathSum(TreeNode* root, int sum) {
        if(!root)
            return false;
        if(!root->left && !root->right)
            return root->val == sum;

        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
1
2
3
4
5
6
7
8

113.Path SumⅡ

vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ret;
        if(!root)
            return ret;

        vector<int> one;
        dfs(root, ret, one, sum);

        return ret;
    }
    void dfs(TreeNode* root, vector<vector<int>> &ret, vector<int> &one, int sum){
        one.push_back(root->val);
        if(root->val == sum && !root->left && !root->right){
            ret.push_back(one);
        }
        else{
            if(root->left){
                dfs(root->left, ret, one, sum-root->val);
            }
            if(root->right){
                dfs(root->right, ret, one, sum-root->val);
            }
        }
        one.pop_back();
    }

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ret;
        if(!root)
            return ret;

        if(!root->left && !root->right){
            if(sum == root->val){
                vector<int> v(1, root->val);
                ret.push_back(v);
                return ret;
            }
            else{
                return ret;
            }
        }

        vector<vector<int>> l = pathSum(root->left, sum-root->val);
        vector<vector<int>> r = pathSum(root->right, sum-root->val);

        for(int i=0;i<l.size();++i){
            l[i].insert(l[i].begin(),root->val);
            ret.push_back(l[i]);
        }
        for(int i=0;i<r.size();++i){
            r[i].insert(r[i].begin(),root->val);
            ret.push_back(r[i]);
        }
        return ret;
    }
};
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

在这里插入图片描述

437.Path SumⅢ

https://www.cnblogs.com/grandyang/p/6007336.html

int pathSum(TreeNode* root, int sum) {
        int res = 0;
        vector<TreeNode*> out;
        helper(root, sum, 0, out, res);
        return res;
    }
    void helper(TreeNode* node, int sum, int curSum, vector<TreeNode*>& out, int& res) {
        if (!node) return;
        curSum += node->val;
        out.push_back(node);
        if (curSum == sum) ++res;
        int t = curSum;
        for (int i = 0; i < out.size() - 1; ++i) {
            t -= out[i]->val;
            if (t == sum) ++res;
        }
        helper(node->left, sum, curSum, out, res);
        helper(node->right, sum, curSum, out, res);
        out.pop_back();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

666.Path Sum Ⅳ

114.Flatten Binary Tree to Linked List

void flatten(TreeNode* root) {
        while(root){
            if(root->left){
                TreeNode* cur = root->left;
                while(cur->right){
                    cur = cur->right;
                }
                cur->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            root = root->right;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

116.Populating Next Right Pointers in Each Node

void connect(TreeLinkNode *root) {
TreeLinkNode * node = NULL;//root表示当前层，node表示当前层的节点，从当前层最左边的节点开始
while(root && root->left){
node = root; // 处理当前层
while(node){
node->left->next = node->right;
if(node->next){
node->right->next = node->next->left;
}
node = node->next;
}
root = root->left;
}
}

116.Populating Next Right Pointers in Each Node Ⅱ

void connect(TreeLinkNode *root) {
        if(!root){
            return;
        }

        queue<TreeLinkNode *> q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            TreeLinkNode * pre = q.front();
            q.pop();
            if(pre->left){
                q.push(pre->left);
            }
            if(pre->right){
                q.push(pre->right);
            }
            for(int i=1;i<size;++i){
                TreeLinkNode * node = q.front();
                q.pop();
                pre->next = node;
                pre = node;
                if(node->left){
                    q.push(node->left);
                }
                if(node->right){
                    q.push(node->right);
                }
            }
        }
    }
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

128.Longest Consecutive Sequence

class Solution {
public:
    vector<int> parent;
    vector<int> size;
    int longestConsecutive(vector<int>& nums) {
        if(!nums.size()) return 0;
        for(int i=0;i<nums.size();++i){
            parent.push_back(i);
            size.push_back(1);
        }

        map<int,int> m;
        for(int i=0;i<nums.size();++i){
            if(m.find(nums[i])!=m.end())
                continue;
            m[nums[i]] = i;
            if(m.find(nums[i]-1)!=m.end()){
                Union(m[nums[i]-1],m[nums[i]]);
            }
            if(m.find(nums[i]+1)!=m.end()){
                Union(m[nums[i]+1],m[nums[i]]);
            }
        }
        int res = *max_element(size.begin(),size.end());
        return res;
    }
    int Find(int a){
        if(parent[a] == a){
            return a;
        }
        else{
            parent[a] = Find(parent[a]);
            return parent[a];
        }
    }
    void Union(int a,int b){
        int pa = Find(a);
        int pb = Find(b);
        if(pa != pb){
            if(size[pa] > size[pb]){
                parent[pb] = pa;
                size[pa] += size[pb];
            }
            else{
                parent[pa] = pb;
                size[pb] += size[pa];
            }
        }
    }

};
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

130.Surrounded Regions

class Solution {
public:
    class UF{
    public:
        int* pa;
        int* rank;
        int count;

        UF(int n){
            count = n;
            pa = new int[n];
            rank = new int[n];
            for(int i=0;i<n;++i){
                pa[i] = i;
                rank[i] = 0;
            }
        }

        ~UF(){
            delete [] pa;
            delete [] rank;
        }

        int find(int x){
            if(pa[x] == x)
                return x;
            else{
                pa[x] = find(pa[x]);
                return pa[x];
            }
            /*
            while(x!=pa[x]){
                pa[x] = pa[pa[x]];
                x = pa[x];
            }
            return x;
            */
        }

        bool connected(int x,int y){
            return find(x)==find(y);
        }

        void connect(int x,int y){
            int u=find(x);
            int v=find(y);
            if(u==v) return;
            if(rank[u] > rank[v]){
                pa[v] = u;
            }
            else if(rank[u] < rank[v]){
                pa[u] = v;
            }
            else{
                pa[u] = v;
                rank[v]++;
            }
            count--;
        }

        int getcount(){
            return count;
        }
    };


    void solve(vector<vector<char>>& board) {
        int m=board.size();
        if(m==0) return;
        int n=board[0].size();
        UF uf(m*n+1);

        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if((i==0||j==0||i==m-1||j==n-1) && board[i][j]=='O'){
                    uf.connect(i*n+j,m*n);
                }
                else if(board[i][j]=='O'){
                    if(board[i-1][j]=='O'){
                        uf.connect(i*n+j,(i-1)*n+j);
                    }
                    if(board[i+1][j]=='O'){
                        uf.connect(i*n+j,(i+1)*n+j);
                    }
                    if(board[i][j-1]=='O'){
                        uf.connect(i*n+j,i*n+j-1);
                    }
                    if(board[i][j+1]=='O'){
                        uf.connect(i*n+j,i*n+j+1);
                    }
                }
            }
        }

        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(!uf.connected(i*n+j,m*n)){
                    board[i][j] = 'X';
                }
            }
        }
    }
};
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
96
97
98
99
100
101
102
103

3.Longest Substring Without Repeating Characters

int lengthOfLongestSubstring(string s) {
        vector<int> loc(256,-1);
        int maxlen=0,start=-1;
        for(int i=0;i<s.size();++i){
            if(loc[s[i]] > start){
                start = loc[s[i]];
            }
            loc[s[i]] = i;
            maxlen = max(maxlen, i-start);
        }
        return maxlen;
    }
1
2
3
4
5
6
7
8
9
10
11
12

5. Longest Palindromic Substring

151. Reverse Words in a String

186. Reverse Words in a String II

557. Reverse Words in a String III

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/115969