leetcode刷题A部分

发表于   |   分类于   |     |   阅读次数

目录

[toc]

1 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

我的做法如下，直接暴力，复杂度是O(n2)，我们试图通过遍历数组的其余部分来寻找它对应的目标，这将耗费O(n)*O(n)的时间。

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<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> res;
        for(int i=0;i<nums.size()-1;i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    res.push_back(i);
                    res.push_back(j);
                }
                else
                {
                    continue;
                }
            }
        }
        return res;
    }
};

也可以使用哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> twoSum(vector<int>& nums, int target) {
      vector<int> twoSum;
      map<int, int> tmpmap;//键值为nums的值，变量值为nums下标
        for (int i = 0; i < nums.size(); i++) {
          tmpmap[nums[i]] = i;
      }
      for (int i = 0; i < nums.size(); i++) {
          if (tmpmap.count(target - nums[i]) != 0 && tmpmap[target-nums[i]]!=i) {//  如果目标值减去循环处的值存在，且它对应的下标不为i，即存在有另一个数与循环值相加等于target，则返回结果
            twoSum.push_back(i);
              twoSum.push_back(tmpmap[target - nums[i]]);
              break;
          }
      }
      return twoSum;
  }

优化版的哈希表如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> twoSum(vector<int>& nums, int target) {  
    vector<int> twoSum;  
    map<int, int> tmpmap;//键值为nums的值，变量值为nums下标  
  
    for (int i = 0; i < nums.size(); ++i) {  
        if (tmpmap.count(nums[i]) != 0) {  
            twoSum.push_back(tmpmap[nums[i]]);  
            twoSum.push_back(i);  
            break;  
        }  
        tmpmap[target - nums[i]] = i;  
    }  
    return twoSum;  
}

2 两数相加(链表)（回到目录）

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
例如：

1
2
3
4
5
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

