Leetcode401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

1
2

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

• The order of output does not matter.
• The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
• The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

首先先明白二进制手表的含义，把1，2，4，8转化为四位的二进制就是0001， 0010， 0100，1000， 9点时亮1和8，是1001。分钟数也是同理。
其次表示小时的数值只有0-11，表示分钟的数值只有0-59。先分别对小时跟分钟的数值进行预处理，按照包含而二进制中包含1的个数分开保存小时数值的字符串跟分钟数值的字符串。

用bitset可以方便地记下来每个数字有几个二进制1，这样可以简单地做出来。

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

class Solution {
	public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        for(int i = 0; i < 12; i ++) {
            bitset<4> h(i);
            for(int j = 0; j < 60; j ++) {
                bitset<6> m(j);
                if(h.count() + m.count() == num)
                    res.push_back(to_string(i) + (j < 10? ":0": ":") + to_string(j));
            }
        }   
        return res;
    }
};

基本还是一道DFS的题目，分别在小时和分钟上做DFS，给定几个灯亮，然后把这些亮的灯枚举分给小时和分钟．需要注意的是剪枝，即小时必须小于12，分钟小于60。然后将小时和分钟组合即可．还有一个需要注意的是如果分钟只有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:
    void DFS(int len, int k, int curIndex, int val, vector<int>& vec)
    {
        if(k==0 && len==4 && val < 12) vec.push_back(val);
        if(k==0 && len==6 && val < 60) vec.push_back(val);
        if(curIndex == len || k == 0) return;
        DFS(len, k, curIndex+1, val, vec);
        val += pow(2, curIndex), k--, curIndex++;
        DFS(len, k, curIndex, val, vec);
    }
    
    vector<string> readBinaryWatch(int num) {
        vector<string> ans;
        for(int i = max(0, num-6); i <= min(4, num); i++)
        {
            vector<int> vec1, vec2;
            DFS(4, i, 0, 0, vec1), DFS(6, num-i, 0, 0, vec2);
            for(auto val1: vec1)
                for(auto val2: vec2) 
                {
                    string str = (to_string(val2).size()==1?"0":"") + to_string(val2);
                    ans.push_back(to_string(val1)+":"+ str);
                }
        }
        return ans;
    }
};

Leetcode402. Remove K Digits

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example 1:

1
2
3

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

这道题让我们将给定的数字去掉k位，要使得留下来的数字最小。

首先来考虑，若数字是递增的话，比如 1234，那么肯定是要从最后面移除最大的数字。若是乱序的时候，比如 1324，若只移除一个数字，移除谁呢？这个例子比较简单，我们一眼可以看出是移除3，变成 124 是最小。这里我们维护一个递增栈，只要发现当前的数字小于栈顶元素的话，就将栈顶元素移除，比如点那个遍历到2的时候，栈里面有1和3，此时2小于栈顶元素3，那么将3移除即可。为何一定要移除栈顶元素呢，后面说不定有更大的数字呢？这是因为此时栈顶元素在高位上，就算后面的数字再大，也是在低位上，我们只有将高位上的数字尽可能的变小，才能使整个剩下的数字尽可能的小。

我们开始遍历给定数字 num 的每一位，对于当前遍历到的数字c，进行如下 while 循环，如果 res 不为空，且k大于0，且 res 的最后一位大于c，那么应该将 res 的最后一位移去，且k自减1。当跳出 while 循环后，我们将c加入 res 中，最后将 res 的大小重设为 n-k。根据题目中的描述，可能会出现 “0200” 这样不符合要求的情况，所以我们用一个 while 循环来去掉前面的所有0，然后返回时判断是否为空，为空则返回 “0”。

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

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res = "";
        int len = num.length();
        for (int i = 0; i < len; i ++) {
            while (k > 0 && res.length() > 0 && num[i] < res.back()) {
                res.pop_back();
                k --;
            }
            if (res.length() > 0 || num[i] != '0')
                res += num[i];
        }
        while(res.size() > 0 && k--)
            res.pop_back();
        return res.empty() ? "0" : res;
    }
};

Leetcode403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog’s last jump was k units, then its next jump must be either k - 1, k , or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone’s position will be a non-negative integer < 231.
• The first stone’s position is always 0.

Example 1:

1
2
3
4
5
6
7
8
9
10
11

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

1
2
3
4

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

题目中说青蛙如果上一次跳了k距离，那么下一次只能跳 k-1, k, 或 k+1 的距离，那么青蛙跳到某个石头上可能有多种跳法，由于这道题只是让判断青蛙是否能跳到最后一个石头上，并没有让返回所有的路径，这样就降低了一些难度。我们可以用递归来做，这里维护一个 HashMap，建立青蛙在 pos 位置和拥有 jump 跳跃能力时是否能跳到对岸。为了能用一个变量同时表示 pos 和 jump，可以将jump左移很多位并或上 pos，由于题目中对于位置大小有限制，所以不会产生冲突。首先判断 pos 是否已经到最后一个石头了，是的话直接返回 true；然后看当前这种情况是否已经出现在 HashMap 中，是的话直接从 HashMap 中取结果。如果没有，就遍历余下的所有石头，对于遍历到的石头，计算到当前石头的距离dist，如果距离小于 jump-1，接着遍历下一块石头；如果 dist 大于 jump+1，说明无法跳到下一块石头，m[key] 赋值为 false，并返回 false；如果在青蛙能跳到的范围中，调用递归函数，以新位置i为 pos，距离 dist 为 jump，如果返回 true 了，给 m[key] 赋值为 true，并返回 true。如果结束遍历给 m[key] 赋值为 false，并返回 false，参加代码如下：

解法一：

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

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, bool> m;
        return helper(stones, 0, 0, m);
    }
    bool helper(vector<int>& stones, int pos, int jump, unordered_map<int, bool>& m) {
        int n = stones.size(), key = pos | jump << 11;
        if (pos >= n - 1) return true;
        if (m.count(key)) return m[key];
        for (int i = pos + 1; i < n; ++i) {
            int dist = stones[i] - stones[pos];
            if (dist < jump - 1) continue;
            if (dist > jump + 1) return m[key] = false;
            if (helper(stones, i, dist, m)) return m[key] = true;
        }
        return m[key] = false;
    }
};

