JySama
0%

刷刷力扣

发表于 更新于
本文字数： 17k 阅读时长 ≈ 15 分钟

day1

数组中重复数字

很简单的一道题，用哈希映射可以做出来，需要额外空间，另一种解法比较难想，是“原地交换”的方法。

1
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
1
2
3
4
5
示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：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
24
25
26
27
//原地交换
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        int i=0;
        while(i<n)
        {
            if(nums[i]==i)
                {
                i++;
                continue;
                }
            if(nums[nums[i]]==nums[i])
                return nums[i];
            swap(nums[nums[i]],nums[i]);
        }
        
        
        return -1;

    }
};
/*
执行用时：24 ms, 在所有 C++ 提交中击败了96.40%的用户
内存消耗：22.4 MB, 在所有 C++ 提交中击败了66.33%的用户
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//映射
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        const int n = nums.size();
        int array[n];//哈希表
        for(int i=0;i<n;i++)
            array[i]=-1;//初始化
        for(int i=0;i<n;i++)
            if(array[nums[i]]==-1)
                array[nums[i]]=1;//标记
            else
                return nums[i];
        return -1;
    }
};
/*
执行用时: 32 ms
内存消耗: 22.9 MB
*/

二维数组中的查找

蛮简单的，但是有些细节需要注意。从左下角看上去就类似是一个二叉搜索树。按照这个性质，从左下角开始比较，目标元素小就往上找，大就往右找，每次都能消去一行。

1
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //注意，必须先判断大小即数组合不合法，因为如果n=0.说明是空数组，这样取m就是错误的了，因为根本没有matrix[0]这个元素
        int n = matrix.size();
        if(n<=0) return false;
        int m = matrix[0].size();
        if(m<=0) return false;
        //查找
        int i=n-1,j=0;
        while(i>=0&&j<=m-1)
        {
            if(target==matrix[i][j])
                return true;
            else if(target<matrix[i][j])
                i--;
            else
                j++;
            
        }
        return false;
    }
};
/*
执行用时：20 ms, 在所有 C++ 提交中击败了79.82%的用户
内存消耗：12.7 MB, 在所有 C++ 提交中击败了51.61%的用户
*/

//实际上上面的if判断有冗余，可以利用bool表达式的形式来简化代码
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int i=n-1,j=0;
        while(i>=0 && j<matrix[0].size())//一旦i<0说明n<=0，此时已经是false，不会判断后面的j，也就不会取matrix[0]
            				//这样一个n的if在while里判断了，一个m的if省略掉了
            				//不能写成j<=matrix[0].size()-1，不造为啥，力扣编译器的问题？
        {
            if(target==matrix[i][j])
                return true;
            else if(target<matrix[i][j])
                i--;
            else
                j++;
            
        }
        return false;
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了97.12%的用户
内存消耗：12.8 MB, 在所有 C++ 提交中击败了5.28%的用户
*/

替换空格

这题主要是对string要有了解。首先需要一个更长的sting，这是我们替换字符（字符数变多）的前提。string可以原地腾出空间，即用resize弄出空位，这给了一个不用额外多一个辅助空间的条件。

所以首先要算出长度，即先遍历一遍sting看空格数，然后resize。

接着重点是，两个指针从尾向前遍历、替换。正是因为从后往前才不会影响到原有的元素（对尾部操作是由于尾部都是空的）。并且从后往前，当两个指针位置相等时就可以停止，因为不可能再替换。

1
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
1
2
3
4
示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."
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 replaceSpace(string s) {
        int count = 0, len = s.size();
        //计数
        for(int i=0;i<len;i++)
            if(s[i]==' ')
                count++;
        //变换大小，变换后是替换后的大小，尾部那些是空位
        s.resize(len+count*2);
		
        //从两个尾部开始，一个是原先的尾部，一个是现在的尾部
        int i = len-1, j = len+count*2-1;
        while(i<j)
        {
            if(s[i]!=' ')//不用换
            {
                s[j]=s[i];
                i--;
                j--;//减了刚好进行下一个if判断
            }
            if(s[i]==' ')//要替换
            {
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=3;
                i--;
            }
        }
        return s;
    }
};

/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了83.37%的用户
*/

day2

从尾到头打印链表

因为是从尾到头，有种先进后出的意思，那么可以用一个辅助栈来存储。如果不允许额外的空间，则可以先反转链表，再顺序取出。

1
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
1
2
3
4
示例 1：

输入：head = [1,3,2]
输出：[2,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
62
63
64
65
66
67
68
//辅助栈
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> vec;
        stack<int> s;
        ListNode* cur = head;
        while(cur)
        {
            s.push(cur->val);
            cur=cur->next;
        }
        while(!s.empty())
        {
            vec.push_back(s.top());
            s.pop();
        }
        return vec;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了73.73%的用户
内存消耗：8.6 MB, 在所有 C++ 提交中击败了35.04%的用户
*/

//反转链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> vec;
        
        ListNode* cur = head;//当前指针
        ListNode* pre = nullptr;//前向指针，注意head的next变为NULL，故pre初始化为nullptr
        while(cur)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        while(pre)
        {
            vec.push_back(pre->val);
            pre = pre->next;
        }
        return vec;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了73.73%的用户
内存消耗：8.3 MB, 在所有 C++ 提交中击败了93.13%的用户
*/

用两个栈实现队列

将栈分为一个主栈一个辅助栈，这样就能将插入和删除更具有目的性，因此插入就很简单，直接push主栈里，而不去考虑位置，这个问题留到删除来解决。

对于删除，主要是要删头部也就是第一个进来的，但在栈中它位于底部。因此要把主栈元素都倒出来，放辅助栈里，这样辅助栈就是一个按顺序的队列。因此：如果辅助栈不是空的，说明它被倒进来了，顶部元素就是第一个元素，删掉它；如果辅助栈是空的，则元素都在主栈里，如果主栈是空的，返回-1；如果主栈不是空的，就需要把元素倒出来给辅助栈，然后删顶部元素。

1
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
1
2
3
4
5
6
示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
1
2
3
4
5
6
示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class CQueue {
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        smain.push(value);
    }
    
    int deleteHead() {
        if(!shelp.empty()) 
        {
            int x=shelp.top();
            shelp.pop();
            return x;
        }
        if(smain.empty())
            return -1;

        while(!smain.empty())
        {
            shelp.push(smain.top());
            smain.pop();
        }
        int x = shelp.top();
        shelp.pop();
        return x;
    }
private:
    stack<int> smain;//主栈
    stack<int> shelp;//辅助栈
};
/*
执行用时：248 ms, 在所有 C++ 提交中击败了76.96%的用户
内存消耗：101 MB, 在所有 C++ 提交中击败了72.52%的用户
*/

day3

斐波那契数列

简单的动态规划，注意要在运算过程中取模，不然会越界。

1
2
3
4
5
6
7
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
1
2
3
4
5
6
7
8
示例 1：

输入：n = 2
输出：1
示例 2：

输入：n = 5
输出：5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        int max = 1000000007;
        int a=1,b=0;//从f1和f0开始
        while(--n)
        {
            int tmp = (a+b)%max;//tmp相当于fn
            b=a;//fn-2向前变成fn-1
            a=tmp;//fn-1向前变成fn
        }
        return a;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了86.1%的用户
*/

青蛙跳台阶问题

一次跳1或2，则到第n个台阶为从n-1或从n-2；因此f(n)=f(n-1)+f(n-2)，本质也是斐波那契问题，用动态规划。不同的是初值不同，f(0)=f(1)=1。

1
2
3
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
1
2
3
4
5
6
7
8
9
10
11
12
示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numWays(int n) {
        if(n==0) return 1;
        if(n<=2) return n;
        int max = 1000000007;
        int a=1,b=1;//从f1和f0开始
        while(--n)
        {
            int tmp = (a+b)%max;//tmp相当于fn
            b=a;//fn-2向前变成fn-1
            a=tmp;//fn-1向前变成fn
        }
        return a;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了93.27%的用户
*/

旋转数组的最小数字

这题的数组在某种程度上是有序的，因此用二分。但二分是用中间值和target比较，这里的target在哪呢？就用两个端点值，而且只能用右端点的值，这样才能缩小区间。为何要用右端点呢，是因为右端点是截断点，根据比较能缩小区间，左端点则不行。原则上将数组分成两个有序数组（左边段和右边段），就可以缩小区间了。

在比较之后，如果中间大于右端点，说明中间在左边段，而最小值一定在右边段，即在low之后，因此可以缩小区间，把low变成mid，而此时mid不可能是最小值，因此可以变成mid+1。并且必须这样，不然假如是5，1，那么low=mid，一直死循环。

如果中间小于右端点，则中间点在右边段了，最小值位置在mid及mid以前，缩小区间high=mid，因为mid也可能是最小值，因此high不能mid-1。

如果中间和右端点相等，这是因为这里的数组元素可以相等，此时high不能直接=mid，因为左边段可以和右边段相等，如3，3，1，3。直接相等就越过了1。也不能让low=mid，因为右段也可以和右端点相等。1，3，3的情况下，就越过了1。因此，直接将high-1就可以了，这样可以保证不越过又可以慢慢缩小区间，如果high是最小值，那么mid也是最小值，不会越过。

1
2
3
4
5
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
1
2
3
4
5
6
7
8
示例 1：

输入：numbers = [3,4,5,1,2]
输出：1
示例 2：

输入：numbers = [2,2,2,0,1]
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0, high = numbers.size()-1;
        while(low<high)
        {
            int mid = low + (high-low)/2;
            if(numbers[mid]<numbers[high]) high = mid;
            else if(numbers[mid]>numbers[high]) low = mid+1;
            else high-=1;
        }
        return numbers[low];
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了86.65%的用户
内存消耗：11.7 MB, 在所有 C++ 提交中击败了71.43%的用户
*/

矩阵中的路径

这道题找路径的，就可以用深度优先搜索（dfs），由于每个元素都可以当开头，因此要对每个元素都用一次dfs。然后考虑一下剪枝，在dfs的过程中每个位置都可以继续向上下左右出发（用逻辑或连接起来），因此第一个要考虑的部分就是越界问题；其次，每次dfs都向后探一个字符串单词的字母，如果正确才能继续，因此第二个要考虑的就是当这个位置的字母不正确就返回false。这样就可以保证找到所有的可能。

还要考虑标记的问题，因为矩阵的元素不能重复使用，当这个元素正确要向后dfs时，必须先把这个元素标记不可用，在c++中用’\0’就可以。在dfs之后，还要标记回来。

1
2
3
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
1
2
3
4
5
6
7
8
示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：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
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();//初始化行列
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(dfs(board,word,i,j,0))//对每个位置都dfs，0表示单词开始，如果找到则直接返回true
                    return true;
        return false;
    }
private:
    int n, m;//声明行列
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k)
    {
        
        if(i<0||j<0||i>=n||j>=m||board[i][j]!=word[k]) return false;//越界或不对应则剪枝
        if(k==word.size()-1) return true;//没越界且对应，长度也对应，成功
        //标记
        board[i][j] = '\0';
        //向上下左右出发，k+1
        bool res = dfs(board, word, i+1, j, k+1)||dfs(board, word, i, j+1, k+1)||
            dfs(board, word, i-1, j, k+1)||dfs(board, word, i, j-1, k+1);
        board[i][j] = word[k];//标记回来
        return res;
    }
};
/*
执行用时：520 ms, 在所有 C++ 提交中击败了18.67%的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了98.27%的用户
*/

day4

I-剪绳子

这种题首先是求最大值，然后因为乘积是可分解的，因此这个问题可以缩小规模，就可以考虑用动态规划，实际上有更简单的数学解法。对于动态规划，n是从2开始的，然后当长度是n的时候，可以将乘积分两段，要么直接乘，要么对前一段再分（也就是小规模的再动态规划），后一段的长度通过遍历解决，就不用动态规划了。因此长度n时有两种选择，两段乘或再分，然后还要继续遍历，因此要保存好前面求的最大值。

1
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]\*k[1]\*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
1
2
3
4
5
6
7
8
9
10
示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;//初始化
        for(int i=3;i<=n;i++)//i从3开始，到n
            for(int j=1;j<=i-1;j++)//j从1开始，长度到i-1（最简单的遍历方式），
                //这里j从2开始也可以，长度到i-2也可以，因为长度为1的划分没有意义
                //但不能同时，要确保能进入循环，才有dp的定义
                dp[i] = max(dp[i],max((i-j)*j,dp[i-j]*j));//首先要和之前遍历出来的dp[i]比较。然后看
        									//是直接乘更大还是继续划分，j不用dp，因为是遍历的
        return dp[n];
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了63.63%的用户
*/

day5

II-剪绳子

这题就不方便用动态规划了，因为会溢出。这个问题出自我们是对结果取余，用动态规划max比较时，取余会造成max比较不正确，比如一个大的取余反而小了。因此不能在比较时候取余，那么在计算过程中就会溢出，即使用long long int也存在这个问题。

那么就可以用到数学的解法，因为数学的解法不需要比较，只需要一直运算就可以：

  • 根据几何不等式，等分时乘积最大；

  • 等分为长x的a段有：ax=n，则乘积为$x^a$，由于 n 为常数，因此当 $x^{\frac{1}{x}}$ 取最大值时， 乘积达到最大值。因为$x^a=x^{\frac{n}{x}}$

  • 因此对$x^{\frac{1}{x}}$求极大值，取对数有lny = lnx/x，求导得x=e。那么x可取2或3，代入一下2和3，同时取6次方发现3^2=9大一些，因此最好分成长为3的。

