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 searchInsert(vector<int>& nums, int target) {
		int left=0;
        int right=nums.size()-1;
        int m=0;
        while(left<=right)
        {
            m=(left+right)/2;
            if(nums[m]==target)
                return m;
            else if(nums[m]>target)
                right=m-1;
            else
                left=m+1;
        }
        //当left>right时，说明数组中没有目标元素，返回left的值为插入位置
        return left;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        //二分查找，找第一个true
        long left=1,right=n,mid;
        //当left>right时返回left
        while(left<=right)
        {
            //取中间值
            mid=(left+right)/2;
            //当为true时，将搜索区间缩小为左半部分
            if(isBadVersion(mid)==true)
            right=mid-1;
            //当为false时，搜索区间缩小为右半部分
            else
            left=mid+1;
        }
        return left;
    }
};

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 pivotIndex(vector<int>& nums) {
        int sum=0;
        int leftsum=0;

        //计算数组总和
        for(int i:nums)
            sum+=i;
        
        for(int i=0;i<nums.size();i++)
        {
            //寻找中心索引，左边部分和等于右边部分和，满足nums[i]==sum-2*leftsum
            if(nums[i]==sum-2*leftsum)
                return i;//满足条件的话返回中心索引
            leftsum+=nums[i];//不满足的话就继续累加
        }
        return -1;
    }
};

1
2
3
4
for (int i = 0; i < nums.length; i++) {
      presum[i+1] = nums[i] + presum[i];
 }

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
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        vector<vector<int>> result;
        
        //冒泡排序，时间超出限制，不用
        /*int m=size;//intervals的长度
        int flag=1;
        vector<int> temp;
        //先对intervals中的区间按左边界进行排序
        while((m>0)&&(flag==1))
        {
            flag=0;
            //冒泡排序(太慢了)
            for(int i=0;i<m-1;i++)//这里要注意边界范围，不能是m，因为后面会索引到i+1这个位置，会超出范围，导致溢出
            {
                if(intervals[i][0]>intervals[i+1][0])
                {
                    flag=1;
                    temp=intervals[i];
                    intervals[i]=intervals[i+1];
                    intervals[i+1]=temp;
                }
            }
            --m;
        }*/
        
        //排序
        sort(intervals.begin(),intervals.end());
        result.push_back(intervals[0]);
        for(int j=1;j<intervals.size();j++)
        {
            if(intervals[j][0]<=result.back()[1])//当前区间左边界小于result中最后一个区间的右边界
            //更新result中的区间
                result.back()[1]=max(result.back()[1],intervals[j][1]);
            else
                result.push_back(intervals[j]);
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int size=matrix.size();
        int temp=0;
        //以主对角线为对称轴交换元素
        for(int i=0;i<size;i++)
        {
            for(int j=0;j<=i;j++)//对j，循环条件注意是小于i，因为只需对一边做交换
            {
                if(i==j)
                {
                    continue;
                }
                temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }
        //沿竖直对称轴镜像交换元素
       for(int i=0;i<size;i++)//循环条件注意是小于号
       {
           for(int j=0;j<size/2;j++)//循环条件注意是小于矩阵列数的二分之一，列数为奇数时，中间列不做交换，只需要做一边的交换就好了
           {
                temp=matrix[i][size-1-j];
                matrix[i][size-1-j]=matrix[i][j];
                matrix[i][j]=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
32
33
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int r=matrix.size();//行数
        int c=matrix[0].size();//列数
        vector<bool> r_ind(r,0);
        vector<bool> c_ind(c,0);
        
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(matrix[i][j]==0)
                {
                    r_ind[i]=1;
                    c_ind[j]=1;
                }
            }
        }
        
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(r_ind[i]||c_ind[j])
                {
                    matrix[i][j]=0;
                }
            }
        }
    }
};

1
2
3
4
5
第一趟：1 的坐标(0, 0)。x + y == 0。
第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1。
第三趟：7 的坐标(0, 2), 5 的坐标(1, 1)，3 的坐标(2, 0)。第三趟 x + y == 2。
第四趟：……

1
2
3
第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x 每次-1，y 每次+1。
第三趟：7 的坐标(0, 2), 5 的坐标(1, 1)，3 的坐标(2, 0)。x 每次 +1，y 每次 -1。

1
2
3
第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1，x 初始值取 1，y 取 0。
第四趟：6 的坐标(2, 1)，8 的坐标(1, 2)。x + y == 3，x 初始值取 2，剩下的加到 y上，y 取 1。

