Leetcode301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

1
2

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

1
2

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

1
2

Input: ")("
Output: [""]

这道题让移除最少的括号使得给定字符串为一个合法的含有括号的字符串，我们从小数学里就有括号，所以应该对合法的含有括号的字符串并不陌生，字符串中的左右括号数应该相同，而且每个右括号左边一定有其对应的左括号，而且题目中给的例子也说明了去除方法不唯一，需要找出所有合法的取法。参考了网上大神的解法，这道题首先可以用 BFS 来解，我把给定字符串排入队中，然后取出检测其是否合法，若合法直接返回，不合法的话，对其进行遍历，对于遇到的左右括号的字符，去掉括号字符生成一个新的字符串，如果这个字符串之前没有遇到过，将其排入队中，用 HashSet 记录一个字符串是否出现过。对队列中的每个元素都进行相同的操作，直到队列为空还没找到合法的字符串的话，那就返回空集，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_set<string> visited{{s}};
        queue<string> q{{s}};
        bool found = false;
        while (!q.empty()) {
            string t = q.front(); q.pop();
            if (isValid(t)) {
                res.push_back(t);
                found = true;
            }
            if (found) continue;
            for (int i = 0; i < t.size(); ++i) {
                if (t[i] != '(' && t[i] != ')') continue;
                string str = t.substr(0, i) + t.substr(i + 1);
                if (!visited.count(str)) {
                    q.push(str);
                    visited.insert(str);
                }
            }
        }
        return res;
    }
    bool isValid(string t) {
        int cnt = 0;
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] == '(') ++cnt;
            else if (t[i] == ')' && --cnt < 0) return false;
        }
        return cnt == 0;
    }
};

下面来看一种递归解法，这种解法首先统计了多余的半括号的数量，用 cnt1 表示多余的左括号，cnt2 表示多余的右括号，因为给定字符串左右括号要么一样多，要么左括号多，要么右括号多，也可能左右括号都多，比如 “)(“。所以 cnt1 和 cnt2 要么都为0，要么都大于0，要么一个为0，另一个大于0。好，下面进入递归函数，首先判断，如果当 cnt1 和 cnt2 都为0时，说明此时左右括号个数相等了，调用 isValid 子函数来判断是否正确，正确的话加入结果 res 中并返回即可。否则从 start 开始遍历，这里的变量 start 表示当前递归开始的位置，不需要每次都从头开始，会有大量重复计算。而且对于多个相同的半括号在一起，只删除第一个，比如 “())”，这里有两个右括号，不管删第一个还是删第二个右括号都会得到 “()”，没有区别，所以只用算一次就行了，通过和上一个字符比较，如果不相同，说明是第一个右括号，如果相同则直接跳过。此时来看如果 cnt1 大于0，说明此时左括号多，而如果当前字符正好是左括号的时候，可以删掉当前左括号，继续调用递归，此时 cnt1 的值就应该减1，因为已经删掉了一个左括号。同理，如果 cnt2 大于0，说明此时右括号多，而如果当前字符正好是右括号的时候，可以删掉当前右括号，继续调用递归，此时 cnt2 的值就应该减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

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        int cnt1 = 0, cnt2 = 0;
        for (char c : s) {
            cnt1 += (c == '(');
            if (cnt1 == 0) cnt2 += (c == ')');
            else cnt1 -= (c == ')');
        }
        helper(s, 0, cnt1, cnt2, res);
        return res;
    }
    void helper(string s, int start, int cnt1, int cnt2, vector<string>& res) {
        if (cnt1 == 0 && cnt2 == 0) {
            if (isValid(s)) res.push_back(s);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            if (i != start && s[i] == s[i - 1]) continue;
            if (cnt1 > 0 && s[i] == '(') {
                helper(s.substr(0, i) + s.substr(i + 1), i, cnt1 - 1, cnt2, res);
            }
            if (cnt2 > 0 && s[i] == ')') {
                helper(s.substr(0, i) + s.substr(i + 1), i, cnt1, cnt2 - 1, res);
            }
        }
    }
    bool isValid(string t) {
        int cnt = 0;
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] == '(') ++cnt;
            else if (t[i] == ')' && --cnt < 0) return false;
        }
        return cnt == 0;
    }
};

下面这种解法由热心网友 fvglty 提供，应该算是一种暴力搜索的方法，并没有太多的技巧在里面，但是思路直接了当，可以作为为面试中最先提出的解法。思路是先将s放到一个 HashSet 中，然后进行该集合 cur 不为空的 while 循环，此时新建另一个集合 next，遍历之前的集合 cur，若某个字符串是合法的括号，直接加到结果 res 中，并且看若 res 不为空，则直接跳过。跳过的部分实际上是去除括号的操作，由于不知道该去掉哪个半括号，所以只要遇到半括号就都去掉，然后加入另一个集合 next 中，这里实际上保存的是下一层的候选者。当前的 cur 遍历完成后，若 res 不为空，则直接返回，因为这是当前层的合法括号，一定是移除数最少的。若 res 为空，则将 next 赋值给 cur，继续循环，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        unordered_set<string> cur{{s}};
        while (!cur.empty()) {
            unordered_set<string> next;
            for (auto &a : cur) {
                if (isValid(a)) res.push_back(a);
                if (!res.empty()) continue;
                for (int i = 0; i < a.size(); ++i) {
                    if (a[i] != '(' && a[i] != ')') continue;
                    next.insert(a.substr(0, i) + a.substr(i + 1));
                }
            }
            if (!res.empty()) return res;
            cur = next;
        }
        return res;
    }
    bool isValid(string t) {
        int cnt = 0;
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] == '(') ++cnt;
            else if (t[i] == ')' && --cnt < 0) return false;
        }
        return cnt == 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

class Solution {
public:
    
    vector<pair<char, int> > data;
    vector<string> ret;
    int maxlength;
    
    string gen(vector<pair<char, int>> ans) {
        string str;
        for (const auto& a : ans)
            str += string(a.second, a.first);
        return str;
    }
    
    // cur是当前要枚举哪一块字符串，s是字符串的和，左括号+1，右括号-1
    // len是当前选中的字符数量，len==maxlength
    // s最后应该为0才合法
    void dfs(int cur, int s, int len, vector<pair<char, int>>& ans) {
        if (cur == data.size()) {
            if (!s && len == maxlength)
                ret.push_back(gen(ans));
            return;
        }

        if (data[cur].first != '(' && data[cur].first != ')') {
            if (len + data[cur].second > maxlength)
                return;
            ans.push_back(data[cur]);
            dfs(cur+1, s, len+data[cur].second, ans);
            ans.pop_back();
            return;
        }
        
        ans.push_back(data[cur]);
        for (int i = 0; i <= data[cur].second; i ++) {
            if (data[cur].first == '(') {
                if (len + i <= maxlength) {
                    ans[cur].second = i; // ans
                    dfs(cur+1, s+i, len+i, ans);
                }
            }
            else { // ')'
                if (s >= i && len + i <= maxlength) {
                    ans[cur].second = i;
                    dfs(cur+1, s-i, len+i, ans);
                }
            }
        }
        
        ans.pop_back();
    }
    
    vector<string> removeInvalidParentheses(string str) {
        int cnt = 0, s = 0, r = 0;
        for (int i = 0; i < str.length(); i ++) {
            if (!i || str[i] == str[i-1])
                cnt ++;
            else {
                data.push_back(make_pair(str[i-1], cnt));
                cnt = 1;
            }
            
            if (str[i] == '(')
                s ++;
            else if (str[i] == ')') {
                if (s) s --;
                else r ++;
            }
        }
        data.push_back(make_pair(str.back(), cnt));
        maxlength = str.length() - (s+r);
        
        vector<pair<char, int> > ans;
        dfs(0, 0, 0, ans);
        
        return ret;
    }
};

Leetcode303. Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

1
2
3
4
5

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class NumArray {
public:
    vector<int> prefix;
    
    NumArray(vector<int>& nums) {
        prefix.push_back(0);
        for(int i=0;i<nums.size();i++)
        {
            prefix.push_back(prefix[i]+nums[i]);
        }
    }
    
    int sumRange(int i, int j) {
        return prefix[j+1]-prefix[i];
    }
};

Leetcode304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, handle multiple queries of the following type:

Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Implement the NumMatrix class:

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:

1
2
3
4
5

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]

Explanation

1
2
3
4

NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

求二维数组中指定左上角和右下角的长方形内所有数字的和。给定的二维数组是不会变的，每次变得是求和的范围。

解题方法：预先求和

这个题肯定是用先把所有的和求出来，然后查找的时候直接计算就行了。我们使用的这个求和矩阵保存的是每个位置到整个矩阵的左上角元素这个矩形的所有元素和。为了方便起见，利用了和DP类似的添加边界的方法，也就是在最左边和最上边添加了全是0的列和行，这样能保证在求和的时候，每个位置的和是左边的和+上边的和+自身-左上元素的和。

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

class NumMatrix {
public:
    vector<vector<int> > dp;
    NumMatrix(vector<vector<int>>& matrix) {
        int width = matrix.size();
        if (width == 0)
            return;
        int height = matrix[0].size();
        
        dp.resize(width+1);
        for (int i = 0; i < dp.size(); i++)
			dp[i].resize(height+1, 0);
        
        for (int i = 1; i <= width; i ++)
            for (int j = 1; j <= height; j ++)
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + matrix[i-1][j-1];
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1] + dp[row1+1][col1+1] - dp[row1-1][col2] - dp[row2][col1-1];
    }
};

Leetcode305. Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

1
2

Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]

Explanation:

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

1
2
3

0 0 0
0 0 0
0 0 0

Operation 1: addLand(0, 0) turns the water at grid[0][0] into a land.

1
2
3

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation 2: addLand(0, 1) turns the water at grid[0][1] into a land.

1
2
3

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation 3: addLand(1, 2) turns the water at grid[1][2] into a land.

1
2
3

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation 4: addLand(2, 1) turns the water at grid[2][1] into a land.

1
2
3

1 1 0
0 0 1   Number of islands = 3
0 1 0

这道题是之前那道 Number of Islands 的拓展，难度增加了不少，因为这次是一个点一个点的增加，每增加一个点，都要统一一下现在总共的岛屿个数，最开始初始化时没有陆地，如下：

1
2
3

0 0 0
0 0 0
0 0 0

假如在(0, 0)的位置增加一个陆地，那么此时岛屿数量为1：

1
2
3

1 0 0
0 0 0
0 0 0

假如再在(0, 2)的位置增加一个陆地，那么此时岛屿数量为2：

1
2
3

1 0 1
0 0 0
0 0 0

假如再在(0, 1)的位置增加一个陆地，那么此时岛屿数量却又变为1：

1
2
3

1 1 1
0 0 0
0 0 0

假如再在(1, 1)的位置增加一个陆地，那么此时岛屿数量仍为1：

1
2
3

1 1 1
0 1 0
0 0 0

为了解决这种陆地之间会合并的情况，最好能够将每个陆地都标记出其属于哪个岛屿，这样就会方便统计岛屿个数。这种群组类问题，很适合使用联合查找 Union Find 来做，又叫并查集 Disjoint Set，一般来说，UF 算法的思路是每个个体先初始化为不同的群组，然后遍历有关联的两个个体，如果发现其 getRoot 函数的返回值不同，则手动将二者加入一个群组，然后总群组数自减1。这里就要分别说一下 root 数组，和 getRoot 函数。两个同群组的个体，通过 getRoot 函数一定会返回相同的值，但是其在 root 数组中的值不一定相同，可以类比成 getRoot 函数返回的是祖先，如果两个人的祖先相同，那么其是属于一个家族的（这里不是指人类共同的祖先哈）。root 可以用数组或者 HashMap 来表示，如果个体是数字的话，那么数组就 OK，如果个体是字符串的话，可能就需要用 HashMap 了。root 数组的初始化可以有两种，可以均初始化为 -1，或者都初始化为不同的数字，博主一般喜欢初始化为不同的数字。getRoot 函数的写法也可用递归或者迭代的方式。

那么具体来看这道题吧，此题跟经典的 UF 使用场景有一点点的区别，因为一般的场景中两个个体之间只有两种关系，属于一个群组或者不属于同一个群组，而这道题里面由于 water 的存在，就多了一种情况，只需要事先检测一下当前位置是不是岛屿就行了，总之问题不大。一般来说 root 数组都是使用一维数组，方便一些，那么这里就可以将二维数组 encode 为一维的，于是需要一个长度为 m*n 的一维数组来标记各个位置属于哪个岛屿，假设每个位置都是一个单独岛屿，岛屿编号可以用其坐标位置表示，但是初始化时将其都赋为 -1，这样方便知道哪些位置尚未变成岛屿。然后开始遍历陆地数组，若某个岛屿位置编码的 root 值不为 -1，说明这是一个重复出现的位置，不需要重新计算了，直接将 cnt 加入结果 res 中。否则将其岛屿编号设置为其坐标位置，然后岛屿计数加1，此时开始遍历其上下左右的位置，遇到越界或者岛屿标号为 -1 的情况直接跳过，现在知道初始化为 -1 的好处了吧，遇到是 water 的地方直接跳过。否则用 getRoot 来查找邻居位置的岛屿编号，同时也用 getRoot 来查找当前点的编号，这一步就是经典的 UF 算法的操作了，因为当前这两个 land 是相邻的，它们是属于一个岛屿，所以其 getRoot 函数的返回值 suppose 应该是相等的，但是如果返回值不同，说明需要合并岛屿，将两个返回值建立关联，并将岛屿计数 cnt 减1。当遍历完当前点的所有邻居时，该合并的都合并完了，将此时的岛屿计数 cnt 存入结果中，参见代码如下：

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:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        vector<int> res;
        int cnt = 0;
        vector<int> roots(m * n, -1);
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        for (auto &pos : positions) {
            int id = n * pos[0] + pos[1];
            if (roots[id] != -1) {
                res.push_back(cnt);
                continue;
            }
            roots[id] = id;
            ++cnt;
            for (auto dir : dirs) {
                int x = pos[0] + dir[0], y = pos[1] + dir[1], cur_id = n * x + y;
                if (x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1) continue;
                int p = findRoot(roots, cur_id), q = findRoot(roots, id);
                if (p != q) {
                    roots[p] = q;
                    --cnt;
                }
            }
            res.push_back(cnt);
        }
        return res;
    }
    int findRoot(vector<int>& roots, int id) {
        return (id == roots[id]) ? id : findRoot(roots, roots[id]);
    }
};

Leetcode306. Additive Number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3is invalid.

Example 1:

1
2
3
4

Input: "112358"
Output: true 
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

1
2
3
4

Input: "199100199"
Output: true 
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

这道题定义了一种加法数，就是至少含有三个数字，除去前两个数外，每个数字都是前面两个数字的和，题目中给了许多例子，也限定了一些不合法的情况，比如两位数以上不能以0开头等等，让我们来判断一个数是否是加法数。

其实这题可用Brute Force的思想来解，我们让第一个数字先从一位开始，第二个数字从一位，两位，往高位开始搜索，前两个数字确定了，相加得到第三位数字，三个数组排列起来形成一个字符串，和原字符串长度相比，如果小于原长度，那么取出上一次计算的第二个和第三个数，当做新一次计算的前两个数，用相同的方法得到第三个数，再加入当前字符串，再和原字符串长度相比，以此类推，直到当前字符串长度不小于原字符串长度，比较两者是否相同，相同返回true，不相同则继续循环。如果所有情况都遍历完了还是没有返回true，则说明不是Additive Number，返回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

class Solution {
public:
    bool isAdditiveNumber(string num) {
        for (int i = 1; i < num.size(); ++i) {
            string s1 = num.substr(0, i);
            if (s1.size() > 1 && s1[0] == '0') break;
            for (int j = i + 1; j < num.size(); ++j) {
                string s2 = num.substr(i, j - i);
                long d1 = stol(s1), d2 = stol(s2);
                if ((s2.size() > 1 && s2[0] == '0')) break;
                long next = d1 + d2;
                string nextStr = to_string(next);
                if (nextStr != num.substr(j, nextStr.length())) continue; // optimization here
                string allStr = s1 + s2 + nextStr;
                while (allStr.size() < num.size()) {
                    d1 = d2;
                    d2 = next;
                    next = d1 + d2;
                    nextStr = to_string(next);
                    allStr += nextStr;
                }
                if (allStr == num) return true;
            }
        }
        return false;
    }
};