我一开始的做法:错的！

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
#include<math.h>
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {   
        int num1,num2=0;
        vector<int> vec1;
        vector<int> vec2;
        while(l1)
        {
            vec1.push_back(l1->val);
            l1=l1->next;
        }
        while(l2)
        {
            vec2.push_back(l2->val);
            l2=l2->next;
        }
        for(int i=0;i<vec1.size();i++)
        {
            num1 +=pow(10,i)*vec1[i];
        }
        for(int j=0;j<vec2.size();j++)
        {
            num2 +=pow(10,j)*vec2[j];
        }
        int sum=num1+num2;
        ListNode head(0);
        ListNode *p=&head;
        int shang=sum/10;
        int yushu=sum%10;
        while(shang)
        {
            p->next=new ListNode(yushu);
            p=p->next;
            shang=shang/10;
            yushu=shang%10;
            
            
        }
        p->next=NULL;
        return head.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
/**
 * 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 target(0); //头结点
        ListNode* node = &target;  //结点
        int sum = 0; //每个结点的和
        while (l1 != NULL || l2 != NULL) {
            sum /= 10;    //求本次的进位
            if (l1 != NULL) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                sum += l2->val;
                l2 = l2->next;
            }
            node->next = new ListNode(sum % 10); //该结点的值 就是结点和的余数
            node = node->next; //指向下一个结点
        }
        if (sum / 10 == 1)   //对最后一个结点进行处理
            node->next = new ListNode(1);
        return target.next;
    }
};

3 无重复字符的最长子串（回到目录）

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

1
2
3
4
5
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列  而不是子串。

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 lengthOfLongestSubstring(string s) 
    {
        int begin=0;
        int result=0;
        int char_map[128]={0};
        string word="";
        for(int i=0;i<s.length();i++)
        {
            char_map[s[i]]++;
            if(char_map[s[i]]==1)
            {
                word += s[i];
                if(result<word.length())
                {
                    result=word.length();
                }
            }
            else
            {
                while(begin<i && char_map[s[i]]>1)
                {
                    char_map[s[begin]]--;
                    begin++;
                }
                word="";
                for(int j=begin;j<=i;j++)
                {
                    word += s[j];
                }
            }
        }
        return result;
    }
};

更简便的方法，维护一个窗口

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 lengthOfLongestSubstring(string s) 
    {
        map<char,int> m;
        int left=0,res=0;
        for(int i=0;i<s.size();i++)
        {
            if(m[s[i]]==0 || m[s[i]]<left)//表示该字母没有出现过，或者它出现过但是在窗口外面；那么就可以计算长度了。
            {
                res=max(res,i-left+1);
            }
            else//该字母出现过，且在窗口内，那么就要更新窗口的左边界了。
            {
                left=m[s[i]];
            }
            m[s[i]]=i+1;//用map来记录每个字母出现的位置
        }
        return res;
    }
};

4 两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 均不为空。

示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0

示例 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        if(nums1.size()==0 && nums2.size()==0) return 0;
        vector<double> vec;
        double res=0;
        int i=0,j=0;
        while(i<nums1.size() && j<nums2.size())
        {
            if(nums1[i]<nums2[j])
            {
                vec.push_back(nums1[i]);
                i++;
            }
            else
            {
                vec.push_back(nums2[j]);
                j++;
            }
            
        }
        for(;i<nums1.size();i++)
        {
            vec.push_back(nums1[i]);
        }
        for(;j<nums2.size();j++)
        {
            vec.push_back(nums2[j]);
        }
        int len=vec.size();
        if(len%2)
        {
            res=vec[len/2];
        }
        else
        {
            res=(vec[len/2]+vec[len/2-1])/2;
        }
        return res;
    }
};

5 最长回文子串（回到目录）

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

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:
    string longestPalindrome(string s) {
        const int len = s.size();
        if(len <= 1)return s;
        int start, maxLen = 0;
        for(int i = 1; i < len; i++)
        {
            //寻找以i-1,i为中点偶数长度的回文
            int low = i-1, high = i;
            while(low >= 0 && high < len && s[low] == s[high])
            {
                low--;
                high++;
            }
            if(high - low - 1 > maxLen)
            {
                maxLen = high - low -1;
                start = low + 1;
            }
             
            //寻找以i为中心的奇数长度的回文
            low = i- 1; high = i + 1;
            while(low >= 0 && high < len && s[low] == s[high])
            {
                low--;
                high++;
            }
            if(high - low - 1 > maxLen)
            {
                maxLen = high - low -1;
                start = low + 1;
            }
        }
        return s.substr(start, maxLen);
    }
};

6 Z字形变换（回到目录）

将字符串 “PAYPALISHIRING” 以Z字形排列成给定的行数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
P   A   H   N
A P L S I I G
Y   I   R
之后从左往右，逐行读取字符："PAHNAPLSIIGYIR"
实现一个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入: s = "PAYPALISHIRING", numRows = 3
输出: "PAHNAPLSIIGYIR"
示例 2:
输入: s = "PAYPALISHIRING", numRows = 4
输出: "PINALSIGYAHRPI"
解释:
P     I    N
A   L S  I G
Y A   H R
P     I

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) {
        int len = s.length();
        int nodeLen = 2*numRows-2;//两整列之间的差 也就是等差数列中的d
        string result = "";
 
        if (len == 0 || numRows == 0 || numRows == 1)//特殊情况特殊处理
            return s;
 
        for (int i = 0; i < numRows; i++)//从第一行遍历到最后一行
            for (int j = i; j < len; j += nodeLen) {
                result += s[j];//第一行和最后一行 还有普通行的整列数字
                if (i != 0 && i != numRows-1 && j - 2*i + nodeLen < len)
                    result += s[j - 2*i + nodeLen];//单列行的数字
            }
 
        return result ;
    }
};

7 反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while (x) {
            int temp = ans * 10 + x % 10;
            if(temp/10 !=ans)
            {
                return 0;
            }
            ans = temp;
            x /= 10;
        }
        return ans;
    }
};

8 字符串转整数 (atoi)（回到目录）

LINK

实现 atoi，将字符串转为整数。

在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。

当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。

若函数不能执行有效的转换，返回 0。

说明：

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。如果数值超过可表示的范围，则返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

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
示例 1:
输入: "42"
输出: 42
示例 2:
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
     
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。
     
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

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:
    
    int myAtoi(string str) 
    {
        int sign=1;
        long res=0;
        int i=0;
        if(str.empty())
        {
            return 0;
        }
        while(str[i]==' ')
        {
            i++;
        }
        if(str[i]=='-' || str[i]=='+')
        {
            sign= (str[i]=='+')?1:-1;
            i++;
        }
        while(str[i]>='0' && str[i]<='9')
        {
            res=res*10+(str[i]-'0');
            i++;
            if(res*sign>=INT_MAX) return INT_MAX;
            if(res*sign<=INT_MIN) return INT_MIN;
        }
        return res*sign;
    }
    
    
};

9 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
    bool isPalindrome(int x)
    {
        if(x<0) return false;
        int tmp=x;
        int reverse=0;
        while(tmp)
        {
            reverse=reverse*10+tmp%10;
            tmp=tmp/10;
        }
        if(x==reverse)
        {
            return true;
        }
        return false;
    }
    
};

10. 正则表达式匹配（回到目录）

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

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
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: fal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() == 1) {
            return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
        }
        if (p[1] != '*') 
        {
            if (s.empty()) return false;
            return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
        while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
            if (isMatch(s, p.substr(2))) return true;
            s = s.substr(1);
        }
        return isMatch(s, p.substr(2));
    }
};

11 盛水（回到目录）

LINK
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool cmp(pair<int,int> &a,pair<int,int> &b)
{
    return a.second>b.second;
}
class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int len=height.size();
        if(len<2) return 0;
        int res=0;
        vector<pair<int,int> > index_height;
        for(int i=0;i<len;i++)
        {
            index_height.push_back(make_pair(i,height[i]));
        }
        sort(index_height.begin(),index_height.end(),cmp);
        int t=index_height[1].first-index_height[0].first;
        res=t*index_height[1].second;
        return res;
        
        
    }
};

我的做法是错的，以为只需要找到最大的两个数，其实不是！还需要考虑index的距离。

还有一种做法，不知道哪里错了。(后来发现是temp的地方放错了！！！)

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:
    int maxArea(vector<int>& height) 
    {
        int len=height.size();
        if(len<2) return 0;
        int start=0;
        int end=len-1;
        int h=0;
        int res=0,temp=0;
        while(start<end)
        {
            if(temp>res)
            {
                res=temp;
            }
            if(height[start]<height[end])
            {
                h=height[start];
                start++;
            }
            else
            {
                h=height[end];
                end--;
            }
            temp=h*(end-start);
        }
        return res;
    }
};

下面的这个方法可以ac:

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 {
public:
    int maxArea(vector<int>& height) 
    {
        int len=height.size();
        if(len<2) return 0;
        int start=0;
        int end=len-1;
        int h=0;
        int result=0,temp=0;
        while(start<end)
        {
            temp=min(height[start],height[end])*(end-start);
            if(temp>res)
                {
                    res=temp;
                }
            if(height[start]<height[end])
            {
                 
                //h=height[start];
                start++;
            }
            else
            {
                //h=height[end];
                end--;
            }
            
        }
        return result;
    }
};

12 整数转换成罗马数字（回到目录）

LINK

我的做法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string intToRoman(int num) 
    {
        string res;
        vector<string> roman={"M","D","C","L","X","V","I"};
        vector<int> val={1000,500,100,50,10,5,1};
        int i=0;
        for(int i=0;num !=0;i++)
        {
            while(num!=0)
            {
                if(num>=val[i])
                {
                    num -= val[i];
                    res += roman[i];
                }
            }
        }
        return res;
    }
};

参考做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string intToRoman(int num) 
    {
        string res;
        vector<string> roman={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        vector<int> val={1000,900,500,400,100,90,50,40,10,9,5,4,1};
        for(int i=0;num !=0;i++)
        {
            while(num>=val[i])
            {
                num -= val[i];
                res += roman[i];
            }
        }
        return res;
    }
};

13 罗马数字转换城整数（回到目录）

LINK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int romanToInt(string s) 
    {
        unordered_map<char,int> char_map={{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
        int sum=char_map[s.back()];
        for(int i=0;i<s.size()-1;i++)
        {
            if(char_map[s[i]]<char_map[s[i+1]])
            {
                sum=sum-char_map[s[i]];
            }
            else
            {
                sum=sum+char_map[s[i]];
            }
        }
        return sum;
    }
};

15 三数之和（回到目录）

链接:
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

1
2
3
4
5
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int> > res;
        int len=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<len-2;i++)
        {
            int j=i+1;
            int k=len-1;
            while(j<k)
            {
                if(nums[i]+nums[j]+nums[k]>0)
                {
                    k--;
                }
                else if(nums[i]+nums[j]+nums[k]<0)
                {
                    j++;
                }
                else
                {
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(nums[j+1]==nums[j])
                    {
                        j++;
                    }
                    while(nums[k]==nums[k-1])
                    {
                        k--;
                    }
                    j++;
                }
            }
            while(nums[i+1]==nums[i])
            {
                i++;
            }
        }
        return res;
    }
};

启发于4数之和的做法，有以下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution 
{
public:
    vector<vector<int> > threeSum(vector<int> &num) //相当于target==0
    {
        vector<vector<int> > res;
        if(num.size()<3) return res;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size()-2;i++)
        {
            int target_2=-num[i];
            int left=i+1,right=num.size()-1;
            while(left<right)
            {
                int sum_2=num[left]+num[right];
                if(sum_2<target_2)
                {
                    left++;
                }
                else if(sum_2>target_2)
                {
                    right--;
                }
                else if(sum_2==target_2)
                {
                    vector<int> item(3,0);
                    item[0]=num[i];
                    item[1]=num[left];
                    item[2]=num[right];
                    res.push_back(item);
                    while(num[left]==item[1]) left++;
                    while(num[right]==item[2]) right--;
                }
            }
            while(num[i+1]==num[i]) i++;
        }
        return res;
    }
};

16 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2(-1 + 2 + 1 = 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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) 
    {
        //int closestSum=nums[0]+nums[1]+nums[2];
        int closestSum=0;
        int diff=99999999999999999;
        //int diff=abs(closestSum-target);
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {
            int left=i+1;
            int right=nums.size()-1;
            while(left<right)
            {
                int sum=nums[i]+nums[left]+nums[right];
                int new_diff=abs(sum-target);
                if(diff>new_diff)
                {
                    diff=new_diff;
                    closestSum=sum;
                }
                if(sum<target)
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return closestSum;
    }
};

17 电话号码的字母组合（回到目录）

定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1:

不对应任何字母。

示例:

1
2
3
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

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<string> letterCombinations(string digits) 
    {
        vector<string> res;
        if(digits.size()==0) return res;
        string local;
        vector<vector<char> > table{{'w'}, {'w'}, {'a','b','c'}, {'d','e','f'}, {'g','h','i'}, {'j','k','l'}, 
        {'m','n','o'}, {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};//前两个，随便定义。。。。
        generate(table,res,local,0,digits);
        return res;
    }
private:
    void generate(vector<vector<char> > &table,vector<string> &res,string &local,int index,string digits)
    {
        int digit=digits[index]-'0';
        if(index==digits.size())
        {
            res.push_back(local);
        }
		if(index>digits.size()) return;
        for(int i=0;i<table[digit].size();i++)
        {
            local.push_back(table[digit][i]);
            generate(table,res,local,index+1,digits);
            local.pop_back();
        }
    }
};

==大坑==：
实际上这行代码是省略了的，因为对于一个字符串来说，结束符是‘\0’,index加到最后面递归函数自然会return，所以可以不用return。我一开始，是直接在res.push_back(local);的下一行加return，那肯定是错的。因为index还没大于digits.size，就不能return.

18 四数之和（回到目录）

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
class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
    
        vector<vector<int> > res;
    
        if (num.size()<4)//原先是num.empy()
            return res;
    
        sort(num.begin(),num.end());
    
        for (int i = 0; i < num.size()-3; i++) {//原先是i<num.size();
        
            int target_3 = target - num[i];
        
            for (int j = i + 1; j < num.size()-2; j++) { //原先是i<num.size()
            
                int target_2 = target_3 - num[j];
            
                int front = j + 1;
                int back = num.size() - 1;
            
                while(front < back) {
                
                    int two_sum = num[front] + num[back];
                
                    if (two_sum < target_2) front++;
                
                    else if (two_sum > target_2) back--;
                
                    else {
                    
                        vector<int> quadruplet(4, 0);
                        quadruplet[0] = num[i];
                        quadruplet[1] = num[j];
                        quadruplet[2] = num[front];
                        quadruplet[3] = num[back];
                        res.push_back(quadruplet);
                    
                        // Processing the duplicates of number 3
                        while (front < back && num[front] == quadruplet[2]) ++front;
                    
                        // Processing the duplicates of number 4
                        while (front < back && num[back] == quadruplet[3]) --back;
                
                    }
                }
                
                // Processing the duplicates of number 2
                while(j + 1 < num.size() && num[j + 1] == num[j]) ++j;
            }
        
            // Processing the duplicates of number 1
            while (i + 1 < num.size() && num[i + 1] == num[i]) ++i;
        
        }
    
        return res;
    
    }
};

19 删除倒数第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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        int len=0;
        ListNode* p=head;
        while(p)
        {
            len++;
            p=p->next;
        }
        if(len==1 && n==1) return NULL;
        if(len!=1 &&len==n)
        {
            head=head->next;
        }
        
        p=head;
        int t1=len-n-1;
        while(t1>0)
        {
            t1--;
            p=p->next;
        }
        ListNode* pre=p;
        p=head;
        int t2=len-n+1;
        while(t2>0)
        {
            t2--;
            p=p->next;
        }
        ListNode* head_next=p;
        pre->next=head_next;
        return head;
    }
};

21 合并两个有序链表（回到目录）

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4

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:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        //新建节点的两种方式
        /*
        ListNode temp(0);
        ListNode* ptr=&temp;
        */
        ListNode* pre=ListNode(0);
        ListNode* ptr=pre;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                ptr=l1;
                l1=l1->next;
            }
            else
            {
                ptr=l2;
                l2=l2->next;
            }
            ptr=ptr->next;
        }
        
        if(l1)
        {
            ptr->next=l1;
        }
        if(l2)
        {
            ptr->next=l2;
        }
        
        return pre->next;
    }
};

20 有效的括号（回到目录）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

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:
    bool isValid(string s) 
    {
        int len=s.size();
        if(len==0) return true;
        if(len==1) return false;
        stack<char> res;
        for(int i=0;i<len;i++)
        {
            if(res.empty()) res.push(s[i]);
            else if((res.top()=='(' && s[i]==')') || (res.top()=='[' && s[i]==']') ||(res.top()=='{' && s[i]=='}'))
            {
                res.pop();
            }
            else
            {
                res.push(s[i]);
            }
            
        }
        return res.empty();
};

23 合并K个有序链表（回到目录）

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

方法1：分治归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.size()==0) return NULL;
        if(lists.size()==1) return lists[0];
        if(lists.size()==2) return mergeTwoLists(lists[0],lists[1]);
        
        int mid=lists.size()/2;
        vector<ListNode*> sublists_1;
        vector<ListNode*> sublists_2;
        for(int i=0;i<mid;i++)
        {
            sublists_1.push_back(lists[i]);
        }
        for(int i=mid;i<lists.size();i++)
        {
            sublists_2.push_back(lists[i]);
        }
        ListNode* l1=mergeKLists(sublists_1);
        ListNode* l2=mergeKLists(sublists_2);
        return mergeTwoLists(l1,l2);
    }