我们也可以用迭代的方法来解，用一个 HashMap 来建立每个石头和在该位置上能跳的距离之间的映射，建立一个一维 dp 数组，其中 dp[i] 表示在位置为i的石头青蛙的弹跳力(只有青蛙能跳到该石头上，dp[i] 才大于0)，由于题目中规定了第一个石头上青蛙跳的距离必须是1，为了跟后面的统一，对青蛙在第一块石头上的弹跳力初始化为0(虽然为0，但是由于题目上说青蛙最远能到其弹跳力+1的距离，所以仍然可以到达第二块石头)。这里用变量k表示当前石头，然后开始遍历剩余的石头，对于遍历到的石头i，来找到刚好能跳到i上的石头k，如果i和k的距离大于青蛙在k上的弹跳力+1，则说明青蛙在k上到不了i，则k自增1。从k遍历到i，如果青蛙能从中间某个石头上跳到i上，更新石头i上的弹跳力和最大弹跳力。这样当循环完成后，只要检查最后一个石头上青蛙的最大弹跳力是否大于0即可，参见代码如下：

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

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_map<int, unordered_set<int>> m;
        vector<int> dp(stones.size(), 0);
        m[0].insert(0);
        int k = 0;
        for (int i = 1; i < stones.size(); ++i) {
            while (dp[k] + 1 < stones[i] - stones[k]) ++k;
            for (int j = k; j < i; ++j) {
                int t = stones[i] - stones[j];
                if (m[j].count(t - 1) || m[j].count(t) || m[j].count(t + 1)) {
                    m[i].insert(t);
                    dp[i] = max(dp[i], t);
                }
            }
        }
        return dp.back() > 0;
    }
};

Leetcode404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

1
2
3
4
5
6

    3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

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 sumOfLeftLeaves(TreeNode* root) {
        if(!root)
            return 0;
        if(!root->left && !root->right)
            return 0;
        queue<TreeNode*> q;
        int res = 0;
        q.push(root);
        while(!q.empty()) {
            TreeNode* temp = q.front();
            q.pop();
            if(temp->left)
                q.push(temp->left);
            if(temp->right && (temp->right->left || temp->right->right))
                q.push(temp->right);
            if(!temp->left && !temp->right)
                 res += temp->val;
	        }
        return res;
    }
};

Leetcode405. Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1. All letters in hexadecimal (a-f) must be in lowercase.
2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

1
2

Input: 26
Output: "1a"

1
2

Input: -1
Output: "ffffffff"

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:
    string toHex(int num) {
        string res = "";
        if(num == 0)
            return "0";
        char digits[] = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        if(num < 0) {
            num = abs(num);
            num = ~num + 1;
        }
        int count = 8;
        while(count --) {
            int temp = 15 & num;
            num = num >> 4;
            res = digits[temp] + res;
            if(num == 0)
                break;
            cout << digits[temp] << "  " << num << endl;
        }
        return res;     
    }
};

Leetcode406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

1
2

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

Explanation:

• Person 0 has height 5 with no other people taller or the same height in front.
• Person 1 has height 7 with no other people taller or the same height in front.
• Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
• Person 3 has height 6 with one person taller or the same height in front, which is person 1.
• Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
• Person 5 has height 7 with one person taller or the same height in front, which is person 1.
• Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

这道题给了我们一个队列，队列中的每个元素是一个 pair，分别为身高和前面身高不低于当前身高的人的个数，让我们重新排列队列，使得每个 pair 的第二个参数都满足题意。首先来看一种超级简洁的方法，给队列先排个序，按照身高高的排前面，如果身高相同，则第二个数小的排前面。然后新建一个空的数组，遍历之前排好序的数组，然后根据每个元素的第二个数字，将其插入到 res 数组中对应的位置，参见代码如下：

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

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
        });
        vector<vector<int>> res;
        for (auto a : people) {
            res.insert(res.begin() + a[1], a);
        }
        return res;
    }
};

Leetcode407. Trapping Rain Water II

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Example 1:

1
2
3
4
5

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small pounds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

1
2

Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10

这道三维的，我们需要用 BFS 来做，解法思路很巧妙，下面我们就以题目中的例子来进行分析讲解，多图预警，手机流量党慎入：

首先我们应该能分析出，能装水的底面肯定不能在边界上，因为边界上的点无法封闭，那么所有边界上的点都可以加入 queue，当作 BFS 的启动点，同时我们需要一个二维数组来标记访问过的点，访问过的点我们用红色来表示，那么如下图所示：

我们再想想，怎么样可以成功的装进去水呢，是不是周围的高度都应该比当前的高度高，形成一个凹槽才能装水，而且装水量取决于周围最小的那个高度，有点像木桶原理的感觉，那么为了模拟这种方法，我们采用模拟海平面上升的方法来做，我们维护一个海平面高度 mx，初始化为最小值，从1开始往上升，那么我们 BFS 遍历的时候就需要从高度最小的格子开始遍历，那么我们的 queue 就不能使用普通队列了，而是使用优先级队列，将高度小的放在队首，最先取出，这样我们就可以遍历高度为1的三个格子，用绿色标记出来了，如下图所示：

如上图所示，向周围 BFS 搜索的条件是不能越界，且周围格子未被访问，那么可以看出上面的第一个和最后一个绿格子无法进一步搜索，只有第一行中间那个绿格子可以搜索，其周围有一个灰格子未被访问过，将其加入优先队列 queue 中，然后标记为红色，如下图所示：

那么优先队列 queue 中高度为1的格子遍历完了，此时海平面上升1，变为2，此时我们遍历优先队列 queue 中高度为2的格子，有3个，如下图绿色标记所示：

我们发现这三个绿格子周围的格子均已被访问过了，所以不做任何操作，海平面继续上升，变为3，遍历所有高度为3的格子，如下图绿色标记所示：

由于我们没有特别声明高度相同的格子在优先队列 queue 中的顺序，所以应该是随机的，其实谁先遍历到都一样，对结果没啥影响，我们就假设第一行的两个绿格子先遍历到，那么那么周围各有一个灰格子可以遍历，这两个灰格子比海平面低了，可以存水了，把存水量算出来加入结果 res 中，如下图所示：

上图中这两个遍历到的蓝格子会被加入优先队列 queue 中，由于它们的高度小，所以下一次从优先队列 queue 中取格子时，它们会被优先遍历到，那么左边的那个蓝格子进行BFS搜索，就会遍历到其左边的那个灰格子，由于其高度小于海平面，也可以存水，将存水量算出来加入结果 res 中，如下图所示：

等两个绿格子遍历结束了，它们会被标记为红色，蓝格子遍历会先被标记红色，然后加入优先队列 queue 中，由于其周围格子全变成红色了，所有不会有任何操作，如下图所示：