结论：

最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 $2 \times 2 > 3 \times 1$。

1
2
3
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]\*k[1]\*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 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 cuttingRope(int n) {
        if (n <= 3) return n - 1;//必须切分一次
        long ret = 1;
        if (n % 3 == 1){
            ret = 4;//最后的4变成2*2
            n = n - 4;
        }
        if (n % 3 == 2){
            ret = 2;//最后的2留着
            n = n - 2;
        }
        while (n) {
            ret = ret * 3 % 1000000007;//这里可以取模的原因是，跟max不同，ret是已经确定好的答案，只是一直没算完，
            						//先模后模的结果是一样的           
            n = n - 3;
        }
        return (int)ret;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了86.22%的用户
*/

二进制中1的个数

第一种方法是逐位看是不是1，直接把1左移然后和n与运算那就好。也可以模2来做。

第二种方法是用n&(n-1)，因为n-1会把第一个1右边的0变成1，且这个1变成0，那么再与n做与运算时，实际上就是把n的第一个1消去了（原来的0和1&也是0，但原来的1由于变成了0，&后也是0），因此每做一次这个操作，就有一个1。

1
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 [汉明重量]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：

输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//逐位比较
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        for(int i=0;i<32;i++)
            if(n&(1<<i))//不断将1左移i位，也就是和n的第i位对齐，然后取与运算
                res++;//如果结果非0，则是一个1
        return res;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了33.03%的用户
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//n&(n-1)
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n)
        {
            n &= n-1;
            res++;
        }
        return res;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了82.14%的用户
*/

day6

数值的整数次方

简单的快速幂+迭代，假如数值是x，次方的n，那么就是要分n是奇数还是偶数，这是因为如果是奇数要多一项，偶数则直接x平方。把n看成二进制的话，举个例子，如果n=1000，则是$x^8$，把x的二次方再二次方再二次方，整个过程三次即可（因为有三个零），但如果是1001，则要先乘一个x，再乘$x^8$。

也就是说，如果n是奇数，则底数累乘一个“x”。为了循环计算，我们要把n每次除以2（其实就是一位一位看是不是1），然后再看是不是奇数。对应此，所谓的“x”就也是累成的，可以定义一个k存储中间结果。

再注意一下细节，如果n是负数，那么要把x取倒数，然后把n正过来。但是负数的n正过来可能会使int溢出，所以要用longlong来做。

1
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if(N<0)//预处理
        {
            x=1/x;
            N=-N;
        }

        double k = x;
        double res = 1;
        while(N)
        {
            if(N%2==1)
                res *= k;//如果最后一位是1，说明对应的k要乘
            k = k*k;//不管如何，因为N要右移了，k要平方一次
            N/=2;//右移
        }
        return res;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了82.47%的用户
*/

day7

打印从1到最大的n位数

这题之所以是简单题，是因为题目设计时不需要考虑大数问题，这类题目最好直接以大数的形式来写，这就需要string来辅助。

由于最后要返回vector，因此定义一个vector成员变量，这里面存int；同时使用两个辅助函数，一个用来递增数，一个用来将string转换为int存到vector里。

public内是主函数，由于定义string需要数的大小n，这是主函数的参数，因此string也要在主函数定义，所以辅助函数也需要传入string这个参数（用引用，递增函数要修改number），具体见代码。然后循环递增，每个数都转int放vector，最后返回就可以了。循环的结束判断利用递增函数的返回值来做，如果溢出则结束（溢出表明数已经大于给定的位数了）

对于转int函数，重点是把string前面多余的’0’去掉，从头开始遍历这些0，当不是0时就退出，然后用另一个string用+=把剩下的都连接起来，最后用stoi函数转int。

对于递增函数，重点是进位。首先定义一个表示进位的变量，然后就能得出每个位置上应该变成的值了：num = number[i]-'0'+takeOver;//当前位等于原来的加上进位的，当然最低位因为递增要加一。takeOver初始化为0，因为最低位没有进位。然后要循环判断进位，因为有可能是…99999的情况。所以我们的循环从最低位开始，最低位的num得出后要num++，然后如果num==10说明要进位，takerOver=1，这一位变成0；同时如果是最高位了，就溢出了，返回false。如果没有进位，就到此为止了，设置这一位的string的值就可以了，最后返回true表示可以继续递增。

1
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
1
2
3
4
示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
public:
    vector<int> printNumbers(int n) {
        //创建一个能容纳最大值的字符数组，由于需要n，因此在函数里创建而不成为类成员，这导致辅助函数需要传入number这个参数
        string number(n,'0');
        //初始全部设置为0，因为输出从1开始，后面就先增加1

        while(increment(number))//在increment的过程中判断是否结束，因为increment既有到哪一位的信息、也有是否进位的信息
            saveNum(number);
        return res;
    }

private:
    vector<int> res;//将string转int，放数组里
    

    bool increment(string &number)//运行一次就+1
    {
        int len = number.size();
        int takeOver = 0;//最大的要点就是考虑进位，一开始的进位是0

        for(int i=len-1; i>=0; i--)//i从最后开始，代表数从最低位开始
        {
            int num = number[i]-'0'+takeOver;//当前位等于原来的加上进位的
            if(i==len-1)
                num++;//如果是最低位，则要+1，代表增加一个1

            if(num==10)//若要进位
            {
                if(i==0)
                    return false;//最高位，且加上进位是10，溢出了，结束
                else
                {
                    number[i] = '0';
                    takeOver = 1;//不用再设回0，因为一旦不用进位就结束了
                }
            }
            else//不用进位就到此为止
            {
                number[i] = num+'0';
                break;
            }
            
        }
        return true;
    }

    void saveNum(string &number)//这个函数主要是把number前面多余的0去掉
    {
        string s = "0";
        int len = number.size();
        int notzero = len;//如果都为0则notzero不会被重新赋值，这会使后面那个循环直接跳过，使得s不变就是"0"

        for(int i=0;i<len;i++)
        {
            if(number[i]=='0')
                continue;
            else//找到第一个不为0的地方
            {
                notzero = i;
                break;
            }
        }

        for(int i=notzero;i<len;i++)
            s += number[i];
        
        int resnum = stoi(s);
        res.push_back(resnum);
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了14.22%的用户
内存消耗：11.6 MB, 在所有 C++ 提交中击败了12.52%的用户
*/

day8

删除链表的节点

简单的双指针应用，一个前一个后，cur指针来判定，pre指针要进行节点越过操作

1
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
1
2
3
4
5
6
7
8
9
10
示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
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* deleteNode(ListNode* head, int val) {
        if(head->val==val) return head->next;
        ListNode *pre = head, *cur = head->next;//现在head不是目标节点，从next开始
        while(cur)
        {
            if(cur->val==val)//如果找到
            {
                pre->next = cur->next;//越过
                break;
            }
            else//否则两个指针向后
            {
                pre = cur;
                cur = cur->next;
            }
        }
        return head;
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了84.51%的用户
内存消耗：8.9 MB, 在所有 C++ 提交中击败了84.76%的用户
*/

调整数组顺序使奇数位于偶数前面

简单的快排思想的应用，其实就是头尾双指针。

1
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
1
2
3
4
5
例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,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:
    vector<int> exchange(vector<int>& nums) {
        int i=0, j=nums.size()-1;
        while(i<j)
        {
            while(nums[i]%2==1 and i<j)//这个过程要加i<j的判断，一方面防止全是奇数时nums[i]的i越界了，一方面减少循环次数
                i++;
            while(nums[j]%2==0 and i<j)
                j--;
            if(i>=j)//减少不必要的交换和动作
                break;
            swap(nums[i],nums[j]);
            //手动推进，可以减少大while或小while的一次判断
            i++;
            j--;
        }
        return nums;
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了99.32%的用户
内存消耗：17.5 MB, 在所有 C++ 提交中击败了87.78%的用户
*/

day9

链表中倒数第k个节点

用快慢双指针就很简单了，快指针先走k步（指向第k+1个节点），然后两个指针再一起走直至快指针为null，此时快指针又走了n-k步，慢指针也走了n-k步，倒数过来就是倒数第k个。

1
2
3
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
1
2
3
4
5
示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *quick = head, *slow = head;
        for(int i=0; i<k; i++)
            quick = quick->next;
        while(quick)
        {
            slow = slow->next;
            quick = quick->next;
        }
        return slow;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了68.49%的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了73.69%的用户
*/

反转链表

简单的双指针pre和cur，前面的从尾到头打印链表写过了。感觉也可以用辅助栈，不过不推荐。

1
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
1
2
3
4
示例:

输入: 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
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr, *cur = head;
        while(cur)
        {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了95.85%的用户
内存消耗：7.9 MB, 在所有 C++ 提交中击败了93.81%的用户
*/

day10

合并两个排序的链表

简单题，大概是一个merge。使用一个非nullptr的伪头节点能减少代码重复（new一个），当然不用也行，这样还是得要一个head和一个cur，不过先比较l1和l2的头节点大小得出head和cur的指向，然后再进while循环。原因是while内要cur->next，如果cur没有指向节点而是null则它都没有next，只能在while里面再if判断是不是第一次进入，这样每次又多了一个if。

1
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
1
2
3
4
示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //由于一开始不知道是l1头小还是l2小，因此可以定义一个伪头节点(不是nullptr，所以用new构建一个)，这样可以
        //使头节点的比较也放在while里，和其他节点一样。这样减少了代码重复
        ListNode *cur = new ListNode(0);
        ListNode *head = cur;//head用来保存，cur用来移动
        
        while(l1 and l2)//合并
        {
            if(l1->val < l2->val)
            {
                cur = cur->next = l1;//添加节点并往下
                l1 = l1->next;
            }
            else
            {
                cur = cur->next = l2;
                l2 = l2->next;
            }
        }
        //合并尾部
        cur->next = l1 == nullptr ? l2 : l1;
        return head->next;//伪头节点后就是
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了92.19%的用户
内存消耗：18.6 MB, 在所有 C++ 提交中击败了78.85%的用户
*/
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
//不使用伪头节点，先比较获得头节点，代码比较臃肿，但是性能不差
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //前置处理
        if(!l1)
            return l2;
        if(!l2)
            return l1;

        ListNode *head;
        if(l1->val < l2->val)
        {
            head = l1;
            l1 = l1->next;
        }
        else
        {
            head = l2;
            l2 = l2->next;
        }
        ListNode *cur = head;
        
        while(l1 and l2)//合并
        {
            if(l1->val < l2->val)
            {
                cur = cur->next = l1;//添加节点并往下
                l1 = l1->next;
            }
            else
            {
                cur = cur->next = l2;
                l2 = l2->next;
            }
        }
        //合并尾部
        cur->next = l1 == nullptr ? l2 : l1;
        return head;
    }
};
/*
执行用时：12 ms, 在所有 C++ 提交中击败了98.83%的用户
内存消耗：18.5 MB, 在所有 C++ 提交中击败了92.94%的用户
*/

顺时针打印矩阵

细节在要注意给的矩阵是不是空的，如果是空要直接返回了，否则会有些越界问题。然后我们先获得上下左右四个边界，然后进入一个大的while循环一遍不断地“绕圈”。然后在while内根据边界右、下、左、上遍历元素，同时更新边界，并判断是否越界，越界就可以退出了。总体下来就是根据“边界”，在while(true)里for循环，知道这个就比较简单了。

1
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
1
2
3
4
5
6
7
8
示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int top = 0, left = 0, bottom = matrix.size()-1, right=0;
        if(bottom==-1)//没有元素
            return res;
        else
            right = matrix[0].size()-1;
        
        while(true)
        {
            for(int i=left;i<=right;i++)
                res.push_back(matrix[top][i]);
            top++;
            if(top>bottom)
                break;

            for(int i=top;i<=bottom;i++)
                res.push_back(matrix[i][right]);
            right--;
            if(left>right)
                break;
            
            for(int i=right;i>=left;i--)
                res.push_back(matrix[bottom][i]);
            bottom--;
            if(top>bottom)
                break;

            for(int i=bottom;i>=top;i--)
                res.push_back(matrix[i][left]);
            left++;
            if(left>right)
                break;
        }
        return res;
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了84.66%的用户
内存消耗：9.6 MB, 在所有 C++ 提交中击败了73.13%的用户
*/

包含min函数的栈

使用双栈来简化操作，一个主栈就进行push、pop和top（不进行其他操作），另一个辅助栈维护min，这样设计就能明确要做什么。

为了维护min，辅助栈的每次push就需要比较，除了空的时候直接放入，后面的push都只放入不大于栈顶的值。因为大于栈顶的值必然不可能再成为最小值了，它会在最小值被pop之前pop（因为先后顺序的原因），同时相等的元素要放入，因为pop了一个最小值，剩下的也可以是最小值。对于pop，只有当主栈pop出去的是最小值时，辅助栈才pop，因此要判断相不相等。

这样，返回min就只用返回辅助栈的top。实际上，核心是将辅助栈设计成一个升序栈（从顶到底），原理是因为后来的更大的值不可能成为最小值。

1
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
1
2
3
4
5
6
7
8
9
10
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -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
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> xstack;
    stack<int> hstack;//help stack，辅助栈维护升序栈
    MinStack() {

    }
    
    void push(int x) {
        xstack.push(x);
        if(hstack.empty())
            hstack.push(x);
        else
            if(x<=hstack.top())
                hstack.push(x);
    //辅助栈维护最小值，因此只有更小的才放进去。大的不放是因为辅助栈的顶部一定是最小值，假如说这个最小值被pop出去不存在了
    //那么这个更大的值肯定也更早被pop出去（因为最小值更先存在，大的在更顶上），所以这个最大值不会成为最小值，没必要放进去。
        //使用等于判断是因为可能有多个最小值，pop出一个还有其他的也算

    }
    
    void pop() {
        int x = xstack.top();//要看辅助栈的最小值要不要pop出去
        xstack.pop();
        if(x==hstack.top())
            hstack.pop();//如果主栈pop出去的是一个最小值，那么这个最小值也要pop
    }
    
    int top() {
        return xstack.top();
    }
    
    int min() {
        return hstack.top();
    }
};
/*
执行用时：12 ms, 在所有 C++ 提交中击败了98.07%的用户
内存消耗：14.6 MB, 在所有 C++ 提交中击败了86.44%的用户
*/

栈的压入、弹出序列

这题主要用模拟，根据生活中“手动判断”的过程来模拟。这是怎么样的过程呢：我们一般会跟踪元素一个个push的过程，然后对比poped序列，一旦一个元素可以pop，那就pop并且把前面能pop的也pop。这是因为数字都是不同的，如果错过了pop时机，再有元素进来就不再能pop了，也就错了。

而这里给的两个序列都是vector，我们模拟要不断pop，这不太方便，所以用到一个辅助栈（这也就是我们手动模拟用到的容器）。这样模拟就是：把pushed一个一个放进辅助栈（pushed如同数组，所以用for循环放直观一些），每放进一个就查看poped序列（记录好上次查看的位置），如果相等就pop，然后poped序列向后继续比较看能不能pop（这就用while循环，因为while直接能进行比较判断，并且也不知道for的次数）。

辅助栈不断加入元素，并且在合适时pop，如果最后辅助栈是空的，那么就是正确的了。

1
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
1
2
3
4
5
6
7
8
9
10
11
12
示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：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
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()!=popped.size())
            return false;//先考虑大小，不同直接false
        int n = pushed.size();
        if(n==0)
            return true;//如果大小为0就true
            
        //然后开始模拟，pushed和popped是不同排列，所以数字相同
        //如果直接对pushed栈模拟，不好操作，因为pushed是个vector，不对顶操作
        //所以用一个辅助栈
        stack<int> st;
        int pop_j = 0;//指向popped的位置

        for(int i=0;i<n;i++)//注意pushed和popped是vector而不是stack，要以数组形式使用
        {
            st.push(pushed[i]);//不断按顺序放入元素
            while(!st.empty() and st.top()==popped[pop_j])//然后尝试倒出，如果能倒则一直倒出，
                                         //因为数字不同正确性是唯一的，能倒时不倒，下一个进来时就不可能再倒出了
                //!st.empty()不能漏，因为top()在没有元素时出错、popped[pop_j]可能会越界，也不能直接判断pop_j，
                //因为存在st空了但pop_j还没越界的情况，使用st一举两得
            {
                st.pop();
                pop_j++;
            }
        }
        return st.empty();       
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了70.50%的用户
内存消耗：14.8 MB, 在所有 C++ 提交中击败了73.76%的用户
*/