1
2
3
第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x 减到 0 为止。
第四趟：6 的坐标(2, 1)，8 的坐标(1, 2)。x 虽然才减到 1，但是 y 已经加到上限了。

1
2
3
x 从大到小，第二趟：2 的坐标(1, 0)，4 的坐标(0, 1)。x + y == 1，x 初始值取 1，y 取 0。结束值 x 减到 0 为止。
x 从小到大，第三趟：7 的坐标(0, 2)，5 的坐标(1, 1)，3 的坐标(2, 0)。x + y == 2，y 初始值取 2，x 取 0。结束值 y 减到 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
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) 
{
	vector<int> nums;			//存储结果
	int m = matrix.size();		//行数
	if (m == 0) return nums;	
	int n = matrix[0].size();	//列数
	if (n == 0) return nums;
    
	//将往右上和往左下的代码合在一起，用一个标记值标记
	bool bXFlag = true;			//1代表右上
    
	for (int i = 0; i < m + n; i++)//i为每趟中x和y的和
	{
		int pm = bXFlag ? m : n;//pm为x的上限
		int pn = bXFlag ? n : m;//y的上限是列数
		
        //确定初始值，x尽量取到最大
		int x = (i < pm) ? i : pm - 1;
        //剩下的给y
		int y = i - x;                
		
        //开始对角线遍历，将元素存到数组
		while (x >= 0 && y < pn)
		{
            //往左下遍历，横坐标从大到小（——），纵坐标从小到大（++）
            //往右上遍历，相反
			nums.push_back(bXFlag ? matrix[x][y] : matrix[y][x]);
			x--;
			y++;
		}

		bXFlag = !bXFlag;
	}
	return nums;
}

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>> generate(int numRows) {
        vector<vector<int>> result(numRows);
        if(numRows==0)
        return result;
        for(int i=0;i<numRows;i++)
        {
            //resize()既分配空间，也创建对象
            result[i].resize(i+1);
            //每行第一个和最后一个元素为1
            result[i][0]=result[i][i]=1;
            for(int j=1;j<i;j++)
            {
            	//对中间的数进行赋值，利用上一行的结果
                result[i][j]=result[i-1][j]+result[i-1][j-1];
            }
        }
        return result;
    }
};

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> getRow(int rowIndex) {
        //构建结果数组，大小为rowIndex+1，初始值都为0
        vector<int>result(rowIndex+1);
        result[0]=1;
        for(int i=1;i<=rowIndex;i++)
        {
            //i代表对每一行进行计算，每一行都是根据上一行的计算结果来的
            //只在一个数组里修改元素，不用另外创建
            //所以要从后往前加
            for(int j=i;j>0;j--)
            {
                result[j]=result[j]+result[j-1];
            }
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        //方法二，将后面k个元素依次插入数组前部，然后删掉，还是很慢
        int tmp;
        for(int i=0;i<k;i++)
        {
            tmp=nums.back();
            nums.pop_back();
            nums.insert(nums.begin(),tmp);
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void rotate(vector<int>& nums, int k) 
	{
        //官方题解三，这个方法好妙
        //先整体全部翻转，然后再在前半段和后半段内部翻转
        //k大于size时取余，因为移动size步相当于没有移
        k=k%nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size()<2)
            return false;
        unordered_set<int> numset;
        for(int i:nums)
        {
            if(numset.find(i)!=numset.end())
                return true;
            numset.insert(i);
        }
        return false;
    }
};

1
2
3
4
x XOR x=0
x XOR 0=x
交换律： x XOR y XOR x=x XOR x XOR y

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

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<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int>result;
        //双指针解法
        int i=0,j=0;
        //先排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        while(i<nums1.size()&&j<nums2.size())
        {
            if(nums1[i]==nums2[j])
            {
                result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if(nums1[i]<nums2[j])
                i++;
            else
                j++;
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            //这里很妙，通过再调用自己来避免写重复代码
            return intersect(nums2, nums1);
        }
        //哈希表
        unordered_map <int, int> m;
        //遍历较短的数组，将元素加到哈希表，元素值作为键，出现次数作为值
        for (int num : nums1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {
            //当存在相同元素，就将该数加到结果数组，然后哈希表中的次数减1
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                //当减为0时，表中删掉这个元素
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        //考虑进位
       for(int i=digits.size()-1;i>=0;i--)
       {
           if(digits[i]+1<10)
            {
                digits[i]++;
                return digits;
            }
            digits[i]=0;
       }
        digits.insert(digits.begin(),1);
        return digits;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>pair;
        for(int i=0;i<nums.size();i++)
        {
            auto itr=pair.find(target-nums[i]);
            if(itr!=pair.end())
                //无需另外创建数组，可直接将结果返回
                return {itr->second,i};
            else
                //没有匹配的数，就将当前数插入哈希表，键为元素值，值为下标
                pair[nums[i]]=i;
        }
        //如果没有答案，则返回空
        return {};
    }
};

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 reverse(int x) {
        int rev = 0;
        while (x != 0) {
            //从低位取数字，类似出栈
            int pop = x % 10;
            x /= 10;
            //溢出判断
            //int的范围：-2147483648 ~ +2147483647
            //如果rev*10+pop导致溢出，那么一定有rev*10+pop > INT_MAX，即有rev >= INT_MAX/10
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            //将低位数字放到前面，相当于压入栈
            //下面这个类似入栈的操作挺妙的
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //先将nums2放到nums1后面然后再排序？
        //复制
        copy(nums2.begin(),nums2.end(),nums1.begin()+m);
        //排序
        sort(nums1.begin(),nums1.end());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            //nums1遍历完了
            //将p2剩下的部分放在前面
            if (p1 == -1) {
                cur = nums2[p2--];
            } 
            //nums2遍历完了
            else if (p2 == -1) {
                cur = nums1[p1--];
            }
            //将较大的元素先放入
            else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } 
            else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public:
    int findRepeatNumber(vector<int>& nums) {
        //遍历数组元素，如果哈希表中没有这个数，就将其放入哈希表
        //如果有，就返回这个数
        unordered_set<int>S;
        for(int i:nums)
        {
            auto find_s=S.find(i);
            if(find_s!=S.end())
            return i;
            else
            S.insert(i);
        }
        return 0;
    }

1
2
3
4
5
6
7
8
9
10
11
int findRepeatNumber(vector<int>& nums) {
        //排序，然后挨个看有没有重复的
        sort(nums.begin(),nums.end());
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i-1]==nums[i])
            return nums[i];
        }
        return 0;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findRepeatNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i])
                return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(!strs.size())
        return "";
        
        string result="";
        string a=strs[0];
        int flag=1;
        
        for(int i=0;i<a.length();i++)
        {
            for(int j=1;j<strs.size();j++)
            {
                if(a[i]!=strs[j][i])
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            result+=a[i];
        }
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {

private:

    bool valid(string s, int left, int right) {
        // 验证子串 s[left, right] 是否为回文串
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

public:


    string longestPalindrome(string s) {
        // 特判
        int size = s.size();
        if (size < 2) {
            return s;
        }

        int maxLen = 1;
        string res = s.substr(0, 1);

        // 枚举所有长度大于等于 2 的子串
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                //valid(s, i, j)判断是否是回文串
                //j - i + 1 > maxLen判断该回文串是否是目前找到的最长的
                if (j - i + 1 > maxLen && valid(s, i, j)) {
                    maxLen = j - i + 1;
                    res = s.substr(i, maxLen);
                }
            }
        }
        return res;
    }
};