此时所有的格子都标记为红色了，海平面继续上升，继续遍历完优先队列 queue 中的格子，不过已经不会对结果有任何影响了，因为所有的格子都已经访问过了，此时等循环结束后返回res即可，参见代码如下：

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

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heights) {
        if (heights.size() == 0)
            return 0;
        int m = heights.size(), n = heights[0].size(), res = 0;
        vector<vector<bool> > visited(m, vector<bool>(n, false));
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
        
        for (int i = 0; i < m; i ++)
            for (int j = 0; j < n; j ++)
                if (i == 0 || i == m-1 || j == 0 || j == n-1) {
                    q.push({heights[i][j], i*n+j});
                    visited[i][j] = true;
                }
        int max_height = 0;
        while(!q.empty()) {
            pair<int, int> t = q.top();
            q.pop();
            int h = t.first, r = t.second / n, c = t.second % n;
            max_height = max(max_height, h);
            for (int i = 0; i < 4; i ++) {
                int x = r + dir[i][0];
                int y = c + dir[i][1];
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y])
                    continue;
                visited[x][y] = true;
                if (heights[x][y] < max_height)
                    res = res + (max_height - heights[x][y]);
                q.push({heights[x][y], x*n+y});
            }
        }
        return res;
    }
};

Leetcode409. Longest Palindrome

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

1
2
3
4

Input: "abccccdd"
Output: 7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

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

class Solution {
public:
    int longestPalindrome(string s) {
        int ch[128] = {0};
        for(char c : s)
            ch[c]++;
        int ans = 0;
        for(int i : ch) {
            ans += (i / 2 * 2);
            if(ans % 2== 0 && i % 2 == 1)
                ans ++;
        }
        return ans;
    }
};

Leetcode410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m , you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note: Given m satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.

Examples:

1
2
3
4
5
6

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:

• There are four ways to split nums into two subarrays.
• The best way is to split it into [7,2,5] and [10,8],
• where the largest sum among the two subarrays is only 18.

这道题给了我们一个非负数的数组 nums 和一个整数m，让把数组分割成m个非空的连续子数组，让最小化m个子数组中的最大值。

首先来分析，如果m和数组 nums 的个数相等，那么每个数组都是一个子数组，所以返回 nums 中最大的数字即可，如果m为1，那么整个 nums 数组就是一个子数组，返回 nums 所有数字之和，所以对于其他有效的m值，返回的值必定在上面两个值之间，所以可以用二分搜索法来做。用一个例子来分析，nums = [1, 2, 3, 4, 5], m = 3，将 left 设为数组中的最大值5，right 设为数字之和 15，然后算出中间数为 10，接下来要做的是找出和最大且小于等于 10 的子数组的个数，[1, 2, 3, 4], [5]，可以看到无法分为3组，说明 mid 偏大，所以让 right=mid，然后再次进行二分查找，算出 mid=7，再次找出和最大且小于等于7的子数组的个数，[1,2,3], [4], [5]，成功的找出了三组，说明 mid 还可以进一步降低，让 right=mid，再次进行二分查找，算出 mid=6，再次找出和最大且小于等于6的子数组的个数，[1,2,3], [4], [5]，成功的找出了三组，尝试着继续降低 mid，让 right=mid，再次进行二分查找，算出 mid=5，再次找出和最大且小于等于5的子数组的个数，[1,2], [3], [4], [5]，发现有4组，此时的 mid 太小了，应该增大 mid，让 left=mid+1，此时 left=6，right=6，循环退出了，返回 right 即可，参见代码如下：

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

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long left = 0, right = 0;
        for (int i = 0; i < nums.size(); ++i) {
            left = max(left, (long)nums[i]);
            right += nums[i];
        }
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (can_split(nums, m, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }
    bool can_split(vector<int>& nums, long m, long sum) {
        long cnt = 1, curSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            curSum += nums[i];
            if (curSum > sum) {
                curSum = nums[i];
                ++cnt;
                if (cnt > m) return false;
            }
        }
        return true;
    }
};

上面的解法相对来说比较难想，在热心网友 perthblank 的提醒下，再来看一种 DP 的解法，相对来说，这种方法应该更容易理解一些。建立一个二维数组 dp，其中 dp[i][j] 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值，初始化为整型最大值，如果无法分为i组，那么还是保持为整型最大值。为了能快速的算出子数组之和，还是要建立累计和数组，难点就是在于推导状态转移方程了。

来分析一下，如果前j个数字要分成i组，那么i的范围是什么，由于只有j个数字，如果每个数字都是单独的一组，那么最多有j组；如果将整个数组看为一个整体，那么最少有1组，所以i的范围是[1, j]，所以要遍历这中间所有的情况，假如中间任意一个位置k，dp[i-1][k] 表示数组中前k个数字分成 i-1 组所能得到的最小的各个子数组中最大值，而 sums[j]-sums[k] 就是后面的数字之和，取二者之间的较大值，然后和 dp[i][j] 原有值进行对比，更新 dp[i][j] 为二者之中的较小值，这样k在 [1, j] 的范围内扫过一遍，dp[i][j] 就能更新到最小值，最终返回 dp[m][n] 即可，博主认为这道题所用的思想应该是之前那道题 Reverse Pairs 中解法二中总结的分割重现关系 (Partition Recurrence Relation)，由此看来很多问题的本质都是一样，但是披上华丽的外衣，难免会让人有些眼花缭乱了，参见代码如下：

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 splitArray(vector<int>& nums, int m) {
        int n = nums.size();
        vector<long> sums(n + 1);
        vector<vector<long>> dp(m + 1, vector<long>(n + 1, LONG_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = i - 1; k < j; ++k) {
                    long val = max(dp[i - 1][k], sums[j] - sums[k]);
                    dp[i][j] = min(dp[i][j], val);
                }
            }
        }
        return dp[m][n];
    }
};

Leetcode412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

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

n = 15,
Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

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

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> res;
        if(n == 0) 
            return res;
        for(int i = 0; i < n; i ++)
        {
            if((i + 1) % 3 == 0 && (i + 1) % 5 == 0)
                res.push_back("FizzBuzz");
            else if((i + 1) % 3 == 0)   
                res.push_back("Fizz");
            else if((i + 1) % 5 == 0)
                res.push_back("Buzz");
            else 
                res.push_back(to_string(i + 1));
        }
        return res;
    }
};

Leetcode413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

1
2
3

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

1
2

Input: nums = [1]
Output: 0

这道题让我们算一种算数切片，说白了就是找等差数列，限定了等差数列的长度至少为3，那么[1,2,3,4]含有3个长度至少为3的算数切片，我们再来看[1,2,3,4,5]有多少个呢:
len = 3: [1,2,3], [2,3,4], [3,4,5]

len = 4: [1,2,3,4], [2,3,4,5]

len = 5: [1,2,3,4,5]

那么我们可以归纳出规律，长度为n的等差数列有1个，长度为n-1的等差数列有2个，… ，长度为3的等差数列有 n-2 个，那么总共就是 1 + 2 + 3 + … + n-2 ，此时就要祭出高斯求和公式了，长度为n的等差数列中含有长度至少为3的算数切片的个数为(n-1)(n-2)/2，那么题目就变成了找原数组中等差数列的长度，然后带入公式去算个数即可，参见代码如下：

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

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int res = 0, len = 2, n = A.size();
        for (int i = 2; i < n; ++i) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                ++len;
            } else {
                if (len > 2) res += (len - 1) * (len - 2) * 0.5;
                len = 2;
            }
        }
        if (len > 2) res += (len - 1) * (len - 2) * 0.5;
        return res;
    }
};