day11

复杂链表的复制

这题有难度，主要在于没见过不太好想。先从正常的复制开始，如果只是复制next，那么我们遍历一遍原来的链表就可以得到next的信息了。为什么不能得到random呢，原因是random指向的那个节点不知道在哪里，不可能再用一层遍历去找。你可能会想着先遍历复制next的信息，再遍历一遍得到random，这里的关键问题是，我们在第二遍遍历的时候，确实是可以知道原来链表的节点random指向的位置，假设为A，但新的链表的节点random指针要指向的节点在哪呢？假设这个节点叫B，我们的问题是不能从A来找到B，B还是未知的。

因此，重点就是解决这个问题。简单的方法是，就把每个新的节点先放在原来节点的后面，这样就可以用next来找到复制的节点。因此上面的B就是A->next。于是就建立好了关系：cur->next->random = cur->random->next;。然而random可以指向null，没有next，所以要判空。

最后执行两个链表的拆分即可。整个过程就是：原地拷贝延申、修改random、拆分。注意拷贝要用new。

1
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
1
2
3
4
5
6
7
8
9
10
11
12
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 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
61
62
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        //前置判空
        if(!head)
            return nullptr;
        
        //原地拷贝延申
        Node *cur = head;
        while(cur)
        {
            Node *newcur = new Node(cur->val);
            newcur->next = cur->next;
            cur->next = newcur;
            cur = newcur->next;
        }
        cur = head;

        //修改random指针
        while(cur)
        {
            if(cur->random)//如果这个random不是null才有意义
                cur->next->random = cur->random->next;//cur->next表示那个新复制的节点，然后->random表示修改指向，
                                                    //指向的是cur->random这个节点的next，也就是对应的新复制的节点
            cur = cur->next->next;
        }

        //拆分
        cur = head;
        Node *newhead = head->next;//记录下来，因为要用到next，所以head不能为null，因此前面要判断是否为null
        while(cur)
        {
            Node *newcur = cur->next;
            cur->next = newcur->next;//cur非null，那么newcur非null，但newcur->next可能是null，也即这是最后一对节点
            if(newcur->next)//如果不是null
                newcur->next  =cur->next->next;
            else//否则直接是null，因为没有null->next
                newcur->next = nullptr;
            cur = cur->next;
        }
        return newhead;
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了73.50%的用户
内存消耗：10.9 MB, 在所有 C++ 提交中击败了90.72%的用户
*/

day12

字符串的排列

挺难的一道题，我用的是“下一个排列”的方法。

下一个排列的方法很难理解，一共有四步：1.从后往前找到第一个（严格）升序的元素对，这个元素对的前一个是“较小数”，后面那一段都是降序（非严格，跳过相同的字符，这里面i和j的比较都加”=”）的；2.从后往前找到第一个比“较小数”大的数，这个数是“较大数”；3.“较小数”和“较大数”交换；4.交换后，降序的那段依然降序，要反过来变成升序（用reverse函数或前后双指针swap）。在第一步中，我们用i和i+1判断元素对，如果字符串已经是最后一个排列了，或字符串是全相等的（或部分相等，不需要再排列了）时，i会变成-1（找不到），则此时要返回false了。

有了下一个排列，就可以慢慢获得所有排列了，首先就是要把原字符串sort变成最小的排列，然后do-while（因为第一个排列总是要放进去的），注意do-while的while有”;”。

1
2
3
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
1
2
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> res;
        sort(s.begin(), s.end());//因为是取下一个排列遍历，所以先排序得到最小排列
        do
        {
            res.push_back(s);
        }while(nextpermutation(s));
        return res;
    }
    bool nextpermutation(string &s)
    {
        int i = s.size()-2;
        //加等号是因为字符串可能有相同字符，这里要加等号越过它们，表示重复的只有一种情况；
        //否则i会停在重复的字符，j会更向前，导致前面的情况又换回来，进入死循环
        while(i>=0&&s[i]>=s[i+1])//从右向左找到第一个非降序的，即突然凹下去的那里
            i--;
        if(i<0)
            return false;//如果都是降序的，说明已经是最后一个排列了
        int j = s.size()-1;
        while(s[i]>=s[j])
            j--;//从右向左找到第一个比a[i]大的
        //if(j<0)
            //return false;//如果字符串都是相等的就可能一直往前走越界，但这种情况已经被i判断了，不用在j这考虑
        swap(s[i],s[j]);
        //现在后面i+1开始那一段是降序的，反转一下变成升序会更小
        for(int n=i+1,m=s.size()-1;n<m;n++,m--)
            swap(s[n],s[m]);
        //可以调库reverse(s.begin() + i + 1, s.end());
        return true;
    }
    
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：16.9 MB, 在所有 C++ 提交中击败了99.15%的用户
*/

数组中出现次数超过一半的数字

摩尔投票法，记住两个变量：候选者、投票数。如果没有计数就重置候选者，然后通过比较候选者和当前值看票数要加一还是减一。知道这个方法就很简单了。

1
2
3
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的组总是存在多数元素。
1
2
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//正常逻辑版本
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int cand;
        for(int num:nums) //这是python取数组内容的形式，c++11也支持（加个变量类型即可），也可以for(int i=0;i<nums.size();i++)用nums[i]
        {
            if(!count)//如果没有计数，则重新开始投票
            {
                cand = num;
                count++;
            }
            else if(num==cand)//如果有计数说明有候选者，相等则计数++
                count++;
            else//即有计数，也不相等
                count--;
        }
        return cand;//题目说一定有众数，就直接返回；否则要再检验一遍，因为此时不一定是众数
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了65.56%的用户
内存消耗：18.2 MB, 在所有 C++ 提交中击败了66.76%的用户
*/
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) {
        int count = 0;
        int cand;
        for(int num:nums) //这是python取数组内容的形式，c++11也支持（加个变量类型即可），也可以for(int i=0;i<nums.size();i++)用nums[i]
        {
            if(!count)//如果没有计数，则重新开始投票
                cand = num;
            count+= num==cand?1:-1;//无论如果都判断一次，这里把count是不是0的情况都包含了
            				//因为count是0也是count++
           	//这种方式也就是把上面的else if的else去掉了，变成两个独立的if而不是一个大if，会快一些。
            
        }
        return cand;//题目说一定有众数，就直接返回；否则要再检验一遍，因为此时不一定是众数
    }
};
/*
执行用时：8 ms, 在所有 C++ 提交中击败了97.96%的用户
内存消耗：18.2 MB, 在所有 C++ 提交中击败了85.24%的用户
*/

最小的k个数

方法是快速排序，使用快排的思想，注释写了很多了，能达到O(n)的时间复杂度

1
输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
1
2
3
4
5
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

输入：arr = [0,1,2,1], k = 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
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int size = arr.size();
        if(size == k)//刚好就不用排了
            return arr;
        quickSelect(arr,k,0,size-1);//快速选择：把最小的k个放在最前面
        vector<int> res;
        for(int i=0;i<k;i++)
            res.push_back(arr[i]);//前k个都是小的了，拷贝一下
        return res;
    }
private:
    void quickSelect(vector<int>& arr, int k, int l, int r) {
        int i=l,j=r;
        while(i<j)//先快排
        {
            while(i<j&&arr[j]>=arr[l])
                j--;
            while(i<j&&arr[i]<=arr[l])//加等号使得相同元素相对位置不改变，稳定排序
                i++;
            swap(arr[i],arr[j]);

        }
        swap(arr[i],arr[l]);
        //快排要把arr[l]放在两段的中间，就需要保证arr[i]是一个不比arr[l]大的数；
        //因此那两个while必须先从j开始，因为当j停下时，要么是碰到了i（上一轮的i已经是小的了），这时全部结束，i是较小的
        //要么是等待置换，此时轮到i走，要结束只能碰到j，j在等待，是较小的
        //如果while先对i做，可以想到i可能停在上一轮的j处，此时j是大的
        //因此如果用左边界，则要从右开始，置换i；用右边界则从左开始，置换j

        
        //此时快排做完，i和i前的元素都是小的，前i+1个元素都是小的，且前i个元素小于第i+1个元素（i代表第i+1个元素）
        //与快排不相同的是，这里分情况再排，而不是两段直接排
        if(i==k||i==k-1) return;//i=k或者i+1=k
        else if(i>k)  quickSelect(arr,k,l,i-1);//i左边元素有些多，对左边再排，i本身不用排了，不可能是
        else  quickSelect(arr,k,i+1,r);//i<k-1，这里只用排k-i-1个元素了，但为什么参数仍然是k呢？
        							//因为我们是从左边界i+1开始的
                                      //排序只对l-r之间的元素，但位置i仍是整体的，并不是从左边界开始从0算起，因此参数仍是k
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了97.66%的用户
内存消耗：18.5 MB, 在所有 C++ 提交中击败了52.99%的用户
*/

day13

连续子数组的最大和

动态规划，递推方程是：dp[i] = max(dp[i-1],0)+nums[i];。dp[i]的意思是前i个数的子数组的最大和，则dp[i]是前面的最大值加上nums[i]，其中如果前面的最大值是一个负数就从头开始，就是0+nums[i]。加上nums[i]才使得这样的递推的子数组是连续的，因为dp[i-1]也加上了nums[i-1]，如果大于0，那么使用它的话就是连续的子数组了。

这里面动态规划注意一个要点，如果递推式不利用历史信息的话，只利用前面一项或几项，那就可以用一个或几个变量代替dp数组，能把空间复杂度从O(n)变成O(1)。

1
2
3
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。
1
2
3
4
5
示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//动态规划普通版本，使用dp数组递推
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i=1;i<n;i++)
        {
            dp[i] = max(dp[i-1],0)+nums[i];
            res = max(res,dp[i]);
        }
        return res;
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了81.76%的用户
内存消耗：22.8 MB, 在所有 C++ 提交中击败了27.27%的用户
*/