Leetcode307. Range Sum Query - Mutable

Given an integer array nums , find the sum of the elements between indices i and j ( i ≤ j ), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

1
2
3
4
5

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

这道题是之前那道 Range Sum Query - Immutable 的延伸，之前那道题由于数组的内容不会改变，所以我们只需要建立一个累计数组就可以支持快速的计算区间值了，而这道题说数组的内容会改变，如果我们还是用之前的方法建立累计和数组，那么每改变一个数字，之后所有位置的数字都要改变，这样如果有很多更新操作的话，就会十分不高效，估计很难通过吧。But，被 OJ 分分钟打脸， brute force 完全没有问题啊，这年头，装个比不容易啊。直接就用个数组 data 接住 nums，然后要更新就更新，要求区域和，就遍历求区域和，就这样 naive 的方法还能 beat 百分之二十多啊，这不科学啊，参见代码如下：

解法一：

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

class NumArray {
public:
    NumArray(vector<int> nums) {
        data = nums;
    }
    
    void update(int i, int val) {
        data[i] = val;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; ++k) {
            sum += data[k];
        }
        return sum;
    }
    
private:
    vector<int> data;
};

上面的方法最大的问题，就是求区域和不高效，如果数组很大很大，每次求一个巨型的区间的和，都要一个一个的遍历去累加，累啊～但是一般的累加数组又无法应对这里的 update 操作，随便修改一个数字的话，那么其之后的所有累加和都会发生改变。所以解决方案就是二者折中一下，分块累加，各不干预。就是将原数组分为若干块，怎么分呢，这里就让每个 block 有 sqrt(n) 个数字就可以了，这个基本是让 block 的个数跟每个 blcok 中数字的个数尽可能相同的分割方法。然后我们就需要一个大小跟 block 个数相同的数组，来保存每个 block 的数字之和。在需要更新的时候，我们就先确定要更新的位置在哪个 block 里，然后只更新该 block 的和。而对于求区域和操作，我们还是要分别确定i和j分别属于哪个 block，若属于同一个 block，那么直接遍历累加即可，若属于不同的，则先从i累加到该 blcok 的末尾，然后中间横跨的那些 block 可以直接将和累加，对于j所在的 blcok，则从该 block 的开头遍历累加到j即可，参见代码如下：

解法二：

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

class NumArray {
public:
    NumArray(vector<int> nums) {
        if (nums.empty()) return;
        data = nums;
        double root = sqrt(data.size());
        len = ceil(data.size() / root);
        block.resize(len);
        for (int i = 0; i < data.size(); ++i) {
            block[i / len] += data[i];
        }
    }
    
    void update(int i, int val) {
        int idx = i / len;
        block[idx] += val - data[i];
        data[i] = val;
    }
    
    int sumRange(int i, int j) {
        int sum = 0;
        int start = i / len, end = j / len;
        if (start == end) {
            for (int k = i; k <= j; ++k) {
                sum += data[k];
            }
            return sum;
        }
        for (int k = i; k < (start + 1) * len; ++k) {
            sum += data[k];
        }
        for (int k = start + 1; k < end; ++k) {
            sum += block[k];
        }
        for (int k = end * len; k <= j; ++k) {
            sum += data[k];
        }
        return sum;
    }
    
private:
    int len;
    vector<int> data, block;
};

Leetcode309. Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the i th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

1
2
3

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

这道题加入了一个冷冻期Cooldown之说，就是如果某天卖了股票，那么第二天不能买股票，有一天的冷冻期。此题需要维护三个一维数组buy, sell，和rest。其中：

• buy[i]表示在第i天之前最后一个操作是买，此时的最大收益。
• sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益。
• rest[i]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。

我们写出递推式为：

1
2
3

buy[i]  = max(rest[i-1] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

上述递推式很好的表示了在买之前有冷冻期，买之前要卖掉之前的股票。一个小技巧是如何保证[buy, rest, buy]的情况不会出现，这是由于buy[i] <= rest[i]， 即rest[i] = max(sell[i-1], rest[i-1])，这保证了[buy, rest, buy]不会出现。

另外，由于冷冻期的存在，我们可以得出rest[i] = sell[i-1]，这样，我们可以将上面三个递推式精简到两个：

1
2

buy[i]  = max(sell[i-2] - price, buy[i-1]) 
sell[i] = max(buy[i-1] + price, sell[i-1])

我们还可以做进一步优化，由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MIN, pre_buy = 0, sell = 0, pre_sell = 0;
        for (int price : prices) {
            pre_buy = buy;
            buy = max(pre_sell - price, pre_buy);
            pre_sell = sell;
            sell = max(pre_buy + price, pre_sell);
        }
        return sell;
    }
};

我自己的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if (len == 0)
            return 0;
        vector<int> buy(len+1, 0), sell(len+1, 0);
        buy[1] = -prices[0];
        for (int i = 2; i < len+1; i ++) {
            buy[i] = max(sell[i-2]-prices[i-1], buy[i-1]);
            sell[i] = max(sell[i-1], buy[i-1]+prices[i-1]);
        }
        return sell[len];
    }
};

Leetcode310. Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs’ root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example 1:

1
2
3

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

1
2

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Example 3:

1
2

Input: n = 1, edges = []
Output: [0]

Example 4:

1
2

Input: n = 2, edges = [[0,1]]
Output: [0,1]

大家推崇的方法是一个类似剥洋葱的方法，就是一层一层的褪去叶节点，最后剩下的一个或两个节点就是我们要求的最小高度树的根节点，这种思路非常的巧妙，而且实现起来也不难，跟之前那到课程清单的题一样，我们需要建立一个图g，是一个二维数组，其中g[i]是一个一维数组，保存了i节点可以到达的所有节点。我们开始将所有只有一个连接边的节点(叶节点)都存入到一个队列queue中，然后我们遍历每一个叶节点，通过图来找到和其相连的节点，并且在其相连节点的集合中将该叶节点删去，如果删完后此节点也也变成一个叶节点了，加入队列中，下一轮删除。那么我们删到什么时候呢，当节点数小于等于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> findMinHeightTrees(int n, vector<pair<int, int> >& edges) {
        if (n == 1) return {0};
        vector<int> res;
        vector<unordered_set<int>> adj(n);
        queue<int> q;
        for (auto edge : edges) {
            adj[edge.first].insert(edge.second);
            adj[edge.second].insert(edge.first);
        }
        for (int i = 0; i < n; ++i) {
            if (adj[i].size() == 1) q.push(i);
        }
        while (n > 2) {
            int size = q.size();
            n -= size;
            for (int i = 0; i < size; ++i) {
                int t = q.front(); q.pop();
                for (auto a : adj[t]) {
                    adj[a].erase(t);
                    if (adj[a].size() == 1) q.push(a);
                }
            }
        }
        while (!q.empty()) {
            res.push_back(q.front()); q.pop();
        }
        return res;
    }
};

Leetcode312. Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i] * nums[right]coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

1
2
3
4

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

这道题提出了一种打气球的游戏，每个气球都对应着一个数字，每次打爆一个气球，得到的金币数是被打爆的气球的数字和其两边的气球上的数字相乘，如果旁边没有气球了，则按1算，以此类推，求能得到的最多金币数。参见题目中给的例子，题意并不难理解。那么大家拿到题后，总是会习惯的先去想一下暴力破解法吧，这道题的暴力搜索将相当的复杂，因为每打爆一个气球，断开的地方又重新挨上，所有剩下的气球又要重新遍历，这使得分治法不能 work，整个的时间复杂度会相当的高，不要指望可以通过 OJ。而对于像这种求极值问题，一般都要考虑用动态规划 Dynamic Programming 来做，维护一个二维动态数组 dp，其中 dp[i][j] 表示打爆区间 [i,j] 中的所有气球能得到的最多金币。题目中说明了边界情况，当气球周围没有气球的时候，旁边的数字按1算，这样可以在原数组两边各填充一个1，方便于计算。这道题的最难点就是找状态转移方程，还是从定义式来看，假如区间只有一个数，比如 dp[i][i]，那么计算起来就很简单，直接乘以周围两个数字即可更新。如果区间里有两个数字，就要算两次了，先打破第一个再打破了第二个，或者先打破第二个再打破第一个，比较两种情况，其中较大值就是该区间的 dp 值。假如区间有三个数呢，比如 dp[1][3]，怎么更新呢？如果先打破第一个，剩下两个怎么办呢，难道还要分别再遍历算一下吗？这样跟暴力搜索的方法有啥区别呢，还要 dp 数组有啥意思。所谓的状态转移，就是假设已知了其他状态，来推导现在的状态，现在是想知道 dp[1][3] 的值，那么如果先打破了气球1，剩下了气球2和3，若之前已经计算了 dp[2][3] 的话，就可以使用其来更新 dp[1][3] 了，就是打破气球1的得分加上 dp[2][3]。那假如先打破气球2呢，只要之前计算了 dp[1][1] 和 dp[3][3]，那么三者加起来就可以更新 dp[1][3]。同理，先打破气球3，就用其得分加上 dp[1][2] 来更新 dp[1][3]。

