Leetcode1207. Unique Number of Occurrences
Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.
Example 1:1
2
3Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.
Example 2:1
2Input: arr = [1,2]
Output: false
Example 3:1
2Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
不同的数字拥有不同的个数，则为真，反之为假；意思就是对数组中的数字进行计数，要保证每个数的个数都是不一样的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
vector<int> cishu(1000, -1);
unordered_map<int, int> mp;
for(int i = 0; i < arr.size(); i ++) {
mp[arr[i]] ++;
}
for(auto it = mp.begin(); it != mp.end(); it ++) {
if(cishu[it->second] != -1)
return false;
else
cishu[it->second] = it->first;
}
return true;
}
};
另一种做法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 bool uniqueOccurrences(vector<int>& arr) {
int i;
map<int, int> mp;
map<int, int> mpp;
map<int, int>::iterator it;
for(i = 0; i < arr.size(); i ++)
{
mp[arr[i]] ++;
}
bool ans = true;
for(it = mp.begin(); it != mp.end(); it ++)
{
if(mpp[it->second] == 1) {
ans = false;
break;
}
mpp[it->second] = 1;
}
return ans;
}
};
Leetcode1209. Remove All Adjacent Duplicates in String II
You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Example 1:1
2
3Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.
Example 2:1
2
3
4
5Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
Example 3:1
2Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"
Constraints:
- 1 <= s.length <= 105
- 2 <= k <= 104
- s only contains lower case English letters.
这道题是之前那道 Remove All Adjacent Duplicates In String 的拓展，那道题只是让移除相邻的相同字母，而这道题让移除连续k个相同的字母，规则都一样，移除后的空位不保留，断开的位置重新连接，则有可能继续生成可以移除的连续字母。最直接暴力的解法就是多次扫描，每次都移除连续k个字母，然后剩下的字母组成新的字符串，再次进行扫描，但是这种方法现在超时了 Time Limit Exceeded，所以必须要用更加高效的解法。由于多次扫描可能会超时，所以要尽可能的在一次遍历中就完成，对于已经相邻的相同字母容易清除，断开的连续字母怎么一次处理呢？答案是在统计的过程中及时清除连续的字母，由于只能遍历一次，所以清除的操作可以采用字母覆盖的形式的，则这里可以使用双指针 Two Pointers 来操作，i指向的是清除后没有k个连续相同字母的位置，j是当前遍历原字符串的位置，这里还需要一个数组 cnt，其中 cnt[i] 表示字母 s[i] 连续出现的个数。i和j初始化均为0，开始遍历字符串s，用 s[j] 来覆盖 s[i]，然后来更新 cnt[i]，判断若i大于0，且 s[i - 1] 等于 s[i]，说明连续字母的个数增加了一个，用 cnt[i-1] + 1 来更新 cnt[i]，否则 cnt[i] 置为1。这样最终前字符串s的前i个字母就是最终移除后剩下的结果，直接返回即可，参见代码如下：
解法一：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
string removeDuplicates(string s, int k) {
int i = 0, n = s.size();
vector<int> cnt(n);
for (int j = 0; j < n; ++j, ++i) {
s[i] = s[j];
cnt[i] = (i > 0 && s[i - 1] == s[i]) ? cnt[i - 1] + 1 : 1;
if (cnt[i] == k) i -= k;
}
return s.substr(0, i);
}
};
我们也可以使用栈来做，这里用个数组来模拟栈，栈中放一个由字符的出现和次数和该字符组成的 pair 对儿，初始化时放个 {0, ‘#’} 进去，是为了防止栈为空。然后开始遍历字符串s的每个字符c，此时判断若栈顶的 pair 对儿不是字符c，则组成的新的 pair 对儿 {1, c} 压入栈中，否则将栈顶 pair 对儿的次数自增1，若此时正好等于k了，则将栈顶 pair 对儿移除，这样最终的残留部分都按顺序保留在栈中了。此时就发现用数组的好处了，因为可以从开头遍历，按顺序将剩余部分放入结果 res 中即可，参见代码如下：
1 | class Solution { |
Leetcode1217. Play with Chips
There are some chips, and the i-th chip is at position chips[i].
You can perform any of the two following types of moves any number of times (possibly zero) on any chip:
- Move the i-th chip by 2 units to the left or to the right with a cost of 0.
- Move the i-th chip by 1 unit to the left or to the right with a cost of 1.
There can be two or more chips at the same position initially. Return the minimum cost needed to move all the chips to the same position (any position).
Example 1:1
2
3Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.
Example 2:1
2
3Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.
移动一格cost1，移动2格cost0，本质上偶数位置的可以免费移动到任意偶数位，奇数位可以免费移动到任意奇数位，那实际上就可以把奇的都放到一个位置上，偶的放到一个位置上，然后哪边少就把少的移动到多的去。1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int odd = 0, even = 0;
for(int i = 0; i < chips.size(); i ++) {
if(chips[i] % 2)
odd ++;
else
even ++;
}
return min(odd, even);
}
};
Leetcode1221. Split a String in Balanced Strings
Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters. Given a balanced string s split it in the maximum amount of balanced strings. Return the maximum amount of splitted balanced strings.
Example 1:1
2
3Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.
Example 2:1
2
3Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.
Example 3:1
2
3Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".
Example 4:1
2
3Input: s = "RLRRRLLRLL"
Output: 2
Explanation: s can be split into "RL", "RRRLLRLL", since each substring contains an equal number of 'L' and 'R'
简单统计L和R的数量。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int balancedStringSplit(string s) {
int cur = 0;
int len = s.length();
int l = 0, r = 0;
for(int i = 0; i < len; i ++) {
if(s[i] == 'L')
l ++;
if(s[i] == 'R')
r ++;
if(l == r) {
l = r = 0;
cur ++;
}
}
return cur;
}
};
Leetcode1222. Queens That Can Attack the King
On an 8x8 chessboard, there can be multiple Black Queens and one White King.
Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.
Example 1:1
2
3
4
5
6
7
8
9Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation:
The queen at [0,1] can attack the king cause they're in the same row.
The queen at [1,0] can attack the king cause they're in the same column.
The queen at [3,3] can attack the king cause they're in the same diagnal.
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1].
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0].
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.
Example 2:1
2Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]
Example 3:1
2Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
queue可以8个方向进行移动，也就是kill，但是queue不能跨越其他单位进行kill。那么我们就可以反向来思考，将king进行8个方向的移动，如果碰到了queue，就说明是可以被kill的，同时，遇到了之后就停止继续那个方向。既然我们需要在棋盘上进行移动，就需要首先将棋盘摆出来。
- 定义一个二维数组用来表示棋盘
- 将queue摆放在棋盘上，也就是将棋盘上queue的位置标注为1
- 定义8个方向，dx和dy表示每个方向上x，y的delta值
- 在每个方向上对king在棋盘范围内进行移动，如果遇到了queue（plant格子==1），那么将该格子放入到结果中，同时终止该方向上的移动
- 8个方向都移动结束后返回结果
1 | class Solution { |
Leetcode1227. Airplane Seat Assignment Probability
n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of passengers will:
Take their own seat if it is still available,
Pick other seats randomly when they find their seat occupied
What is the probability that the n-th person can get his own seat?
Example 1:1
2
3Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.
Example 2:1
2
3Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).
Constraints:
- 1 <= n <= 10^5
这道题说是有n个人要登机，且飞机上正好有n个座位，说是第一个人会在n个座位中随机选一个位置坐，然后从第二个人开始，遵循这样的选座方法：若其对应的座位号是空的，则坐到自己的位置，否则就在剩余的位置中随机挑选一个位置坐，现在问第n个人能坐到自己的位置的概率是多少。这道题其实没有太多的算法在里面，本质上其实是一道数学题，一般来说这种类似脑筋急转弯的题目在数学推导方面完成了之后，代码可能就非常的简单了，甚至一两行就可以搞定了，但难点就是在于数学推导的部分。现在来分析一下吧，由于第一个人是随机挑选座位，其挑选的座位对后面的人的影响是不同的，需要分情况来讨论：
当第一个人正好选到了自己的座位时，这种情况的概率是 1/n，那么对于之后的所有人来说，自己的座位都是空的，可以直接坐，那么每个人坐到自己位子的概率也就是第一个人坐到自己位置的概率，都为 1/n（包括第n个人）。
当第一个人直接一勾子坐到第n个座位上（概率是 1/n），那么不管中间的人怎么坐，第n个人都无法再坐到自己的位置上了，概率为0。
当第一个人坐到了范围 [2, n-1] 中的任意一个位置，共有的 n-2 个位置可供选择，到达这种情况的总概率是 (n-2)/n，但坐到每一个位子的概率还是 1/n。若第一个人坐到了第二个位子，第二个人此时就有三种选择：1）坐到第一个人的位子，则之后所有的人都可以坐到自己的位子了，包括第n个人，概率是 (n-2)/n 1/(n-2)。2）坐到第n个座位，则第n个人就无法坐自己位子了，概率是0。3）坐其他的座位，范围是 [1, 1] 并 [3, n-1]，这里还是得分情况讨论，有没有没发现，这三种情况其实就是对应着第一个人开始的三种情况，也就是说当前实际上就变成了一个共 n-1 个座位的子问题，此时第二个人就相当于变成了第一个人，但可能有的童鞋会有疑问，不对吧，此时的第二个人不能坐自己的位置，而第一个人开始是可以坐自己的位置的，两人的情况不同啊，怎么能说是子问题呢？其实看是不是子问题，主要是看对所求的结果是否有影响，求的只是第n个人能坐到自己位置的概率，即便第二个人不能坐自己的位置，但是可以坐第一个人的位置，那么就相当于前两个人都坐了自己的位置，对后面的人没有影响，所以可以看作是子问题，这种情况的概率是 (n-2)/n 1/(n-2) f(n-1)。当第一个人坐到第三个位子的时候，那么第二个人就可以坐自己的位置，第三个人实际又面临相同的三个选择，此时就是共有 n-2 个座位的子问题, 这种情况的概率是 (n-2)/n 1/(n-2) * f(n-2)，后面都是依次类推。
所以，整个的概率可以写为如下表达式：
f(n) = 1/n + 0 + (n-2)/n (1/(n-2) f(n-1) + 1/(n-2) f(n-2) + … + 1/(n-2) f(2))
化简一下可得：
f(n) = 1/n + 1/n * (f(n-1) + f(n-2) + … + f(2))
注意这是n大于2的情况，n小于等于2的时候，可以直接分析出来，就是 0.5。现在的目标是要化简上面的表达式，首先两边同时乘以n，可以得到：
n * f(n) = 1 + f(n-1) + f(n-2) + … + f(2)
把上面这个称作公式1，然后将上面公式中的n用 n-1 替换，可以得到公式2:
(n-1) * f(n-1) = 1 + f(n-2) + f(n-3) + … + f(2)
然后用公式1减去公式2，可以得到：
n f(n) - (n-1) f(n-1) = f(n-1)
化简后可得：
f(n) = f(n-1)
我们已经知道 f(2) = 0.5，那么根据上面这个式子，就可以知道任何大于2的n的函数值都是 0.5，所以这道题也就一行代码搞定了，参见代码如下：
1 | class Solution { |
Leetcode1232. Check If It Is a Straight Line
You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.
Example 1:1
2Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true
Example 2:1
2Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false
判断给出的这些坐标点是否形成一条直线。我自己写的很繁琐，有可能有冗余的部分。通过斜率判断。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
if(a[0] > b[0])
return true;
else if(a[0] < b[0])
return false;
else
if(a[1] > b[1])
return true;
else
return false;
}
bool checkStraightLine(vector<vector<int>>& coordinates) {
sort(coordinates.begin(), coordinates.end(), cmp);
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
if(dx == 0) {
for(int i = 1; i < coordinates.size(); i ++)
if(coordinates[i][0] != coordinates[0][0])
return false;
return true;
}
if(dy == 0) {
for(int i = 1; i < coordinates.size(); i ++)
if(coordinates[i][1] != coordinates[0][1])
return false;
return true;
}
// (y1-y0)/(x1-x0) = (yi-y0)/(xi-x0)
//-> (y1-y0)*(xi-x0) = (yi-y0)*(x1-x0)
auto &c0 = coordinates[0], &c1 = coordinates[1];
for(int i = 2; i < coordinates.size(); i ++) {
auto &c2 = coordinates[i];
if ((c1[1] - c0[1])*(c2[0] - c0[0]) != (c2[1] - c0[1])*(c1[0] - c0[0]))
return false;
}
return true;
}
};
Leetcode1237. Find Positive Integer Solution for a Given Equation
Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.
The function is constantly increasing, i.e.:1
2f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined like this:1
2
3
4
5interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.
You may return the solutions in any order.
Example 1:1
2
3Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y
Example 2:1
2
3Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y
无聊的题，遍历就行，找到满足那个函数的取值。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/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* class CustomFunction {
* public:
* // Returns f(x, y) for any given positive integers x and y.
* // Note that f(x, y) is increasing with respect to both x and y.
* // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
* int f(int x, int y);
* };
*/
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int>> res;
for(int i = 1; i < 1001; i ++) {
for(int j = 1; j < 1001; j ++) {
if(customfunction.f(i, j) == z)
res.push_back({i, j});
else if(customfunction.f(i, j) > z)
break;
}
}
return res;
}
};
Leetcode1252. Cells with Odd Values in a Matrix
Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.
Return the number of cells with odd values in the matrix after applying the increment to all indices.
Example 1:1
2
3
4
5Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.
Example 2:1
2
3Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.
这道题的意思就是把indices给出的那行和那列的数在原有的基础上+1。处理完之后，计算数组中奇数的个数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int oddCells(int n, int m, vector<vector<int>>& indices) {
vector<vector<int>> mapp(n, vector<int>(m, 0));
for(int i = 0; i < indices.size(); i ++) {
for(int j = 0; j < m; j ++)
mapp[indices[i][0]][j] ++;
for(int j = 0; j < n; j ++)
mapp[j][indices[i][1]] ++;
}
int res = 0;
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(mapp[i][j] % 2 != 0)
res ++;
return res;
}
};
Leetcode1260. Shift 2D Grid
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation:
- Element at grid[i][j] moves to grid[i][j + 1].
- Element at grid[i][n - 1] moves to grid[i + 1][0].
- Element at grid[m - 1][n - 1] moves to grid[0][0].
- Return the 2D grid after applying shift operation k times.
Example 1:1
2Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]
Example 2:1
2Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
Example 3:1
2Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]
矩阵转换，每个元素向右移动k个位置，可以循环1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> res(m, vector<int>(n, 0));
for(int i = 0; i < m; i ++) {
int x, y;
for(int j = 0; j < n; j ++) {
y = j + k;
x = i;
if(y >= n) {
int temp;
temp = y / n;
y = y % n;
x = (x + temp) % m;
}
res[x][y] = grid[i][j];
}
}
return res;
}
};
Leetcode1266. Minimum Time Visiting All Points
On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.
You can move according to the next rules:
In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
You have to visit the points in the same order as they appear in the array.
Example 1:1
2
3
4
5
6Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds
Example 2:1
2Input: points = [[3,2],[-2,2]]
Output: 5
为了计算两个点的最短时间对应的路径，我们应该尽量走对角，比如(1, 1) 到 (3, 4), 通过走对角方式(1, 1) -> (2, 2) -> (3, 3) -> (3, 4), 不能直接从（1, 1）到 (3, 4), 会先走3对角，在往垂直方向1。
针对(x1, y1) -> (x2, y2), 水平方向 |x2 - x1|, 垂直方向|y2 - y1|, 走对角 min(|x2 - x1|, |y2 - y1|), 走水平或垂直max(|x2 - x1|, |y2 - y1|) - min(|x2 - x1|, |y2 - y1|), 加起来为max(|x2 - x1|, |y2 - y1|,
根据题意，可以直接贪心思想，求出相邻两点的时间，并累加。1
2
3
4
5
6
7
8
9
10class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int cnt = 0;
for(int i = 1; i < points.size(); i ++) {
cnt += max(abs(points[i][0] - points[i - 1][0]), abs(points[i][1] - points[i - 1][1]));
}
return cnt;
}
};
Leetcode1275. Find Winner on a Tic Tac Toe Game
Tic-tac-toe is played by two players A and B on a 3 x 3 grid.
Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.
You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.
Example 1:1
2
3
4
5
6Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X " "X " "X " "X " "X "
" " -> " " -> " X " -> " X " -> " X "
" " "O " "O " "OO " "OOX"
Example 2:1
2
3
4
5
6Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X " "X " "XX " "XXO" "XXO" "XXO"
" " -> " O " -> " O " -> " O " -> "XO " -> "XO "
" " " " " " " " " " "O "
Example 3:1
2
3
4
5
6Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"
Example 4:1
2
3
4
5
6Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X "
" O "
" "
- 虽然有A、B、Pending、Draw四种答案的可能。我们首先判断A、B谁能赢，再讨论A、B都未胜的情况下游戏是结束了还是继续进行；
- 判断A、B是否有人能取胜，只需要判断最后一个落棋的人是否能胜；（因为要是另外一个人赢了，游戏就结束了，不再有继续下棋的机会）
- 用数组记录最后落棋者的走棋情况，如果等于三，游戏结束，此人胜利；（以3x3为例，其余可以类推）
- 最后落棋者为未胜时，棋盘被下满则Draw，棋盘未下满则Pending。
1 | class Solution { |
Leetcode1277. Count Square Submatrices with All Ones
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:1
2
3
4
5
6
7
8
9
10
11Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Constraints:
- 1 <= arr.length <= 300
- 1 <= arr[0].length <= 300
- 0 <= arr[i][j] <= 1
1 | class Solution { |
令 dp[i][j] 为以 A[i][j] 为右下角元素的所能得到的最大的 square submatrices 的个数.
如果 A[i][j] == 0, 则 dp[i][j] = 0, 表示以 A[i][j] 为右下角元素的 square submatrices 为 0.
如果 A[i][j] == 1, 那么 dp[i][j] 的值由 dp[i - 1][j], dp[i - 1][j - 1] 以及 dp[i][j - 1] 中的最小值决定:
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
1 | class Solution { |
优化版本：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
int count = 0;
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
if (i > 0 && j > 0 && matrix[i][j] == 1)
matrix[i][j] = std::min(matrix[i - 1][j - 1],
std::min(matrix[i - 1][j], matrix[i][j - 1])) + 1;
count += matrix[i][j]; // 其余情况
}
}
return count;
}
};
Leetcode1281. Subtract the Product and Sum of Digits of an Integer
Given an integer number n, return the difference between the product of its digits and the sum of its digits.
Example 1:1
2
3
4
5
6Input: n = 234
Output: 15
Explanation:
Product of digits = 2 * 3 * 4 = 24
Sum of digits = 2 + 3 + 4 = 9
Result = 24 - 9 = 15
Example 2:1
2
3
4
5
6Input: n = 4421
Output: 21
Explanation:
Product of digits = 4 * 4 * 2 * 1 = 32
Sum of digits = 4 + 4 + 2 + 1 = 11
Result = 32 - 11 = 21
给定整数n，返回其数字乘积与数字总和之间的差。1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int subtractProductAndSum(int n) {
int he = 0, ji = 1;
while(n) {
int temp = n % 10;
n /= 10;
he += temp;
ji *= temp;
}
return ji - he;
}
};
Leetcode1287. Element Appearing More Than 25% In Sorted Array
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
Example 1:1
2Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
从第0个元素开始判断，i+1/4size 的元素是否还是自己，若是，则该值为所求。否则，判断下一个元素。一直到，size-1/4size的元素，若该元素还不是，那么以后的元素也不可能出现超过1/4的频率了，也就不用再循环判断了。1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
int step = arr.size() / 4;
for(int i = 0; i < arr.size() - step; i ++) {
if(arr[i] == arr[i+step])
return arr[i];
}
return -1;
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int findSpecialInteger(vector<int>& arr) {
int N = arr.size();
int freq = N / 4;
int pos = 0;
for (int i = 1; i < arr.size(); ++i) {
if (arr[i] == arr[i - 1])
continue;
if ( (i - pos) > freq)
return arr[i-1];
pos = i;
}
return arr.back();
}
Leetcode1289. Minimum Falling Path Sum II
Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.
Example 1:1
2
3
4
5
6
7
8Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation:
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.
Example 2:1
2Input: grid = [[7]]
Output: 7
给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。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
26class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(n, 0), dp2;
for (int i = 0; i < n; i ++)
dp[i] = matrix[0][i];
for (int i = 1; i < m; i ++) {
dp2.assign(n, 0);
for (int j = 0; j < n; j ++) {
int minn = INT_MAX;
for (int k = 0; k < n; k ++)
if (k != j)
minn = min(minn, dp[k]);
dp2[j] = minn + matrix[i][j];
}
swap(dp, dp2);
}
int res = INT_MAX;
for (int i = 0; i < n; i ++)
res = min(res, dp[i]);
return res;
}
};
Leetcode1290. Convert Binary Number in a Linked List to Integer
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
Example 1:1
2
3Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
Example 2:1
2Input: head = [0]
Output: 0
Example 3:1
2Input: head = [1]
Output: 1
Example 4:1
2Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880
Example 5:1
2Input: head = [0,0]
Output: 0
二进制链表转换成十进制数1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
int getDecimalValue(ListNode* head) {
int res = 0;
while(head) {
res = res * 2 + head->val;
head = head->next;
}
return res;
}
};
Leetcode1295. Find Numbers with Even Number of Digits
Given an array nums of integers, return how many of them contain an even number of digits.
Example 1:1
2
3
4
5
6
7
8
9Input: nums = [12,345,2,6,7896]
Output: 2
Explanation:
12 contains 2 digits (even number of digits).
345 contains 3 digits (odd number of digits).
2 contains 1 digit (odd number of digits).
6 contains 1 digit (odd number of digits).
7896 contains 4 digits (even number of digits).
Therefore only 12 and 7896 contain an even number of digits.
Example 2:1
2
3
4Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.
送分题，判断一个数里有几个数字组成1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findNumbers(vector<int>& nums) {
int digits, result=0;
for(int i=0;i<nums.size();i++) {
digits=0;
int num = nums[i];
while(num) {
digits++;
num/=10;
}
if(digits%2==0)
result ++;
}
return result;
}
};
Leetcode1299. Replace Elements with Greatest Element on Right Side
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Example 1:1
2Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
替换当前元素为，当前元素以后元素的最大值。 最后一个元素替换为-1。1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
vector<int> replaceElements(vector<int>& arr) {
int maxx = -1;
vector<int> res(arr.size(), 0);
for(int i = arr.size()-2; i >= 0; i --) {
maxx = max(maxx, arr[i+1]);
res[i] = maxx;
}
res[arr.size()-1] = -1;
return res;
}
};
1 | class Solution { |