private:
    ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
    {
        ListNode temp(0);
        ListNode* ptr= &temp;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                ptr->next=l1;
                l1=l1->next;
            }
            else
            {
                ptr->next=l2;
                l2=l2->next;
            }
            ptr=ptr->next;
        }
        if(l1)
        {
            ptr->next=l1;
        }
        if(l2)
        {
            ptr->next=l2;
        }
        return temp.next;
    }
};

方法2: 将所有的节点放在一个vector,然后再排序，最后相连。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        vector<ListNode*> node_vec;
        for(int i=0;i<lists.size();i++)
        {
            node_vec.push_back(lists[i]);
            
        }
        if(node_vec.size()==0)
        {
            return NULL;
        }
        sort(node_vec.begin(),node_vec.end(),cmp);
        for(int i=1;i<node_vec.size();i++)
        {
            node_vec[i-1]->next=node_vec[i];
        }
        node_vec[node_vec.size()-1]->next=NULL;
        return node_vec[0];
    }
private:
    bool cmp(const ListNode* a,const ListNode* b)
    {
        return a->val < b->val;
    }
};

24 两两交换链表中相邻的节点（回到目录）

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

说明:

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {//递归
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL)
            return NULL;
        if(head->next == NULL)
            return head;
        
        ListNode* temp = head->next;
        head->next = swapPairs(temp->next);
        temp->next = head;//这个temp和上一行函数里面的temp不一样。
        
        return temp;
    }
};

26 删除排序数组中的重复项（82，83）（回到目录）

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

1
2
3
4
5
给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

方法1

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:
        int removeDuplicates(vector<int>& nums) 
        {
            if(nums.size()==0) return 0;
            int cnt=0;
            for(int i=1;i<nums.size();i++)
            {
                if(nums[i] ==nums[i-1])
                {
                     cnt++;               
                }
                else
                {
                    nums[i-cnt]=nums[i];
                }
            }
            return (nums.size()-cnt);
        }
    };

方法2（我更倾向）

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) 
        {
            if(nums.size()==0) return 0;
            int index=0;
            for(int i=1;i<nums.size();i++)
            {
                if(nums[i] !=nums[i-1])
                {
                    index++;
                    nums[index]=nums[i];
                }
            }
            return index+1;
        }
    };

快慢指针:同方法2

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int pre = 0, cur = 0, n = nums.size();
        while (cur < n) {
            if (nums[pre] == nums[cur]) ++cur;
            else nums[++pre] = nums[cur++];
        }
        return pre + 1;
    }
};

80 删除排序数组中的重复项 II（回到目录）

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1:
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        if(nums.size()<=2) return nums.size();
        int pre=0;
        int cur=1;
        int count=1;
        while(cur<nums.size())
        {
            if(nums[pre]==nums[cur] && count==0) cur++;
            else
            {
                if(nums[pre]==nums[cur]) count--;
                else
                {
                    count=1;
                }
                nums[++pre]=nums[cur++];
            }
        }
        return pre+1;
    }
};

31 下一个排列（回到目录）

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

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:
    void nextPermutation(vector<int>& nums) 
    {
        int len=nums.size();
        int j;
        for(int i=len-2;i>=0;i--)
        {
            if(nums[i]<nums[i+1])
            {
                for(j=len-1;j>i;j--)//为了找第一个比nums[i]大的数字
                {
                    if(nums[j]>nums[i]) break;
                }
                swap(nums[i],nums[j]);
                reverse(nums.begin()+i+1,nums.end());
                return;
            }
        }
        reverse(nums.begin(),nums.end());
        
    }
};

32 最长有效括号（回到目录）

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

使用栈

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 longestValidParentheses(string s) 
    {
        stack<int> index;
        int res=0;
        int start=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(')
            {
                index.push(i);
            }
            else if(s[i]==')')
            {
                if(index.empty())
                {
                    start=i+1;
                }
                else
                {
                    index.pop();
                    if(index.empty())
                    {
                        res=max(res,i-start+1);
                    }
                    else
                    {
                        res=max(res,i-index.top());
                    }
                }
            }
        }
        return res;
    }
};

33 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

1
2
3
4
5
6
7
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int begin=0;
        int end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                return mid;
            }
            else if(target<nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]>nums[mid])
                {
                    end=mid-1;
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
            else if(target>nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    begin=mid+1;
                }
                else if(nums[begin]>nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
        }
        return -1;
    }
};

二分查找
这道题让在旋转数组中搜索一个给定值，若存在返回坐标，若不存在返回-1。我们还是考虑二分搜索法，但是这道题的难点在于我们不知道原数组在哪旋转了，我们还是用题目中给的例子来分析，对于数组[0 1 2 4 5 6 7] 共有下列七种旋转方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
0　　1　　2　　 4　　5　　6　　7
7　　0　　1　　 2　　4　　5　　6
6　　7　　0　　 1　　2　　4　　5
5　　6　　7　　 0　　1　　2　　4
4　　5　　6　　7　　0　　1　　2
2　　4　　5　　6　　7　　0　　1
1　　2　　4　　5　　6　　7　　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
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        if(nums.size()==0) return -1;
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<nums[right])//说明右半边有序
            {
                if(nums[mid]<target && target<=nums[right]) left=mid+1;
                else right=mid-1;
            }
            else if(nums[mid]>=nums[right])//说明左半部有序
            {
                if(target>=nums[left] && target<nums[mid]) right=mid-1;
                else left=mid+1;
            }
        }
        return -1;
    }
};

34 在排序数组中查找元素的第一个和最后一个位置（回到目录）

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

1
2
3
4
5
6
7
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> result;
        result.push_back(left_bound(nums,target));
        result.push_back(right_bound(nums,target));
        return result;
    }
private:
    int left_bound(vector<int> &nums,int target)
    {
        int begin=0,end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                if(nums[mid-1]<target || mid==0)
                {
                    return mid;
                }
                end=mid-1;
            }
            else if(target<nums[mid])
            {
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                begin=mid+1;
            }
        }
        return -1;
    }
    
int right_bound(vector<int> &nums,int target)
{
    int begin=0,end=nums.size()-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;
        if(target==nums[mid])
        {
            if(nums[mid+1]>target || mid==nums.size()-1)
            {
                return mid;
            }
            begin=mid+1;
        }
       else if(target<nums[mid])
        {
            end=mid-1;
        }
        else if(target>nums[mid])
        {
            begin=mid+1;
        }
    }
    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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        if(nums.empty()) return res;
        int left = 0, right = nums.size()-1;//这里是因为左边界的数不可能到数组最后一位
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (nums[right]!= target) return res;
        res[0] = right;
        right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) left = mid + 1;
            else right= mid;
        }
        res[1] = left - 1;
        return res;
    }
};

35 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 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
33
34
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int index=-1;
        int begin=0;
        int end=nums.size()-1;
        while(index==-1)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                index=mid;
            }
            else if(target<nums[mid])
            {
                if(mid==0 || target>nums[mid-1])
                {
                    index=mid;
                }
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                if(mid==nums.size()-1 || target<nums[mid+1])
                {
                    index=mid+1;
                }
                begin=mid+1;
            }
        }
        return index;
    }
};

其他解法1

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= target) return i;
        }
        return nums.size();
    }
};

其他解法2:二分查找法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if (nums.back() < target) return nums.size();
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;//相当于查找第一个大于target的数
        }
        return right;
    }
};

39 组合总和 I

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

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:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());
        vector<vector<int> >res;
        vector<int> item;
        generate(candidates,res,item,target,0);
        return res;
        
        
    }
    void generate(vector<int> &candidates,vector<vector<int> > &res,vector<int> &item,int target,int begin)
    {
        int len=candidates.size();
        if(target==0)
        {
            res.push_back(item);
            return;
        }
        if(target<0) return;
        for(int i=begin;i<len;i++)
        {
            item.push_back(candidates[i]);
            generate(candidates,res,item,target-candidates[i],i);
            item.pop_back();
        }
    }
};

40 组合总和 II（回到目录）

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

方法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
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) 
    {
        vector<vector<int>> res;
        sort(num.begin(),num.end());
        vector<int> local;
        findCombination(res, 0, target, local, num);
        return res;
    }
    void findCombination(vector<vector<int>>& res, const int start, const int target, vector<int>& local, const vector<int>& num)
    {
        if(target==0)
        {
            res.push_back(local);
            return;
        }
        else
        {
            for(int i = start;i<num.size();i++) // iterative component
            {
                if(target<0) return;
                if(num[i]==num[i-1] && i>start) continue; // check duplicate combination
                local.push_back(num[i]),
                findCombination(res,i+1,target-num[i],local,num); // recursive componenet
                local.pop_back();
            }
        }
    }
};

另一种做法:使用set容器，代码和上面那题一样的

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:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) 
    {
        set<vector<int>> res;
        sort(num.begin(),num.end());
        vector<int> local;
        findCombination(res, 0, target, local, num);
        return vector<vector<int> > (res.begin(),res.end());
    }
    void findCombination(set<vector<int>>& res, const int order, const int target, vector<int>& local, const vector<int>& num)
    {
        if(target==0)
        {
            res.insert(local);
            return;
        }
        else
        {
            for(int i = order;i<num.size();i++) // iterative component
            {
                if(target<0) return;
                //if(num[i]==num[i-1]&&i>order) continue; // check duplicate combination
                local.push_back(num[i]),
                findCombination(res,i+1,target-num[i],local,num); // recursive componenet
                local.pop_back();
            }
        }
    }
};