Leetcode414. Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

1
2
3

Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

1
2
3

Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

1
2
3
4

Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

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

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long min = LONG_MIN, mid = LONG_MIN, max = LONG_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); i ++) {
            if(nums[i] == max || nums[i] == mid)
                continue;
            if(nums[i] > max) {
                min = mid;
                mid = max;
                max = nums[i];
                count ++;
            }
            else if(nums[i] > mid) {
                min = mid;
                mid = nums[i];
                count ++;
            }
            else if(nums[i] >= min) {
                min = nums[i];
                count ++;
            }
        }
        
        if(count >= 3)
            return min;
        else return max;
    }
};

Leetcode415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

• The length of both num1 and num2 is < 5100.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

简单模拟，做的及其纠结。

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 addStrings(string nums1, string nums2) {
        if(nums1.length() < nums2.length()) {
            string temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int i, j;
        for(i = nums1.length()-1, j = nums2.length()-1; i >= 0 && j >= 0; i --, j --) {
            nums1[i] = nums1[i] + nums2[j] - 48;
            if(nums1[i] > 57) {
                if(i == 0)
                    break;
                nums1[i] -= 10;
                nums1[i - 1] = nums1[i - 1] + 1;
            }
        }
        if(i < 0) {
            i ++;
            if(nums1[i] > 57) {
                nums1[i] -= 10;
                if(i == 0)
                    nums1 = "1" + nums1;
                else
                    nums1[i - 1] ++;
            }
        }
        else { 
            while(i >= 0 && nums1[i] > 57) {
                nums1[i] -= 10;
                if(i == 0)
                    nums1 = "1" + nums1;
                else
                    nums1[i - 1] ++;
                i --;
            }
        }
        return nums1;
    }
};

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

class Solution {
public:
    string addStrings(string num1, string num2) {
        // computing lengths of both strings
        int num1length = num1.length() - 1;
        int num2length = num2.length()- 1;
        
        //  solution string
        string sol = "";
        
        // remainder for when summing two numbers
        int remainder = 0;
        
        // while both strings haven't been consumed 
        while (num1length >= 0 || num2length >= 0) {
            
            // get current characters of iteration
            int current_num1 = (num1length >= 0) ? num1.at(num1length) - '0' : 0;
            int current_num2 = (num2length >= 0) ? num2.at(num2length) - '0' : 0;
            
            // appending sum and remainder from previous to solution string 
            int sum = current_num1 + current_num2 + remainder;     
            sol = std::to_string(sum % 10) + sol;
            
            // determining whether there's a remainder for next sum
            remainder = (sum > 9) ? 1 : 0;
            
            // decrementing for next addition
            num1length--;
            num2length--;
            
        }
        
        // append final remainder if there is one 
        sol = (remainder == 1) ? std::to_string(1) + sol : sol;
        
        return sol;        
    }
};

Leetcode416. Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

1
2
3

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

这道题给了我们一个数组，问这个数组能不能分成两个非空子集合，使得两个子集合的元素之和相同。那么想，原数组所有数字和一定是偶数，不然根本无法拆成两个和相同的子集合，只需要算出原数组的数字之和，然后除以2，就是 target，那么问题就转换为能不能找到一个非空子集合，使得其数字之和为 target。开始博主想的是遍历所有子集合，算和，但是这种方法无法通过 OJ 的大数据集合。于是乎，动态规划 Dynamic Programming 就是不二之选。定义一个一维的 dp 数组，其中 dp[i] 表示原数组是否可以取出若干个数字，其和为i。那么最后只需要返回 dp[target] 就行了。

初始化 dp[0] 为 true，由于题目中限制了所有数字为正数，就不用担心会出现和为0或者负数的情况。关键问题就是要找出状态转移方程了，需要遍历原数组中的数字，对于遍历到的每个数字 nums[i]，需要更新 dp 数组，既然最终目标是想知道 dp[target] 的 boolean 值，就要想办法用数组中的数字去凑出 target，因为都是正数，所以只会越加越大，加上 nums[i] 就有可能会组成区间 [nums[i], target] 中的某个值，那么对于这个区间中的任意一个数字j，如果 dp[j - nums[i]] 为 true 的话，说明现在已经可以组成 j-nums[i] 这个数字了，再加上 nums[i]，就可以组成数字j了，那么 dp[j] 就一定为 true。如果之前 dp[j] 已经为 true 了，当然还要保持 true，所以还要 ‘或’ 上自身，于是状态转移方程如下：

1

dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)

有了状态转移方程，就可以写出代码了，这里需要特别注意的是，第二个 for 循环一定要从 target 遍历到 nums[i]，而不能反过来，想想为什么呢？因为如果从 nums[i] 遍历到 target 的话，假如 nums[i]=1 的话，那么 [1, target] 中所有的 dp 值都是 true，因为 dp[0] 是 true，dp[1] 会或上 dp[0]，为 true，dp[2] 会或上 dp[1]，为 true，依此类推，完全使的 dp 数组失效了，参见代码如下：

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

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
        if (sum & 1) return false;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};

Leetcode417. Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

1
2

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2:

1
2

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

上面一条边和左边一条边代表的是太平洋，右边一条边和下边一条边代表的是大西洋。现在告诉你水往低处流，问哪些位置的水能同时流进太平洋和大西洋？

直接DFS求解。一般来说DFS需要有固定的起点，但是对于这个题，四条边界的每个位置都算作起点。

使用两个二维数组，分别记录每个位置的点能不能到达太平洋和大西洋。然后对4条边界进行遍历，看这些以这些边为起点能不能所有的地方。注意了，因为是从边界向中间去寻找，所以，这个时候是新的点要比当前的点海拔高才行。

最坏情况下的时间复杂度是O((M+N)*MN)，空间复杂度是O(MN)。

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

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        if (m == 0)
            return {};
        int n = heights[0].size();
        vector<vector<int>> res;
        vector<vector<bool>> p_flags(m, vector<bool>(n ,false));
        vector<vector<bool>> a_flags(m, vector<bool>(n ,false));
        
        for (int i = 0; i < m; i ++) {
            dfs(heights, p_flags, i, 0);
            dfs(heights, a_flags, i, n-1);
        }
        for (int i = 0; i < n; i ++) {
            dfs(heights, p_flags, 0,   i);
            dfs(heights, a_flags, m-1, i);
        }
        
        for (int i = 0; i < m; i ++)
            for (int j = 0; j < n; j ++)
                if (p_flags[i][j] && a_flags[i][j]) {
                    vector<int> t;
                    t.push_back(i);
                    t.push_back(j);
                    res.push_back(t);
                }
        return res;
    }
    
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& flags, int i, int j) {
        int m = heights.size(), n = heights[0].size();
        vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        flags[i][j] = true;
        for (int ii = 0; ii < 4; ii ++) {
            int x = i + dirs[ii].first;
            int y = j + dirs[ii].second;
            if (x >= 0 && x < m && y >= 0 && y < n && !flags[x][y] && heights[x][y] >= heights[i][j]) {
                flags[x][y] = true;
                dfs(heights, flags, x, y);
            }
        }
    }
};