那么对于有很多数的区间 [i, j]，如何来更新呢？现在是想知道 dp[i][j] 的值，这个区间可能比较大，但是如果知道了所有的小区间的 dp 值，然后聚沙成塔，逐步的就能推出大区间的 dp 值了。还是要遍历这个区间内的每个气球，就用k来遍历吧，k在区间 [i, j] 中，假如第k个气球最后被打爆，那么此时区间 [i, j] 被分成了三部分，[i, k-1]，[k]，和 [k+1, j]，只要之前更新过了 [i, k-1] 和 [k+1, j] 这两个子区间的 dp 值，可以直接用 dp[i][k-1] 和 dp[k+1][j]，那么最后被打爆的第k个气球的得分该怎么算呢，你可能会下意识的说，就乘以周围两个气球被 nums[k-1] * nums[k] * nums[k+1]，但其实这样是错误的，为啥呢？dp[i][k-1] 的意义是什么呢，是打爆区间 [i, k-1] 内所有的气球后的最大得分，此时第 k-1 个气球已经不能用了，同理，第 k+1 个气球也不能用了，相当于区间 [i, j] 中除了第k个气球，其他的已经爆了，那么周围的气球只能是第 i-1 个，和第 j+1 个了，所以得分应为 nums[i-1] * nums[k] * nums[j+1]，分析到这里，状态转移方程应该已经跃然纸上了吧，如下所示：

 dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j])                 ( i ≤ k ≤ j )

有了状态转移方程了，就可以写代码，下面就遇到本题的第二大难点了，区间的遍历顺序。一般来说，遍历所有子区间的顺序都是i从0到n，然后j从i到n，然后得到的 [i, j] 就是子区间。但是这道题用这种遍历顺序就不对，在前面的分析中已经说了，这里需要先更新完所有的小区间，然后才能去更新大区间，而用这种一般的遍历子区间的顺序，会在更新完所有小区间之前就更新了大区间，从而不一定能算出正确的dp值，比如拿题目中的那个例子 [3, 1, 5, 8] 来说，一般的遍历顺序是：

[3] -> [3, 1] -> [3, 1, 5] -> [3, 1, 5, 8] -> [1] -> [1, 5] -> [1, 5, 8] -> [5] -> [5, 8] -> [8] 

显然不是我们需要的遍历顺序，正确的顺序应该是先遍历完所有长度为1的区间，再是长度为2的区间，再依次累加长度，直到最后才遍历整个区间：

[3] -> [1] -> [5] -> [8] -> [3, 1] -> [1, 5] -> [5, 8] -> [3, 1, 5] -> [1, 5, 8] -> [3, 1, 5, 8]

这里其实只是更新了 dp 数组的右上三角区域，最终要返回的值存在 dp[1][n] 中，其中n是两端添加1之前数组 nums 的个数。参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int len = 1; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1;
                for (int k = i; k <= j; ++k) {
                    dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }
        return dp[1][n];
    }
};

对于题目中的例子[3, 1, 5, 8]，得到的dp数组如下：

1
2
3
4
5
6

0    0    0    0    0    0
0    3    30   159  167  0
0    0    15   135  159  0
0    0    0    40   48   0
0    0    0    0    40   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

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        return burst(nums, dp, 1 , n);
	    }
    int burst(vector<int>& nums, vector<vector<int>>& dp, int i, int j) {
        if (i > j) return 0;
        if (dp[i][j] > 0) return dp[i][j];
        int res = 0;
        for (int k = i; k <= j; ++k) {
            res = max(res, nums[i - 1] * nums[k] * nums[j + 1] + burst(nums, dp, i, k - 1) + burst(nums, dp, k + 1, j));
        }
        dp[i][j] = res;
        return res;
    }
};

Leetcode313. Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of sizek. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

1. 1 is a super ugly number for any given primes.
2. The given numbers in primes are in ascending order.
3. 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

这道题让我们求超级丑陋数，是之前那两道Ugly Number 丑陋数和Ugly Number II 丑陋数之二的延伸，质数集合可以任意给定，这就增加了难度。但是本质上和Ugly Number II 丑陋数之二没有什么区别，由于我们不知道质数的个数，我们可以用一个idx数组来保存当前的位置，然后我们从每个子链中取出一个数，找出其中最小值，然后更新idx数组对应位置，注意有可能最小值不止一个，要更新所有最小值的位置，参见代码如下：

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

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> res(1, 1), idx(primes.size(), 0);
        while (res.size() < n) {
            vector<int> tmp;
            int mn = INT_MAX;
            for (int i = 0; i < primes.size(); ++i) {
                tmp.push_back(res[idx[i]] * primes[i]);
            }
            for (int i = 0; i < primes.size(); ++i) {
                mn = min(mn, tmp[i]);
            }
            for (int i = 0; i < primes.size(); ++i) {
                if (mn == tmp[i]) ++idx[i];
            }
            res.push_back(mn);
        }
        return res.back();
    }
};

Leetcode315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

1
2
3
4
5
6
7

Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

这道题给定了一个数组，让我们计算每个数字右边所有小于这个数字的个数，目测不能用 brute force，OJ 肯定不答应，那么为了提高运算效率，首先可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Binary Search
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int left = 0, right = t.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (t[mid] >= nums[i]) right = mid;
                else left = mid + 1;
            }
            res[i] = right;
            t.insert(t.begin() + right, nums[i]);
        }
        return res;
    }
};

上面使用二分搜索法是一种插入排序的做法，我们还可以用 C++ 中的 STL 的一些自带的函数，比如求距离 distance，或是求第一个不小于当前数字的函数 lower_bound()，这里利用这两个函数代替了上一种方法中的二分搜索的部分，两种方法的核心思想都是相同的，构造有序数组，找出新加进来的数组在有序数组中对应的位置存入结果中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

// Insert Sort
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
            res[i] = d;
            t.insert(t.begin() + d, nums[i]);
        }
        return res;
    }
};

再来看一种利用二分搜索树来解的方法，构造一棵二分搜索树，稍有不同的地方是需要加一个变量 smaller 来记录比当前结点值小的所有结点的个数，每插入一个结点，会判断其和根结点的大小，如果新的结点值小于根结点值，则其会插入到左子树中，此时要增加根结点的 smaller，并继续递归调用左子结点的 insert。如果结点值大于根结点值，则需要递归调用右子结点的 insert 并加上根结点的 smaller，并加1，参见代码如下：

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

// Binary Search Tree
class Solution {
public:
    struct Node {
        int val, smaller;
        Node *left, *right;
        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
    };
    int insert(Node*& root, int val) {
        if (!root) return (root = new Node(val, 0)), 0;
        if (root->val > val) return root->smaller++, insert(root->left, val);
        return insert(root->right, val) + root->smaller + (root->val < val ? 1 : 0);
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        Node *root = NULL;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] = insert(root, nums[i]);
        }
        return res;
    }
};

我们通过一个实例来看看。假设我们有两个已排序的序列等待合并，分别是L = { 8, 12, 16, 22, 100 }和R = { 7, 26, 55, 64, 91 }。一开始我们用指针 lPtr = 0 指向 LL 的头部，rPtr = 0 指向 RR 的头部。记已经合并好的部分为 MM。

1
2
3