45 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

1
2
3
4
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int jump(vector<int>& nums) 
    {
        if(nums.size()<2)
            return 0;
        int current_max_index=nums[0];
        int pre_max_index=nums[0];
        int jump_min=1;
        for(int i=1;i<nums.size();i++)
        {
            if(i>current_max_index)
            {
                jump_min++;
                current_max_index=pre_max_index;
            }
                         
            if(pre_max_index<nums[i]+i)
            {
                pre_max_index=nums[i]+i;
            }
        }
        return jump_min;
    }
};

46 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,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
class Solution {//递归
public:
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<vector<int> > res;
        generate(nums,res,0);
        return res;
    }
private:
    void generate(vector<int> &nums,vector<vector<int> >&res,int begin)
    {
        if(begin>=nums.size())
        {
            res.push_back(nums);
            return;
        }
        for(int i=begin;i<nums.size();i++)//循环实现和begin+1之后的全排列
        {
            swap(nums[begin],nums[i]);
            generate(nums,res,begin+1);
            swap(nums[begin],nums[i]);
        }
    }
};

注：我们来仔细推敲一下循环体里的代码，当我们对序列进行交换之后，就将交换后的序列除去第一个元素放入到下一次递归中去了，递归完成了再进行下一次循环。这是某一次循环程序所做的工作，这里有一个问题，那就是在进入到下一次循环时，序列是被改变了。可是，如果我们要假定第一位的所有可能性的话，那么，就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后，要还原，确保初始状态一致。

47 全排列II（回到目录）

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
8
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        vector<vector<int> >res;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        generate(res,res_set,nums,0);
        return res;
    }
private:
    void generate(vector<vector<int> > &res,set<vector<int> > &res_set,vector<int> &nums,int begin)
    {
        if(begin>=nums.size() && res_set.find(nums) ==res_set.end())
        {
            res.push_back(nums);
            res_set.insert(nums);
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            swap(nums[begin],nums[i]);
            generate(res,res_set,nums,begin+1);
            swap(nums[begin],nums[i]);
            
        }
    }
};

48 旋转图像（回到目录）

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

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:
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
示例 2:
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//i表示的是绕中心的层数，j是列数
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        int n=matrix.size();
        for(int i=0;i<n/2;i++)
        {
            for(int j=i;j<n-1-i;j++)
            {
                int t=matrix[i][j];
                matrix[i][j]=matrix[n-1-j][i];
                matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
                matrix[j][n-1-i]=t;
            }
        }
    }
};

49 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

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:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {  
        map<vector<int>,vector<string> >anagram;
        vector<vector<string> > res;
        for(int i=0;i<strs.size();i++)
        {
            vector<int> vec;
            change_to_vec(strs[i],vec);
            if(anagram.find(vec)==anagram.end())
            {
                vector<string> item;
                anagram[vec]=item;
            }
            anagram[vec].push_back(strs[i]);
        }
        map<vector<int>,vector<string> >::iterator it;
        for(it=anagram.begin();it!=anagram.end();it++)
        {
            res.push_back((*it).second);
        }
        return res;
    }
private:
    void change_to_vec(string &str,vector<int> &vec)
    {
        for(int i=0;i<26;i++)
        {
            vec.push_back(0);
        }
        for(int i=0;i<str.length();i++)
        {
            vec[str[i]-'a']++;
        }
    }
};

另一种更为巧妙地方法：使用哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        vector<vector<string> > res;
        map<string,vector<string> > m;
        for(int i=0;i<strs.size();i++)
        {
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            m[temp].push_back(strs[i]);
        }
        for(auto item:m)
        {
            res.push_back(item.second);
        }
        return res;
    }
};

51 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) 
    {
        vector<vector<string> > result;
        vector<vector<int> > mark;
        vector<string> location;
        for(int i=0;i<n;i++)
        {
            mark.push_back(vector<int> ());
            for(int j=0;j<n;j++)
            {
                mark[i].push_back(0);
            }
            location.push_back("");//字符串向量的初始化
            location[i].append(n,'.');
            
        }
        generate(0,n,location,result,mark);
        return result;
    }
private:
    void generate(int k,int n,vector<string> &location,vector<vector<string> > &result,vector<vector<int> > &mark)
    {
        if(k==n)
        {
            result.push_back(location);
            return;
        }
        for(int i=0;i<n;i++)
        {
            if(mark[k][i]==0)
            {
                vector<vector<int> > temp_mark;
                temp_mark=mark;
                location[k][i]='Q';
                put_down_queen(k,i,mark);
                generate(k+1,n,location,result,mark);
                mark=temp_mark;
                location[k][i]='.';
                
            }
        }
    }
    void put_down_queen(int x,int y,vector<vector<int> > &mark)
    {
        static const int dx[]={-1,1,0,0,-1,-1,1,1};
        static const int dy[]={0,0,-1,1,-1,1,-1,1};
        mark[x][y]=1;
        for(int i=1;i<mark.size();i++)
        {
            for(int j=0;j<8;j++)
            {
                int new_x=x+i*dx[j];
                int new_y=y+i*dy[j];
                if(new_x>=0 && new_x<mark.size() && new_y>=0 && new_y<mark.size())
                {
                    mark[new_x][new_y]=1;
                }
            }
        }
    }
};

53 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

动态规划

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

常规方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,curSum=0,maxSum=-1e5;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
        curSum+=arr[i];
        if(curSum>maxSum){
            maxSum=curSum;
        }
        if(curSum<0){
            curSum=0;
        }
    }
    cout<<maxSum<<endl;
    return 0;
}

55 跳跃游戏（回到目录）

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

1
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 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
class Solution
{
public:
    bool canjump(vector<int> nums)
    {
        vector<int> index;
        int jump=0;
        for(int i=0;i<nums.size();i++)
        {
            index.push_back(i+nums[i]);
        }
        int max_jump=index[0];
        while(jump<index.size() && jump<max_jump)
        {
            if(max_jump<index[jump])
            {
                max_jump=index[jump];
            }
            jump++;
        }
        if(jump==index.size()
        {
            return true;
        }
        return false;
    }
    
};

另一个好的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) 
    {   
        int reach=0;
        for(int i=0;i<nums.size();i++)
        {
            if(i>reach || reach==nums.size()-1) break;
            reach=max(reach,i+nums[i]);
        }
        return reach>=(nums.size()-1);
    }
};

61 旋转链表（回到目录）

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 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
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
**链表移动位置和数组不一样**