Leetcode419. Battleships in a Board

Given an 2D board, count how many battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:
You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:

1
2
3

X..X
...X
...X

1
2
3

...X
XXXX
...X

利用最简单的方法找有多少个X块，这里用的遍历很方便。

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

class Solution {
	public:
    int countBattleships(vector<vector<char>>& board) {
        int x = board.size();
        int y = board[0].size();
        int res=0;
        for(int i=0;i<x;i++)
            for(int j=0;j<y;j++)
                if(board[i][j]=='X'){
                    if(j<y-1 && board[i][j+1]=='X') continue;
                    if(i<x-1 && board[i+1][j]=='X') continue;
                    res++;
	           }
	    return res;
    }
};

Leetcode421. Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Example 1:

1
2
3

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

1
2

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

• 1 <= nums.length <= 2 * 105
• 0 <= nums[i] <= 231 - 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

class Solution {
public:
    
    struct Node {
        int son[2];
        Node() {
            son[0] = son[1] = -1;
        }
    };
    
    vector<Node> nodes;
    
    int findMaximumXOR(vector<int>& a) {
        // 让异或的结果最高位尽可能大
        // 从高位到低位考虑，ai当前这个位为0，那希望aj当前位为1
        // 用前缀树
	        
        if (a.size() == 0)
            return 0;
	        
        nodes.push_back({});
        insert(a.back());
        
        int ret = 0;
        for (int i = a.size()-2; i >= 0; i --) {
           int ans = query(a[i]);
           ret = max(ret, ans);
           insert(a[i]);
        }
        return ret;
	    }
    
    void insert(int a) {
        int id = 0;
        for (int i = 31; i >= 0; i --) {
            int t = (a >> i) & 1;
            if (nodes[id].son[t] == -1) {
                nodes.push_back({});
                nodes[id].son[t] = nodes.size()-1;
            }
            id = nodes[id].son[t];
        }
    }
    
    int query(int x) {
        int ret = 0;
        int id = 0;
        for (int i = 31; i >= 0; i --) {
            int b = (x >> i) & 1;
            int b2 = b ^ 1;
            if (nodes[id].son[b2] != -1) {
               id = nodes[id].son[b2];
               ret |= (1 << i);
            }
            else {
                id = nodes[id].son[b];
            }
        }
        return ret;
    }    
};

Leetcode423. Reconstruct Original Digits from English

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

• Input contains only lowercase English letters.
• Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
• Input length is less than 50,000.

Example 1:

1
2

Input: "owoztneoer"
Output: "012"

Example 2:

1
2

Input: "fviefuro"
Output: "45"

这道题给了我们一串英文字符串，是由表示数字的英文单词组成的，不过字符顺序是打乱的，让我们重建出数字。那么这道题的思路是先要统计出各个字符出现的次数，然后算出每个单词出现的次数，然后就可以重建了。由于题目中限定了输入的字符串一定是有效的，那么不会出现无法成功重建的情况，这里需要用个trick。

我们仔细观察这些表示数字的单词”zero”, “one”, “two”, “three”, “four”, “five”, “six”, “seven”, “eight”, “nine”，我们可以发现有些的单词的字符是独一无二的，比如z，只出现在zero中，还有w，u，x，g这四个单词，分别只出现在two，four，six，eight中，那么这五个数字的个数就可以被确定了，由于含有o的单词有zero，two，four，one，其中前三个都被确定了，那么one的个数也就知道了；由于含有h的单词有eight，three，其中eight个数已知，那么three的个数就知道了；由于含有f的单词有four，five，其中four个数已知，那么five的个数就知道了；由于含有s的单词有six，seven，其中six个数已知，那么seven的个数就知道了；由于含有i的单词有six，eight，five，nine，其中前三个都被确定了，那么nine的个数就知道了。

知道了这些问题就变的容易多了，我们按这个顺序”zero”, “two”, “four”, “six”, “eight”, “one”, “three”, “five”, “seven”, “nine”就能找出所有的个数了，参见代码如下：

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

class Solution {
public:
    string originalDigits(string s) {
        string res = "";
        vector<string> words{"zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"};
        vector<int> nums{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}, counts(26, 0);
        vector<char> chars{'z', 'w', 'u', 'x', 'g', 'o', 'h', 'f', 's', 'i'};
        for (char c : s) ++counts[c - 'a'];
        for (int i = 0; i < 10; ++i) {
            int cnt = counts[chars[i] - 'a'];
            for (int j = 0; j < words[i].size(); ++j) {
                counts[words[i][j] - 'a'] -= cnt;
            }
            while (cnt--) res += (nums[i] + '0');
        }
        sort(res.begin(), res.end());
        return res;
    }
};

Leetcode424. Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 10 4.

Example 1:

1
2
3
4
5
6
7
8

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5
6
7
8
9

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

这道题给我们了一个字符串，说我们有k次随意置换任意字符的机会，让我们找出最长的重复字符的字符串。我们首先来想，如果没有k的限制，让我们求把字符串变成只有一个字符重复的字符串需要的最小置换次数，那么就是字符串的总长度减去出现次数最多的字符的个数。如果加上k的限制，我们其实就是求满足 (子字符串的长度减去出现次数最多的字符个数)<=k 的最大子字符串长度即可，搞清了这一点，我们也就应该知道怎么用滑动窗口来解了吧。我们用一个变量 start 记录滑动窗口左边界，初始化为0，然后遍历字符串，每次累加出现字符的个数，然后更新出现最多字符的个数，然后我们判断当前滑动窗口是否满足之前说的那个条件，如果不满足，我们就把滑动窗口左边界向右移动一个，并注意去掉的字符要在 counts 里减一，直到满足条件，我们更新结果 res 即可。需要注意的是，当滑动窗口的左边界向右移动了后，窗口内的相同字母的最大个数貌似可能会改变啊，为啥这里不用更新 maxCnt 呢？这是个好问题，原因是此题让求的是最长的重复子串，maxCnt 相当于卡了一个窗口大小，我们并不希望窗口变小，虽然窗口在滑动，但是之前是出现过跟窗口大小相同的符合题意的子串，缩小窗口没有意义，并不会使结果 res 变大，所以我们才不更新 maxCnt 的，参见代码如下：

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