L = [8, 12, 16, 22, 100]   R = [7, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr

我们发现 lPtr 指向的元素大于 rPtr 指向的元素，于是把 rPtr 指向的元素放入答案，并把 rPtr 后移一位。

1
2
3

L = [8, 12, 16, 22, 100]   R = [7, 26, 55, 64, 91]  M = [7]
     |                              |
    lPtr                          rPtr

接着我们继续合并：

1
2
3

L = [8, 12, 16, 22, 100]   R = [7, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr

此时 lPtr 比 rPtr 小，把 lPtr 对应的数加入答案。如果我们要统计 88 的右边比 88 小的元素，这里 77 对它做了一次贡献。如果带合并的序列L={8,12,16,22,100}，R={7,7,7,26,55,64,91}，那么一定有一个时刻，lPtr 和 rPtr 分别指向这些对应的位置：

1
2
3

L = [8, 12, 16, 22, 100]   R = [7, 7, 7, 26, 55, 64, 91]  M = [7, 7, 7]
     |                                   |
    lPtr                                rPtr

下一步我们就是把 88 加入 MM 中，此时三个 77 对 88 的右边比 88 小的元素的贡献为 33。以此类推，我们可以一边合并一边计算 RR 的头部到 rPtr 前一个数字对当前 lPtr 指向的数字的贡献。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候，只在 lPtr 右移的时候计算，是基于这样的事实：当前 lPtr 指向的数字比 rPtr 小，但是比 RR 中 [0 … rPtr - 1] 的其他数字大，[0 … rPtr - 1] 的数字是在 lPtr 右边但是比 lPtr 对应数小的数字，贡献为这些数字的个数。

但是我们又遇到了新的问题，在「并」的过程中 88 的位置一直在发生改变，我们应该把计算的贡献保存到哪里呢？这个时候我们引入一个新的数组，来记录每个数字对应的原数组中的下标，例如：

1
2

    a = [8, 9, 1, 5, 2]
index = [0, 1, 2, 3, 4]

排序的时候原数组和这个下标数组同时变化，则排序后我们得到这样的两个数组：

1
2

    a = [1, 2, 5, 8, 9]
index = [2, 4, 3, 0, 1]

我们用一个数组 ans 来记录贡献。我们对某个元素计算贡献的时候，如果它对应的下标为 p，我们只需要在 ans[p] 上加上贡献即可。

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> res;
    vector<int> idx;
    
    void merge(vector<int>& nums, int l, int r) {
        if (l >= r)
            return;
        int mid = (l + r) >> 1;
        merge(nums, l, mid);
        merge(nums, mid+1, r);
        
        vector<int> tmp(r - l + 1);
        int k = 0, i = l, j = mid+1;
        while(i <= mid && j <= r) {
            if (nums[idx[i]] <= nums[idx[j]]) {
                res[idx[i]] += (j - 1 - mid);
                tmp[k++] = idx[i ++];
            }
            else 
                tmp[k++] = idx[j ++];
        }
        
        while(i <= mid) {
            res[idx[i]] += r - mid;
            tmp[k++] = idx[i++];
        }
        
        while(j <= r)
            tmp[k++] = idx[j++];
        
        for (int i = 0; i < tmp.size(); i ++)
            idx[l+i] = tmp[i];
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        res.assign(nums.size(), 0);    
        idx.assign(nums.size(), 0);
        for (int i = 0; i < nums.size(); i ++)
            idx[i] = i;
        merge(nums, 0, nums.size()-1);
        
        return res;
    }
};

Leetcode316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

1
2

Input: s = "bcabc"
Output: "abc"

Example 2:

1
2

Input: s = "cbacdcbc"
Output: "acdb"

从一组字符串中取字符，使得生成结果中每个字符必须出现一次而且只出现一次，并且要求所得结果是字符串顺序最小的。

这个题的难点在于使得结果是字符串顺序最小。解题思路也是围绕这个展开。

先顺一下思路，首先，每个字符都必须要出现一次，那么当这个字符只有一次机会的时候，必须添加到结果字符串结尾中去，反之，如果这个字符的次数没有降为0，即后面还有机会，那么可以先把优先级高的放进来，把这个字符放到后面再处理。所以，我们可以使用一个栈，有点类似单调递增栈的意思，但其实并不是单调栈。我们的思路就是把还可以放到后面的字符弹出栈，留着以后处理，字符序小的插入到对应的位置。

首先，为了知道每个字符出现了多少次，必须做一次次数统计，这个步骤大家都是知道的。

然后，需要借助一个栈来实现字符串构造的操作。具体操作如下：

从输入字符串中逐个读取字符c，并把c的字符统计减一。

1. 如果当前字符c已经在栈里面出现，那么跳过。
2. 如果当前字符c在栈里面，那么：
   1. 如果当前字符c小于栈顶，并且栈顶元素有剩余（后面还能再添加进来），则出栈栈顶，标记栈顶不在栈中。重复该操作直到栈顶元素不满足条件或者栈为空。
   2. 入栈字符c，并且标记c已经在栈中。

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:
    string removeDuplicateLetters(string s) {
        string res = "";
        int size = s.length();
        unordered_map<char, int> m;
        unordered_map<char, bool> visited;
        for (int i = 0; i < size; i ++) {
            m[s[i]] ++;
            visited[s[i]] = false;
        }

        for (int i = 0; i < size; i ++) {
            m[s[i]] --;
            if (visited[s[i]])
                continue;
            while(!res.empty() && m[res.back()] > 0 && s[i] < res.back()) {
                visited[res.back()] = false;
                res.pop_back();
            }
            res += s[i];
            visited[s[i]] = true;
        }
        return res;
    }
};

Leetcode318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

1
2
3

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

1
2
3

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

这道题给我们了一个单词数组，让我们求两个没有相同字母的单词的长度之积的最大值。我开始想的方法是每两个单词先比较，如果没有相同字母，则计算其长度之积，然后每次更新结果就能找到最大值。因为题目中说都是小写字母，那么只有26位，一个整型数int有32位，我们可以用后26位来对应26个字母，若为1，说明该对应位置的字母出现过，那么每个单词的都可由一个int数字表示，两个单词没有共同字母的条件是这两个int数与为0，用这个判断方法可以通过OJ，参见代码如下。注意移位运算符的优先级很低。

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 maxProduct(vector<string>& words) {
        int len = words.size();
        vector<int> wordss, lennn;
        for (int i = 0; i < len; i ++) {
            int t = 0;
            for (int j = 0; j < words[i].length(); j ++) {
                t = t | (1 << (words[i][j]-'a'));
            }
            wordss.push_back(t);
            lennn.push_back(words[i].length());
        }
        
        int res = -1;
        for (int i = 0; i < len; i ++)
            for (int j = i + 1; j < len; j ++)
                if ((wordss[i] & wordss[j]) == 0)
                    res = max(res, int(lennn[i] * lennn[j]));
        return res;
    }
};

Leetcode319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the n th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

1
2
3
4
5
6
7
8

Given _n_ = 3.   

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].   

So you should return 1, because there is only one bulb is on.

这道题给了我们n个灯泡，第一次打开所有的灯泡，第二次每两个更改灯泡的状态，第三次每三个更改灯泡的状态，以此类推，第n次每n个更改灯泡的状态。让我们求n次后，所有亮的灯泡的个数。此题是CareerCup 6.6 Toggle Lockers 切换锁的状态。

那么我们来看这道题吧，还是先枚举个小例子来分析下，比如只有5个灯泡的情况，’X’表示灭，‘√’表示亮，如下所示：

初始状态： X X X X X

第一次： √ √ √ √ √

第二次： √ X √ X √

第三次： √ X X X √

第四次： √ X X √ √

第五次： √ X X √ X

那么最后我们发现五次遍历后，只有1号和4号灯泡是亮的，而且很巧的是它们都是平方数，是巧合吗，还是其中有什么玄机。我们仔细想想，对于第n个灯泡，只有当次数是n的因子的之后，才能改变灯泡的状态，即n能被当前次数整除，比如当n为36时，它的因数有(1,36), (2,18), (3,12), (4,9), (6,6), 可以看到前四个括号里成对出现的因数各不相同，括号中前面的数改变了灯泡状态，后面的数又变回去了，等于灯泡的状态没有发生变化，只有最后那个(6,6)，在次数6的时候改变了一次状态，没有对应其它的状态能将其变回去了，所以灯泡就一直是点亮状态的。所以所有平方数都有这么一个相等的因数对，即所有平方数的灯泡都将会是点亮的状态。