代码

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
/**
 * 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==NULL) return NULL;
        int len=1;
        ListNode* p=head;
        while(p->next)//注意这里一定要使用p->next,不然编译器会报错。
        {
            len++;
            p=p->next;
        }
        p->next=head;
        int begin_pos=len-k%len-1;
        ListNode* cur=head;
        while(begin_pos)
        {
            begin_pos--;
            cur=cur->next;
        }
        ListNode* new_head=cur->next;
        cur->next=NULL;
        return new_head;
    }
};

64 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

代码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:
    int minPathSum(vector<vector<int>>& grid) 
    {
        if(grid.size()==0) return 0;
        int row=grid.size();
        int col=grid[0].size();
        vector<vector<int> >dp(row,vector<int>(col,0));
        dp[0][0]=grid[0][0];
        for(int j=1;j<col;j++)
        {
            dp[0][j]=grid[0][j]+dp[0][j-1];
            
        }
        for(int i=1;i<row;i++)
        {
            dp[i][0]=grid[i][0]+dp[i-1][0];
            for(int j=1;j<col;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
};

代码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
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        if(m == 0 || n == 0)
            return 0;
        vector<vector<int>> dp(m, vector<int>(n));
        for(int i = 0; i < m; i++) 
        {
            for(int j = 0; j < n; j++) 
            {
                if(i == 0 && j == 0) 
                {
                    dp[i][j] = grid[i][j];
                } 
                else if(i == 0) 
                {
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                } 
                else if(j == 0) 
                {
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                } 
                else 
                {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

66 加一（回到目录）

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 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
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) 
    {
        int len=digits.size();
        for(int i=len-1;i>=0;i--)
        {
            if(digits[i]!=9)
            {
                digits[i]++;
                break;
            }
            else
            {
                digits[i]=0;
            }
            if(digits[0]==0)
            {
                digits[0]=1;
                digits.push_back(0);
            }
        }
        return digits;
    }
};

67 二进制求和（回到目录）

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

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
class Solution {
public:
    string addBinary(string a, string b) 
    {
        string res;
        int len_a=a.size();
        int len_b=b.size();
        int n=max(len_a,len_b);
        int carry=0;
        if(len_a>len_b)
        {
            for(int i=0;i<len_a-len_b;i++)
            {
                b.insert(b.begin(),'0');
            }
        }
        else if(len_b>len_a)
        {
            for(int i=0;i<len_b-len_a;i++)
            {
                a.insert(a.begin(),'0');
            }
        }
        for(int i=n-1;i>=0;i--)
        {
            int temp=0;
            if(carry)
            {
                temp=(a[i]-'0')+(b[i]-'0')+1;
            }
            else
            {
                temp=(a[i]-'0')+(b[i]-'0');
            }
            switch(temp)
            {
                case 0:
                    res.insert(res.begin(),'0');
                    carry=0;
                    break;
                case 1:
                    res.insert(res.begin(),'1');
                    carry=0;
                    break;
                case 2:
                    res.insert(res.begin(),'0');
                    carry=1;
                    break;
                case 3:
                    res.insert(res.begin(),'1');
                    carry=1;
                    break;
            }
        }
        if(carry)
        {
            res.insert(res.begin(),'1');
        }
        return res;
    }
};

69 x 的平方根（回到目录）

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
4
5
6
7
8
9
10
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int mySqrt(int x) {
        int low = 0,  high = x, mid;
        if(x<2) return x; // to avoid mid = 0
        while(low<high)
        {
            mid = (low + high)/2;
            if(x/mid >= mid) low = mid+1;
            else high = mid;
        }
        return high-1;
        
    }
};

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//原来的i是int,不通过，改成long之后，就可以了
class Solution {
public:
    int mySqrt(int x) 
    {
        int res=0;
        int n=x/2;
        if(x<2) return x; 
        for(long i=0;i<=n;i++)
        {
            if(x>=i*i && x<(i+1)*(i+1))
            {
                res=i;
                break;
            }
        }
        return res;
    }
};

70 爬楼梯答（回到目录）

假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 步 + 1 步
2.  2 步
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) 
    {
        vector<int> dp(n,0);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

76 最小覆盖子串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

1
2
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

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 {
private:
	bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
    	for (int i = 0; i < vec_t.size(); i++){
    		if (map_s[vec_t[i]] < map_t[vec_t[i]]){
		    	return false;
		    }
	    }
	    return true;
    }
public:
    std::string minWindow(std::string s, std::string t) {
        const int MAX_ARRAY_LEN = 128;
        int map_t[MAX_ARRAY_LEN] = {0};
        int map_s[MAX_ARRAY_LEN] = {0};
        std::vector<int> vec_t;
        for (int i = 0; i < t.length(); i++){
        	map_t[t[i]]++;
        }
        for (int i = 0; i < MAX_ARRAY_LEN; i++){
        	if (map_t[i] > 0){
	        	vec_t.push_back(i);
	        }
        }
        
        int window_begin = 0;
        std::string result;
        for (int i = 0; i < s.length(); i++){
        	map_s[s[i]]++;
        	while(window_begin < i){
        		char begin_ch = s[window_begin];
	        	if (map_t[begin_ch] == 0){
	        		window_begin++;
	        	}
	        	else if	(map_s[begin_ch] > map_t[begin_ch]){
	        		map_s[begin_ch]--;
	        		window_begin++;
	        	}
                else
                    {break;}
	        }
	        if (is_window_ok(map_s, map_t, vec_t)){
        		int new_window_len = i - window_begin + 1;
        		if (result == "" || result.length() > new_window_len){
		        	result = s.substr(window_begin, new_window_len);
				}
        	}
        }
        return result;
    }
};

77 组合（回到目录）

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: n = 4, k = 2
输出:
[
  [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
23
24
25
26
class Solution {
public:
    vector<vector<int>> combine(int n, int k) 
    {
        vector<vector<int> >res;
        vector<int> item(0,k);
        if(k>n) return res;
        generate(n,k,0,0,item,res);
        return res;
    }
private:
    void generate(int n,int k,int numOfDigit,int begin,vector<int> &item,vector<vector<int> > &res)
    {
        if(numOfDigit==k)
        {
            res.push_back(item);
            return;
        }   
        for(int i=begin;i<n;i++)
        {
            item.push_back(i+1);
            generate(n,k,numOfDigit+1,i+1,item,res);
            item.pop_back();
        }
    }
};

78 子集（回到目录）

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

小象写法

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> >subsets(vector<int> &nums)
    {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        generate(0,nums,item,result);
        return result;
    }
private:
    void generate(int i,vector<int> &nums,vector<int> &item, vector<vector<int> >&result)
    {
        if(i>=nums.size()) return;
        item.push_back(nums[i]);
        result.push_back(item);
        generate(i+1,nums,item,result);
        item.pop_back();
        generate(i+1,nums,item,result);
    }
};

for循环里递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {//for循环
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int> >res;
        vector<int> item;
        res.push_back(item);
        sort(nums.begin(),nums.end());//解答错误不是没有排序的问题
        generate(res,item,nums,0);
        
        return res;
    }
private:
    void generate(vector<vector<int> > &res, vector<int> &item, vector<int> &nums, int begin)
    {
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            item.push_back(nums[i]);
            res.push_back(item);
            generate(res,item,nums,i+1);
            item.pop_back();
        }
    }
};

90 子集 II（回到目录）

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int> >result;
        vector<int> item;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,item,result,res_set);
        return result;
        
    }
private:
    void generate(int i, vector<int> &nums,vector<int> & item, vector<vector<int> > &result, set<vector<int> > &res_set)
    {
        if(i>=nums.size())
            return;
        item.push_back(nums[i]);
        
        if(res_set.find(item)==res_set.end())
        {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i+1,nums,item,result,res_set);
        item.pop_back();
        generate(i+1,nums,item,result,res_set);
    }
    
};

for循环里面递归

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:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int> >res;
        vector<int> item;
        res.push_back(item);
        sort(nums.begin(),nums.end());//解答错误不是没有排序的问题
        generate(res,item,nums,0);
        
        return res;
    }
private:
    void generate(vector<vector<int> > &res, vector<int> &item, vector<int> &nums, int begin)
    {
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            item.push_back(nums[i]);
            res.push_back(item);
            generate(res,item,nums,i+1);
            item.pop_back();
            while(i+1<nums.size() && nums[i]==nums[i+1]) i++;
        }
    }
};

82 删除排序链表中的重复元素II（回到目录）

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

1
2
3
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

1
2
3
4
输入: 1->1->1->2->3
输出: 2->3
`

新建链表头结点指针pDel，pDel->next=head，并设置指针prev指针指向pDel，curr指针指向head->next（代表遍历指针）;当curr->next不为NULL，如果curr->next->val == curr->val，curr=curr->next；如果curr->next->val != curr->val；则需判断prev->next=curr？如果是，则prev=curr；如果不是，则prev->next=curr->next.（这里是说，prev先假设一个next指针，即curr=curr->next；当进行下一步判断时，如果curr->next->val != curr->val 且 prev->next==curr，则说明假设正确，prev直接指向curr）

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
//这题一定要借用头节点，来获取pre指针。
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {             
        if(head==NULL || head->next==NULL)
        {
            return head;
        }
        ListNode* pre_head=new ListNode(0);
        pre_head->next=head;
        ListNode* pre=pre_head;
        ListNode* cur=head;
        while(cur->next)
        {
            if(cur->val != cur->next->val)
            {
                if(pre->next==cur)
                {
                    pre=cur;
                }
                else
                {
                    pre->next=cur->next;
                }
            }
            
            cur=cur->next;
        }
        if(pre->next !=cur)
        {
            pre->next=cur->next;
        }
        return pre_head->next;
        
    }
};

83 删除排序链表中的重复元素（回到目录）

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例1:

1
2
3
输入: 1->1->2
输出: 1->2

示例2:

1
2
3
输入: 1->1->2->3->3
输出: 1->2->3

代码

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:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(!head) return NULL;
        ListNode* pre=head;
        ListNode* cur=head->next;
        while(cur)
        {
            if(cur->val==pre->val)
            {
                pre->next=cur->next;
            }
            else
            {
                pre=pre->next;
            }
            cur=cur->next;
        }
        return head;
    }
};

86 分割链表（回到目录）

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

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:
    ListNode* partition(ListNode* head, int x) 
    {
        ListNode less_head(0);
        ListNode more_head(0);
        ListNode* less_ptr= &less_head;
        ListNode* more_ptr= &more_head;
        while(head)
        {
            if(head->val <x)
            {
                less_ptr->next=head;
                less_ptr=head;
            }
            else
            {
                more_ptr->next=head;
                more_ptr=head;
            }
            head=head->next;
        }
        less_ptr->next=more_head.next;
        more_ptr->next=NULL;
        return less_head.next;
    }
};

88 合并有序数组

给定两个有序整数数组nums1和 nums2，将nums2 合并到nums1 中，使得num1成为一个有序数组。

说明:

初始化 nums1和 nums2的元素数量分别为m 和n。
你可以假设nums1有足够的空间（空间大小大于或等于 m + n）来保存nums2中的元素。

示例:

1
2
3
4
5
6
输入: 
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        int i=m-1;
        int j=n-1;
        int k=m+n-1;
        while(i>=0 && j>=0)
        {
            if(nums2[j]>=nums1[i])
            {
                nums1[k]=nums2[j];
                k--;
                j--;
            }
            else
            {
                nums1[k]=nums1[i];
                k--;
                i--;
            }
        }
        while(j>=0)
        {
            nums1[k]=nums2[j];
            k--;
            j--;
        }
    }
};

92 反转链表II（回到目录）

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

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:
    ListNode* reverseBetween(ListNode* head, int m, int n) 
    {
        int list_len=n-m+1;
        ListNode* pre_head=NULL;
        ListNode* result=head;
        while(head && --m)
        {
            pre_head=head;
            head=head->next;
        }
        ListNode* modify_list_tail=head;
        ListNode* new_head=NULL;
        while(head && list_len)
        {
            ListNode* next=head->next;
            head->next=new_head;
            new_head=head;
            head=next;
            list_len--;
        }
        modify_list_tail->next=head;
        if(pre_head)
        {
            pre_head->next=new_head;
            
        }
        else
        {
            result=new_head;
        }   
        return result;
        
    }
};

94 二叉树的中序遍历（144，145）（回到目录）

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        if(root==NULL) return res;
        vector<int> temp1=inorderTraversal(root->left);
        for(int i=0;i<temp1.size();i++)
        {
            res.push_back(temp1[i]);
        }
        res.push_back(root->val);
        
        vector<int> temp2=inorderTraversal(root->right);
        for(int i=0;i<temp2.size();i++)
        {
            res.push_back(temp2[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
25
26
27
28
29
30
31
class Solution {
    vector<int> res;
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        if(root==NULL) return res;
        vector<int> res;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* node=s.top();
            if(node->left)
            {
                s.push(node->left);
                node->left=NULL;
            }
            else
            {
                res.push_back(node->val);
                s.pop();
                if(node->right)
                {
                    s.push(node->right);
                    
                }
            }
        }
        return res;
    }
};

101 对称二叉树（回到目录）

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树[1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
6
7
8
9
10
11
12
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1
   / \
  2   2
   \   \
   3    3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isSymmetric(TreeNode* left,TreeNode* right) 
    {
        if(left==NULL && right==NULL)
            return true;
        if(left==NULL && right!=NULL)
            return false;
        if(left!=NULL && right==NULL)
            return false;
        if(left->val !=right->val)
            return false;
        bool res=(isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left));
        return res;
        
    }
    bool isSymmetric(TreeNode* root) 
    {
        if(root==NULL) 
            return true;
        bool res=isSymmetric(root->left,root->right);
        return res;
        
    }
};

102 二叉树的层次遍历

非递归

分析：先建立一个queue，然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，此时queue里的元素就是下一层的所有节点，用一个for循环遍历它们，然后存到一个一维向量里，遍历完之后再把这个一维向量存到二维向量里，以此类推，可以完成层序遍历。代码如下：

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> > levelOrder(TreeNode *root) {
        vector<vector<int> > res;
        if (root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> oneLevel;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = q.front();
                q.pop();
                oneLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

递归做法

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>> levelOrder(TreeNode* root) 
    {
        vector<vector<int> >res;
        preorder(root,res,0);
        return res;
    }
private:
    void preorder(TreeNode* root,vector<vector<int> > &res,int depth)
    {   
        if(root==NULL) return;
        if(depth==res.size())
        {
            res.push_back(vector<int>());
        }
        
        res[depth].push_back(root->val);
        preorder(root->left,res,depth+1);
        preorder(root->right,res,depth+1);
    }
};

104 二叉树的最大深度（递归）

深度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxDepth(TreeNode* root) 
    {
        int depth=0;
        if(root==NULL) return 0;
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        depth=1+max(left,right);
        return depth;
        
    }
};

宽度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxDepth(TreeNode *root)
{
    if(root == NULL)
        return 0;
    
    int res = 0;
    queue<TreeNode *> q;
    q.push(root);
    while(!q.empty())
    {
        ++ res;
        for(int i = 0, n = q.size(); i < n; ++ i)
        {
            TreeNode *p = q.front();
            q.pop();
            
            if(p -> left != NULL)
                q.push(p -> left);
            if(p -> right != NULL)
                q.push(p -> right);
        }
    }
    return res;
}

111 二叉树的最小深度（回到目录）

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 class Solution {//递归
public:
    int minDepth(TreeNode* root) 
    {
        int depth=0;
        if(root==NULL) return 0;
        int left=minDepth(root->left);
        int right=minDepth(root->right);
        if(left==0 || right==0)
        {
            depth=left+right+1;
        }
        else
        {
            depth=1+min(left,right);
        }
        return depth;       
        
    }
};

108 将有序数组转换为二叉搜索树（回到目录）

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

1
2
3
4
5
     0
    / \
  -3   9
  /   /
-10  5

代码

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
 /**
 * 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* sortedArrayToBST(vector<int>& nums) 
    {
        if(nums.size()==0) return NULL;
        if(nums.size()==1) return new TreeNode(nums[0]);
        int mid=nums.size()/2;
        TreeNode* root=new TreeNode(nums[mid]);
        vector<int> left(nums.begin(),nums.begin()+mid);
        vector<int> right(nums.begin()+mid+1,nums.end());
        root->left=sortedArrayToBST(left);
        root->right=sortedArrayToBST(right);
        
        return root;
    }
};

109 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

使用了递归，和那个24题差不多,关键是如何找到链表的中间位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {//使用了递归，和那个24题差不多
public:
    TreeNode* sortedListToBST(ListNode* head) 
    {
        if(head==NULL) return NULL;
        else if(head->next==NULL) 
        {
            return (new TreeNode(head->val));
        }
        ListNode* fast=head->next->next;
        ListNode* slow=head;
        
        while(fast && fast->next)//这段代码是在找链表中间位置的元素
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        
        TreeNode* root=new TreeNode(slow->next->val);//这就是找到的中间位置
        printf("%d\n",root->val);
        root->right=sortedListToBST(slow->next->next);
        slow->next=NULL;
        root->left=sortedListToBST(head);
                
        return root;
    }
};

110 平衡二叉树（回到目录）

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

1
2
3
4
5
6
7
8
给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

1
2
3
4
5
6
7
8
9
10
给定二叉树 [1,2,2,3,3,null,null,4,4]
       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root==NULL) return true;
        if(abs(depth(root->left)-depth(root->right))>1)
        {
            return false;
        }
        return isBalanced(root->left)&&isBalanced(root->right);
    }
private:
    int depth(TreeNode* root)
    {
        if(root==NULL) return 0;
        return 1+max(depth(root->left),depth(root->right));
    }
};

112 路径之和（二叉树）（回到目录）

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

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 {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        
        bool result=false;
        vector<int> path;
        int path_sum=0;
        preorder(root,path_sum,sum,path,result);
        return result;
        
    }
private:
    void preorder(TreeNode* node, int &path_sum,int sum,vector<int> &path,bool &result)
    {
        if(!node)
        {
            return;
        }
        path_sum=path_sum+node->val;
        path.push_back(node->val);
        if(sum==path_sum && !node->left && !node->right)
        {
            result=true;
        }
        preorder(node->left,path_sum,sum,path,result);
        preorder(node->right,path_sum,sum,path,result);
        path_sum=path_sum-node->val;
        path.pop_back();
            
        
    }
    
};

118 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int> >res(numRows,vector<int>());
        //vector<vector<int> >res;
        if(numRows==0) return res;
        res[0].push_back(1);
        for(int i=1;i<numRows;i++)
        {
            res[i].push_back(1);
            for(int j=1;j<i;j++)
            {
                res[i].push_back(res[i-1][j-1]+res[i-1][j]);
            }
            res[i].push_back(1);
        }
        return res;
    }
};

119 杨辉三角II（回到目录）

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

示例:

1
2
输入: 3
输出: [1,3,3,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//后面的覆盖前面的数据   节省空间
class Solution {
public:
    vector<int> getRow(int rowIndex) 
    {
        vector<int> res(rowIndex+1,0);
        res[0]=1;
        
        for(int i=1;i<=rowIndex;i++)
        {
            for(int j=i;j>=1;j--)
            {
                res[j]=res[j]+res[j-1];
            }
        }
            return res;
    }
};

125 验证回文串（回到目录）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

1
2
3
4
5
6
7
8
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(string s) 
    {
        int l=0;
        int r=s.size()-1;
        while(l<r)
        {
            while(l<r && !isalnum(s[l])) l++;//这两行的l<r，一定要加上，不然“.,”就出错了
            while(l<r && !isalnum(s[r])) r--;
            if(toupper(s[l]) !=toupper(s[r]))
           {
               return false;
           }
            l++;r--;
        }  
        return true;
    } 
};

121 买卖股票的最佳时机（回到目录）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

1
2
输入: [7,1,5,3,6,4]
输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
输入: [7,6,4,3,1]
输出: 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
class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if(prices.size()<=1) return 0;
        int max_pro=0;
        int temp_min=prices[0];
        int len=prices.size();
        for(int i=1;i<len;i++)
        {
            if(temp_min>prices[i])
            {
                temp_min=prices[i];
            }
            else
            {
                int temp_max=prices[i]-temp_min;
                max_pro=max(max_pro,temp_max);
            }
        }
        return max_pro;
    }
};

134 加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

贪心相关:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        int total=0;
        int sum=0;
        int start=0;
        for(int i=0;i<gas.size();i++)
        {
            total=total+gas[i]-cost[i];
            sum=sum+gas[i]-cost[i];
            if(sum<0)
            {
                start =i+1;
                sum=0;
            }
        }
        if(total<0)
        {
            return -1;
        }
        return start;
        
    }
};

135 分发糖果（回到目录）

老师想给孩子们分发糖果，有 N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

1
2
3
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

1
2
3
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

思路：

假设每个孩子分到的糖果数组为A[N]，初始化为{1}，因为每个人至少分到一颗糖。

1、与前面的邻居比较，前向遍历权重数组ratings，如果ratings[i]>ratings[i-1]，则A[i]=A[i-1]+1；

2、与后面的邻居比较，后向遍历权重数组ratings，如果ratings[i]>ratings[i+1]且A[i]<A[i+1]+1，则更新A，A[i]=A[i+1]+1；

3、对A求和即为最少需要的糖果。

时间复杂度：O(n)

空间复杂度：O(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
class Solution {
public:
    int candy(vector<int>& ratings) 
    {
        int sum=0;
        int len=ratings.size();
        vector<int> nums(len,1);
        for(int i=1;i<len;i++)
        {
            if(ratings[i]>ratings[i-1])
            {
                nums[i]=nums[i-1]+1;
            }
        }
        sum=nums[len-1];
        for(int i=len-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1] && nums[i]<nums[i+1]+1)
            {
                nums[i]=nums[i+1]+1;
            }
            sum=sum+nums[i];
        }
        return sum;
    }
};

136 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

我的做法

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

按位异或
用到位运算之异或的特性：n ^ n = 0, 0 ^ x = x。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            res=res^nums[i];
        }
        return res;
    }
};

137 只出现一次的数字II（回到目录）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

我的做法

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

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int length = nums.size();
        int result = 0;
        for(int i = 0; i<32; i++){
            int count = 0; 
            int mask = 1<< i;
            for(int j=0; j<length; j++){
                if(nums[j] & mask)
                    count++;
            }
          if(count %3)
                result |= mask;
        }
        return result;
    }
};

141 环形链表（回到目录）

给定一个链表，判断链表中是否有环。

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution 
{
public:
    bool hasCycle(ListNode *head) 
    {
        set<ListNode*> node_set;
        while(head)
        {
            if(node_set.find(head)!=node_set.end())
            {
                return true;
            }
            node_set.insert(head);
            head=head->next;
        }
        return false;
    }
};

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution 
{
public:
    bool hasCycle(ListNode *head) 
    {
        if(head==NULL || head->next==NULL || head->next->next==NULL) return false;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast && fast->next)
        {
            fast=fast->next;
            slow=slow->next;
            fast=fast->next;
            if(fast==slow)
            {
                return true;
            }
        }
        return false;
    }
};

142 环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

说明：不允许修改给定的链表。

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:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* fast=head;
        ListNode* slow=head;
        ListNode* meet=NULL;
        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow)
            {
                meet=fast;
                break;
            }
        }
        if(meet==NULL)
        {
            return NULL;
        }
        while(head && meet)
        {
            if(head==meet)
            {
                return head;
            }
            head=head->next;
            meet=meet->next;
        }
        
        return NULL;
    }
};

144 二叉树的前序遍历

题目描述提示帮助提交记录社区讨论阅读解答
给定一个二叉树，返回它的 前序 遍历。

示例:

1
2
3
4
5
6
7
输入: [1,null,2,3]  
   1
    \
     2
    /
   3 
输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归方法

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<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        if(root==NULL) 
        {
            return res;
        }
        res.push_back(root->val);
        vector<int> temp1=preorderTraversal(root->left);
        for(int i=0;i<temp1.size();i++)
        {
            res.push_back(temp1[i]);
        }
        vector<int> temp2=preorderTraversal(root->right);
        for(int i=0;i<temp2.size();i++)
        {
            res.push_back(temp2[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
25
26
27
28
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        stack<TreeNode*> s;
        if(root==NULL) 
        {
            return res;
        }
        s.push(root);
        while(!s.empty())
        {
            TreeNode* temp=s.top();
            res.push_back(temp->val);
            s.pop();
            if(temp->right)
            {
                s.push(temp->right);
            }
            if(temp->left)
            {
                s.push(temp->left);
            }
        }
        return res;
    }
};

145 二叉树的后序遍历

递归方法
递归1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        postorder(root,res);
        return res;
    }
private:
    void postorder(TreeNode* root,vector<int> &res)
    {
        if(root==NULL)
        {
            return;
        }
        postorder(root->left,res);
        postorder(root->right,res);
        res.push_back(root->val);
    }
};

递归2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        if(root==NULL) return res;
        vector<int> temp1=postorderTraversal(root->left);
        for(int i=0;i<temp1.size();i++)
        {
            res.push_back(temp1[i]);
        }
        vector<int> temp2=postorderTraversal(root->right);
        for(int i=0;i<temp2.size();i++)
        {
            res.push_back(temp2[i]);
        }
        res.push_back(root->val);
        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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> res;
        if(root==NULL) return res;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode* temp=s.top();
            s.pop();
            res.push_back(temp->val);
            if(temp->left)
            {
                s.push(temp->left);
            }
            if(temp->right)
            {
                s.push(temp->right);
            }
        }
        //vector反转的两种方式
        //return vector<int>(res.rbegin(),res.rend());//vector反转方式1
        
        reverse(res.begin(),res.end());//vector反转方式2
        return res;
    }
};

160 求两个链表的交点。(回到目录)

已知链表A的头节点指针headA，链表B的头节点指针headB，两个链表相交，求两个链表交点对应的节点。

方法一：使用std中的set函数

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:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        std::set<ListNode*> node_set;
        while(headA)
        {
            node_set.insert(headA);
            headA=headA->next;
        }
        while(headB)
        {
            if(node_set.find(headB)!=node_set.end())
            {
                return headB;
            }
            headB=headB->next;
        }
        return NULL;
    }
    
};

方法二

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int lenA=compute_len(headA);
        int lenB=compute_len(headB);
        int t=0;
        if(lenB>lenA)
        {
            t=lenB-lenA;
            while(headB && t)
            {
                headB=headB->next;
                t--;
            }
            while(headA && headB)
            {
                if(headA==headB) return headA;
                headA=headA->next;
                headB=headB->next;
            }
        }
        else
        {
            t=lenA-lenB;
            while(headA && t)
            {
                headA=headA->next;
                t--;
            }
            while(headA && headB)
            {
                if(headA==headB) return headB;
                headA=headA->next;
                headB=headB->next;
            }
        }
        return NULL;
    }
private:
    int compute_len(ListNode* head)
    {
        int len=0;
        while(head)
        {
            len++;
            head=head->next;
        }
        return len;
    }
};

169 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

1
2
输入: [3,2,3]
输出: 3

示例 2:

1
2
输入: [2,2,1,1,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
class Solution {
public:
    int majorityElement(vector<int>& nums) 
    {
        map<int,int> hash_map;
        for(int i=0;i<nums.size();i++)
        {
            hash_map[nums[i]]++;
        }
        int temp=hash_map[nums[0]];
        int res=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(hash_map[nums[i]]>temp)
            {
                temp=hash_map[nums[i]];
                res=nums[i];
            }
        }
        return res;
    }
};

189 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5
6
7
8
9
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

我的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void rotate(vector<int>& nums, int k) 
    {
        int len=nums.size();
        for(int i=0;i<k;i++)
        {
            int temp=nums[len-1];
            for(int j=len-1;j>0;j--)
            {
                nums[j]=nums[j-1];
            }
            nums[0]=temp;
        }     
    }
};

191 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 :

1
2
3
输入: 11
输出: 3
解释: 整数 11 的二进制表示为 00000000000000000000000000001011

示例 2:

1
2
3
输入: 128
输出: 1
解释: 整数 128 的二进制表示为 00000000000000000000000010000000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hammingWeight(uint32_t n) 
    {
        int cnt=0;
        while(n)
        {
            if(n%2)
            {
                cnt++;
            }
            n=n/2;
        }
        return cnt;
    }
};

法2:位运算

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) 
    {
        int res=0;
        for(int i=0;i<32;i++)
        {
            if(n&(1<<i)) res++;
        }
        return res;
    }
};

199 二叉树的右视图（回到目录）

递归做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//递归做法
class Solution {
public:
    void preorder(TreeNode *root, int depth, vector<int> &res)
    {
        if(root==NULL) return ;
        if(res.size()<depth) res.push_back(root->val);
        preorder(root->right, depth+1, res);
        preorder(root->left, depth+1, res);
    }
    
    vector<int> rightSideView(TreeNode *root) {
        vector<int> res;
        preorder(root, 1, res);
        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
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        vector<int> view;
        queue<pair<TreeNode*,int> >Q;
        if(root)
        {
            Q.push(make_pair(root,0));
        }
        while(!Q.empty())
        {
            TreeNode *node=Q.front().first;
            int depth=Q.front().second;
            if(view.size()==depth)
            {
                view.push_back(node->val);
            }
            else
            {
                view[depth]=node->val;
            }
            Q.pop();
            if(node->left)
            {
                Q.push(make_pair(node->left,depth+1));
                
            }
            if(node->right)
            {
                Q.push(make_pair(node->right,depth+1));
            }
        }
        return view;
    }
};

206 反转链表（回到目录）

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* new_head=NULL;
        while(head)
        {
            ListNode* next=head->next;
            head->next=new_head;
            new_head=head;
            head=next;
        }
        return new_head;
        
    }
};

215 数组中的第k个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

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 findKthLargest(vector<int>& nums, int k) 
    {
        set<int,greater<int> >nums_set;
        for(int i=0;i<nums.size();i++)
        {
            nums_set.insert(nums[i]);
        }
        set<int> ::iterator it=nums_set.begin();
        if(nums_set.size()>=k)
        {
            k=k-1;
            while(k)
            {
                k--;
                it++;
            }
        }
        return *it;
        
    }
};

225 用队列实现栈

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
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> temp_queue;
        temp_queue.push(x);
        while(!data_queue.empty())
        {
            temp_queue.push(data_queue.front());
            data_queue.pop();
        }
        while(!temp_queue.empty())
        {
            data_queue.push(temp_queue.front());
            temp_queue.pop();
        }
        
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x=data_queue.front();
        data_queue.pop();
        return x;
    }
    
    /** Get the top element. */
    int top() {
        return data_queue.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return data_queue.empty();
    }