class Solution {
public:
    int characterReplacement(string s, int k) {
        int res = 0, maxCnt = 0, start = 0;
        vector<int> counts(26, 0);
        for (int i = 0; i < s.size(); ++i) {
            maxCnt = max(maxCnt, ++counts[s[i] - 'A']);
            while (i - start + 1 - maxCnt > k) {
                --counts[s[start] - 'A'];
                ++start;
            }
            res = max(res, i - start + 1);
        }
        return res;
    }
};

Leetcode427. Construct Quad Tree

Given a n * n matrix grid of 0’s and 1’s only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1’s or False if the node represents a grid of 0’s.
• isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

1
2
3
4
5
6
7
8

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e all 1’s or all 0’s) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.

Example 1:

1
2
3
4
5
6

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

这道题让我们根据一个二维数组来建立一棵四叉树，首先整个数组被分成了四等份，左上，左下，和右下部分内的值均相同，那么他们都是一个叶结点，而右上只有再四等分一下，才能使各自部分内的值相同，所以其就不是叶结点，而四等分后的每个区间才是叶结点。题目中限定了N的值一定是2的指数，就是说其如果可分的话，一定可以四等分，而之前说了，只有区间内的值不同时，才需要四等分，否则整体就当作一个叶结点。所以我们需要check四等分区间内的值是否相同，当然，我们可以将二维数组拆分为四个二维数组，但是那样可能不太高效，而且还占用额外空间，一个比较好的选择是用坐标变量来控制等分数组的范围，我们只需要一个起始点坐标，和区间的长度，就可以精确定位一个区间了。

比如说对于例子中的整个二维数组数组来说，知道起始点坐标 (0, 0)，还有长度8，就知道表示的是哪个区间。我们可以遍历这个区间上的其他所有的点，跟起点对比，只要有任何点跟起点不相同，则说明该区间是可分的，因为我们前面说了，只有一个区间上所有的值均相同，才能当作一个叶结点。只要有不同，就表示可以四分，那么我们就新建一个结点，这里的左上，左下，右上，和右下四个子结点就需要用过调用递归函数来实现了，实现原理都一样。

对于非叶结点，结点值可以是true或者false都没问题。如果某个区间上所有值均相同，那么就生成一个叶结点，结点值就跟区间值相同，isLeaf是true，四个子结点均为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

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return build(grid, 0, 0, grid.size()-1, grid.size()-1);
    }
    
    Node* build(vector<vector<int>>& grid, int r0, int c0, int r1, int c1) {
        if (r0 > r1 || c0 > c1)
            return NULL;
        bool isleaf = true;
        int val = grid[r0][c0];
        for (int i = r0; i <= r1; i ++)
            for (int j = c0; j <= c1; j ++)
                if (grid[i][j] != val) {
                    isleaf = false;
                    break;
                }
        if (isleaf)
            return new Node(val == 1, true, NULL, NULL, NULL, NULL);
        int mid1 = (r0+r1) / 2, mid2 = (c0+c1) / 2;
        return new Node(false, false, 
                       build(grid, r0, c0, mid1, mid2), 
                       build(grid, r0, mid2+1, mid1, c1),
                       build(grid, mid1+1, c0, r1, mid2), 
                       build(grid, mid1+1, mid2+1, r1, c1));
    }
};

Leetcode429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

Note:

• The depth of the tree is at most 1000.
• The total number of nodes is at most 5000.

这道题给了我们一棵N叉树，让我们对其进行层序遍历。虽说现在每一个结点可能有很多个子结点，但其实处理的思路的都是一样的。子结点放到了一个children数组中，我们访问的时候只要遍历数组就行了。先来看迭代的写法，用到了队列queue来辅助，首先判断root是否为空，为空直接返回空数组，否则加入queue中。然后遍历queue，这里用的trick就是，要加个for循环，要将当前queue中的结点的个数统计下来，因为再加入下一层的结点时，queue的结点个数会增加，而在加入下一层结点之前，当前queue中的结点个数全都属于一层，所以我们要把层与层区分开来，将同一层的结点都放到一个数组out中，之后再放入结果res中，这种层序遍历的思想在迷宫遍历找最短路径的时候应用的也很多，是个必须要掌握的方法呢，参见代码如下：

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

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<Node*> q{{root}};
        while (!q.empty()) {
            vector<int> out;
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); q.pop();
                out.push_back(t->val);
                if (!t->children.empty()) {
                    for (auto a : t->children) q.push(a);
                }
            }
            res.push_back(out);
        }
        return res;
    }
};

Leetcode430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

1
2

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]

Explanation:

The multilevel linked list in the input is as follows:

Example 2:

1
2

Input: head = [1,2,null,3]
Output: [1,3,2]

Explanation:

1
2
3
4
5

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

这道题给了一个多层的双向链表，让我们压平成为一层的双向链表，题目中给了形象的图例，不难理解题意。根据题目中给的例子，我们可以看出如果某个结点有下一层双向链表，那么下一层双向链表中的结点就要先加入进去，如果下一层链表中某个结点还有下一层，那么还是优先加入下一层的结点，整个加入的机制是DFS的，就是有岔路先走岔路，走到没路了后再返回，这就是深度优先遍历的机制。好，那么既然是DFS，肯定优先考虑递归啦。方法有了，再来看具体怎么递归。由于给定的多层链表本身就是双向的，所以我们只需要把下一层的结点移到第一层即可，那么没有子结点的结点就保持原状，不作处理。只有对于那些有子结点的，我们需要做一些处理，由于子结点链接的双向链表要加到后面，所以当前结点之后要断开，再断开之前，我们用变量 next 指向下一个链表，然后对子结点调用递归函数，我们 suppose 返回的结点已经压平了，那么就只有一层，就相当于要把这一层的结点加到断开的地方，所以需要知道这层的最后一个结点的位置，我们用一个变量 last，来遍历到压平的这一层的末结点。现在就可以开始链接了，首先把子结点链到 cur 的 next，然后把反向指针 prev 也链上。此时 cur 的子结点 child 可以清空，然后压平的这一层的末节点 last 链上之前保存的 next 结点，如果 next 非空，那么链上反向结点 prev。这些操作完成后，我们就已经将压平的这一层完整的加入了之前层断开的地方，继续在之前层往下遍历即可，参见代码如下：

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

class Solution {
public:
    Node* flatten(Node* head) {
        Node *cur = head;
        while (cur) {
            if (cur->child) {
                Node *next = cur->next;
                Node *last = cur->child;
                while (last->next) last = last->next;
                cur->next = cur->child;
                cur->next->prev = cur;
                cur->child = NULL;
                last->next = next;
                if (next) next->prev = last;    
            }
            cur = cur->next;
        }
        return head;
    }
};