那么问题就简化为了求1到n之间完全平方数的个数，我们可以用force brute来比较从1开始的完全平方数和n的大小，参见代码如下：

1
2
3
4
5
6
7
8

class Solution {
public:
    int bulbSwitch(int n) {
        int res = 1;
        while (res * res <= n) ++res;
        return res - 1;
    }
};

还有一种方法更简单，我们直接对n开方，在C++里的sqrt函数返回的是一个整型数，这个整型数的平方最接近于n，即为n包含的所有完全平方数的个数，参见代码如下：

1
2
3
4
5
6

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

Leetcode322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

1
2
3

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

1
2

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

我们希望既避免重复地计算，又避免无意义的计算（没有答案的子问题）。
生成所有可能的金钱总量就可以避免无意义的计算。
dp[i]表示金钱i对应的最少硬币数。

• 初始的金钱总量为0，硬币面值为 coins = [1, 2, 5]。
• 只有一个硬币可以组成的金钱分别为[1, 2, 5]，dp[1]=dp[2]=dp[5]=1
• 在金钱为1的基础上继续生成[2, 3, 6]，即dp[3]=dp[6]=2，而dp[2]=min(dp[2],dp[1]+1)=1
• 在金钱为2的基础上生成[3, 4, 7]，即dp[4]=dp[7]=dp[2]+1=2
• 在金钱为3的基础上生成[4, 5, 8]，即dp[8]=2
• 依次更新，直到计算到以金钱amount为基础时，结束。

当以某个金钱为基础生成接下来的金钱时，这个金钱对应的最少硬币数已经得到。
通过这种递推的方式可以生成所有的小于amount的有解金钱总量，反证法证明之

• 假设某个金钱m是有解的，但是并没有被上述的递推过程生成
• m一定是由{ m-coins[i] | 0 <= i < coins.size() }中某个金钱生成的，这些金钱中一定有某几个（或一个）是有解的，但是也没有被递推过程生成，这样反向推理肯定可以到初始金钱数为0
• 既然能反推到初始金钱数，那么m一定是有解的。

解题的思想有点类似有向图的宽度优先搜索找最短路径

• 所有的小于amount的有解金钱总量对应于有向图中的结点
• m < n ,结点m和n之前有边m -> n当且仅当 m + coins[i] = n
• 每条边的权值为1，对应于每次硬币数加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(), coins.end());
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<amount;i++){
            if(dp[i]==INT_MAX)
                continue;
            for(auto& num: coins){
                if(i+(long long)num>amount) 
                    break;
                dp[i+num] = min(dp[i]+1,dp[i+num]);
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }
};

我们维护一个一维动态数组 dp，其中 dp[i] 表示钱数为i时的最小硬币数的找零，注意由于数组是从0开始的，所以要多申请一位，数组大小为 amount+1，这样最终结果就可以保存在 dp[amount] 中了。初始化 dp[0] = 0，因为目标值若为0时，就不需要硬币了。其他值可以初始化是 amount+1，为啥呢？因为最小的硬币是1，所以 amount 最多需要 amount 个硬币，amount+1 也就相当于当前的最大值了，注意这里不能用整型最大值来初始化，因为在后面的状态转移方程有加1的操作，有可能会溢出，除非你先减个1，这样还不如直接用 amount+1 舒服呢。好，接下来就是要找状态转移方程了，没思路？不要紧！回归例子1，假设我取了一个值为5的硬币，那么由于目标值是 11，所以是不是假如我们知道 dp[6]，那么就知道了组成 11 的 dp 值了？所以更新 dp[i] 的方法就是遍历每个硬币，如果遍历到的硬币值小于i值（比如不能用值为5的硬币去更新 dp[3]）时，用 dp[i - coins[j]] + 1 来更新 dp[i]，所以状态转移方程为：

dp[i] = min(dp[i], dp[i - coins[j]] + 1);
其中 coins[j] 为第j个硬币，而 i - coins[j] 为钱数i减去其中一个硬币的值，剩余的钱数在 dp 数组中找到值，然后加1和当前 dp 数组中的值做比较，取较小的那个更新 dp 数组。先来看迭代的写法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return (dp[amount] > amount) ? -1 : dp[amount];
    }
};

Leetcode326. Power of Three

Given an integer, write a function to determine if it is a power of three.

Example 1:

1
2

Input: 27
Output: true

Example 2:

1
2

Input: 0
Output: false

Example 3:

1
2

Input: 9
Output: true

Example 4:

1
2

Input: 45
Output: false

这道题让我们判断一个数是不是3的次方数，3的次方数没有显著的特点，最直接的方法就是不停地除以3，看最后的余数是否为1，要注意考虑输入是负数和0的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n == 0)
            return false;
        while(n != 1) {
            if(n % 3 != 0)
                return false;
            n /= 3;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

题目中的Follow up让我们不用循环，那么有一个投机取巧的方法，由于输入是int，正数范围是0-231，在此范围中允许的最大的3的次方数为319=1162261467，那么我们只要看这个数能否被n整除即可，参见代码如下：

1
2
3
4
5
6

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && 1162261467 % n == 0);
    }
};

最后还有一种巧妙的方法，利用对数的换底公式来做，高中学过的换底公式为logab = logcb / logca，那么如果n是3的倍数，则log3n一定是整数，我们利用换底公式可以写为log3n = log10n / log103，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log10n / log103是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断，参见代码如下：

1
2
3
4
5
6

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0);
    }
};

Leetcode327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note: A naive algorithm of O ( n 2) is trivial. You MUST do better than that.

Example:

1
2
3

Input: _nums_ = [-2,5,-1], _lower_ = -2, _upper_ = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

这道题给了我们一个数组，又给了一个下限和一个上限，让求有多少个不同的区间使得每个区间的和在给定的上下限之间。类似的区间和的问题一定是要计算累积和数组 sums 的，其中 sum[i] = nums[0] + nums[1] + … + nums[i]，对于某个i来说，只有那些满足 lower <= sum[i] - sum[j] <= upper 的j能形成一个区间 [j, i] 满足题意，目标就是来找到有多少个这样的 j (0 =< j < i) 满足 sum[i] - upper =< sum[j] <= sum[i] - lower，可以用 C++ 中由红黑树实现的 multiset 数据结构可以对其中数据排序，然后用 upperbound 和 lowerbound 来找临界值。lower_bound 是找数组中第一个不小于给定值的数(包括等于情况)，而 upper_bound 是找数组中第一个大于给定值的数，那么两者相减，就是j的个数，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int res = 0;
        long long sum = 0;
        multiset<long long> sums;
        sums.insert(0);
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            res += distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));
            sums.insert(sum);
        }
        return res;
    }        
};

我们再来看一种方法，这种方法的思路和前一种一样，只是没有 STL 的 multiset 和 lower_bound 和 upper_bound 函数，而是使用了 Merge Sort 来解，在混合的过程中，已经给左半边 [start, mid) 和右半边 [mid, end) 排序了。当遍历左半边，对于每个i，需要在右半边找出k和j，使其满足：

j是第一个满足 sums[j] - sums[i] > upper 的下标

k是第一个满足 sums[k] - sums[i] >= lower 的下标

那么在 [lower, upper] 之间的区间的个数是 j - k，同时也需要另一个下标t，用来拷贝所有满足 sums[t] < sums[i] 到一个寄存器 Cache 中以完成混合排序的过程，这个步骤是混合排序的精髓所在，实际上这个寄存器的作用就是将 [start, end) 范围内的数字排好序先存到寄存器中，然后再覆盖原数组对应的位置即可，(注意这里 sums 可能会整型溢出，使用长整型 long 代替)，参见代码如下：

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

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long> sums(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); ++i) {
            sums[i + 1] = sums[i] + nums[i];
        }
        return countAndMergeSort(sums, 0, sums.size(), lower, upper);
    }
    int countAndMergeSort(vector<long>& sums, int start, int end, int lower, int upper) {
        if (end - start <= 1) return 0;
        int mid = start + (end - start) / 2;
        int cnt = countAndMergeSort(sums, start, mid, lower, upper) + countAndMergeSort(sums, mid, end, lower, upper);
        int j = mid, k = mid, t = mid;
        vector<int> cache(end - start, 0);
        for (int i = start, r = 0; i < mid; ++i, ++r) {
            while (k < end && sums[k] - sums[i] < lower) ++k;
            while (j < end && sums[j] - sums[i] <= upper) ++j;
            while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
            cache[r] = sums[i];
            cnt += j - k;
        }
        copy(cache.begin(), cache.begin() + t - start, sums.begin() + start);
        return cnt;
    }
};