private:
    queue<int> data_queue;
};

226 翻转二叉树（回到目录）

使用递归方法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root==NULL) return NULL;
        TreeNode* temp=root->left;
        root->left=invertTree(root->right);
        root->right=invertTree(temp);
        return root;
    }
};

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Non-Recursion
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            TreeNode *tmp = node->left;
            node->left = node->right;
            node->right = tmp;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return root;
    }
};

258 各位相加（回到目录）

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

1
2
3
4
5
示例:
输入: 38
输出: 2

解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶:

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int addDigits(int num) 
    {
        if(num<10) return num;
        int sum=0;
        while(num)  
        {
            sum=num%10 +sum;
            num=num/10;
        }
        return addDigits(sum);
        
    }
};

循环方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int addDigits(int num) {
        int i,sum = 0;
        while(1)
        {
            while(num != 0)
            {
                sum += num%10;
                num /= 10;
            }
            if(sum >= 10)
            {
                num = sum;
                sum = 0;
            }
            else
                break;
        }
        return sum;
    }
};

295 数据流的中位数（回到目录）

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如:

1
2
3
4
5
6
7
8
9
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例：

1
2
3
4
5
6
7
8
9
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 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
45
46
47
48
49
50
51
52
class MedianFinder {
public:
    MedianFinder() {
    }
    void addNum(int num) {
    	if (big_queue.empty()){
	    	big_queue.push(num);
	    	return;
	    }
        if (big_queue.size() == small_queue.size()){
        	if (num < big_queue.top()){
	        	big_queue.push(num);
	        }
	        else{
        		small_queue.push(num);
        	}
        }
        else if(big_queue.size() > small_queue.size()){
        	if (num > big_queue.top()){
	        	small_queue.push(num);
	        }
	        else{
        		small_queue.push(big_queue.top());
        		big_queue.pop();
        		big_queue.push(num);
        	}
        }
        else if(big_queue.size() < small_queue.size()){
        	if (num < small_queue.top()){
	        	big_queue.push(num);
	        }
	        else{
        		big_queue.push(small_queue.top());
        		small_queue.pop();
        		small_queue.push(num);
        	}
        }
    }
    double findMedian(){
    	if (big_queue.size() == small_queue.size()){
        	return (big_queue.top() + small_queue.top()) / 2;
        }
        else if (big_queue.size() > small_queue.size()){
        	return big_queue.top();
        }
        return small_queue.top();
    }
private:
	//priority_queue<double> big_queue;//最大堆的两种定义方式
    priority_queue<double,vector<double>,less<double> > big_queue;//最大堆
	priority_queue<double, vector<double>, greater<double> > small_queue;//最小堆
};