这里面呢，实际上dp数组在遍历时只用到前面一项，更之前的信息完全不用，实际上就可以简化为两个变量cur和pre，一个代表dp[i]，一个代表dp[i-1]。更进一步，cur和pre只是前一轮和这一轮的关系，用一个变量完全足够了

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 maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int pre = nums[0];
        int res = pre;
        for(int i=1;i<n;i++)
        {
            /*
            等价于：
            cur = max(pre,0)+nums[i];
            pre = cur;
            */
            pre = max(pre,0)+nums[i];//其实就是pre = cur = max(pre,0)+nums[i]; cur完全不需要。
            res = max(res,pre);
        }
        return res;
    }
};
/*
执行用时：12 ms, 在所有 C++ 提交中击败了95.96%的用户
内存消耗：22.3 MB, 在所有 C++ 提交中击败了88.01%的用户
*/

数据流的中位数

这题是困难的，比较难想，不会就快排再算。这里考虑的是数据流，比较偏应用，就是要用一个合适的数据结构来做（也说了要选数据结构）。这里插入对于数据结构都好说，主要是中位数怎么找。根据中位数的性质可以把数据均分成较大的一组和较小的一组，然后只要找到两个数据组中“突出”的那一个就好了，也就是中位数或两个用于计算中位数的数。我们只要一个或两个数，这些数是较大组的最小值或较小组的最大值（这样才居中）。

因此就可以用堆，因为堆就是用来存最大值和最小值的，在c++中可以用优先级队列priority_queue来做。堆有两个，一个小顶堆存较大数据的最小值、一个大顶堆存较小数据的最大值。这里的重点是维护数据均分，如果是偶数则两个堆数据个数相同，如果是奇数则其中任意一个多一个数据，这里选大顶堆多一个元素。

因此就分两种情况插入数据，如果插入前两个堆大小相等，则要向大顶堆插入。但不知道这个数据多大，因此不能直接插入，而需要先插入小顶堆，再从小顶堆拿出（pop）顶部元素插入大顶堆。这个过程就是把新元素和较大元素比较，拿出最小的放入大顶堆，保证了大顶堆中的元素全都小于小顶堆。如果插入前大顶堆个数多（根据设计不可能小顶堆更多），则要向小顶堆插入，同样的要先插入大顶堆，然后拿出顶部元素插入小顶堆。

最后是取中位数，如果堆大小相等，则取两个堆顶部元素（即数据流大小最中间的两个元素）取平均；否则大顶堆多一个元素，根据大小关系直接返回大顶堆的顶部元素。注意这里取平均在除以2之前要*1.0转double。

这样插入时间复杂度是O(logn)，取中位数是O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[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
10
11
12
示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MedianFinder {
public:
    /** initialize your data structure here. */

    // 大顶堆，存储较小的一半的数据，堆顶为最大值
    priority_queue<int, vector<int>, less<int>> maxHeap;//less表示降序排序
    // 小顶堆， 存储较大的一半的数据，堆顶为最小值
    priority_queue<int, vector<int>, greater<int>> minHeap;//greater表示升序排序
    //第一个参数是类型、第二个参数是底部容器（使用heap的算法）、第三个参数是比较方式

    MedianFinder() {
    }

    // 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
    void addNum(int num) {
        /*
         * 当两堆的数据个数相等时候，向大顶堆添加元素（也可以向小顶堆添加，指定一个堆放多的元素）。
         * 采用的方法不是直接将数据插入大顶堆，而是将数据先插入小顶堆（因为这个元素大小不好说），算法调整后
         * 将堆顶的数据（较大数中最小的）插入到大顶堆，这样保证大顶堆插入的元素始终比小顶堆的元素小。
         * 同理如果大顶堆数据多，往小顶堆添加数据的时候，先将数据放入大顶堆，选出最大值（top）放到小顶堆中。
         */
        //这种添加方式是让奇数个数时多的那一个放到大顶堆中，实际上也可以放小顶堆中，方式是镜像的
        //但使用一种方式后，其他的操作要适应它。因为这些数据个数决定了中位数的取法。

        if (maxHeap.size() == minHeap.size()) {
            minHeap.push(num);//先放小顶堆
            int top = minHeap.top();//把较大的值中最小的那个拿出来
            minHeap.pop();//pop
            maxHeap.push(top);//给大顶堆
        } else {
            maxHeap.push(num);
            int top = maxHeap.top();
            maxHeap.pop();
            minHeap.push(top);
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) 
            return (maxHeap.top()+minHeap.top())*1.0/2;//转double
        else 
            return maxHeap.top()*1.0;
        
    }
};
/*
执行用时：92 ms, 在所有 C++ 提交中击败了75.35%的用户
内存消耗：40.6 MB, 在所有 C++ 提交中击败了84.11%的用户
*/

day14

数字序列中某一位的数字

本质是找规律的题目，个位数有9个（下标从0开始，序列算了0，相当于抵消）、个位数有90个、百位数有900个…根据这些规律就能得出n在那一个位数的阶段中，比如n=11就在10~99这个两位数的段里。然后就能得出从这个段起始开始还要走多少个数字x（因为前面的总数字数肯定是知道的，这样才能得到在哪个段嘛），根据这个x和位数的关系又能得出是第几个数的第几位，然后转string取出来就好了。

注意这里当n比这一位数和前面位数的数字要多时，要算后面的位数的总个数，但是这样可能会越界，因为乘以了9，数没有那么多。那么就要有溢出判断，不应该乘以9时就不做了。

这种题还是用些实例来想过程，比如取11、12等等。

1
2
3
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。
1
2
3
4
5
6
7
8
示例 1：

输入：n = 3
输出：3
示例 2：

输入：n = 11
输出：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
class Solution {
public:
    int findNthDigit(int n) {
        if(n<10) return n;
        int intmax = 0x7fffffff;
        bool flag = true;//溢出判断，false是溢出
        int digit = 1;//位数
        int total = 9;//总数
        int start = 1;//起始点，因为每个起始都是10、100、1000这样的，每次乘10就可以
        //因为下标也从0开始计数，所以n=9时对应的是9，因此total为9表示个位数
        while(n>total)//首先确定n代表的数在哪个位数中
        {
            digit++;//表示进入下一位数的范围
            start *= 10;
            if(digit*start>=intmax/9)//做乘法会溢出，不做了
            {   
                flag = false;
                break;
            }
            total += digit*start*9;//下一位数有9*start个数，每个数有digit位，这就能算出下一位数的数字个数
        }

        //
        int x;//x是从start开始的数字个数
        if(flag)//如果没溢出
            x = n-total+digit*start*9;
        else //如果要溢出，说明最后的total是没做的
            x = n-total;//前面有total个单个的数字

        int num = start + (x-1)/digit;//第num个数，x-1是因为start本身就是第一位，比如10的话应该是10+0/digit，但此时x是1
        int k = (x-1)%digit;//k是指第num个数的第k位，x要减一同理

        string nums = to_string(num);//to_string函数把int转string
        return nums[k]-'0';//这里nums[k]是char要转一下
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了89.87%的用户
*/

把数组排成最小的数

这题也比较难想，一般直接去想会想成遍历或规划问题。实际上这题被做成了一道排序问题，假如有数字x，y，如果x+y>y+x，那么x应该放在y前面（后面充要证明）。当x和y相邻时这很好理解，但当xy不相邻时，为什么x一定要在y前面呢？必要性：我们假设有一个最小的排列axyzb，我们很容易得到a<x，x<y，y<z，z<b，否则我们可以交换相邻的元素得到更小的排列，即假如z>b我们可以交换z和b。充分性：如果a<x，x<y，y<z，z<b，那么按axyzb的排列一定最小，因为交换 a,b（表示任意交换两个元素）相当于依次交换 ax,ay,az，接着交换 ab,zb,yb,xb 。每一次相邻交换都使得交换后的值更大。

因此，如果x+y>y+x，那么x应该放在y前面。那么我们对这个数组进行排序就可以了，能够排序的原因是每两个元素都能得到明确的大小关系和可传递性（一旦x>y，y>z，那么x>z，即如果x在y前面，y在z前面，根据前面的充要证明，x一定在z前面），这和正常的比大小一样。因此能使用快排来做，每次都和左边界标值比较，看x应该放在标值前还是后。

将数组转string的vector，然后排序，再拼接就可以了。

1
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
1
2
3
4
5
6
7
8
示例 1:

输入: [10,2]
输出: "102"
示例 2:

输入: [3,30,34,5,9]
输出: "3033459"
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

class Solution {
public:
    string minNumber(vector<int>& nums) {
        //先转string
        vector<string> str;
        int n = nums.size();
        for(int i=0;i<n;i++)
            str.push_back(to_string(nums[i]));

        quickSort(str,0,n-1);

        string s = "";
        for(string strs : str)
            s += strs;
        return s;
    }

private:
    void quickSort(vector<string>& str,int l,int r)//排序
    {
        if(l>=r) return;
        int i=l, j = r;//左边界右边界
        while(i<j)
        {
            while(i<j and str[l]+str[j]<=str[j]+str[l]) j--;
            //j--的情况是前+后的值小于后+前，前是标值l，后是值j，此时说明不用换
            while(i<j and str[l]+str[i]>=str[i]+str[l]) i++;
            swap(str[i],str[j]);
        }
        swap(str[i],str[l]);

        quickSort(str,l,i-1);
        quickSort(str,i+1,r);
    }
};

/*
执行用时：4 ms, 在所有 C++ 提交中击败了91.34%的用户
内存消耗：11 MB, 在所有 C++ 提交中击败了53.92%的用户
*/

day15

把数字翻译成字符串

通过读题目可以发现，要么对一位数字直接翻译，要么对两位数字进行翻译，即1或2，这和动态规划的青蛙跳台阶很像。对于第i位结尾的数字，如果能知道第i-1位结尾时翻译总数和第i-2位结尾时的翻译总数，那么就有f(i)=f(i-1)+f(i-2)。这个递推式是解释是，第i位要么单独翻译要么和i-1位一起翻译，能这么做的原因是这两种翻译出来的字符串肯定不一样。

然而还需要考虑的是，i和i-1位组成的数字不一定能够翻译（10–25之间），因此在不能翻译时，递推式退化成f(i)=f(i-1)，这只是一个if的事情。

根据这个递推式，就可以使用动态规划，由于最多往前两项，那么用三个变量即可，不用用数组。

1
2
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
1
2
3
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
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 translateNum(int num) {
        //翻译范围是0-9，10-25
        //f(i) = f(i-1)+f(i-2)，其中i和i-1要能满足翻译范围，否则f(i) = f(i-1)
        int pre = 0;//f(i-1)
        int prepre = 0;//f(i-2)
        int cur = 1;
        string str = to_string(num);
        
        for(int i = 0;i<str.size();i++)
        {
            prepre = pre;
            pre = cur;
            if(i==0)
                continue;
            string s = str.substr(i-1,2);//拿出i和i-1
            /*
            * string substr (size_t pos = 0, size_t len = npos) const;
            * 在字符位置pos开始，跨越len个字符（或直到字符串的结尾，以先到者为准）对象的部分。
            */
            if(s<="25"&&s>="10")
                cur = pre + prepre;
            else
                cur = pre;


        }
        return cur;

    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了82.92%的用户
*/

礼物的最大价值

一眼动态规划。dp[i][j] = max(dp[i-1][j],dp[i][j-1])+gird[i][j]，从左边或上边到来，选一个大的路径加上本身（价值大于0）。这里巧妙的地方是，不需要一个额外的dp[n][m]数组，可以直接修改grid，因为遍历到grid某处时的值只需要使用自身和前面的累加值，那么在使用了自身后就可以把自己修改成累加值，以后不用自身原来的值了：grid[i][j] = max(grid[i-1][j],grid[i][j-1])+gird[i][j]，简便写法：grid[i][j] += max(grid[i-1][j],grid[i][j-1])。最后，最大值一定是右下角元素，因为所有礼物最大值都大于0，路径一定会走到那里。

1
2
3
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
1
2
3
4
5
6
7
8
输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→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
25
26
27
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        //dp[i][j] = max(dp[i-1][j],dp[i][j-1])+gird[i][j]，从左边或上边到来，选一个大的路径加上本身（价值大于0）
        //vector<vector<int>> dp;不用额外的数组，在grid原地修改即可，
        //因为grid本身的数组并不需要，后面的计算使用的是前面的累加

        //初始化dp数组初始化
        for(int i = 1;i<m;i++)//累加第一行
            grid[0][i] += grid[0][i-1];//第一行右边的价值只能由左边累加
        for(int i = 1;i<n;i++)//累加第一列
            grid[i][0] += grid[i-1][0];//第一列下边的价值只能由上边累加

        //开始动态规划
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                grid[i][j] += max(grid[i-1][j],grid[i][j-1]);

        //最后一定走到右下角，因为价值大于0
        return grid[n-1][m-1];
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了95.90%的用户
内存消耗：8.7 MB, 在所有 C++ 提交中击败了94.41%的用户
*/

day16

最长不含重复字符的子字符串

这种字符串的问题，可以考虑以第i位为结尾的后缀怎么怎么样。设dp[i]是以第i位结尾的字符串的最长不含重复字符的子字符串的长度，注意这里隐含地说明了第i位一定在这个字符串里，这给连续性带来了方便。

那么假如知道了dp[i-1]，那么dp[i]怎么得出呢？我们只需要知道s[i]上一次出现的位置即可（假设是j）。如果上一次出现的位置在dp[i-1]到i的范围内，那么这个子串需要缩小，dp[i]=i-j，从j开始算。否则，i在dp[i-1]前面或者根本没出现，这两种情况都可以直接dp[i]=d[i-1]+1，即s[i]和前面连接

如何记录上一次s[i]的位置呢？用一个哈希表存储，map[s[i]]表示和s[i]相同的字符上一次出现的位置

1
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "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
37
38
39
40
41
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        /*
        这种字符串的问题，可以考虑以第i位为结尾的后缀怎么怎么样
        设dp[i]是以第i位结尾的字符串的最长不含重复字符的子字符串的长度，
        注意这里隐含地说明了第i位一定在这个字符串里，这给连续性带来了方便

        那么假如知道了dp[i-1]，那么dp[i]怎么得出呢？我们只需要知道s[i]上一次出现的位置即可（假设是j）。
        如果上一次出现的位置在dp[i-1]到i的范围内，那么这个子串需要缩小，dp[i]=i-j，从j开始算
        否则，i在dp[i-1]前面或者根本没出现，这两种情况都可以直接dp[i]=d[i-1]+1，即s[i]和前面连接

        如何记录上一次s[i]的位置呢？用一个哈希表存储，map[s[i]]表示和s[i]相同的字符上一次出现的位置
        */
        int n = s.size();
        if(n<=1) return n;//因为要创建dp和map，如果n是0就出问题。这里顺便把n=1的情况也一起干了

        vector<int> dp(n,0);
        unordered_map<char,int> map;

        dp[0] = 1;
        int max_v = 1;
        map[s[0]] = 0;

        for(int i=1;i<n;i++)
        {
            //map.find()在找到元素时返回迭代器，否则返回map.end()。当还不确定找不到得到时，先判断一下
            if(map.find(s[i]) == map.end())//没有这个元素，如果直接map[s[i]]就报错了，所以这里的顺序很重要
                dp[i] = dp[i-1]+1;
            else if(map[s[i]]<i-dp[i-1])
                dp[i] = dp[i-1]+1;
            else
                dp[i] = i-map[s[i]];

            map[s[i]] = i;//更新
            max_v = max(dp[i],max_v);//每次都要和dp[i]比较，这是这个解法的核心：每个不同位置结尾的子串都可能最长
        }
        return max_v;
        
    }
};

丑数

简单的规律是一个丑数乘以2、3或5能得到更大的丑数，更进一步可以推导到：每个丑数都无非是前面的丑数乘2、3或5不断增加得来的。那么我们可以用动态规划，把前面得到的丑数不断乘以2、3、5就能得到更大的、后面的丑数

这里的问题是如果单单对一个数同时乘以2、3、5，那么会导致顺序不对，我们明确了要第n个丑数，因此这里有个排序的问题。除了排序的问题，还有重复的问题（如2*5和5*2是同一个丑数）

因此好的解法是，当要求下一个丑数时，一定是某些数（不一定是同一个数）乘2、3或5，把最小的那个拿来，然后把对应的数移向下一个（这导致了数不同）并判断重复，如果重复了这个数也要后移。因为上一个丑数是更前面的某些数乘2、3或5得到的最小值，且考虑了重复问题，那么这个新的最小的丑数比上一个丑数要大，且会比下一个丑数要小，这就有顺序了。

1
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int nthUglyNumber(int n) {
        //每个丑数都无非是前面的丑数乘2、3或5不断增加得来的
        //那么我们可以用动态规划，把前面得到的数字不断乘以2、3、5就能得到更大的、后面的丑数
        //这里的问题是如果单单对一个数同时乘以2、3、5，那么会导致顺序不对，因此这里有个排序的问题。
        //除了排序的问题，还有重复的问题
        //因此好的解法是，当要求下一个丑数时，一定是某些数乘2、3或5，把最小的那个拿来
        //然后把对应的数移向下一个并判断重复，如果有重复其他也要后移
        int a = 0, b = 0, c = 0;//分别指向下一次要乘2、3、5的位置
        vector<int> dp(n);//记录第i个丑数
        dp[0] = 1;//初始化
        for(int i=1;i<n;i++)//重复n次
        {
            int numa = dp[a]*2, numb = dp[b]*3, numc = dp[c]*5;
            dp[i] = min(numa,min(numb,numc));

        //如果dp[i]等于这些数的某个或某几个，说明是使用了或者有重复，要向下跳一个
            if(numa == dp[i])
                a++;
            if(numb == dp[i])
                b++;
            if(numc == dp[i])
                c++;
        }
        return dp[n-1];//返回第n个丑数
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.4 MB, 在所有 C++ 提交中击败了73.97%的用户
*/

day17

第一个只出现一次的字符

哈希表查看有没有重复，然后再遍历一次找到第一个没重复的即可

1
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
1
2
3
4
5
6
7
8
示例 1:

输入：s = "abaccdeff"
输出：'b'
示例 2:

输入：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:
    char firstUniqChar(string s) {
        int n = s.size();
        if(n==0) return ' ';

        unordered_map<char,bool> map;

        //遍历查看重复
        for(int i=0;i<n;i++)
        {
            if(map.find(s[i])==map.end())//用find函数看是否已存在
                map[s[i]] = true;
            else
                map[s[i]] = false;
        }
        
        //遍历查询第一个
        for(int i=0;i<n;i++)
            if(map[s[i]])//按s[i]的顺序来遍历
                return s[i];
        return ' ';
    }
};
/*
执行用时：40 ms, 在所有 C++ 提交中击败了39.13%的用户
内存消耗：10.4 MB, 在所有 C++ 提交中击败了75.44%的用户
*/

数组中的逆序对

算法课写过的一道题，可以使用归并排序，只需要添加一点细节就可以了。这个算法的核心是，在归并排序merge的过程中，我们有两个指针指向前一段和后一段，如果后一段的元素要放上去，说明这个元素比前面一段的剩余元素要小，这就产生了逆序对，数量是前面那一段剩余的元素。而当我们把递归的小的段排好后，把这一段产生的逆序对给上层累加，上层继续merge就又可以计算了。排序并不会影响逆序对的数量，因为前一段和后一段分别有序，也不影响前后之间的相对关系。

1
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
1
2
输入: [7,5,6,4]
输出: 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
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSortCount(0,n-1,nums,tmp);
    }
private:
    int mergeSortCount(int left, int right, vector<int>& nums, vector<int>& tmp)
    {
        if(left>=right) return 0;
        int middle = left+(right-left)/2;

        //最终结果是这一次归并加上左右递归归并产生的逆序对，因为递归时已经排序好了，那个过程中记录的逆序对数要返回上层
        int res = mergeSortCount(left,middle,nums,tmp)+mergeSortCount(middle+1,right,nums,tmp);
  
        //现在左右两段分别是有序的，要创建一个辅助空间，有三种方式
        /*
        * 1.vector<int> tmp = nums;//辅助空间，如果这样写每次都要拷贝一个很大的nums，会超时
        * 2.
        * int tmp[right-left+1];
        * for(int k=0;k<right-left+1;k++)
        *     tmp[k] = nums[left+k];//创建对应位置的tmp，不过后面使用tmp就要注意下标了
        * 3.像1一样创建一个大的全局tmp，这使得下标能和nums对应，同时使用2的做法，只
        * 在使用时拷贝对应的元素，这就使得全过程只进行了线性拷贝
        * 这个使用时是指在底层的两段排序好后，像2一样，不过既然是全局的，就要用引用传入参数
        */
        //tmp拷贝元素
        for(int k=left;k<=right;k++)
            tmp[k] = nums[k];

        int i = left, j = middle+1;//双指针分别指向两段的开头
        int cur = left;//指向nums数组
        while(i<=middle and j<=right)
        {
            if(tmp[i]<=tmp[j])
                nums[cur++] = tmp[i++];//赋值同时指针移动
 
            else//后面的小于前面的，只有这时要产生逆序对，所有i-middle的元素都可以和j构成逆序对
            {
                nums[cur++] = tmp[j++];//赋值同时指针移动
                res += middle-i+1;//i-middle共有middle-i+1个元素
            }
        }
        //收尾
        while(i<=middle) nums[cur++] = tmp[i++];//前一段剩下的都大于后一段，不过对应的j要产生的逆序对在前面的while产生完了
        while(j<=right) nums[cur++] = tmp[j++];//后面的大于前面的
        return res;
    }
};
/*
执行用时：144 ms, 在所有 C++ 提交中击败了86.13%的用户
内存消耗：43.3 MB, 在所有 C++ 提交中击败了64.45%的用户
*/

