Leetcode1301 - 1400

Posted on

Leetcode1304. Find N Unique Integers Sum up to Zero

Given an integer n, return any array containing n unique integers such that they add up to 0.

Example 1:

1
2
3
Input: n = 5
Output: [-7,-1,1,3,4]
Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].

Example 2:
1
2
Input: n = 3
Output: [-1,0,1]

Example 3:
1
2
Input: n = 1
Output: [0]

偶数关于原点对称，奇数加上一个0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> sumZero(int n) {
        if(n == 1)
            return {0};
        vector<int> res;
        int sum = 0;
        for(int i = 0; i < n-1; i ++){
            sum += i;
            res.push_back(i);
        }
        res.push_back(-sum);
        return res;
    }
};

Leetcode1309. Decrypt String from Alphabet to Integer Mapping

Given a string s formed by digits (‘0’ - ‘9’) and ‘#’ . We want to map s to English lowercase characters as follows:

  • Characters (‘a’ to ‘i’) are represented by (‘1’ to ‘9’) respectively.
  • Characters (‘j’ to ‘z’) are represented by (‘10#’ to ‘26#’) respectively.

Return the string formed after mapping. It’s guaranteed that a unique mapping will always exist.

Example 1:

1
2
3
Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

Example 2:
1
2
Input: s = "1326#"
Output: "acz"

Example 3:
1
2
Input: s = "25#"
Output: "y"

Example 4:
1
2
Input: s = "12345678910#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#"
Output: "abcdefghijklmnopqrstuvwxyz"

简单的模拟题，但是很麻烦：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string freqAlphabets(string s) {
        string res = "";
        for(int i = 0; i < s.length(); ) {
            char c = s[i];
            if(i+2 < s.length() && s[i+2] == '#') {
                char cc = s[i+1];
                int temp = (c - '0') * 10 + (cc - '0') - 1;
                res += ('a' + temp);
                i += 3;
            }
            else {
                char cc = 'a' + (c - '0' - 1);
                res += cc;
                i += 1;
            }
        }
        return res;
    }
};

Leetcode1313. Decompress Run-Length Encoded List

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [freq, val] = [nums[2i], nums[2i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.

Return the decompressed list.

Example 1:

1
2
3
4
5
Input: nums = [1,2,3,4]
Output: [2,4,4,4]
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].
At the end the concatenation [2] + [4,4,4] is [2,4,4,4].

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

Constraints:

  • 2 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        vector<int> result;
        for(int i=0;i<nums.size();i+=2) {
            for(int j=0;j<nums[i];j++) {
                result.push_back(nums[i+1]);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        vector<int> res;
        int i=0;
        while(i+1<nums.size()-i){
            int a=nums[2*i],b=nums[2*i+1];
            while(a--)
                res.push_back(b);
            i+=1;
        }
        return res;
    }
};

Leetcode1314. Matrix Block Sum

Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:

  • i - k <= r <= i + k,
  • j - k <= c <= j + k, and
  • (r, c) is a valid position in the matrix.

Example 1:

1
2
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

1
2
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100

二维前缀和求一个矩形区域的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        vector<vector<int>> ret(m, vector<int>(n, 0));
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
        }
        
        for (int i = 1; i <= m; i ++) {
            for (int j = 1; j <= n; j ++) {
                int r1 = max(1, i-k), c1 = max(1, j-k);
                int r2 = min(m, i+k), c2 = min(n, j+k);
                
                ret[i-1][j-1] = dp[r2][c2] - dp[r2][c1-1] - dp[r1-1][c2] + dp[r1-1][c1-1];
            }
        }
        return ret;
    }
};

Leetcode1317. Convert Integer to the Sum of Two No-Zero Integers

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

  • A and B are No-Zero integers.
  • A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

1
2
Input: n = 2 : [1,1]
Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

把一个数分解成两个不含有0的数的和。
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 have0(int nn) {
        while(nn) {
            int temp = nn % 10;
            if(temp == 0)
                return true;
            nn = nn / 10;
        }
        return false;
    }
    
    vector<int> getNoZeroIntegers(int n) {
        for(int i = 1; i <= n/2; i ++) {
            if(!have0(i) && !have0(n-i))
                return {i, n-i};
        }
        return {};
    }
};