315 计算右侧小于当前元素的个数（回到目录）

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

1
2
3
4
5
6
7
输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
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
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
class Solution
{
public:
   vector<int> countSmaller(vector<int> &nums)
   {
       vector<int> count;
       vector<pair<int,int> > vec;
       for(int i=0;i<nums.size();i++)
       {
           vec.push_back(make_pair(nums[i],i));
           count.push_back(0);
       }
       merge_sort(vec,count);
       return count;
   }
private:
    void merge_sort_two_vec(vector<pair<int,int> > &sub_vec1,vector<pair<int,int> > &sub_vec2,vector<pair<int,int> > &vec,vector<int> &count)
    {
        int i=0;
        int j=0;
        while(i<sub_vec1.size() && j<sub_vec2.size())
        {
            if(sub_vec1[i].first<=sub_vec2[j].first)
            {
                count[sub_vec1[i].second] +=j;
                vec.push_back(sub_vec1[i]);
                i++;
            }
            else
            {
                vec.push_back(sub_vec2[j]);
                j++;
            }
        }
        for(;i<sub_vec1.size();i++)
        {   
            count[sub_vec1[i].second] +=j;
            vec.push_back(sub_vec1[i]);
        }
        for(;j<sub_vec2.size();j++)
        {
            vec.push_back(sub_vec2[j]);
        }
    }
    void merge_sort(vector<pair<int,int> > &vec,vector<int> &count)
    {
        if(vec.size()<2)
        {
            return;
        }
        int mid=vec.size()/2;
        vector<pair<int,int> > sub_vec1;
        vector<pair<int,int> > sub_vec2;
        for(int i=0;i<mid;i++)
        {
            sub_vec1.push_back(vec[i]);
        }
        for(int i=mid;i<vec.size();i++)
        {
            sub_vec2.push_back(vec[i]);
        }
        merge_sort(sub_vec1,count);
        merge_sort(sub_vec2,count);
        vec.clear();
        merge_sort_two_vec(sub_vec1,sub_vec2,vec,count);
    }
};