day18

两个链表的第一个公共节点

这个算法的核心是，A指针走完A就从B的头开始走，B指针走完B就从A的头开始走，那么它们就能在走过相同步长后在相交点相遇。

假如没有相交点，最终会同时到达nullptr（等长则第一轮抵达，不等长则第二轮抵达）这就使得我们可以和判断相交一样，采用判断A==B的形式，此时退出循环刚好返回nullptr，这在注释里有更详细的解释。

1
输入两个链表，找出它们的第一个公共节点。
1
2
3
4
5
6
7
8
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 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
/**
 * 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) {
        if(headA==nullptr || headB == nullptr) return nullptr;//有没有都不影响算法的正确性
        ListNode *A = headA, *B = headB;
        
        /*
        判断是否要跳转或是否往下走，而不是先往下走再判断或者先判断再往下走
        如果先往下再判断，那么while中A和B就不可能是nullptr
        如果先判断再往下走，那么跳到head之后总会next，而head可能是相交节点
        因此跳转和next是互斥的，不能同时做（要同时的话需要其他辅助手段）
        
        当没有交点时，最终会同时到达nullptr（等长则第一轮抵达，不等长则第二轮抵达）
        采用判断的话，A和B可以在执行next后同时到达nullptr达成break条件
        
        而有交点时，如果A和B等长，则在第一轮中间就结束返回
        如果不等长，则第一轮A和B不会同时为nullptr，是nullptr就跳，不是就往下
        */

        while(A != B)
        {
            if(A == nullptr) A = headB;//跳转
            else A = A->next;

            if(B == nullptr) B = headA;
            else B = B->next;
        }

        return A;
    }
};
/*
执行用时：32 ms, 在所有 C++ 提交中击败了97.75%的用户
内存消耗：14.1 MB, 在所有 C++ 提交中击败了90.20%的用户
*/

在排序数组中查找数字I

排序数组第一时间想二分法，同时根据二分法比较时有没有“=”，即nums[middle]<target和nums[middle]<=target的不同，指针会停在不同的位置，我们设置两次二分，得到左边界和右边界就好了。

1
统计一个数字在排序数组中出现的次数。
1
2
3
4
5
6
7
8
示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //二分法，判断条件的“=”能使得算法指针停在不同的边界
        //分别得出target左边界和右边界即可知道有多少个
        int i = 0, r = nums.size()-1;
        if(r<0) return 0;
        while(i<=r)
        {   
            int middle = i + (r-i)/2;
            if(nums[middle]<target)
                i = middle+1;
            else
                r = middle-1;//如果找到target，会缩小右边界，继续往前找
            //也就是说i是左边界，i是target第一次出现的位置（如果有）
        }
        if(i>=nums.size() || nums[i]!=target) return 0;//i越界或者i的位置不是target，说明找不到，提前返回
                                    //越界是因为可能所有元素都比target小

        int j = 0;
        r = nums.size()-1;

        while(j<=r)
        {   
            int middle = j + (r-j)/2;
            if(nums[middle]<=target)//如果找到target，会缩小左边界，继续往后找
                j = middle+1;
            else
                r = middle-1;
            //也就是说j是右边界，这个右边界是target之后的那个数，因为找到target会继续往后
        }
        return j-i;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了90.78%的用户
内存消耗：12.8 MB, 在所有 C++ 提交中击败了82.86%的用户
*/

day19

0~n-1中缺失的数字

排序数组用二分，这些题其实就二分的判断条件改改就完事了，然后注意边界怎么缩小的，要不要-1，while结束是i<j还是i<=j。一般来讲，边界都是m+1和m-1，对应的结束条件就是i<=j。