Leetcode433. Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from ‘A’, ‘C’, ‘G’, and ‘T’.

Suppose we need to investigate a mutation from a gene string start to a gene string end where one mutation is defined as one single character changed in the gene string.

For example, “AACCGGTT” —> “AACCGGTA” is one mutation. There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings start and end and the gene bank bank, return the minimum number of mutations needed to mutate from start to end. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

1
2

Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

1
2

Input: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

Example 3:

1
2

Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3

先建立bank数组的距离场，这里距离就是两个字符串之间不同字符的个数。然后以start字符串为起点，向周围距离为1的点扩散，采用BFS搜索，每扩散一层，level自加1，当扩散到end字符串时，返回当前level即可。注意我们要把start字符串也加入bank中，而且此时我们也知道start的坐标位置，bank的最后一个位置，然后在建立距离场的时候，调用一个count子函数，用来统计输入的两个字符串之间不同字符的个数，注意dist[i][j]和dist[j][i]是相同，所以我们只用算一次就行了。然后我们进行BFS搜索，用一个visited集合来保存遍历过的字符串，注意检测距离的时候，dist[i][j]和dist[j][i]只要有一个是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

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        if (bank.empty())
            return -1;
        bank.push_back(start);
        int res = 0, len = bank.size();
        queue<int> q;
        vector<vector<int> > dist(len, vector<int>(len, 0));
        vector<int> visited(len, 0);
        for (int i = 0; i < len; i ++)
            for (int j = i+1; j < len; j ++)
                dist[i][j] = cal_dist(bank[i], bank[j]);
        q.push(len-1);
        
        while(!q.empty()) {
            res ++;
            int size = q.size();
            for (int i = 0; i < size; i ++) {
                int t = q.front();
                q.pop();
                visited[t] = true;
                 for (int j = 0; j < len; j ++) {
                    if ((dist[t][j] != 1 && dist[j][t] != 1) || visited[j])
                        continue;
                    q.push(j);
                    if (bank[j] == end)
                        return res;
                }
            }
        }
        return -1;
    }
    
    int cal_dist(string a, string b) {
        int cnt = 0, len = a.length();
        for (int i = 0; i < len; i ++)
            if (a[i] != b[i])
                cnt ++;
        return cnt;
    }
};

Leetcode434. Number of Segments in a String

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

1
2

Input: "Hello, my name is John"
Output: 5

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

class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        if(s == "" || s == " ")
            return 0;
        for(int i = 0; i < s.length(); i ++) {
            if(s[i] != ' ')
                res ++;
            while(i < s.length() && s[i] != ' ')
                i ++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8

int countSegments(string s) {
	stringstream ss(s);
	string word;
	int count = 0;
	while (ss >> word)
		count++;
	return count;
}

Leetcode435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

1
2
3

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

1
2
3

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

这道题给了我们一堆区间，让求需要至少移除多少个区间才能使剩下的区间没有重叠，那么首先要给区间排序，根据每个区间的 start 来做升序排序，然后开始要查找重叠区间，判断方法是看如果前一个区间的 end 大于后一个区间的 start，那么一定是重复区间，此时结果 res 自增1，我们需要删除一个，那么此时究竟该删哪一个呢，为了保证总体去掉的区间数最小，我们去掉那个 end 值较大的区间，而在代码中，我们并没有真正的删掉某一个区间，而是用一个变量 last 指向上一个需要比较的区间，我们将 last 指向 end 值较小的那个区间；如果两个区间没有重叠，那么此时 last 指向当前区间，继续进行下一次遍历，参见代码如下：

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

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int res = 0, begin = 0, end = 0;
        sort(intervals.begin(), intervals.end());
        begin = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i ++) {
            if (end > intervals[i][0]) {
                res ++;
                if (end > intervals[i][1])
                    end = intervals[i][1];
            }
            else
                end = intervals[i][1];
        }
        return res;
    }
};

Leetcode436. Find Right Interval

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

1
2
3

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

1
2
3
4

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

这道题给了我们一堆区间，让我们找每个区间的最近右区间，要保证右区间的 start 要大于等于当前区间的 end，由于区间的顺序不能变，所以我们不能给区间排序，我们需要建立区间的 start 和该区间位置之间的映射，由于题目中限定了每个区间的 start 都不同，所以不用担心一对多的情况出现。然后我们把所有的区间的 start 都放到一个数组中，并对这个数组进行降序排序，那么 start 值大的就在数组前面。然后我们遍历区间集合，对于每个区间，我们在数组中找第一个小于当前区间的 end 值的位置，如果数组中第一个数就小于当前区间的 end，那么说明该区间不存在右区间，结果 res 中加入-1；如果找到了第一个小于当前区间 end 的位置，那么往前推一个就是第一个大于等于当前区间 end 的 start，我们在 HashMap 中找到该区间的坐标加入结果 res 中即可，参见代码如下：（下边改进为二分搜索，速度快了十几倍）

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

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        unordered_map<int, int> map;
        vector<int> start;
        for (int i = 0; i < intervals.size(); i ++) {
            map[intervals[i][0]] = i;
            start.push_back(intervals[i][0]);
        }
        sort(start.begin(), start.end());
        vector<int> ress;
        int len = intervals.size();
        
        for (int i = 0; i < len; i ++) {
            int low = 0, high = len-1, mid;
            int best = -1;
            while(low <= high) {
                mid = low + (high-low) / 2;
                if (start[mid] < intervals[i][1])
                    low = mid+1;
                else {
                    best = map[start[mid]];
                    high = mid-1;
                }
            }
            ress.push_back(best);
        }
        return ress;
    }
};

Leetcode437. Path Sum III

You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

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

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

这道题让我们求二叉树的路径的和等于一个给定值，说明了这条路径不必要从根节点开始，可以是中间的任意一段，而且二叉树的节点值也是有正有负。那么可以用递归来做，相当于先序遍历二叉树，对于每一个节点都有记录了一条从根节点到当前节点到路径，同时用一个变量 curSum 记录路径节点总和，然后看 curSum 和 sum 是否相等，相等的话结果 res 加1，不等的话继续查看子路径和有没有满足题意的，做法就是每次去掉一个节点，看路径和是否等于给定值，注意最后必须留一个节点，不能全去掉了，因为如果全去掉了，路径之和为0，而如果给定值刚好为0的话就会有问题。

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

class Solution {
public:
    int ans = 0;
    
    void dfs(TreeNode* root, vector<TreeNode*>& out, int sum, int cur) {
        if(root == NULL)
            return;
        cur += root->val;
        if (cur == sum) ++ans;
        out.push_back(root);
        int t = cur;
        for(int i = 0; i < out.size() - 1; i ++) {
            t = t - out[i]->val;
            if (t == sum) 
                ++ans;
        }
        dfs(root->left, out, sum, cur);
        dfs(root->right, out, sum, cur);
        out.pop_back();
    }
    