Leetcode328. Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1:

1
2

Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

这道题给了我们一个链表，让我们分开奇偶节点，所有奇节点在前，偶节点在后。我们可以使用两个指针来做，pre指向奇节点，cur指向偶节点，然后把偶节点cur后面的那个奇节点提前到pre的后面，然后pre和cur各自前进一步，此时cur又指向偶节点，pre指向当前奇节点的末尾，以此类推直至把所有的偶节点都提前了即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *odd = head, *even = head->next, *p = even;
        while(odd->next && even->next) {
            odd->next = even->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = p;
        return head;
    }
};

Leetcode329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

1
2
3
4
5
6
7
8

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

1
2
3
4
5
6
7
8

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

这道题给我们一个二维数组，让我们求矩阵中最长的递增路径，规定我们只能上下左右行走，不能走斜线或者是超过了边界。那么这道题的解法要用递归和DP来解，用DP的原因是为了提高效率，避免重复运算。我们需要维护一个二维动态数组dp，其中dp[i][j]表示数组中以(i,j)为起点的最长递增路径的长度，初始将dp数组都赋为0，当我们用递归调用时，遇到某个位置(x, y), 如果dp[x][y]不为0的话，我们直接返回dp[x][y]即可，不需要重复计算。我们需要以数组中每个位置都为起点调用递归来做，比较找出最大值。在以一个位置为起点用DFS搜索时，对其四个相邻位置进行判断，如果相邻位置的值大于上一个位置，则对相邻位置继续调用递归，并更新一个最大值，搜素完成后返回即可，参见代码如下：

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

class Solution {
public:
    int dirs[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int** dp;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) 
            return 0;
        int res = 1, m = matrix.size(), n = matrix[0].size();
        dp = (int**)malloc(sizeof(int*)*m);
        for(int i=0;i<m;i++){
            dp[i] = (int*)malloc(sizeof(int)*n);
            memset(dp[i],0,n*sizeof(int));
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {        
                res = max(res, dfs(matrix, i, j));
            }
        }
        return res;
    }
    
    int dfs(vector<vector<int>>& matrix,int i,int j){
        if (dp[i][j]) 
            return dp[i][j];
        int mx = 1, m = matrix.size(), n = matrix[0].size();
        for(int ii=0;ii<4;ii++){
            int x = i + dirs[ii][0], y = j + dirs[ii][1];
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) 
                continue;
            int len = 1 + dfs(matrix, x, y);
            mx = max(mx, len);
        }
        dp[i][j]=mx;
        return mx;
    }
};

Leetcode331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#“, where # represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character # representing null pointer.

You may assume that the input format is always valid.

For example, it could never contain two consecutive commas, such as “1,,3”.
Note: You are not allowed to reconstruct the tree.

Example 1:

1
2

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

Example 2:

1
2

Input: preorder = "1,#"
Output: false

Example 3:

1
2

Input: preorder = "9,#,#,1"
Output: false

通过二叉树的性质，所有二叉树中Null指针的个数=节点个数+1。因为一棵树要增加一个节点，必然是在null指针的地方增加一个叶子结点，也就是毁掉一个null指针的同时带来两个null指针，意味着每增加一个节点，增加一个null指针。然而最开始一颗空树本来就有一个null指针，因此二叉树中null指针的个数等于节点数+1。从头开始扫描这个字串，如果途中#的个数超了，或者字符串扫描完不满足等式则返回false。

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

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int len = preorder.length();
        int i = 0, cnt = 0;
        while(i < len-1) {
            if (preorder[i] == '#') {
                if (cnt == 0)
                    return false;
                cnt --;
                i ++;
            }
            else {
                for(; i < len && preorder[i] != ','; i ++) ;
                cnt ++;
            }
            i ++;
        }
        return cnt == 0 && preorder[len-1] == '#';
    }
};

Leetcode334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example 1:

1
2
3

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

1
2
3

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

1
2
3

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

dp数组，分别记录当前位置的最大和最小数。时间复杂度O(n)。空间复杂度O（n）.

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

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length<3)
            return false;
        int mindp[]=new int[nums.length];
        mindp[0]=nums[0];
        int tempmin=nums[0];
        for(int i=1;i<nums.length;i++){
            tempmin=Math.min(tempmin,nums[i-1]);
            mindp[i]=tempmin;
        }
        int maxdp[]=new int[nums.length];
        maxdp[nums.length-1]=nums[nums.length-1];
        int tempmax=nums[nums.length-1];
        for(int i=nums.length-2;i>=0;i--){
            tempmax=Math.max(tempmax,nums[i+1]);
            maxdp[i]=tempmax;
        }
        for(int i=1;i<nums.length-1;i++){
                if(nums[i]>mindp[i] && nums[i]<maxdp[i])
                    return true;
        }
        return false;
    }
}

找出两个数，分别记录为次小和最小，当一个数 比这两个数都大时，返回true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int One=Integer.MAX_VALUE,Tow=Integer.MAX_VALUE;
        for(int i=0;i< nums.length;i++){
            if(nums[i]<=One)
                One=nums[i];
            else if(nums[i]<=Tow)
                Tow=nums[i];
            else
                return true;
        }
        return false;
    }
}

Leetcode337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

1
2
3

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

这道题是之前那两道 House Robber II 和 House Robber 的拓展，这个小偷又偷出新花样了，沿着二叉树开始偷，碉堡了，题目中给的例子看似好像是要每隔一个偷一次，但实际上不一定只隔一个，比如如下这个例子：

1
2
3
4
5
6
7

      4
     /
    1
   /
  2
 /
3

如果隔一个偷，那么是 4+2=6，其实最优解应为 4+3=7，隔了两个，所以说纯粹是怎么多怎么来，那么这种问题是很典型的递归问题，可以利用回溯法来做，因为当前的计算需要依赖之前的结果，那么对于某一个节点，如果其左子节点存在，通过递归调用函数，算出不包含左子节点返回的值，同理，如果右子节点存在，算出不包含右子节点返回的值，那么此节点的最大值可能有两种情况，一种是该节点值加上不包含左子节点和右子节点的返回值之和，另一种是左右子节点返回值之和不包含当期节点值，取两者的较大值返回即可，但是这种方法无法通过 OJ，超时了，所以必须优化这种方法，这种方法重复计算了很多地方，比如要完成一个节点的计算，就得一直找左右子节点计算，可以把已经算过的节点用 HashMap 保存起来，以后递归调用的时候，现在 HashMap 里找，如果存在直接返回，如果不存在，等计算出来后，保存到 HashMap 中再返回，这样方便以后再调用，参见代码如下：

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

class Solution {
public:
    int rob(TreeNode* root) {
        unordered_map<TreeNode*, int> m;
        return dfs(root, m);
    }
    int dfs(TreeNode *root, unordered_map<TreeNode*, int> &m) {
        if (!root) return 0;
        if (m.count(root)) return m[root];
        int val = 0;
        if (root->left) {
            val += dfs(root->left->left, m) + dfs(root->left->right, m);
        }
        if (root->right) {
            val += dfs(root->right->left, m) + dfs(root->right->right, m);
        }
        val = max(val + root->val, dfs(root->left, m) + dfs(root->right, m));
        m[root] = val;
        return val;
    }
};

下面再来看一种方法，这种方法的递归函数返回一个大小为2的一维数组 res，其中 res[0] 表示不包含当前节点值的最大值，res[1] 表示包含当前值的最大值，那么在遍历某个节点时，首先对其左右子节点调用递归函数，分别得到包含与不包含左子节点值的最大值，和包含于不包含右子节点值的最大值，则当前节点的 res[0] 就是左子节点两种情况的较大值加上右子节点两种情况的较大值，res[1] 就是不包含左子节点值的最大值加上不包含右子节点值的最大值，和当前节点值之和，返回即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> res = dfs(root);
        return max(res[0], res[1]);
    }
    vector<int> dfs(TreeNode *root) {
        if (!root) return vector<int>(2, 0);
        vector<int> left = dfs(root->left);
        vector<int> right = dfs(root->right);
        vector<int> res(2, 0);
        res[0] = max(left[0], left[1]) + max(right[0], right[1]);
        res[1] = left[0] + right[0] + root->val;
        return res;
    }
};