1
2
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
1
2
3
4
5
6
7
8
示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8
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 missingNumber(vector<int>& nums) {
        int i=0, j=nums.size()-1;
        while(i<=j)
        {
            int middle = i+(j-i)/2;
            //索引k处的值要么大于k要么等于k
            if(nums[middle]==middle)
                i = middle+1;//middle和middle前都是正确的，缩小左边界
            else//大于
                j = middle-1;//middle处已经大于了，要么是middle要么往前，缩小右边界
                    //那么middle为什么能-1呢？这样不会跳过正确答案吗？
                    //这是因为如果middle是正确答案且-1跳过了，那么会一直i=middle+1，最后回到正确答案且结束循环
                    //同时如果不减一则while循环无法结束，卡在i=j处（一直执行j=middle=i）
            
        }
        return i;
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了53.30%的用户
内存消耗：16.6 MB, 在所有 C++ 提交中击败了94.64%的用户
*/

数组中数字出现的次数

这个问题特殊之处在于，除了出现一次的数字，其他数字都出现了两次，这个两次很关键，它可以通过异或运算来加工——两个相同的数异或为0，0异或其他数字为其他数字。因此，把这些出现了两次的数字都异或了，结果就是0，接着去异或一个出现一次的数字，那么异或的结果就是这个数字了。

然而问题还没有这么简单，这个数组有两个出现一次的数字。我们的想法是，如果能把这两个数字分分组，就像奇偶一样分成两组就好了，因为每一组其他的数字都出现两次（相同的当然在一组啦），那么分别对这两组异或就能得到两个答案了。

但这两个目标数字不一定一个是奇数一个是偶数，我们可以肯定的是它们数值不一样。我们接着从异或出发，因为我们在异或整个数组前不知道两个数字是什么，那么我们在异或整个数组后能得到一个数z，z相当于这两个数字异或，肯定有一位是1，记这一位是m（全0说明这两数相同了）。就像奇数偶数一样，它们只是最后一位不同，那么我们也可以根据这一位m来分组，第m位为1的一组，第m位为0的一组，这样就分成两组了，分别异或就好了。

1
2
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求时间复杂度是O(n)，空间复杂度是O(1)。
1
2
3
4
5
6
7
8
示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,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<int> singleNumbers(vector<int>& nums) {
        //先遍历异或找出z
        int z = 0;//初始为0，因为0异或谁结果就是谁
        for(int num : nums)
            z ^= num;//注意这里是^=，z=z异或num
        
        //找出z为1的第m位
        int m = 1;//00000....00001
        while((z&m) == 0)
            m <<= 1;//如果与运算是0，说明还没到1的那位，m左移把1对过去，注意这里是<<=，m等于m左移一位

        //现在知道m了，边分组边异或
        int x=0, y=0;//初始化同z
        for(int num : nums)
        {
            if(num&m)
                x ^= num;//第m位为1的异或
            else
                y ^= num;//第m位为0的异或
            //两个数字肯定不在一起异或，因为第m位不同
        }
        return vector<int> {x,y};
        
    }
};
/*
执行用时：12 ms, 在所有 C++ 提交中击败了89.84%的用户
内存消耗：15.6 MB, 在所有 C++ 提交中击败了85.82%的用户
*/

day20

数组中数字出现的次数II

上一个问题是出现两次的数字异或是0，现在呢，出现三次的数字加起来，再模三就是0。因此所有数字加起来模三就是那个只出现一次的数字模三，但这只能求得余数，不过这至少给我们一些启发。

这个余数是小于3的，如果要用加法和余数表示这个数字的话，那么这个数字原来的那位数就必须小于3。由此联想到二进制的一位数，我们把所有的数字都看成二进制的话，它们相加就是每一位相加。对于那些出现三次的数字，全部来看的话，二进制上每个位都正好被3整除，因为数字要么这一位是0，要么就有三个1。最后我们把目标数字的二进制添加上去，因为要么是0要么是1，没有超出余数的范围，这样的话模三就可以了。

注意这里的二进制“相加”并不是真的相加，而是统计每个二进制位到底有多少个1，然后模三，余数就是目标数字二进制的对应位置的值。

总结一下就是：考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是 3 的倍数。因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。

1
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
1
2
3
4
5
6
7
8
示例 1：

输入：nums = [3,4,3,3]
输出：4
示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：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
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //int最多只有三十二位，所以只需要统计32位上每一位的1的个数
        vector<int> binary(32,0);

        //遍历统计每一个num
        for(int num:nums)
            //对于每一个数，统记二进制位
            for(int i=0;i<32;i++)//0表示最低位，往高位走
            {
                binary[i] += num&1;//取最后一位，如果是1就+1，如果是0就+0，数值对应就不用if-else了，直接加法
                num >>= 1;//num右移一位
            }
        
        //现在要模三，取每一位数
        int res = 0;
        for(int i=0;i<32;i++)
        {
            //从高位来，这样res不断左移就往高处推了
            //如果从低位开始，res不能左移不能右移，反而k每次要左移i次
            //虽然影响不大，终究浪费点效率 
            int k = binary[31-i]%3;
            
            //k要么是0要么是1，k总是在最低位，所以res要不断左移
            res <<= 1;//先左移再取位，顺序反了的话最低位总是会左移...
            res |= k;//res = res|k
            
        }
        return res;
    }
};
/*
执行用时：32 ms, 在所有 C++ 提交中击败了66.58%的用户
内存消耗：15.6 MB, 在所有 C++ 提交中击败了89.42%的用户
*/

和为s的两个数字

前后双指针，老生常谈了。

优化的话，可把while里面if判等的条件放在while判断

1
2
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
如果有多对数字的和等于s，则输出任意一对即可。
1
2
3
4
5
6
7
8
示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i=0, j=nums.size()-1;
        while(nums[i]+nums[j]!=target)
        {
            if(nums[i]+nums[j]>target)
                j--;
            else
                i++;
        }
        return vector<int>{nums[i],nums[j]};
    }
};
/*
执行用时：140 ms, 在所有 C++ 提交中击败了96.73%的用户
内存消耗：98.1 MB, 在所有 C++ 提交中击败了67.91%的用户
*/

day21

和为s的连续正整数序列

双指针一直往前滑动，维护一个滑动窗口就好了。这种方式实际上是在不断否定前面的序列，因为如果大了，那么右边界移动就更不可能了，所以只能左边界移动；如果小了就只移动右边界扩大，因为左边界起始点不动是可能的。

1
2
3
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
1
2
3
4
5
6
7
8
示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
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>> findContinuousSequence(int target) {
        //双指针
        int i=1, j=2;//窗口的左边界和右边界，一直往前看就行
        vector<vector<int>> res;
        int count;
        while(i<j)//i不能=j
        {   
            count = (i+j)*(j-i+1)/2;
            if(count==target)
            {
                vector<int> tmp;
                for(int k=i;k<=j;k++)
                    tmp.push_back(k);
                res.push_back(tmp);
                i++;//i往后一位
                j++;//i往后肯定更小，j一定要往后
            }
            else if(count<target)
                j++;//小了就j++，扩大右边界
            else
                i++;//大了就i++，缩小左边界，减去小的值
        }
        return res;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.5 MB, 在所有 C++ 提交中击败了62.75%的用户
*/

翻转单词顺序

用个辅助栈咯，在遍历过程中用个string存单词字母，遇到空格说明单词存好了，放入栈里，同时这个string变成空。那么如果后面还是空格，string是空，就可以辨别出是不是连续的空格了，因为单词后的空格string不是空。

最后要拼接，再把多余的空格删除。string经常要删除最后一个字符，用pop_back()舒服点。

1
2
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    string reverseWords(string s) {
        stack<string> help;
        string res = "";
        string tmp = "";
        //这轮遍历只记单词，空格一律过滤掉
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ' and tmp=="")//遇到连续的空格
                continue;
            else if(s[i]==' ' and tmp!="")//遇到第一个空格
            {
                help.push(tmp);
                tmp = "";
            }
            else//最后一个单词不一定有空格，所以还要if一下
            {

                tmp+=s[i];//不是空格的话
                if(i==s.size()-1)//最后的了
                    help.push(tmp);

                
            }
        }


        while(!help.empty())
        {
            res += help.top();
            help.pop();
            res += " ";
        }
        //最后会多一个空格
        //可以用substr(0,len-1)左闭右开
        //可以用earse(len-1)
        //可以用pop_back()
        res.pop_back();
        return res;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了77.87%的用户
内存消耗：8.2 MB, 在所有 C++ 提交中击败了50.94%的用户
*/

day22

左旋转字符串

简单

1
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
1
2
3
4
5
6
7
8
示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int size = s.size();
        string tmp = s.substr(0,n);//把前面n个记录下来
        for(int i=0;i<size-n;i++)
            s[i] = s[i+n];//往前挪
        for(int i=size-n;i<size;i++)
            s[i] = tmp[i-size+n];//把后面填上去
        return s;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了52.27%的用户
*/

day23

滑动窗口的最大值

记住：使用一个辅助的非严格递减的双端队列，先进先出，头部元素就是窗口的最大值。

这题正常想挺难想的，关键词是顺序遍历（滑动）、最值，实际上跟min栈很像，也是以一定顺序push和pop。min栈用的是辅助栈，滑动窗口是先进先出的，因此可以考虑用一个辅助的单调双端队列。

这个队列是维持窗口可能的最大值的，要怎么设计的呢？我们的窗口向后移动时，会移除最前面的元素，添加后面的元素。如果后的元素较大，那么更前的比它小的元素一定不可能再成为之后某个窗口的最大值，因为它们比后面的元素先出去，还比后面的元素小。

基于这样的思想，就可以在插入单调队列时把比这个元素小的都移除，这些被移除的元素在nums数组的位置肯定在插入的元素前。那么怎么移除呢，完全遍历的话就浪费时间，如果能维持单调递减，就可以从后往前比较大小和pop了，

在窗口移动的过程中，我们不仅增加了一个元素还减少了一个元素，如果这个元素在单调队列里面，我们需要把它删掉。如果它不是前一个窗口的最大值，那么它一定不在单调队列了，因为它是前一个窗口的第一个元素，没有后面元素大肯定不在；如果它是前一个窗口的最大值，那它在队列头部，pop掉就完事了。这能保持队列内的候选者都是当前窗口内的元素。

这样，单调队列的第一个元素，即最大的元素一定是这个滑动窗口的最大值了。

1
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //单调队列，非严格递减
        vector<int> res;
        deque<int> deq;
        deq.push_back(nums[0]);//初始化
        //没形成窗口前，先维护双端队列
        for(int i=1;i<k;i++)
        {
            //把比nums[i]小的都丢了，当然如果队列已经空了就不做了
            while(!deq.empty() and nums[i]>deq.back())
                deq.pop_back();
            //把nums[i]添加进去
            deq.push_back(nums[i]);
        }
        res.push_back(deq[0]);
        //现在已经有一个滑动窗口了
        //移向下一个滑动窗口
        for(int i=1,j=k;j<nums.size();i++,j++)
        {
            //deq现在是上一个滑动窗口的单调队列
            if(nums[i-1]==deq[0])
                deq.pop_front();//如果移除的值是最大值，就把最大值移出单调队列 

            //把比nums[j]小的都丢了，当然如果队列已经空了就不做了
            while(!deq.empty() and nums[j]>deq.back())
                deq.pop_back();//在j之前的数还比j小的话，那么这些数不可能是最大值了，因为这些数走得早
            //把nums[j]添加进去
            deq.push_back(nums[j]);
            
            /*
             前面的操作能保证i-j窗口以外的元素已经绝对不在deq里了
             因为j之后的还没添加，i之前的，如果i-1不是最大值，那么上一个窗口的最大值就在i-j-1之间
             根据单调队列的实现，i之前的元素都不会在，如果i-1是最大值，那么i-1之前的元素都不会在
             且i-1会被pop掉
            */
            res.push_back(deq[0]);//添加最大值
        }   
        return res;
    }
};
/*
执行用时：212 ms, 在所有 C++ 提交中击败了32.23%的用户
内存消耗：125 MB, 在所有 C++ 提交中击败了34.95%的用户
*/

day24

n个骰子的点数

在现实中，我们计算概率的时候会从前n-1个骰子的结果推向第n个骰子的结果，因为第n个骰子无非是1-6，某个值s的概率就是前n-1个骰子产生s-i的概率除以6（i从1到6），然后这些s-i都可以到达s，因此把这些概率累加。这种递推的想法给我们动态规划的考虑。

动态规划f(n,x) = f(n-1,x-i)/6.0（i：1-6，累加）。

这是逆向的想法，我们想要得到一个f(n,x)，要逆向推f(n-1,x-i)。但如果逆向，即从骰子为n一直向前推，当x<=6时都要做特殊处理。

因此改成正向的动态规划，从骰子为1开始，由于新增骰子的点数只可能为 1 至 6 ，因此概率 f(n−1,x) 仅与 f(n,x+1) , f(n,x+2), … , f(n,x+6) 相关。正向的递推就是当我们得到一个f(n,x)，可以产生一部分f(n+1,x+i)的概率，对不同的x，累加这些x+i即可。

因而，遍历 f(n−1) 中各点数和的概率，并将其相加至 f(n) 中所有相关项，即可完成 f(n−1) 至 f(n) 的递推。

具体的：动态规划正向递推，从小到大遍历n个骰子，遍历每个骰子的每一个值，对每个值遍历下一个骰子的1-6的值。