Leetcode1323. Maximum 69 Number

Given a positive integer num consisting only of digits 6 and 9. Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

1
2
3
4
5
6
7
8
Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:
1
2
3
Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:
1
2
3
Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

翻转一位数（6变9）找到最大的，只要找到从头到尾第一个6就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maximum69Number (int num) {
        string numm = to_string(num);
        for(int i =0; i < numm.size(); i ++) {
            if(numm[i] == '6'){
                numm[i] = '9';
                return stoi(numm);
            }
        }
        return num;
    }
};

Leetcode1331. Rank Transform of an Array

Given an array of integers arr, replace each element with its rank. The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

1
2
3
Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

把一个数组中的数字用排序后这个数字的rank来替换，注意没有跨越rank的那种情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        map<int, int> mp;
        vector<int> rr(arr);
        sort(rr.begin(), rr.end());
        int rank = 1;
        for(int i = 0; i < rr.size(); i ++) {
            if(mp[rr[i]] == 0)
                mp[rr[i]] = rank ++;
        }
        for(int i = 0; i < arr.size(); i ++) {
            arr[i] = mp[arr[i]];
        }
        return arr;
    }
};

Leetcode1332. Remove Palindromic Subsequences

Given a string s consisting only of letters ‘a’ and ‘b’. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

1
2
3
Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:
1
2
3
4
Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:
1
2
3
4
Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:
1
2
Input: s = ""
Output: 0

由于只有 a 和 b 两个字符。其实最多的消除次数就是 2。因为我们无论如何都可以先消除全部的 1 再消除全部的 2（先消除 2 也一样），这样只需要两次即可完成。 我们再看一下题目给的一次消除的情况，题目给的例子是“ababa”，我们发现其实它本身就是一个回文串，所以才可以一次全部消除。那么思路就有了：

如果 s 是回文，则我们需要一次消除；否则需要两次，一定要注意特殊情况， 对于空字符串，我们需要 0 次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int removePalindromeSub(string s) {
        if(s.length() == 0)
            return 0;
        int ii = 0, jj = s.length()-1;
        while(ii < jj) {
            if(s[ii] != s[jj])
                break;
            ii ++;
            jj --;
        }
        if(ii < jj)
            return 2;
        else
            return 1;
    }
};

Leetcode1337. The K Weakest Rows in a Matrix

Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 2 
row 1 -> 4 
row 2 -> 1 
row 3 -> 2 
row 4 -> 5 
Rows ordered from the weakest to the strongest are [2,0,3,1,4]

Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 1 
row 1 -> 4 
row 2 -> 1 
row 3 -> 1 
Rows ordered from the weakest to the strongest are [0,2,3,1]

在mat的2维阵列中，算出每一个row当中，1的数量。利用1的数量进行排序，并返回前k名。
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> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<int> weak;
        for(int i = 0; i < mat.size(); i ++) {
            weak.push_back(0);
            int count = 0;
            for(int j = 0; j < mat[i].size(); j ++) {
                count += mat[i][j];
            }
            weak[i] = count;
        }
        map<int, vector<int>> mp;
        for(int i = 0; i < mat.size(); i ++) {
            mp[weak[i]].push_back(i);
        }
        sort(weak.begin(), weak.end());
        vector<int> res;
        int kk = 0;
        for(auto i = mp.begin(); i != mp.end() ; i ++) {
            for(int ii = 0; ii < (i->second).size(); ii ++) {
                res.push_back((i->second)[ii]);
                kk ++;
                if(kk == k)
                    break;
            }
            if(kk == k)
                break;
        }
        return res;
    }
};

Leetcode1340. Jump Game V

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

  • i + x where: i + x < arr.length and 0 < x <= d.
  • i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

1
2
3
4
5
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

1
2
3
Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

1
2
3
Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Constraints:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 105
  • 1 <= d <= arr.length

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

  • i + x ，其中 i + x < arr.length 且 0 < x <= d 。
  • i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, 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
