猩猩的乐园

原题说明

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example 1:

Input: "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

Note:

1. S.length <= 10000
2. S[i] is "(" or ")"
3. S is a valid parentheses string
   Read more »

原题说明

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers.

Example 1:

Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:

1. The number of nodes in the tree is between 1 and 1000.
2. node.val is 0 or 1.
3. The answer will not exceed 2^31 - 1.

原题说明

You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.

Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We can’t cover [0,5] with only [0,1] and [0,2].

Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation:
We can take clips [0,4], [4,7], and [6,9].

Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation:
Notice you can have extra video after the event ends.

解题思路

先对clips按起始段位置从小到大排序。然后我们用贪心算法，用cur_end记录当前实际位置的最远端，potential_end记录目前可能的最远端。分别初始化为-1和0。

对clips进行遍历：

1. 当potential_end大于T或者clip的起始位置大于potential_end，意味着之后所有的clip都不需要再做考虑了，要么已经满足题意，要么就会出现不能覆盖的区间。
2. 否则，当clip的起始位置大于cur_end，意味着为了覆盖所有区间，必须更新cur_end 和 potential_end，同时有一个clip需要加入res中。

示例代码 (cpp)

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

class Solution {
private:
    static bool clipCmp(vector<int> clipA, vector<int> clipB) {
        return clipA[0] == clipB[0] ? clipA[1] <= clipB[1] : clipA[0] < clipB[0]; 
    }
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end(), clipCmp);
        int res = 0;
        int cur_end = -1; // 当前实际的最远端
        int potential_end = 0; // 当前可能的最远端
        for (auto clip : clips) {
            if (potential_end >= T || clip[0] > potential_end) {
                break;
            }
            else if (clip[0] > cur_end) { //当前的这个clip不可能被选取，需要更新cur_end，并让res++
                res++;
                cur_end = potential_end;
            }
            potential_end = max(potential_end, clip[1]);
        }
        return potential_end >= T ? res : -1;
    }
};

复杂度分析

时间复杂度: O(n*log n)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！

原题说明

Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)

A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.

Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: There are three 1s that are enclosed by 0s, and one 1 that isn’t enclosed because its on the boundary.

Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: All 1s are either on the boundary or can reach the boundary.

Note:

1. 1 <= A.length <= 500
2. 1 <= A[i].length <= 500
3. 0 <= A[i][j] <= 1
4. All rows have the same size.

原题说明

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

Input: [0,1,1]
Output: [true,false,false]
Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.

Input: [1,1,1]
Output: [false, false, false]

Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]

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

Note:

1. 1 <= A.length <= 30000
2. A[i] is 0 or 1

原题说明

Given a binary string S (a string consisting only of '0' and '1's) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true

Example 2:

Input: S = "0110", N = 4
Output: false

Note:

1. 1 <= S.length <= 1000
2. 1 <= N <= 10^9

原题说明

Given an array A of positive integers, A[i] represents the value of the i - th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: [8, 1, 5, 2, 6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11.

Note:

1. 2 <= A.length <= 50000
2. 1 <= A[i] <= 1000

原题说明

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Input: 1000
Output: 262.

Note:

1. 1 <= N <= 10^9

解题思路

题目要求求出比N小，同时至少存在一个重复数字的正整数的个数。运用brute force方法直接计算满足题目要求的数会有超时的问题，时间复杂度是O(N)，不满足要求。更好的方法是先求出所有不满足要求的数的个数res，再用N减去res，反过来得出答案。

这里，不满足题目要求的数可以分为两类;

1. 第一类是位数比N小的数，同时数字各不相同
2. 第二类是位数与N相同的，比N小，同时数字各不相同。

这两类数就包含了所有不大于N，同时数字各不相同的数，而剩下的数就是至少包含一个相同数字，且不大于N的数。

同时，我们需要一个辅助函数helper,它的作用是用来求出m个不同数字组成长度是n位的数的个数。

第一类数的求解相对简单，最高位的可能是1~9一共9中可能，之后可以直接调用helper方便求解。

第二类数，需要分别对不同的相同前缀做分类计算。在确定相同前缀之后，再次调用helper可以求出对应的数的个数。

示例代码 (cpp)

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

/*
example: 8765

the number with digits < N

XXX
XX
X

number with same prefix

1XXX ~ 7XXX
80XX ~ 86XX
870X ~ 875X
8760 ~ 8765
*/

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        int N_copy = N + 1;
        int res = 0;
        vector<int> arr;
        while (N_copy > 0) {
            arr.insert(arr.begin(), N_copy % 10);
            N_copy = N_copy / 10;
        }
        int n = arr.size();
        // count the number with digits < N
        for (int i = 1; i < n; ++i) {
            res += 9 * helper(9 , i - 1);
        }
        // cout the number with same prefix
        unordered_set<int> seen;
        for (int i = 0; i < n; ++i) {
            for (int j = i == 0 ? 1 : 0; j < arr[i]; ++j) {
                if (!seen.count(j)) {
                    res += helper(9 - i, n - i - 1);
                }
            }
            if (seen.count(arr[i])) { //相同前缀中有相同的数字，不符合要求，不用继续计算之后的前缀了
                break;
            }
            seen.insert(arr[i]);
        }
        return N - res;
    }
    // helper函数，返回由m个digit，n位数位可以组成的数的个数
    // m--可以用于组合数字的digit个数
    // n--需要组成的位数
    int helper(int m, int n) {
        return n == 0 ? 1 : m * helper(m - 1, n - 1);
    }
};

复杂度分析

时间复杂度: O(log N)
空间复杂度: O(log N)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！

原题说明

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1. 1 <= time.length <= 60000
2. 1 <= time[i] <= 500

解题思路

一个pair能被60整除，意味着两个数的余数的和也能被60整除。因此，一个数可以按照对60的余数进行分类。这样，按题目给出的要求，一共有0，1，2，...，59一共60个分类。当两个分类的和被60整除时，从每个分类中任意选取1个数，都能组成满足题目要求的一个pair。

因此，我们可以用一个哈希表mapping记录上述的分类，哈希表的key是余数，value是有着对应余数的数的个数。

这里，最简单的做法是先遍历一边time，将mapping更新好。然后再遍历一边mapping,按照余数计算pair的数量。但是这个方法的缺点在于：

1. 需要遍历一遍time，再遍历一遍mapping
2. 需要对0和30两类余数的情况做特殊处理。因为他们对应的满足题目条件的余数就是他们自身。

所以我们提供一种只遍历一遍time的方法，并且不需要特别处理余数是0和30的情况

算法：遍历time，在每个 iteration 中，当前元素对60的余数是remainder，在pair中对应的余数是c_remainder。这样，pair增加的数量就是mapping中c_remainder的value。同时，需要再更新mapping，使得mapping[remainder]++。

示例代码 (cpp)

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

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {        
        unordered_map<int,int> mapping;
        int res = 0;
        for (auto ele : time) {
            int remainder = ele % 60;
            int c_remainder = (60 - remainder) % 60;
            if (mapping.count(c_remainder)) {
                res += mapping[c_remainder];
            }
            mapping[remainder]++;
        }
        
        return res;
    }
};

复杂度分析

时间复杂度: O(n)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！