1
2
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
1
2
3
4
5
6
7
8
示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
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:
//动态规划f(n,x) = f(n-1,x-i)/6.0（i：1-6，累加）
//如果逆向，即从骰子为n一直向前推，当x<=6时都要做特殊处理
//因此改成正向的动态规划，从骰子为1开始，由于新增骰子的点数只可能为 1 至 6 ，因此概率 f(n−1,x) 仅与 f(n,x+1) , f(n,x+2), ... , f(n,x+6) 相关。
//因而，遍历 f(n−1) 中各点数和的概率，并将其相加至 f(n) 中所有相关项，即可完成 f(n−1) 至 f(n) 的递推。

    vector<double> dicesProbability(int n) {
        //点数范围是n-6n，个数是5n+1
        //真实的值s是下标+1
        vector<double> dp(6,1.0/6.0);//初始化，骰子1
        for(int i=2;i<=n;i++)//遍历骰子数量
        {    
            vector<double> tmp(5*i+1,0);//i个骰子时，有5i+1个值
            for(int j=0;j<dp.size();j++)//对上一个骰子的每一个值，能对下一个骰子产生的值起作用
                for(int k=0;k<6;k++)//下一个骰子的值是1-6，每个值概率是六分之一
                    tmp[j+k] += dp[j]/6.0;//第j+k个值可以由dp[j]产生，概率是六分之一。注意是+=，累加的，比如2+3和3+2点数都是5
            dp = tmp;//如果还有循环，dp就代表上一个骰子的值的概率
        }   
        return dp;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了94.82%的用户
*/

day25

扑克牌中的顺子

很自然地想到排序（顺子嘛），然后正常的想法是遍历0，然后知道0的数目（4个0直接true），再接下去遍历，如果后面遍历遇到重复就false，如果往后都是+1递增就继续，如果不是+1递增，就把当前值+1（同时把0的数目减少一个，相当于补充一个中间+1值），再看是不是+1，如果不是，再用一个0…这样下去，遍历完就true，0用完就false。

当有更直观的办法，如果知道0的数目，也判断了没有重复，那么这5张牌是顺子的充要条件是max-min<5。max是最大值，min是除0外的最小值。只要差值比5小，由于没有重复，那么0就可以填充在序列的中间，或者序列的外部（如果原来就是顺子，就填充在外部）

1
2
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
1
2
3
4
5
6
7
8
9
10
示例 1:

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

示例 2:

输入: [0,0,1,2,5]
输出: True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    bool isStraight(vector<int>& nums) {

    //先排序
    quickSort(nums,0,4);//数组长度为5，就直接利用了
    //统计大小王与判断重复
    int count = 0;
    //为什么只遍历前四个元素呢？
    //原因是比较前后两个元素对头尾的下标有要求，不能越界，这里少遍历一个元素
    //更重要的一点是，如果有四个大小王，那么无论如何也能形成顺子，最后一个元素不用看了
    //如果没有四个大小王，说明第四个不是0，最后一个无论如何也不是0，没必要看
    for(int i=0;i<4;i++)
    {
        if(nums[i]==0) count++;
        else if(nums[i]==nums[i+1]) return false;//如果重复就false，注意要elseif，因为0是可以重复的
    }
    //四个王就结束了
    if(count == 4) return true;
    //这里很关键，如果没有重复，那么除去0后剩下的元素要形成顺子，它们的梯度小于5即可
    return (nums[4]-nums[count]<5);
    }

private:
    void quickSort(vector<int>& nums, int l, int r)
    {
        if(l>=r) return;
        int i=l, j=r;
        while(i<j)
        {
            while(i<j && nums[j]>=nums[l]) j--;
            while(i<j && nums[i]<=nums[l]) i++;
            
            swap(nums[i],nums[j]);
        }
        swap(nums[i],nums[l]);//最后i停在比nums[l]小的元素，交换它们，把基准值放中间
        quickSort(nums,l,i-1);
        quickSort(nums,i+1,r);
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：9.7 MB, 在所有 C++ 提交中击败了92.27%的用户
*/

day26

圆圈中最后剩下的数字

约瑟夫环问题，用链表模拟会超时。约瑟夫环有数学上的递推公式，因此有动态规划的解法。

输入 n, m，记此约瑟夫环问题为 「n, m 问题」 ，设解（即最后留下的数字）为 f(n) ，则有：

「n, m 问题」：数字环为 0, 1, 2, …, n - 1，解为 f(n) ；
「n-1, m 问题」：数字环为 0, 1, 2, …, n - 2，解为 f(n-1)；

对于「n, m 问题」，首轮删除环中第 m 个数字后，得到一个长度为 n - 1 的数字环。由于有可能 m > n ，因此删除的数字为 (m−1)%n ，删除后的数字环从下个数字（即 m%n ）开始，设 t=m%n ，可得数字环：

t,t+1,t+2,…,0,1,…,t−3,t−2

删除一轮后的数字环也变为一个「n-1, m 问题」，观察以下数字编号对应关系：

「n−1,m问题」 → 「n,m问题」删除后
0 → t+0
1 → t+1
… → …
n-2 → t-2

设「n-1, m 问题」某数字为 x ，则可得递推关系：x→(x+t)%n。

换而言之，若已知「n-1, m 问题」的解 f(n - 1) ，则可通过以上公式计算得到「n, m 问题」的解 f(n)，即：

f(n)=(f(n−1)+t)%n=(f(n−1)+m%n)%n=**(f(n−1)+m)%n**

这个怎么理解呢？从正向递推去看，如果知道n-1问题的解，那么能对应到n问题的解。因为n问题首先要删除一个数变成n-1问题，而n问题的解和n-1问题的解从元素角度看必然是同一个（因为本来就是同一个问题的不同过程），只是它们在不同的序列，拥有不同的值而已。那么我们只需要把值做一次映射，就能从n-1问题的解的值映射到n问题的解的值。从n问题到n-1问题，删除了(m-1)%n，新序列每个值都减了或加了(m-1)%n+1，反过来只要加回去就可以了（加什么值最好用一个例子推）。从n=1时开始往后推，不断映射到下一个规模的解返回即可（因为最终返回的解的值是在n问题序列的解）。

1
2
3
4
5
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。
求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，
则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3
1
2
3
4
5
6
7
8
示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lastRemaining(int n, int m) {
        int x = 0;//n=1时的结果
        for(int i=2;i<=n;i++)//从n=1递推到n=2，一直递推到n
            x = (x+m)%i;
        return x;
    }   
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了93.52%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了94.35%的用户
*/

day27

股票的最大利润

动态规划，不谈了，ez

1
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
1
2
3
4
5
6
7
8
9
10
11
示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min = 0x7fffffff;
        int profit = 0;
        for(int num : prices)
        {
            //如果今天的价格比存储的最小值小，则更改最小值
            if(num<=min)
                min = num;//不可能在今天卖出，因为一定是亏的或者是0
            else//如果大的话可以卖一下，min存储了前几天的最小值
            {
                profit = max(profit,num-min);//更新利润
            }
        }
        return profit;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了88.00%的用户
内存消耗：12.4 MB, 在所有 C++ 提交中击败了79.39%的用户
*/

day28

求1+2+…+n

首先不能用while等循环，显然就用递归了。然后当n>0才递归，因此要判断，但是不能用if那些，可以考虑用布尔逻辑的短路效应。

1
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
1
2
3
4
5
6
7
8
示例 1：

输入: n = 3
输出: 6
示例 2：

输入: n = 9
输出: 45
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int sumNums(int n) {
        //n>0时，n是真，根据与表达式，还要看后面的真假，所以会做 n+=sumNums(n-1);
        //n=0时，整个表达式已经是假了，不会做后面的运算了，递归终止。
        //整个表达式的布尔真假没有意义，并不需要，只需要用来根据n的值决定做不做递归即可，最后返回n
        n && (n += sumNums(n-1));
        return n;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了25.90%的用户
*/

day29

不用加减乘除做加法

加法器原理，用位运算实现。a+b相当于无进位加法加上进位。假设无进位加法结果是n，进位是c，则a+b=n+c。无进位加法n=a^b，即两数异或，位全1或全0这一位的结果都是0。进位可以用与运算，c=(a&b)<<1，因为是进位所以要左移。

在位运算后，我们就变成了要计算n+c，这还是一个加法，因此又要一轮无进位加法和进位，像递归一样不断往复下去，直到没有进位就可以停止了。

1
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
1
2
输入: a = 1, b = 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:
    //分为无进位加法结果n和进位结果c，则a+b=n+c
    int add(int a, int b) {
        //位运算，把a当结果，把b加到a上
        int c;//存储进位，无进位加法结果直接存a上，相当于n=a^b，下一轮两个加数是n和c，则n=a，b=c；n可以用a替代
        while(b)//b不为0时进行，b为0说明加完了
        {
            //c++不支持负数左移，要转unsigned，因为整个过程只是bit串运算，不用管正负，不需要c++去解释正负
            c = (unsigned int)(a&b) << 1;//两数的每个bit的进位

            //无进位加法，加完再和进位加就可以
            a = a^b;//对于加法，都是1就进位，结果是0，都是0那结果也是0。都是1时进位在c那
            b=c;//c已经左移过了，本身是要a+c，但也不能用加法，所以还是要异或，a+c就像a+b一样，一直循环直到没进位
        }
        return a;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了69.28%的用户
*/

day30

构建乘积数组

不能用除法，所以考虑乘法，再考虑性能的话就要考虑乘法的递推。累乘的中间是割裂的，但割裂的这个i是递增的，所以这里面也有些规律可循。

再来思考一下，从形式上看有递推的效果，可以考虑动态规划，但是递推总是割裂的，差一点，原因是还要找规律。

- - - - - - -
B[0]= 1 A[1] A[2] … A[n-1] A[n]
B[1]= A[0] 1 A[2] … A[n-1] A[n]
B[2]= A[0] A[1] 1 … A[n-1] A[n]
… … … … … … …
B[n-1]= A[0] A[1] A[2] … 1 A[n]
B[n]= A[0] A[1] A[2] … A[n-1] 1

整个累乘可以分成上三角矩阵和下三角矩阵，B[i]的计算可以分成两次计算。前面动态规划差一点的原因就是中间有断裂，那么可以分别从两个三角来。比如先计算下三角的部分，那么B[0] = 1; B[i] = B[i-1]*A[i-1];，这样子迭代就计算好了下三角，注意我们是迭代的递推的，因此要从小的开始慢慢乘起来，所以在回头计算上三角时，是从下往上的，从A[n]累乘到A[1]，从B[n-1]到B[0]。

1
2
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 
即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
1
2
输入: [1,2,3,4,5]
输出: [120,60,40,30,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
class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        if(n==0) return vector<int>{};
        vector<int> B(n,0);
        B[0] = 1;
        //下三角递推
        for(int i =1;i<n;i++)
            B[i] = B[i-1]*a[i-1];
        int tmp = 1;//不能用B[i-1]来递推了，用个tmp保存递推的中间值
        //上三角递推
        for(int i =n-2;i>=0;i--)
        {
            tmp *= a[i+1];
            B[i] *= tmp;  
        }
        return B;
    }
};
/*
执行用时：16 ms, 在所有 C++ 提交中击败了86.75%的用户
内存消耗：23.7 MB, 在所有 C++ 提交中击败了91.26%的用户
*/

day31

今天忘记了，明天补一道/(ㄒoㄒ)/~~

day32

把字符串转换成整数

主要是越界的处理，要提前去判断。先说一下具体的操作：

  • 先把开头的空格遍历过去
  • 获得第一个非空格字符，如果非数字和正负号，返回0
  • 如果是负号，存储sign变量；正号同理
  • 如果是数字，说明是正号，正号可以不显式出现，因此默认情况下sign是正号。
  • 然后开始处理连续的数字，前面存储的是res，当前数字是num，num=str[i]-‘0’，res = res*10+num。在此过程中，要提前判断：
    • 如果遇到非数字字符就直接break，返回res和正负
    • 如果是数字字符，要判断拼接后会不会溢出，一个是res是否大于max/10，如果大于的话*10就溢出了。最恰好的情况是res==max/10，如果num>7就溢出了，根据正负号返回max或min。因为8的时候是正的溢出，返回max；但8不是负的溢出，但是此时的值也是min，不用再额外判断了。这种判断方式对于判断溢出、返回max和min很有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 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
27
示例 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
36
class Solution {
public:
    int strToInt(string str) {
        bool sign = true;   //默认为正数
        //先舍弃开头可能存在的空格
        int i = 0;
        while(i < str.size() && str[i] == ' ') i++;
        //接着判断首个字符是否为正负号
        if(str[i] == '-') {
            sign = false;  //该字符串片段为负数
            i++;          //移至下一个字符接着判断
        }
        else if(str[i] == '+') i++;   //如果首个字符为‘+’则sign已经默认为true而无须更改，直接移动到下一位即可
        //下面开始对非正负符号位进行判断
        if(str[i] < '0' || str[i] > '9') return 0;  //如果第一个正负号字符后的首个字符就不是数字字符(也可能第一个字符就不是正负号)，那么直接返回0
        int res = 0;   //这里res用的int型，需要更加仔细考虑边界情况，但如果用long的话可以省去一些麻烦
        int num;      //用来单独存储单个字符转换而成的数字
        int border = INT_MAX / 10;  //用来验证计算结果是否溢出int范围的数据
        while(i < str.size()){
            if(str[i] < '0' || str[i] > '9') break;  //遇到非数字字符则返回已经计算的res结果
            if(res > border || res == border && str[i] > '7')  //注意这句话要放在字符转换前，因为需要验证的位数比实际值的位数要少一位
//这里比较巧妙的地方在于 1. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值 2. 将超过最大值和低于最小值的情况都包括了
            return sign == true ? INT_MAX : INT_MIN;
            //开始对数字字符进行转换
            num = str[i] - '0';
            res = res * 10 + num;
            i++;
        }
        //最后结果根据符号添加正负号
        return sign == true ? res : -res;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了63.07%的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了78.85%的用户
*/

二进制加法

手动模拟，逐位加。把顺序先倒过来会好一点。然后这里遍历的长度是较长的那个，同时判断，如果短的到边了那就是+0。

1
2
3
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。
1
2
3
4
5
6
7
8
示例 1:

输入: a = "11", b = "10"
输出: "101"
示例 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
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
		
        //carry即表示进位又表示结果
        //carry表示进位和a、b位相加，其实就是三者中有多少个1。模二就是结果，结果是二就继续进位
        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a[i] == '1') : 0;//如果长度不够就是0，够的话用比较或者-'0'都行
            carry += i < b.size() ? (b[i] == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');//当前位相加的结果，转char
            carry /= 2;//下一位的进位，三者之和是2或3才有进位
        }

        if (carry) {//最后的处理
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了85.36%的用户
*/

day33

前n个数字二进制中1的个数

动态规划，二进制中1的个数要想到 n&(n-1)能把n中最低的1变成0。这个变成0一方面让数字变小，一方面让1的个数少了1；也即：缩小了规模同时得到了数值关系。因此就有了递推式：bit[i] = bit[ i&(i-1) ] +1。

1
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例 1:

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);//初始化，bits[0] = 0;起始条件
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;//递推，i缩小了规模，尽管缩小的程序不知道，但因为i是递增的，所以<i的都解决了
        }
        return bits;
    }
};
/*
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：7.6 MB, 在所有 C++ 提交中击败了72.76%的用户
*/

day34

单词长度的最大乘积

传统的暴力解法：遍历每个字符串对，然后再看两个字符串有没有相同字母。

先思考下一定要遍历字符串对吗，有没有递推的方式？答案是没有，因为这里不同的字符串对前后文没有关系，没有什么能够保存的状态，无法递推或分治，每对字符串都是新状态，所以一定要遍历所有字符串。同时要判断重复，就又得遍历两个字符串的字母，时间复杂度是大于n方的。

采取空间换取时间的方式，利用一个额外空间把字符串是否重复的信息存取。注意不能遍历字符串对去获取信息，这样就没有差别了。因此，要对每个字符串自身获取信息，同时利用这个信息在O(1)的复杂度判断有无重复。

O(1)的复杂度值得我们去考虑数学运算或位运算，尤其是判断重复会想到哈希表，也就想到映射。因此可以把字符串的字母映射到26位长的比特串上，如果有对应字母，对应的位置就是1。由于最多26位，所以可以用单个int来保存这个信息，也就是掩码。在判重时，两个掩码进行与运算，如果结果为0说明没有相同字母。

核心是：利用位掩码判断两个字符串是否有相同字符（进行与运算)。