45
46
47
48
49
50
class Solution {
public:
    
    vector<vector<int>> g;
    vector<int> dp;
    
    int dfs(int u) {
        if (dp[u] != -1)
            return dp[u];
        
        dp[u] = 0;
        for (int v : g[u]) {
            int dist = dfs(v);  // f[v]
            dp[u] = max(dp[u], dist); // 取最大的f[v]
        }
        
        dp[u] ++;
        // 这个++表示u到v的这条边
        
        return dp[u];
    }
    
    
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        g.assign(n, vector<int>());
        
        for (int i = 0; i < n; i ++) {
            // 在两个方向上，构图
            for (int j = 1; j <= d && i - j >= 0 && arr[i-j] < arr[i]; j ++)
                // 最远不能超过d，高度小过a[i]，不能跑出去边界
                g[i].push_back(i - j);
            for (int j = 1; j <= d && i + j < n && arr[i+j] < arr[i]; j ++)
                // 最远不能超过d，高度小过a[i]，不能跑出去边界
                g[i].push_back(i + j);
        }
        
        dp.assign(n, -1);
        // 从一个点出发能走的最长路径
        
        for (int i = 0; i < n; i ++)
            dfs(i);

        int res = -1;
        for (int i = 0; i < n; i ++)
            res = max(res, dp[i]);
        
        return res;
    }
};

Leetcode1346. Check If N and Its Double Exist

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

Example 1:

1
2
3
Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:
1
2
3
Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:
1
2
3
Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

注意0的问题，只有有两个0的时候返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        map<int, int> mp;
        for(int i = 0; i < arr.size(); i ++)
            mp[arr[i]] ++;
        for(int i = 0; i < arr.size(); i ++) {
            if(mp[arr[i]*2] && arr[i] != 0 || arr[i] == 0 && mp[arr[i]] > 1  )
                return true;
        }
        return false;
    }
};

Leetcode1349. Maximum Students Taking Exam

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by ‘#’ character otherwise it is denoted by a ‘.’ character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

1
2
3
4
5
Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

1
2
3
4
5
6
7
Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

1
2
3
4
5
6
7
Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

状态压缩dp

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
class Solution {
public:
    
    bool check2(int s, int ss, int m) {
        for (int k = 0; k < m; k ++) {
            int b = (s >> k) & 1;
            if (!b)
                continue;
            int bss0 = 0, bss2 = 0;
            if (k)
                bss0 = (ss >> (k-1)) & 1;
            if (k != m-1)
                bss2 = (ss >> (k+1)) & 1;
            if (bss0 || bss2)
                return false;
        }
        return true;
    }
    
    bool check(int s, const vector<char>& line, int m) {
        int preb = 0;
        for (int k = 0; k < m; k ++) {
            int b = (s >> k) & 1;
            if (b && line[k] == '#')
                return false;
            if (preb && b)
                return false;
            preb = b;
        }
        return true;
    }
    
    
    int maxStudents(vector<vector<char>>& seats) {
        int n = seats.size(), m = seats[0].size();
        
        int maxseats = 1 << m;
        vector<int> y(maxseats, 0);
        vector<int> x(maxseats, 0);
        vector<bool> oky(maxseats, true);
        vector<bool> okx(maxseats, true);
        
        for (int i = 0; i < n; i ++) {
            x.assign(maxseats, 0);
            okx.assign(maxseats, false);
            
            for (int s = 0; s < maxseats; s ++) {
                okx[s] = check(s, seats[i], m);
                if (!okx[s])
                    continue;
                
                int cnt = 0;
                for (int k = 0; k < m; k ++)
                    cnt += ( s >> k) & 1;
                
                for (int ss = 0; ss < maxseats; ss ++)
                    if (oky[ss]) {
                        if (!check2(s, ss, m))
                            continue;
                        x[s] = max(x[s], y[ss] + cnt);
                    }
            }
            swap(x, y);
            swap(okx, oky);
        }
        
        int maxv = 0;
        for (int v : y)
            maxv = max(maxv, v);
        return maxv;
    }
};