    int pathSum(TreeNode* root, int sum) {
        vector<TreeNode*> out;
        dfs(root, out, sum, 0);
        return ans;
    }
};

Leetcode438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

Example 1:

1
2
3
4
5

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

1
2
3
4
5
6

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

这道题给了我们两个字符串s和p，让在s中找字符串p的所有变位次的位置，所谓变位次就是字符种类个数均相同但是顺序可以不同的两个词，那么肯定首先就要统计字符串p中字符出现的次数，然后从s的开头开始，每次找p字符串长度个字符，来验证字符个数是否相同，如果不相同出现了直接 break，如果一直都相同了，则将起始位置加入结果 res 中，参见代码如下：（不用unordered_map而是用vector会更快！）

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

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> map, maps;
        vector<int> res;
        int lens = s.length(), lenp = p.length();
        for (int i = 0; i < 26; i ++) {
            map['a' + i] = 0;
            maps['a' + i] = 0;
        }
        for (int i = 0; i < lenp; i ++) {
            map[p[i]] ++;
        }
        if (lenp > lens) 
            return {};
        for (int i = 0; i < lenp-1; i ++)
            maps[s[i]] ++;
        for (int i = lenp-1; i < lens; i ++) {
            maps[s[i]] ++;
            
            int j = 0;
            for(j = 0; j < 26; j ++) 
                if (maps['a' + j] != map['a' + j])
                    break;            
            if (j == 26)
                res.push_back(i-lenp+1);
            maps[s[i-lenp+1]] --;
        }
        return res;
    }
};

Leetcode441. Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7

n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

1
2
3
4
5
6
7
8
9

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

1
2
3
4
5
6
7
8
9
10

int arrangeCoins(int n) {
    int i = 1, ans = n;
    if(n == 1)
        return 1;
    while(ans >= i) {
        ans -= i;
        i ++;
    }
    return i-1;
}

1
2
3
4

int arrangeCoins(int n)
{
    return (int)(sqrt(2 * (double)n + 0.25) - 0.5);
}

Leetcode442. Find All Duplicates in an Array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

1
2

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

1
2

Input: nums = [1,1,2]
Output: [1]

Example 3:

1
2

Input: nums = [1]
Output: []

这类问题的一个重要条件就是1 ≤ a[i] ≤ n (n = size of array)，不然很难在O(1)空间和O(n)时间内完成。首先来看一种正负替换的方法，这类问题的核心是就是找nums[i]和nums[nums[i] - 1]的关系，我们的做法是，对于每个nums[i]，我们将其对应的nums[nums[i] - 1]取相反数，如果其已经是负数了，说明之前存在过，我们将其加入结果res中即可，参见代码如下：

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

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            int idx = abs(nums[i]) - 1;
            if (nums[idx] < 0) res.push_back(idx + 1);
            nums[idx] = -nums[idx];
        }
        return res;
    }
};

本题使用Set的数据结构对数组进行遍历，找到出现两次的元素。

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

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        set<int> s;
        unordered_map<int, bool> flags;
        for (int n : nums) {
            if (!s.count(n))
                s.insert(n);
            else
                res.push_back(n);
        }
        return res;
    }
};

Leetcode443. String Compression

Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

1
2
3
4
5
6
7
8

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

1
2
3
4
5
6
7
8

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

1
2
3
4
5
6
7
8
9

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

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 compress(vector<char>& chars) {
        int ans = 0;
        char c = chars[0], cc = c;
        int cur = 1, pointer = 0;
        string nums;
        for(int i = 1; i < chars.size(); i ++) {
            if(chars[i] != c) {
                cout << c << " " << cur << endl;
                chars[pointer++] = c;
                nums = to_string(cur);
                if(cur == 1) {
                    c = chars[i];
                    continue;
                }
                for(int i = 0; i < nums.length(); i ++) {
                    chars[pointer++] = nums[i];
                }
                cur = 1;
                c = chars[i];
            }
            else
                cur ++;
        }
        chars[pointer++] = c;
        if(cur == 1) {
            return pointer;
        }
        nums = to_string(cur);
        for(int i = 0; i < nums.length(); i ++) {
            chars[pointer++] = nums[i];
        }
        return pointer;
    }
};

Leetcode445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

1
2

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

1
2

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

1
2

Input: l1 = [0], l2 = [0]
Output: [0]

由于加法需要从最低位开始运算，而最低位在链表末尾，链表只能从前往后遍历，没法取到前面的元素，那怎么办呢？我们可以利用栈来保存所有的元素，然后利用栈的后进先出的特点就可以从后往前取数字了，我们首先遍历两个链表，将所有数字分别压入两个栈s1和s2中，我们建立一个值为0的res节点，然后开始循环，如果栈不为空，则将栈顶数字加入sum中，然后将res节点值赋为sum%10，然后新建一个进位节点head，赋值为sum/10，如果没有进位，那么就是0，然后我们head后面连上res，将res指向head，这样循环退出后，我们只要看res的值是否为0，为0返回res->next，不为0则返回res即可，参见代码如下：

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

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        ListNode *head = l1;
        while(head) {
            s1.push(head->val);
            head = head->next;
        }
        head = l2;
        while(head) {
            s2.push(head->val);
            head = head->next;
        }
        head = NULL;
        int sum = 0;
        while(!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }
            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }
            head = new ListNode(sum%10, head);
            sum /= 10;
        }
        if (sum > 0)
            head = new ListNode(sum, head);
        return head;
    }
};

Leetcode447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

1
2
3

Input: [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

抓住两组点 (x1,y1)、(x2,y2) 和 (x1,y1)、(x3,y3) 之间的距离相等这个信息：distance = sqrt{(x1-x2)^2+(y1-y2)^2} = sqrt{(x1-x3)^2+(y1-y3)^2}

按照这种相等的距离，我们可以给所有点进行分类，相同距离的这些点（假设n个）可以构成一个排列组合中的排列：n*(n-1)个回旋镖。

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

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        unordered_map<int, int> hash;
        for(int i=0;i<points.size();i++){
            for(int j=0;j<points.size();j++){
                hash[pow(points[i][0]-points[j][0],2)+pow(points[i][1]-points[j][1],2)] += 1;
            }
            for(auto d:hash){
                ans += d.second*(d.second-1);
            }
            hash.clear();
        }
        return ans;
    }
};

Leetcode448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

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

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
                --i;
            }
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

Leetcode449. Serialize and Deserialize BST

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

1
2

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

1
2

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

用队列来做，比较慢，但是很原生且具有通用性：

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