1
2
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。
假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1:

输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
示例 2:

输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。
示例 3:

输入: words = ["a","aa","aaa","aaaa"]
输出: 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:
    int maxProduct(vector<string>& words) 
    {
        int length = words.size();
        vector<int> masks(length);//掩码，初始化为0。一个掩码由一位int表示

        //遍历所有字母
        for (int i = 0; i < length; i++) //遍历所有字符串，words[i]对应masks[i]
        {
            string word = words[i];
            int wordLength = word.size();
            for (int j = 0; j < wordLength; j++)//遍历某个字符串，每个掩码假想有26位对应26个字母
            {
                masks[i] |= 1 << (word[j] - 'a');//获取是哪个字母，然后把1左移到对应位置上或起来。
            }
        }
        int maxProd = 0;
        for (int i = 0; i < length; i++)//遍历每个字符串对
        {
            for (int j = i + 1; j < length; j++)//j从i后面开始就可以了，降重
            {
                if ((masks[i] & masks[j]) == 0) //没有相同字母也就是掩码对应的1位置不同，与的结果是0
                {
                    maxProd = max(maxProd, int(words[i].size() * words[j].size()));
                }
            }
        }
        return maxProd;
    }
};
/*
执行用时：40 ms, 在所有 C++ 提交中击败了76.83%的用户
内存消耗：16.1 MB, 在所有 C++ 提交中击败了47.94%的用户
*/

day35

数组中和为0的三个数

固定元素+双指针

1
2
3
4
5
6
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
//排序双指针
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        sort(nums.begin(), nums.end());//排序
        for(int i = 0; i < n - 2; i ++)//固定第一个元素，0到倒数第三个
        {
            if(i > 0 && nums[i] == nums[i - 1])//如果跟前面一个一样，那么就算找到了也是和前面答案一样的，重复了
                continue;

            int c = - nums[i];//c是剩下两个元素的和
            //头尾双指针
            int ll = i + 1, rr = n - 1;               //j从i+1开始可以避免重复

            while(ll < rr)//左右边界不重合，注意一定要遍历完，因为3+7和4+6都是答案
            {
                int sum = nums[ll] + nums[rr];
                //移动头尾双指针找到第一个target
                if(sum > c)
                    rr --;
                else if(sum < c)
                    ll ++;
                else
                {
                    ans.push_back({nums[i], nums[ll], nums[rr]});//找到了就添加答案
                    //然后要把重复的都过滤掉，不然又是一组相同答案
                    while(ll < rr && nums[ll] == nums[++ ll]);      //找到一个不重复的ll

                    while(ll < rr && nums[rr] == nums[-- rr]);
                    //过滤完后继续找下一个
                }                
            }
        }
        return ans;
    }
};
/*
执行用时：48 ms, 在所有 C++ 提交中击败了99.33%的用户
内存消耗：19.4 MB, 在所有 C++ 提交中击败了71.60%的用户
*/

day36

和大于等于target的最短子数组

这种连续子数组，尤其时牵扯到子数组的长度、连续和等等，可以用滑动窗口，更新边界即可。

1
2
3
4
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
如果不存在符合条件的子数组，返回 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,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
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minlen = INT_MAX;
        int i=0 ,j=0;//相等是因为可以只有1个元素满足
        int n = nums.size();
        int count = nums[0];
        //j不能改成<n-1，因为j=n-1时虽然到最后了，不能退出，还要再判断更新一次minlen
        while(i<=j and j<n)//i>j时返回，说明有len=1的满足
        {
            if(target <= count)//当前窗口符合，缩小左边界
            {
                minlen = min(minlen,j-i+1);//更新，窗口是i-j，大小是j-i+1
                count -= nums[i];//左边界移动更新count
                i++;
            }
            else
            {
                j++;//右边界移动，注意j++和i++顺序不同，因为一个是加新的，一个是减旧的
                if(j==n) 
                    break;//提前返回，当到最后（即使前面有符合的）不存在符合的子数组会越界
                            //因为当j到n-1时，在符合的窗口i++后可能不符合，j会尝试++，nums会越界
                            //一直不符合就更简单了，j一直++，但是又不能在while里改条件
                count += nums[j];   
            }
        }
        return (minlen==INT_MAX)?0:minlen;
    }
};
/*
执行用时：4 ms, 在所有 C++ 提交中击败了95.59%的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了79.18%的用户
*/

day37

乘积小于K的子数组

滑动窗口，控制边界。这里的重点是对子数组个数的计数，如何不重复又如何不遗漏。这里子数组的连续性给了比较好的性质。当我们的窗口乘积比较大的时候，要缩小左边界，用乘积除以左边界的值更新乘积；而当乘积小于K的时候，这时就产生了子数组，且移动右边界。

我们从移动右边界的情形来看计数，当我们要更新计数时，上一个右边界（右边界-1）已经计数好了，那么当前的这个窗口只需要更新那些新产生的子数组的个数。这些新产生的子数组必然包含了右边界的元素（因为没包含右边界元素的子数组在上一次计数就算进去了）且包含了右边界的元素一定是新产生的子数组，那么我们从右边界往左边界数子数组的个数，子数组大小从1开始（根据子数组的连续性）：[nums[j]]，[nums[j],num[j-1]],…,[nums[j],…,nums[i]]，个数就是窗口的大小j-i+1。这本质上是由于递推，上一次的子数组已经计算进去了。

因此，当乘积大时，更新左边界；当乘积符合时，更新计数，然后更新右边界。

1
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
1
2
3
4
5
6
7
8
9
10
示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
示例 2:

输入: nums = [1,2,3], k = 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
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        //滑动窗口
        int i=0, n=nums.size();
        int pro = 1;
        int res = 0;
        //根据右边界来计数，每移动一次j都要更新值，所以用for的形式移动
        for(int j=0;j<n;j++)
        {
            pro *= nums[j];
            //i能等于j是为了能跳过某个本身就大于k的数，此时i=j+1，更新计数j-i+1也是0，然后就从下一个数开始
            while(i<=j && pro >= k)//如果pro较大，移动左边界直到窗口符合条件
            {
                pro /= nums[i];
                i++;
            }
            //有符合的窗口
            res += j-i+1;
        }
        return res;
    }
};
/*
执行用时：64 ms, 在所有 C++ 提交中击败了71.68%的用户
内存消耗：59.7 MB, 在所有 C++ 提交中击败了65.21%的用户
*/

day38

和为K的子数组

本以为这题和上一题差不多，但还是不一样，因为数组中的数字可以是负的，这把思路都改变了。前面小于的话，当找到合适的窗口，里面的更小的子数组都可以算进去，这样每次滑动窗口就可以了。但是由于这里数字是负的，并不知道该移动哪个边界，移动左边界窗口和既有可能增大也有可能减小。

如果没有负数，测试了几个例子，理论上滑动窗口也是可以解决的。而当前这种情况，就要用到一种更为通用的方式：前缀和（对应前一题为前缀积）。

这里使用额外的空间，保存一些前缀和pre[i]，其中pre[i]表示从0-i所有元素的和。那么当我们每次遍历i时，能够通过之前的线性迭代很快获得当前的前缀和，这时要向前看x步找寻有没有和为k的一个子数组序列，本质上就是截出一段来，那么假设pre[i] - pre[j] =k，我们就截到了j-i这一段，注意由于我们是遍历过来的，所以j会比i小（这里的本质是，发现所有符合条件的以nums[i]结尾的子数组，既然是nums[i]结尾，那么其余元素一定是向前的）。

如果找到了这么一个pre[j] = pre[i] - k，就可以计数了。注意这样的pre[j]也许不只有一个，那么就可以用哈希表映射到次数，每次遍历完更新一下哈希表就好了。

注意前缀和是0的情况，因为为0时，也许有前缀和为0，也可以就是pre[i]而不减去其他前缀和，因此hash[0]本身应该多1，即初始化为1，其他为0。

1
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
1
2
3
4
5
6
7
8
9
示例 1：

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2：

输入:nums = [1,2,3], k = 3
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;//key为前缀和，value为次数
        mp[0] = 1;
        int count = 0, pre = 0;
        for (int x:nums) {
            pre += x;//前缀和
            if (mp.find(pre - k) != mp.end()) {//如果找得到pre-k的前缀和，则找到一组子数组
                count += mp[pre - k];//mp的值是pre-k的前缀和出现的次数
            }
            mp[pre]++;//pre这个对应的前缀和+1，初始为0
        }
        return count;
    }
};
/*
执行用时：48 ms, 在所有 C++ 提交中击败了99.09%的用户
内存消耗：35.1 MB, 在所有 C++ 提交中击败了72.84%的用户
*/

day39

0 和 1 个数相同的子数组

核心思想就是把0看成-1，这样个数相同的子数组的和就是0，这样问题归约为：最长和为0的连续子数组。这与上一题相似，只不过上一题是个数，这一题是最长长度。假设有前缀和count，位置为i，那么上一次出现的count处，位置为j，j+1——i这一段子数组就符合要求。因此使用一个哈希表，把前缀和映射到count出现的第一个位置（这样能使子数组最长）。具体的，这个第一个位置，只要我们在找到count时不更新即可，如果找不到count就更新。

1
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
1
2
3
4
5
6
7
8
9
10
11

示例 1：

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 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
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int maxLength = 0;
        unordered_map<int, int> mp;//长度就映射到位置，个数就映射到个数
        int counter = 0;
        mp[counter] = -1;//如果此时前缀和为0的话，就是从头开始，这个要手动初始化
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            if (num == 1) {//为1就累加前缀和
                counter++;
            } 
            else {//为0就前缀和减一
                counter--;
            }
            if (mp.count(counter)) {//从下标prevIndex+1 到下标 i 的子数组中有相同数量的 0 和 1，该子数组的长度为i−prevIndex
                int prevIndex = mp[counter];
                maxLength = max(maxLength, i - prevIndex);
            } 
            else {//如果counter 的值在哈希表中不存在，则将当前余数和当前下标 i 的键值对存入哈希表中。
                mp[counter] = i;//第一次出现count的位置
            }
        }
        return maxLength;
    }
};
/*
执行用时：100 ms, 在所有 C++ 提交中击败了78.11%的用户
内存消耗：81.7 MB, 在所有 C++ 提交中击败了74.39%的用户
*/

day40

左右两边子数组的和相等

很简单的一道题，实际上就是遍历i，看每个i能不能当中心下标，那么在遍历的时候，累加前缀和和累减后缀和就可以判断了

1
2
3
4
5
6
7
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
示例 1：

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 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
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //实际上就是遍历i，看每个i能不能当中心下标
        //那么在遍历的时候，累加前缀和和累减后缀和就可以判断了
        int after = 0;
        int pre = 0;
        int res = -1;
        for(int num:nums)
            after += num;
        for(int i=0;i<nums.size();i++)
        {
            after -= nums[i];//首先要减去这个值，把i空出来
            if(pre == after)//然后pre先别加再判断
            {
                res = i;
                break;//找最左边的
            }
                
            pre += nums[i];//往后移，pre填上
        }
        return res;
    }
};
/*
执行用时：12 ms, 在所有 C++ 提交中击败了97.48%的用户
内存消耗：30.1 MB, 在所有 C++ 提交中击败了92.36%的用户
*/