Leetcode1351. Count Negative Numbers in a Sorted Matrix

Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise. Return the number of negative numbers in grid.

Example 1:

1
2
3
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

统计一个矩阵中有多少个负数？有毛病，这么简单。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int res = 0;
        for(int i = 0; i < grid.size(); i ++)
            for(int j = 0; j < grid[0].size(); j ++)
                if(grid[i][j] < 0)
                    res ++;
        return res;
    }
};

Leetcode1356. Sort Integers by The Number of 1 Bits

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

1
2
3
4
5
6
7
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:
1
2
3
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

根据数字二进制下 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
class Solution {
public:
    
    static int bitnum(int a) {
        int res = 0;
        while(a) {
            res += a & 1;
            a = a >> 1;
        }
        return res;
    }
    
    static bool cmp(int a, int b) {
        if(bitnum(a) < bitnum(b))
            return true;
        else if(bitnum(a) == bitnum(b))
            return a < b;
        else
            return false;
    }
    
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

Leetcode1360. Number of Days Between Two Dates

Write a program to count the number of days between two dates. The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

1
2
Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:
1
2
Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

计算时间间隔，无聊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        tm time1, time2; //tm是表示日期的结构体
        memset(&time1, 0, sizeof(tm));
        memset(&time2, 0, sizeof(tm)); //初始化
        time1.tm_year = stoi(date1.substr(0, 4)) - 1900; //year表示与1900年的差值
        time1.tm_mon = stoi(date1.substr(5, 2)) - 1;
        time1.tm_mday = stoi(date1.substr(8, 2));
        time2.tm_year = stoi(date2.substr(0, 4)) - 1900;
        time2.tm_mon = stoi(date2.substr(5, 2)) - 1; //mon从0开始取值
        time2.tm_mday = stoi(date2.substr(8, 2));
        time_t t1 = mktime(&time1), t2 = mktime(&time2); //mktime用于将struct tm转化为time_t类型
        return abs(t1 - t2) / (3600 * 24);  //time_t就是天数
    }
};

Leetcode1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j’s such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

这个算法用的是map，为什么能管用呢，因为map内部已经把数字排好序了，用iterator遍历的时候相当于是有序的了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res;
        map<int, int> mp;
        for(int i = 0; i < nums.size(); i ++) {
            mp[nums[i]] ++;
        }
        int presum = 0;
        for(auto a = mp.begin(); a != mp.end(); a ++) {
            int sec = a->second;
            mp[a->first] = presum;
            presum = presum + sec;
        }
        for(int i = 0; i < nums.size(); i ++){
            res.push_back(mp[nums[i]]);
        }
        return res;
    }
};

Leetcode1370. Increasing Decreasing String

Given a string s. You should re-order the string using the following algorithm:

  • Pick the smallest character from s and append it to the result.
  • Pick the smallest character from s which is greater than the last appended character to the result and append it.
  • Repeat step 2 until you cannot pick more characters.
  • Pick the largest character from s and append it to the result.
  • Pick the largest character from s which is smaller than the last appended character to the result and append it.
  • Repeat step 5 until you cannot pick more characters.
  • Repeat the steps from 1 to 6 until you pick all characters from s.
  • In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

1
2
3
4
5
6
7
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

没看懂题意，因为踩的人比较多，所以简单看看就过了。
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 sortString(string s) {
        string res;
        vector<int> ma(26, 0);
        int i = 0, len = s.length();
        for(int i = 0; i < len; i ++)
            ma[s[i] - 'a'] ++;
        int count = 0;
        while(count < len) {
            for(int i = 0; i < 26; i ++)
                if(ma[i]) {
                    res += ('a' + i);
                    ma[i] --;
                    count ++;
                }
            for(int i = 25; i >= 0; i --)
                if(ma[i]) {
                    res += ('a' + i);
                    ma[i] --;
                    count ++;
                }
        }
        return res;
    }
};

Leetcode1374. Generate a String With Characters That Have Odd Counts

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times. The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.

Example 1:

1
2
3
Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:
1
2
3
Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