389 找不同

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

1
2
3
4
5
6
7
输入：
s = "abcd"
t = "abcde"
输出：
e
解释：
'e' 是那个被添加的字母。

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:
    char findTheDifference(string s, string t) 
    {
        map<char,int> hash_map;
        char res;
        for(int i=0;i<t.size();i++)
        {
            hash_map[t[i]]++;
        }
        for(int i=0;i<s.size();i++)
        {
            hash_map[s[i]]--;
        }
        for(int i=0;i<t.size();i++)
        {
            if(hash_map[t[i]]==1)
            {
                res=t[i];
                break;
            }
        }
        return res;
    }
};

402 移掉k个数字（回到目录）

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 1 :

1
2
3
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

1
2
3
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

1
2
3
输入: num = "10", k = 2
输出: "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
33
34
35
class Solution {
public:
    string removeKdigits(string num, int k) 
    {
        vector<int> S;
        string result="";
        for(int i=0;i<num.length();i++)
        {
            int number=num[i]-'0';
            while(S.size()!=0 && k>0 && S[S.size()-1]>number)
            {
                S.pop_back();
                k--;
            }
            if(number !=0 || S.size()!=0)
            {
                S.push_back(number);
            }
        }
            while(k>0 && S.size()!=0)
            {
                S.pop_back();
                k--;
            }
            for(int i=0;i<S.size();i++)
            {
                result.append(1,'0'+S[i]);
            }
            if(result=="")
            {
                result="0";
            }
        return result;
    }
};

414 第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
示例 1:
输入: [3, 2, 1]
输出: 1
解释: 第三大的数是 1.
示例 2:
输入: [1, 2]
输出: 2
解释: 第三大的数不存在, 所以返回最大的数 2 .
示例 3:
输入: [2, 2, 3, 1]
输出: 1
解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int thirdMax(vector<int>& nums) 
    {
        set<int,greater<int> >nums_set;//从大到小排序
        for(int i=0;i<nums.size();i++)
        {
            nums_set.insert(nums[i]);
        }
        set<int> ::iterator it=nums_set.begin();
        if(nums_set.size()>=3)
        {
            int k=2;
            while(k)
            {
                k--;
                it++;
            }
        }
        return *it;
    }
};

520 检测大写字母（回到目录）

给定一个单词，你需要判断单词的大写使用是否正确。

我们定义，在以下情况时，单词的大写用法是正确的：

全部字母都是大写，比如”USA”。
单词中所有字母都不是大写，比如”leetcode”。
如果单词不只含有一个字母，只有首字母大写， 比如 “Google”。
否则，我们定义这个单词没有正确使用大写字母。

1
2
3
4
5
6
7
8
9
示例 1:
输入: "USA"
输出: True
示例 2:
输入: "FlaG"
输出: False

注意: 输入是由大写和小写拉丁字母组成的非空单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool detectCapitalUse(string word) 
    {
        int len=word.size();
        if(len==1) return true;
        int cnt=0;
        for(int i=0;i<len;i++)
        {
            if(word[i]<='Z' && word[i]>='A')
            {
                cnt++;
            }
        }
        if((cnt==1 && word[0]<='Z' && word[0]>='A') || cnt==len || cnt==0)
        {
            return true;
        }
        return false;
    }
};

633 平方数之和

给定一个非负整数c,你要判断是否存在两个整数a和b，使得$a^{2}+b^{2}=c$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
 
示例2:
输入: 3
输出: False

我的做法如下：

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:
    bool judgeSquareSum(int c) 
    {
        int a=0,b=sqrt(c);
        while(a<=b)
        {
            if(a*a+b*b>c)
            {
                b--;
            }
            else if(a*a+b*b<c)
            {
                a++;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

下面这种方法用到了集合set，从0遍历到c的平方根，对于每个i*i，都加入集合set中，然后计算c-i*i，如果这个差值也在集合set中，返回true，遍历结束返回false，参见代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool judgeSquareSum(int c) {
        unordered_set<int> s;
        for (int i = 0; i <= sqrt(c); ++i) {
            s.insert(i * i);
            if (s.count(c - i * i)) return true;
        }
        return false;
    }
};

784 字母大小写全排列（回到目录）

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例:
输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]
输入: S = "3z4"
输出: ["3z4", "3Z4"]
输入: S = "12345"
输出: ["12345"]
**注意**：
S 的长度不超过12。
S 仅由数字和字母组成。

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
char chang_upOrLow(char s)//递归
    {
        char res;
        if(s>='A' && s<='Z')
        {
            res=s+32;
        }
        if(s>='a' && s<='z')
        {
            res=s-32;
        }
        return res;
    }
void generate(string &S,vector<string> &res,int index)
{
    if(index>=S.size())
    {
        res.push_back(S);
        return;
    }
    if((S[index]>='a' && S[index]<='z') ||(S[index]>='A' && S[index]<='Z')) 
    //if(S[index]>='A' && S[index]<='z')
    {
        S[index]=chang_upOrLow(S[index]);
        generate(S,res,index+1);
        S[index]=chang_upOrLow(S[index]);
    }
        generate(S,res,index+1);
    
}
class Solution {
public:
    vector<string> letterCasePermutation(string S) 
    {
        vector<string> res;
        generate(S,res,0);
        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
char chang_upOrLow(char s)
    {
        char res;
        if(s>='A' && s<='Z')
        {
            res=s+32;
        }
        if(s>='a' && s<='z')
        {
            res=s-32;
        }
        return res;
    }
void generate(string &S,vector<string> &res,int index)
{
    if(index>=S.size())
    {
        res.push_back(S);
        return;
    }
    if((S[index]>='a' && S[index]<='z') ||(S[index]>='A' && S[index]<='Z')) 
    //if(S[index]>='A' && S[index]<='z')
    {
        S[index]=chang_upOrLow(S[index]);
        generate(S,res,index+1);
        S[index]=chang_upOrLow(S[index]);
        generate(S,res,index+1);
    }
    else
    {
        generate(S,res,index+1);
    }
}
class Solution {
public:
    vector<string> letterCasePermutation(string S) 
    {
        vector<string> res;
        generate(S,res,0);
        return res;
    }
};

-------------本文结束感谢您的阅读-------------
您的小小鼓励，是我不断更新的强大动力！