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 3
Input: 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.
booluniqueOccurrences(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 3
Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete.
Example 2:
1 2 3 4 5
Input: 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 2
Input: 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 13
classSolution { 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); } };
classSolution { public: string removeDuplicates(string s, int k){ string res; vector<pair<int, char>> st{{0, '#'}}; for (char c : s) { if (st.back().second != c) { st.push_back({1, c}); } elseif (++st.back().first == k) { st.pop_back(); } } for (auto &a : st) { res.append(a.first, a.second); } return res; } };
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 3
Input: 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 3
Input: 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.
classSolution { public: intminCostToMoveChips(vector<int>& chips){ int odd = 0, even = 0; for(int i = 0; i < chips.size(); i ++) { if(chips[i] % 2) odd ++; else even ++; } returnmin(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 3
Input: 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 3
Input: 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 3
Input: s = "LLLLRRRR" Output: 1 Explanation: s can be split into "LLLLRRRR".
Example 4:
1 2 3
Input: 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 19
classSolution { public: intbalancedStringSplit(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 9
Input: 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 2
Input: 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 2
Input: 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]]
classSolution { public: vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) { int x = king[0], y = king[1]; vector<vector<int>> graph(8, vector<int>(8, 0)); vector<vector<int>> res; for(int i = 0; i < queens.size(); i ++) graph[queens[i][0]][queens[i][1]] = 1; int dy[8] = {0,0,-1,1,-1,1,-1,1}; int dx[8] = {-1,1,0,0,-1,-1,1,1}; int xx, yy; for(int i = 0; i < 8; i ++) { int x = king[0], y = king[1]; xx = x + dx[i]; yy = y + dy[i]; while(0 <= xx && xx <= 7 && 0 <= yy && yy <= 7) { if(graph[xx][yy] == 1) { res.push_back({xx, yy}); break; } xx = xx + dx[i]; yy = yy + dy[i]; } } return res; } };
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 3
Input: n = 1 Output: 1.00000 Explanation: The first person can only get the first seat.
Example 2:
1 2 3
Input: 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).
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.
classSolution { public: staticboolcmp(const vector<int>& a, const vector<int>& b){ if(a[0] > b[0]) returntrue; elseif(a[0] < b[0]) returnfalse; else if(a[1] > b[1]) returntrue; else returnfalse; } boolcheckStraightLine(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]) returnfalse; returntrue; } if(dy == 0) { for(int i = 1; i < coordinates.size(); i ++) if(coordinates[i][1] != coordinates[0][1]) returnfalse; returntrue; } // (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])) returnfalse; } returntrue; } };
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 2
f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1)
The function interface is defined like this:
1 2 3 4 5
interface 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 3
Input: 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 3
Input: function_id = 2, z = 5 Output: [[1,5],[5,1]] Explanation: function_id = 2 means that f(x, y) = x * y
/* * // 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); * }; */
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 5
Input: 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 3
Input: 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.
classSolution { 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 6
Input: 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
classSolution { public: intminTimeToVisitAllPoints(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 6
Input: 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"
Input: 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 6
Input: moves = [[0,0],[1,1]] Output: "Pending" Explanation: The game has not finished yet. "X " " O " " "
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 12
Input: 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 11
Input: 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.
classSolution { public: intcountSquares(vector<vector<int>>& matrix){ if (matrix.empty() || matrix[0].empty()) return0; int m = matrix.size(), n = matrix[0].size(); int count = 0; int s = std::min(m, n); for (int i = 0; i < m; ++ i) { for (int j = 0; j < n; ++ j) { // 发现为 1 的值, 然后从这个值出发, 访问以这个值为左上角的子方阵 // 子方阵的大小 k 的范围为 [1, s] // 之后访问子方阵中的 matrix[i : i + k, j : j + k] 范围内的每个元素 // 判断是否都是 1, 如果都是 1, 那么最后 is_all_ones 肯定为 true, // 此时累加 count. if (matrix[i][j] == 1) { count ++; bool is_all_ones = true; for (int k = 1; k <= s; ++ k) { if ((i + k >= m) || (j + k >= n)) break; // 越界则不用考虑了 for (int h = i; h <= i + k && is_all_ones; ++ h) { if ((j + k >= n) || (j + k < n && matrix[h][j + k] != 1)) is_all_ones = false; } for (int w = j; w <= j + k && is_all_ones; ++ w) { if ((i + k >= m) || (i + k < m && matrix[i + k][w] != 1)) is_all_ones = false; } if (is_all_ones) count ++; } } } } return count; } };
classSolution { public: intcountSquares(vector<vector<int>>& matrix){ int n = matrix.size(), m = matrix[0].size(); vector<vector<int>> dp1(n+1, vector<int>(m+1, 0)), dp2(n+1, vector<int>(m+1, 0)), dp(n+1, vector<int>(m+1, 0)); for (int r = 1; r <= n; r ++) { for (int c = 1; c <= m; c ++) { if (!matrix[r-1][c-1]) dp1[r][c] = dp2[r][c] = 0; else { dp1[r][c] = dp1[r-1][c] + 1; dp2[r][c] = dp2[r][c-1] + 1; } } } int ret = 0; for (int r = 1; r <= n; r ++) { for (int c = 1; c <= m; c ++) { if (matrix[r-1][c-1]) { dp[r][c] = max(1, min(dp[r-1][c-1]+1, min(dp1[r][c], dp2[r][c]))); ret += dp[r][c]; } } } return ret; } };
优化版本：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intcountSquares(vector<vector<int>>& matrix){ if (matrix.empty() || matrix[0].empty()) return0; 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 6
Input: 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 6
Input: 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 14
classSolution { public: intsubtractProductAndSum(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.
classSolution { public: intfindSpecialInteger(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 16
intfindSpecialInteger(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 8
Input: 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.
classSolution { public: intminFallingPathSum(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 3
Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10
Example 2:
1 2
Input: head = [0] Output: 0
Example 3:
1 2
Input: head = [1] Output: 1
Example 4:
1 2
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] Output: 18880
Example 5:
1 2
Input: head = [0,0] Output: 0
二进制链表转换成十进制数
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intgetDecimalValue(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 9
Input: 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 4
Input: 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 17
classSolution { public: intfindNumbers(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.