下面这种解法思路和解法二有些类似。这里的 helper 函数返回当前结点为根结点的最大 rob 的钱数，里面的两个参数l和r表示分别从左子结点和右子结点开始 rob，分别能获得的最大钱数。在递归函数里面，如果当前结点不存在，直接返回0。否则对左右子结点分别调用递归函数，得到l和r。另外还得到四个变量，ll和lr表示左子结点的左右子结点的最大 rob 钱数，rl 和 rr 表示右子结点的最大 rob 钱数。那么最后返回的值其实是两部分的值比较，其中一部分的值是当前的结点值加上 ll, lr, rl, 和 rr 这四个值，这不难理解，因为抢了当前的房屋，则左右两个子结点就不能再抢了，但是再下一层的四个子结点都是可以抢的；另一部分是不抢当前房屋，而是抢其左右两个子结点，即 l+r 的值，返回两个部分的值中的较大值即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int rob(TreeNode* root) {
        int l = 0, r = 0;
        return helper(root, l, r);
    }
    int helper(TreeNode* node, int& l, int& r) {
        if (!node) return 0;
        int ll = 0, lr = 0, rl = 0, rr = 0;
        l = helper(node->left, ll, lr);
        r = helper(node->right, rl, rr);
        return max(node->val + ll + lr + rl + rr, l + r);
    }
};

Leetcode338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example 1:

1
2

Input: 2
Output: [0,1,1]

Example 2:

1
2

Input: 5
Output: [0,1,1,2,1,2]

Follow up: It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass? Space complexity should be O(n). Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

从低位入手。‘1’的个数等于除了最低位之外的‘1’的个数加上最低位‘1’的个数，即ret[n] = ret[n>>1] + n%2，具体代码：

1
2
3
4
5
6
7
8
9

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num+1, 0);
        for(int i=1; i<=num; ++i)
            ret[i] = ret[i>>1] + i%2;
        return ret;
    }
};

Leetcode 339. Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

1
2
3

Input: [[1,1],2,[1,1]]
Output: 10 
Explanation: Four 1's at depth 2, one 2 at depth 1.

Example 2:

1
2
3

Input: [1,[4,[6]]]
Output: 27 
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.

这道题定义了一种嵌套链表的结构，链表可以无限往里嵌套，规定每嵌套一层，深度加1，让我们求权重之和，就是每个数字乘以其权重，再求总和。那么我们考虑，由于嵌套层数可以很大，所以我们用深度优先搜索DFS会很简单，每次遇到嵌套的，递归调用函数，一层一层往里算就可以了，我最先想的方法是遍历给的嵌套链表的数组，对于每个嵌套链表的对象，调用getSum函数，并赋深度值1，累加起来返回。在getSum函数中，首先判断其是否为整数，如果是，则返回当前深度乘以整数，如果不是，那么我们再遍历嵌套数组，对每个嵌套链表再调用递归函数，将返回值累加起来返回即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        int res = 0;
        for (auto a : nestedList) {
            res += getSum(a, 1);
        }
        return res;
    }
    int getSum(NestedInteger ni, int level) {
        int res = 0;
        if (ni.isInteger()) return level * ni.getInteger();
        for (auto a : ni.getList()) {
            res += getSum(a, level + 1);
        }
        return res;
    }
};

但其实上面的方法可以优化，我们可以把给的那个嵌套链表的一维数组直接当做一个嵌套链表的对象，然后调用递归函数，递归函数的处理方法跟上面一样，只不过用了个三元处理使其看起来更加简洁了一些：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    int helper(vector<NestedInteger>& nl, int depth) {
        int res = 0;
        for (auto a : nl) {
            res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
        }
        return res;
    }
};

Leetcode342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

1
2

Input: 16
Output: true

Example 2:

1
2

Input: 5
Output: false

这道题让我们判断一个数是否为4的次方数，那么最直接的方法就是不停的除以4，看最终结果是否为1，参见代码如下：

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isPowerOfFour(int num) {
        while (num && (num % 4 == 0)) {
            num /= 4;
        }
        return num == 1;
    }
};

还有一种方法是跟 Power of Three 中的解法三一样，使用换底公式来做

1
2
3
4
5
6

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && int(log10(num) / log10(4)) - log10(num) / log10(4) == 0;
    }
};

下面这种方法是网上比较流行的一种解法，思路很巧妙，首先根据 Power of Two 中的解法，我们知道 num & (num - 1) 可以用来判断一个数是否为2的次方数，更进一步说，就是二进制表示下，只有最高位是1，那么由于是2的次方数，不一定是4的次方数，比如8，所以我们还要其他的限定条件，我们仔细观察可以发现，4的次方数的最高位的1都是奇数位，那么我们只需与上一个数 (0x55555555) <==> 1010101010101010101010101010101，如果得到的数还是其本身，则可以肯定其为4的次方数：

1
2
3
4
5
6

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
    }
};

Leetcode343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

1
2
3

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

1
2
3

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

这道题给了我们一个正整数n，让拆分成至少两个正整数之和，使其乘积最大。当前的拆分方法需要用到之前的拆分值，这种重现关系就很适合动态规划 Dynamic Programming 来做，我们使用一个一维数组 dp，其中 dp[i] 表示数字i拆分为至少两个正整数之和的最大乘积，数组大小为 n+1，值均初始化为1，因为正整数的乘积不会小于1。可以从3开始遍历，因为n是从2开始的，而2只能拆分为两个1，乘积还是1。i从3遍历到n，对于每个i，需要遍历所有小于i的数字，因为这些都是潜在的拆分情况，对于任意小于i的数字j，首先计算拆分为两个数字的乘积，即j乘以 i-j，然后是拆分为多个数字的情况，这里就要用到 dp[i-j] 了，这个值表示数字 i-j 任意拆分可得到的最大乘积，再乘以j就是数字i可拆分得到的乘积，取二者的较大值来更新 dp[i]，最后返回 dp[n] 即可，

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 1);
        for (int i = 3; i <= n; i ++) {
            for (int j = 1; j < i; j ++)
            dp[i] = max(dp[i], max(j*(i-j), dp[i-j] *j)); 
        }
        return dp[n];
    }
};

题目提示中让用 O(n) 的时间复杂度来解题，而且告诉我们找7到 10 之间的规律，那么我们一点一点的来分析：

正整数从1开始，但是1不能拆分成两个正整数之和，所以不能当输入。

那么：

• 2只能拆成 1+1，所以乘积也为1。
• 数字3可以拆分成 2+1 或 1+1+1，显然第一种拆分方法乘积大为2。
• 数字4拆成 2+2，乘积最大，为4。
• 数字5拆成 3+2，乘积最大，为6。
• 数字6拆成 3+3，乘积最大，为9。
• 数字7拆为 3+4，乘积最大，为 12。
• 数字8拆为 3+3+2，乘积最大，为 18。
• 数字9拆为 3+3+3，乘积最大，为 27。
• 数字10拆为 3+3+4，乘积最大，为 36。

….

那么通过观察上面的规律，我们可以看出从5开始，数字都需要先拆出所有的3，一直拆到剩下一个数为2或者4，因为剩4就不用再拆了，拆成两个2和不拆没有意义，而且4不能拆出一个3剩一个1，这样会比拆成 2+2 的乘积小。这样我们就可以写代码了，先预处理n为2和3的情况，然后先将结果 res 初始化为1，然后当n大于4开始循环，结果 res 自乘3，n自减3，根据之前的分析，当跳出循环时，n只能是2或者4，再乘以 res 返回即可：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};

直接分别算出能拆出3的个数和最后剩下的余数2或者4，然后直接相乘得到结果，参见代码如下：

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2 || n == 3) return n - 1;
        if (n == 4) return 4;
        n -= 5;
        return (int)pow(3, (n / 3 + 1)) * (n % 3 + 2);
    }
};

Leetcode344. Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters.

Example 1:

1
2

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

1
2

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

我的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, r = s.size() - 1;
        while(l < r) {
            int temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l ++;
            r --;
        }
    }
};