返回一个字符串，每个字母都只出现过奇数次。神经病题，要处理奇数和偶数的不同情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string generateTheString(int n) {
        string res;
        if(n % 2 == 0) {
            for(int i = 0; i < n-1; i ++)
                res += 'a';
            res += 'b';
        }
        if(n % 2 == 1) {
            for(int i = 0; i < n; i ++)
                res += 'a';
        }
        return res;
    }
};

Leetcode1380. Lucky Numbers in a Matrix

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

1
2
3
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

Example 2:
1
2
3
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

找到行最小，列最大的数，做法简单直白，但是有好的做法。
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:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        vector<int> res;
        int row = matrix.size(), col = matrix[0].size();
        for(int i = 0; i < row; i ++) {
            int j = 0, minn = 999999, minn_j = -1;
            for(; j < col; j ++) {
                if(minn > matrix[i][j]) {
                    minn = matrix[i][j];
                    minn_j = j;
                    }
            }
            int ii;
            for(ii = 0; ii < row; ii ++)
                if(matrix[ii][minn_j] > minn)
                    break;
            if(ii == row)
                res.push_back(minn);
        }
        return res;
    }
};

Leetcode1385. Find the Distance Value Between Two Arrays

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays. The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

计算一行中没有差的绝对值大于d的行数。「距离值」 定义为符合此描述的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int res = 0;
        for(int i = 0; i < arr1.size(); i ++) {
            int j;
            for(j = 0; j < arr2.size(); j ++) {
                if(abs(arr1[i] - arr2[j]) <= d)
                    break;
            }
            if(j == arr2.size())
                res ++;
        }
        return res;
    }
};

Leetcode1389. Create Target Array in the Given Order

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

  • Initially target array is empty.
  • From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
  • Repeat the previous step until there are no elements to read in nums and index.
  • Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

1
2
3
4
5
6
7
8
9
Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

目标数组 target 最初为空。按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。重复上一步，直到在 nums 和 index 中都没有要读取的元素。
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i ++) {
            res.insert(res.begin()+index[i], nums[i]);
        }
        return res;
    }
};

没用insert函数也行，但是效率好低
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:

    void move(vector<int>& nums, int i) {
        int ii;
        for(ii = i + 1; ii < nums.size() && nums[ii] != -1; ii ++);
        for(int k = ii; k > i; k --) {
            nums[k] = nums[k-1];
        }
    }
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> res(nums.size(), -1);
        for(int i = 0; i < nums.size(); i ++) {
            if(res[index[i]] == -1)
                res[index[i]] = nums[i];
            else {
                move(res, index[i]);
                res[index[i]] = nums[i];
            }
        }
        return res;
    }
};

Leetcode1394. Find Lucky Integer in an Array

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value. Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Example 1:

1
2
3
Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:
1
2
3
Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

找一个数量是它自身的元素，如果有多个，则返回最大的那个，如果没有就返回-1。别忘了排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findLucky(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int prev = arr[0], count = 1, res = -1;
        for(int i = 1; i < arr.size(); i ++) {
            if(prev != arr[i]) {
                if(count == prev)
                    res = prev;
                prev = arr[i];
                count = 1;
            }
            else {
                count ++;
            }
        }
        if(count == prev)
            res = prev;
        return res;
    }
};

Leetcode1399. Count Largest Group

Given an integer n. Each number from 1 to n is grouped according to the sum of its digits. Return how many groups have the largest size.

Example 1:

1
2
3
4
Input: n = 13
Output: 4
Explanation: There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13:
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.

把数字按照各位和分组，找到个数最多的那些组，输出个数。
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:
    
    int get(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    
    int countLargestGroup(int n) {
        map<int, int> mp;
        for(int i = 1; i <= n; i ++)
            mp[get(i)] ++;
        int maxx = -1, res = 0;
        for(auto i = mp.begin(); i != mp.end(); i ++) {
            if(maxx < i->second) {
                maxx = i->second;
                res = 1;
            }
            else if(maxx == i->second)
                res ++;
        }
        
        return res;
    }
};