1
2
3
4
情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i+1] [j-1]是否为true。

1
2
3
4
5
6
7
8
if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        dp[i][j] = true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string longestPalindrome(string s) {
        //创建并初始化dp数组
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        //记录最长回文串的长度和起始位置就好，最后返回在原字符串上截取的子串
        int maxlenth = 0;
        int left = 0;
        int right = 0;
        //填表
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        dp[i][j] = true;
                    }
                }
                //查找最长（maxlengh最大）回文串（dp[i][j]为ture
                if (dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1;
                    left = i;
                    right = j;
                }
            }

        }
        return s.substr(left, right - left + 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
class Solution {
public:
    
    int left = 0;
    int right = 0;
    int maxLength = 0;
    
    string longestPalindrome(string s) {
        int result = 0;
        //遍历可能的中心点，向两边扩散看是否存在回文数
        for (int i = 0; i < s.size(); i++) {
            extend(s, i, i, s.size()); // 以i为中心
            extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        //截取子串
        return s.substr(left, maxLength);
    }
    
    //定义中心扩散的函数，作用在给定字符串和中心位置的情况下，从中心位置开始向外扩散，找到最长回文串的左右边界
    void extend(const string& s, int i, int j, int n) {
        // 中心点两边的元素要满足条件s[i] == s[j]
        //左边界扩散的极限是0，有便捷的极限是n-1
        while (i >= 0 && j < n && s[i] == s[j]) {
            if (j - i + 1 > maxLength) {
                left = i;
                right = j;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int firstUniqChar(string s) {
        //利用哈希表，先将字符串整个存入表中
        //键为字符，值为出现次数
        unordered_map<char,int>str;
        for(int i=0;i<s.length();i++)
            ++str[s[i]];
        for(int j=0;j<s.length();j++)
        {
            auto itr=str.find(s[j]);
            //当在哈希表中找到当前字符，并且出现次数为1，即为答案
            if(itr!=str.end()&&itr->second==1)
                return j;
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int myAtoi(string s) {
        bool symbol=true;
        int i=0;
        int num=0;
        //读入字符
        //舍弃前面的空格
        while(s[i]==' ') i++;
        //检查是否有负号，只需要读取一个符号，后面再出现将作为非数字字符处理，没有符号就默认为正号。
        //确定最终结果为正数还是负数
        if(s[i]=='-') 
        {
            symbol=false;
            i++;
        }
        //遇到正号就将指针往后挪一位
        else if(s[i]=='+') i++;
        //读入数字，直到到达末尾，或者遇到非数字字符
        while(i<s.size()&&isdigit(s[i]))
        {
            //溢出判断
            //上边界
            if(symbol && (num>INT_MAX/10 ||(num==INT_MAX/10 && (s[i]-'0'>6)))) 
                return INT_MAX;
            //下边界
            if(!symbol && (num>INT_MAX/10 ||(num==INT_MAX/10 && (s[i]-'0'>7)))) 
                return INT_MIN;
            //后面那个s[i]-'0'是将数字字符转化成了s[i]对应的整数
            num=num*10+(s[i]-'0');
            i++;
        }
        if(symbol) //正
            return num;
        else 	   //负
            return -num;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

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:
    string countAndSay(int n) {
        //当减到n为1时，触发递归退出的条件，返回“1”，返回给tmp变量
        //然后再利用tmp字符串逐层求出上层项的描述字符串
        if(n==1)
            return "1";

        //每次调用返回的字符串
        string result;
        //应用递归，向下求出底层项的描述字符串
        string tmp=countAndSay(n-1);

        //i是遍历指针
        //c用于计数，记录每个组中连续的最多相同字符数
        int c=1;
        for(int i=0;i<tmp.length();i++)
        {
            //相邻字符相同时计数器加1
            if(tmp[i]==tmp[i+1])
                c++;
            //不同时i指向的是最后一个，比如“3322251”，第一次不同时，i指向第二个3
            else
            {
                result+=to_string(c)+tmp[i];
                //重置计数器
                c=1;
            }
        }
        //返回每次调用产生的字符串
        return result;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //双指针，活动窗口
        //左右指针指向滑动窗口的左右边界
        //用一个哈希表来判断是否有重复字符
        unordered_set<char>set;
        int i=0,rk=0,res=0;
        while(i<s.size())
        {
            for(;rk<s.size();rk++)
            {
                if(!set.count(s[rk]))
                {
                    set.emplace(s[rk]);
                }
                else
                break;
            }
            int n=set.size();
            res=max(n,res);
            //左边界向右移动时，从哈希表中移除相应字符
            set.erase(s[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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        vector<int> cnt1(26), cnt2(26);
        //s1中字符出现次数，s2初始窗口中字符出现次数
        for (int i = 0; i < n; ++i) {
            ++cnt1[s1[i] - 'a'];
            ++cnt2[s2[i] - 'a'];
        }
        if (cnt1 == cnt2) {
            return true;
        }
        //i为滑动窗口右边界，是新进入窗口的字符，i-n是窗口左边界，是要从窗口中移除的字符
        for (int i = n; i < m; ++i) {
            ++cnt2[s2[i] - 'a'];
            --cnt2[s2[i - n] - 'a'];
            //每次移动窗口都比较两个哈希表是否相等
            if (cnt1 == cnt2) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;//利用新索引idx直接在原字符串上进行修改，以及作为找到的每个单词的末端索引
        
        for (int start = 0; start < n; ++start) {
        	//只有s[start]为非空格时才开始执行，这样就能避开前面的空格
            if (s[start] != ' ') {
            
                // 第一次进入if时，还没有读到过单词，idx为0，此时不用在前面补空格
                  //之后再进入if的时候，已经读到了一个完整单词，单词后面应该有一个空格，此时idx处填一个空白字符，然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';//单词之间的空格
                // 从非空格字符s[start]开始，循环遍历至单词的末尾
                int end = start;
                
                while (end < n && s[end] != ' ') 
                //这里是在找字符串中属于单词的部分，当s[end]为空格时暂停遍历，一轮遍历得到的是一个完整单词
                //将end遍历到的每个字符以idx存储
                s[idx++] = s[end++];
				//以上工作相当于将原字符串前后两端以及中间多余的空格舍去后重新保存，并且使用的是原字符串空间，没有另创空间。
				
                // 反转整个单词
                //reverse函数用于反转在[first,last)范围内的顺序
                //（包括first指向的元素，不包括last指向的元素），reverse函数无返回值
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词，此时的s[end]是空格
                //进行下一轮的时候同样，会先避开下一个单词之前的空格，只有s[start]非空格时才会进入if，开始遍历单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return 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
class Solution {
public:
    string reverseWords(string s) {
        if(s.length()==0)
            return s;
        int i=0,j=0;
        while(j<s.length())
        {
            if(s[j]!=' ')
            {
                j++;
            }
            else if(s[j]==' ')
            {
                reverse(s.begin()+i,s.begin()+j);
                i=j+1;
                j++;
            }
        }
    	//跳出循环时，最后一个单词还没有翻转，需要再做一次
        reverse(s.begin()+i,s.end());
        return 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
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int>answer;
        int i=0,j=numbers.size()-1;
        int tolt=0;
        while(i<j)
        {
            tolt=numbers[i]+numbers[j];
            if(tolt==target)
            {
                answer.push_back(i+1);
                answer.push_back(j+1);
                break;
            }
            else if(tolt>target)
            {
                j--;
            }
            else
            {
                i++;
            }
        }
        return answer;
    }
};

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 minSubArrayLen(int target, vector<int>& nums) {
        int i=0,j=0,sum=0,n=INT_MAX;
        while(j<nums.size())
        {
        	//元素和
            sum+=nums[j];
            while(sum>=target)
            {
            	//n始终取较小的那个
                n=min(n,j-i+1);
                //减去左边元素，看是否还大于target
                sum-=nums[i];
                i++;
            }
            j++;
        }
        //当数组中不存在满足条件的子串，返回0
        return n==INT_MAX?0:n;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
   int findMin(vector<int>& nums) {
       //利用双指针，找到梯度位置
       if(nums.size()==1)
           return nums[0];
       int left=0,right=nums.size()-1;
       if(nums[left]<nums[right])
           return nums[left];
       while(nums[right]<nums[left]&&nums[right]>nums[right-1]&&nums[left]<nums[left+1])
       {
           left++;
           right--;
       }
       return min(nums[left+1],nums[right]);
   }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //利用快慢双指针
        if(nums.size()==0)
            return 0;
        int i=0,j=1;
        while(j<nums.size())
        {
            if(nums[j]==nums[i])
                j++;
            else
                nums[++i]=nums[j++];
        }
        return i+1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //利用双指针，i来指向正确的数组，j来遍历
        int i=0,j=0;
        //将非零元素放到前面
        while(j<nums.size())
        {
            if(nums[j]==0)
                j++;
            else
                nums[i++]=nums[j++];
        }
        //将i之后的元素全部置为0
        while(i<nums.size())
        {
            nums[i++]=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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //利用双指针
        if(prices.size()==1)
            return 0;
        int i=0,j=0,sum=0;
        while(j<prices.size()-1)
        {
            //从当前位置找第一个最小值，找应该买入股票时的低价
            while((j<prices.size()-1)&&(prices[j]>=prices[j+1]))
                j++;
            //遇到前一个小于后一个时退出，此时找到一个局部最低点
            i=j;
            //从j当前位置开始找局部最高点，找到应该卖出股票的时候
            if(j!=prices.size()-1)
            {
                while((j<prices.size()-1)&&(prices[j]<prices[j+1]))
                    j++;
            }
            sum+=prices[j]-prices[i];
        }
        return sum;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {   
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isPalindrome(string s) {
        //利用双指针
        int i=0,j=s.length()-1;
        while(i<j)
        {
            //左指针跳过除字母的部分
            while(i<j&&!isalnum(s[i])) 
            {
                i++;
            }
            //右指针跳过除字母的部分
            while(i<j&&!isalnum(s[j])) 
            {
                j--;
            }
            //当左右两个字母相同时，两指针同时向中间移，不相同的话返回false
            if(tolower(s[i])==tolower(s[j]))
            {
                i++;
                j--;
            }
            else
                return false;
            
        }
        //当左右指针相遇还没有返回false 时，说明字符串是回文串，返回true
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int result;
        //先排个序，然后遍历的时候看哪个地方的差不为1
        sort(nums.begin(),nums.end());
        for(int i=1;i<n;i++)
        {
            if((nums[i]-nums[i-1])!=1)
            result=(nums[i]+nums[i-1])/2;
        }
        if(nums[n-1]!=n)
        return n;
        if(nums[0]!=0)
        return 0;
        return result;
    }
};