A cell (r, c) of an excel sheet is represented as a string "<col><row>" where
“
“denotes the column number:”c”of the cell. It is represented by alphabetical letters
For example, the 1st column is denoted by 'A', the 2nd by 'B', the 3rd by 'C', and so on.
<row> is the row number r of the cell. The rth row is represented by the integerr.
You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, <col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.
Return the list of cells(x, y)such thatr1 <= x <= r2andc1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.
Example 1:
1 2 3 4 5
Input: s = "K1:L2" Output: ["K1","K2","L1","L2"] Explanation: The above diagram shows the cells which should be present in the list. The red arrows denote the order in which the cells should be presented.
Example 2:
1 2 3 4 5
Input: s = "A1:F1" Output: ["A1","B1","C1","D1","E1","F1"] Explanation: The above diagram shows the cells which should be present in the list. The red arrow denotes the order in which the cells should be presented.
Constraints:
s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s consists of uppercase English letters, digits and ':'.
Easy，转化为行列二重循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: vector<string> cellsInRange(string s){ char start_letter = s[0], end_letter = s[3]; char start_number = s[1], end_number = s[4]; std::vector<string> res; for (char c = start_letter; c <= end_letter; c++) { for (char n = start_number; n <= end_number; n++) { stringy(""); y += c; y += n; res.push_back(y); } } return res; } };
You are given an integer array nums and an integer k. Append kunique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.
Return the sum of thekintegers appended tonums.
Example 1:
1 2 3 4 5
Input: nums = [1,4,25,10,25], k = 2 Output: 5 Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3. The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum. The sum of the two integers appended is 2 + 3 = 5, so we return 5.
Example 2:
1 2 3 4 5
Input: nums = [5,6], k = 6 Output: 25 Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8. The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 108
Medium，原数组排序，依次计算放入后的最小值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: longlongminimalKSum(vector<int>& nums, int k){ sort(nums.begin(), nums.end()); unordered_set<int> used; longlong sum = ((longlong)k * (longlong)(k + 1)) / 2; int temp = k + 1; for (int num: nums) { if (num < temp && used.find(num) == used.end()) { sum -= num; sum += temp; used.insert(num); temp++; } } return sum; } };
You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,
If isLefti == 1, then childi is the left child of parenti.
If isLefti == 0, then childi is the right child of parenti.
Construct the binary tree described by descriptions and return its root.
The test cases will be generated such that the binary tree is valid.
Example 1:
1 2 3 4
Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] Output: [50,20,80,15,17,19] Explanation: The root node is the node with value 50 since it has no parent. The resulting binary tree is shown in the diagram.
Example 2:
1 2 3 4
Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]] Output: [1,2,null,null,3,4] Explanation: The root node is the node with value 1 since it has no parent. The resulting binary tree is shown in the diagram.
Constraints:
1 <= descriptions.length <= 104
descriptions[i].length == 3
1 <= parenti, childi <= 105
0 <= isLefti <= 1
The binary tree described by descriptions is valid.
You are given an array of integers nums. Perform the following steps:
Find any two adjacent numbers in nums that are non-coprime.
If no such numbers are found, stop the process.
Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
Repeat this process as long as you keep finding two adjacent non-coprime numbers.
Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.
The test cases are generated such that the values in the final array are less than or equal to 108.
Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: nums = [6,4,3,2,7,6,2] Output: [12,7,6] Explanation: - (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2]. - (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2]. - (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2]. - (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [12,7,6]. Note that there are other ways to obtain the same resultant array.
Example 2:
1 2 3 4 5 6 7 8 9
Input: nums = [2,2,1,1,3,3,3] Output: [2,1,1,3] Explanation: - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3]. - (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3]. - (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3]. There are no more adjacent non-coprime numbers in nums. Thus, the final modified array is [2,1,1,3]. Note that there are other ways to obtain the same resultant array.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
The test cases are generated such that the values in the final array are less than or equal to 108.
You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.
Return a list of all k-distant indices sorted in increasing order.
Example 1:
1 2 3 4 5 6 7 8 9 10 11
Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1 Output: [1,2,3,4,5,6] Explanation: Here, nums[2] == key and nums[5] == key. - For index 0, |0 - 2| > k and |0 - 5| > k, so there is no j where |0 - j| <= k and nums[j] == key. Thus, 0 is not a k-distant index. - For index 1, |1 - 2| <= k and nums[2] == key, so 1 is a k-distant index. - For index 2, |2 - 2| <= k and nums[2] == key, so 2 is a k-distant index. - For index 3, |3 - 2| <= k and nums[2] == key, so 3 is a k-distant index. - For index 4, |4 - 5| <= k and nums[5] == key, so 4 is a k-distant index. - For index 5, |5 - 5| <= k and nums[5] == key, so 5 is a k-distant index. - For index 6, |6 - 5| <= k and nums[5] == key, so 6 is a k-distant index. Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.
Example 2:
1 2 3 4
Input: nums = [2,2,2,2,2], key = 2, k = 2 Output: [0,1,2,3,4] Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index. Hence, we return [0,1,2,3,4].
There is an n x n0-indexed grid with some artifacts buried in it. You are given the integer n and a 0-indexed 2D integer array artifacts describing the positions of the rectangular artifacts where artifacts[i] = [r1i, c1i, r2i, c2i] denotes that the ith artifact is buried in the subgrid where:
(r1i, c1i) is the coordinate of the top-left cell of the ith artifact and
(r2i, c2i) is the coordinate of the bottom-right cell of the ith artifact.
You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it.
Given a 0-indexed 2D integer array dig where dig[i] = [ri, ci] indicates that you will excavate the cell (ri, ci), return the number of artifacts that you can extract.
The test cases are generated such that:
No two artifacts overlap.
Each artifact only covers at most 4 cells.
The entries of dig are unique.
Example 1:
1 2 3 4 5 6 7
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]] Output: 1 Explanation: The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid. There is 1 artifact that can be extracted, namely the red artifact. The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it. Thus, we return 1.
Example 2:
1 2 3
Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]] Output: 2 Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2.
Constraints:
1 <= n <= 1000
1 <= artifacts.length, dig.length <= min(n2, 105)
artifacts[i].length == 4
dig[i].length == 2
0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
r1i <= r2i
c1i <= c2i
No two artifacts will overlap.
The number of cells covered by an artifact is at most4.
You are given a 0-indexed integer array nums representing the contents of a pile, where nums[0] is the topmost element of the pile.
In one move, you can perform either of the following:
If the pile is not empty, remove the topmost element of the pile.
If there are one or more removed elements, add any one of them back onto the pile. This element becomes the new topmost element.
You are also given an integer k, which denotes the total number of moves to be made.
Return the maximum value of the topmost element of the pile possible after exactlykmoves. In case it is not possible to obtain a non-empty pile after k moves, return -1.
Example 1:
1 2 3 4 5 6 7 8 9
Input: nums = [5,2,2,4,0,6], k = 4 Output: 5 Explanation: One of the ways we can end with 5 at the top of the pile after 4 moves is as follows: - Step 1: Remove the topmost element = 5. The pile becomes [2,2,4,0,6]. - Step 2: Remove the topmost element = 2. The pile becomes [2,4,0,6]. - Step 3: Remove the topmost element = 2. The pile becomes [4,0,6]. - Step 4: Add 5 back onto the pile. The pile becomes [5,4,0,6]. Note that this is not the only way to end with 5 at the top of the pile. It can be shown that 5 is the largest answer possible after 4 moves.
Example 2:
1 2 3 4 5
Input: nums = [2], k = 1 Output: -1 Explanation: In the first move, our only option is to pop the topmost element of the pile. Since it is not possible to obtain a non-empty pile after one move, we return -1.
You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1.
You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] denotes that there exists a directed edge from fromi to toi with weight weighti.
Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.
Return the minimum weight of a subgraph of the graph such that it is possible to reachdestfrom bothsrc1andsrc2via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.
A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.
Example 1:
1 2 3 4 5 6
Input: n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5 Output: 9 Explanation: The above figure represents the input graph. The blue edges represent one of the subgraphs that yield the optimal answer. Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.
Example 2:
1 2 3 4 5
Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2 Output: -1 Explanation: The above figure represents the input graph. It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.
You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].
Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.
Return the number of hills and valleys innums.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: nums = [2,4,1,1,6,5] Output: 3 Explanation: At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley. At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill. At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley. At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2. At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill. At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley. There are 3 hills and valleys so we return 3.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: nums = [6,6,5,5,4,1] Output: 0 Explanation: At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley. At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley. At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley. At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley. At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley. At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley. There are 0 hills and valleys so we return 0.
There are n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a unique point.
You are given a 0-indexed string directions of length n. directions[i] can be either 'L', 'R', or 'S' denoting whether the ith car is moving towards the left, towards the right, or staying at its current point respectively. Each moving car has the same speed.
The number of collisions can be calculated as follows:
When two cars moving in opposite directions collide with each other, the number of collisions increases by 2.
When a moving car collides with a stationary car, the number of collisions increases by 1.
After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.
Return the total number of collisions that will happen on the road.
Example 1:
1 2 3 4 5 6 7 8 9
Input: directions = "RLRSLL" Output: 5 Explanation: The collisions that will happen on the road are: - Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2. - Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3. - Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4. - Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5. Thus, the total number of collisions that will happen on the road is 5.
Example 2:
1 2 3 4
Input: directions = "LLRR" Output: 0 Explanation: No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.
classSolution { public: intcountCollisions(string directions){ int res = 0; stack<char> stk; stk.push(directions[0]); for (int i = 1; i < directions.length(); i++) { char c = directions[i]; if (!stk.empty() && stk.top() == 'R' && c == 'L') { res += 2; stk.pop(); stk.push('S'); } elseif(!stk.empty() && stk.top() == 'R' && c == 'S') { res++; stk.pop(); // same here stk.push('S'); } elseif(!stk.empty() && stk.top() == 'S' && c == 'L') // third case res++; else stk.push(c); // if no condition is matched push the current element; } // handling 4th case while(!stk.empty() && stk.top() == 'R') // remove the leading R's stk.pop(); while(!stk.empty()) { if (stk.top() == 'R') res++; stk.pop(); } return res; } };
Alice and Bob are opponents in an archery competition. The competition has set the following rules:
Alice first shoots numArrows arrows and then Bob shoots numArrows arrows.
The points are then calculated as follows:
The target has integer scoring sections ranging from 0 to 11inclusive.
For each section of the target with score k (in between 0 to 11), say Alice and Bob have shot ak and bk arrows on that section respectively. If ak >= bk, then Alice takes k points. If ak < bk, then Bob takes k points.
However, if ak == bk == 0, then nobody takes k points.
For example, if Alice and Bob both shot 2 arrows on the section with score 11, then Alice takes 11 points. On the other hand, if Alice shot 0 arrows on the section with score 11 and Bob shot 2 arrows on that same section, then Bob takes 11 points.
You are given the integer numArrows and an integer array aliceArrows of size 12, which represents the number of arrows Alice shot on each scoring section from 0 to 11. Now, Bob wants to maximize the total number of points he can obtain.
Return the arraybobArrowswhich represents the number of arrows Bob shot on each scoring section from0to11. The sum of the values in bobArrows should equal numArrows.
If there are multiple ways for Bob to earn the maximum total points, return any one of them.
Example 1:
1 2 3 4 5
Input: numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0] Output: [0,0,0,0,1,1,0,0,1,2,3,1] Explanation: The table above shows how the competition is scored. Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47. It can be shown that Bob cannot obtain a score higher than 47 points.
Example 2:
1 2 3 4 5
Input: numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2] Output: [0,0,0,0,0,0,0,0,1,1,1,0] Explanation: The table above shows how the competition is scored. Bob earns a total point of 8 + 9 + 10 = 27. It can be shown that Bob cannot obtain a score higher than 27 points.
You are given a 0-indexed string s. You are also given a 0-indexed string queryCharacters of length k and a 0-indexed array of integer indicesqueryIndices of length k, both of which are used to describe k queries.
The ith query updates the character in s at index queryIndices[i] to the character queryCharacters[i].
Return an arraylengthsof lengthkwherelengths[i]is the length of the longest substring ofsconsisting of only one repeating character after theithqueryis performed.
Example 1:
1 2 3 4 5 6 7 8
Input: s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3] Output: [3,3,4] Explanation: - 1st query updates s = "bbbacc". The longest substring consisting of one repeating character is "bbb" with length 3. - 2nd query updates s = "bbbccc". The longest substring consisting of one repeating character can be "bbb" or "ccc" with length 3. - 3rd query updates s = "bbbbcc". The longest substring consisting of one repeating character is "bbbb" with length 4. Thus, we return [3,3,4].
Example 2:
1 2 3 4 5 6
Input: s = "abyzz", queryCharacters = "aa", queryIndices = [2,1] Output: [2,3] Explanation: - 1st query updates s = "abazz". The longest substring consisting of one repeating character is "zz" with length 2. - 2nd query updates s = "aaazz". The longest substring consisting of one repeating character is "aaa" with length 3. Thus, we return [2,3].
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
k == queryCharacters.length == queryIndices.length
1 <= k <= 105
queryCharacters consists of lowercase English letters.
Given two 0-indexed integer arrays nums1 and nums2, return a listanswerof size2where:
answer[0]is a list of all distinct integers innums1which are not present innums2.
answer[1]is a list of all distinct integers innums2which are not present innums1.
Note that the integers in the lists may be returned in any order.
Example 1:
1 2 3 4 5
Input: nums1 = [1,2,3], nums2 = [2,4,6] Output: [[1,3],[4,6]] Explanation: For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3]. For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].
Example 2:
1 2 3 4 5
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2] Output: [[3],[]] Explanation: For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3]. Every integer in nums2 is present in nums1. Therefore, answer[1] = [].
You are given a 0-indexed integer array nums. The array nums is beautiful if:
nums.length is even.
nums[i] != nums[i + 1] for all i % 2 == 0.
Note that an empty array is considered beautiful.
You can delete any number of elements from nums. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.
Return the minimum number of elements to delete fromnumsto make itbeautiful.
Example 1:
1 2 3
Input: nums = [1,1,2,3,5] Output: 1 Explanation: You can delete either nums[0] or nums[1] to make nums = [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to make nums beautiful.
Example 2:
1 2 3
Input: nums = [1,1,2,2,3,3] Output: 2 Explanation: You can delete nums[0] and nums[5] to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.
Given an integer array queries and a positive integer intLength, return an arrayanswerwhereanswer[i]is either thequeries[i]thsmallest positive palindrome of lengthintLengthor-1if no such palindrome exists.
A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.
Example 1:
1 2 3 4 5 6
Input: queries = [1,2,3,4,5,90], intLength = 3 Output: [101,111,121,131,141,999] Explanation: The first few palindromes of length 3 are: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ... The 90th palindrome of length 3 is 999.
Example 2:
1 2 3 4 5
Input: queries = [2,4,6], intLength = 4 Output: [1111,1331,1551] Explanation: The first six palindromes of length 4 are: 1001, 1111, 1221, 1331, 1441, and 1551.
classSolution { public: vector<longlong> kthPalindrome(vector<int>& queries, int intLength){ vector<longlong> res; longlong base = 1; int half = (intLength + 1) / 2; for (int i = 0; i < half - 1; i++) { base *= 10; } for (int i = 0; i < queries.size(); i++) { res.push_back(countPalindrome(queries[i], base, intLength)); } return res; } longlongcountPalindrome(int k, longlong base,int intLength){ if (base + k - 1 >= base * 10) return-1; base += (k - 1); longlong res = base; if (intLength % 2 == 1) { base /= 10; } int half = intLength / 2; for (int i = 0; i < half; i++) { res *= 10; res += base % 10; base /= 10; } return res; } };
There are npiles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.
In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactlykcoins optimally.
Example 1:
1 2 3 4 5
Input: piles = [[1,100,3],[7,8,9]], k = 2 Output: 101 Explanation: The above diagram shows the different ways we can choose k coins. The maximum total we can obtain is 101.
Example 2:
1 2 3 4
Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7 Output: 706 Explanation: The maximum total can be obtained if we choose all coins from the last pile.
Constraints:
n == piles.length
1 <= n <= 1000
1 <= piles[i][j] <= 105
1 <= k <= sum(piles[i].length) <= 2000
Hard，记忆化深度搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intmaxValueOfCoins(vector<vector<int>>& piles, int k){ int n = piles.size(); vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0)); function<int(int, int)> dfs = [&](int i, int k) { if (dp[i][k] > 0) return dp[i][k]; if (i == n || k == 0) return0; int res = dfs(i + 1, k), cur = 0; for (int j = 0; j < piles[i].size() && j < k; j++) { cur += piles[i][j]; res = max(res, dfs(i + 1, k - j - 1) + cur); } dp[i][k] = res; return res; }; return dfs(0, k); } };
You are given two strings current and correct representing two 24-hour times.
24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.
Return the minimum number of operations needed to convertcurrenttocorrect.
Example 1:
1 2 3 4 5 6 7 8
Input: current = "02:30", correct = "04:35" Output: 3 Explanation: We can convert current to correct in 3 operations as follows: - Add 60 minutes to current. current becomes "03:30". - Add 60 minutes to current. current becomes "04:30". - Add 5 minutes to current. current becomes "04:35". It can be proven that it is not possible to convert current to correct in fewer than 3 operations.
Example 2:
1 2 3
Input: current = "11:00", correct = "11:01" Output: 1 Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.
You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.
Return a listanswerof size2where:
answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.
The values in the two lists should be returned in increasing order.
Note:
You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.
Example 1:
1 2 3 4 5 6 7
Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]] Output: [[1,2,10],[4,5,7,8]] Explanation: Players 1, 2, and 10 have not lost any matches. Players 4, 5, 7, and 8 each have lost one match. Players 3, 6, and 9 each have lost two matches. Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].
Example 2:
1 2 3 4 5 6
Input: matches = [[2,3],[1,3],[5,4],[6,4]] Output: [[1,2,5,6],[]] Explanation: Players 1, 2, 5, and 6 have not lost any matches. Players 3 and 4 each have lost two matches. Thus, answer[0] = [1,2,5,6] and answer[1] = [].
You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.
You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.
Return the maximum number of candies each child can get.
Example 1:
1 2 3
Input: candies = [5,8,6], k = 3 Output: 5 Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.
Example 2:
1 2 3
Input: candies = [2,5], k = 11 Output: 0 Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.
You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.
A string is encrypted with the following process:
For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.
Note that in case a character of the string is not present in keys, the encryption process cannot be carried out, and an empty string "" is returned.
A string is decrypted with the following process:
For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.
Implement the Encrypter class:
Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.
Explanation Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]); encrypter.encrypt("abcd"); // return "eizfeiam". // 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am". encrypter.decrypt("eizfeiam"); // return 2. // "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'. // Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd". // 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.
Constraints:
1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
1 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decryptin total.
classEncrypter { public: array<string, 26> mp; unordered_map<string, int> cnt; Encrypter(vector<char>& keys, vector<string>& values, vector<string>& dictionary) { for (int i = 0; i < keys.size(); i++) { mp[keys[i] - 'a'] = values[i]; } for (string word: dictionary) { cnt[encrypt(word)]++; } } stringencrypt(string word1){ string res; for (char ch : word1) { auto &s = mp[ch - 'a']; if (s == "") return""; res += s; } return res; } intdecrypt(string word2){ return cnt.count(word2) ? cnt[word2] : 0; } };
/** * Your Encrypter object will be instantiated and called as such: * Encrypter* obj = new Encrypter(keys, values, dictionary); * string param_1 = obj->encrypt(word1); * int param_2 = obj->decrypt(word2); */
You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).
Return the largest possible value ofnumafter any number of swaps.
Example 1:
1 2 3 4 5 6
Input: num = 1234 Output: 3412 Explanation: Swap the digit 3 with the digit 1, this results in the number 3214. Swap the digit 2 with the digit 4, this results in the number 3412. Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number. Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.
Example 2:
1 2 3 4 5
Input: num = 65875 Output: 87655 Explanation: Swap the digit 8 with the digit 6, this results in the number 85675. Swap the first digit 5 with the digit 7, this results in the number 87655. Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.
classSolution { public: intlargestInteger(int num){ vector<int> odd, even; int temp = num; int base = 0; while (temp > 0) { int cur = temp % 10; if (cur % 2 == 0) { even.push_back(cur); } else { odd.push_back(cur); } if (base == 0) { base = 1; } else { base = base * 10; } temp = temp / 10; } sort(odd.begin(), odd.end()); sort(even.begin(), even.end()); int res = 0; while (base > 0) { res = res * 10; int cur = num / base; if (cur % 2 == 0) { res += even.back(); even.pop_back(); } else { res += odd.back(); odd.pop_back(); } num = num % base; base = base / 10; } return res; } };
You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.
Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.
Return expressionafter adding a pair of parentheses such thatexpressionevaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.
The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
Example 1:
1 2 3 4 5
Input: expression = "247+38" Output: "2(47+38)" Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170. Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'. It can be shown that 170 is the smallest possible value.
Input: expression = "999+999" Output: "(999+999)" Explanation: The expression evaluates to 999 + 999 = 1998.
Constraints:
3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.
You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.
Return the maximumproduct ofnumsafter at mostkoperations. Since the answer may be very large, return it modulo109 + 7. Note that you should maximize the product before taking the modulo.
Example 1:
1 2 3 4 5 6
Input: nums = [0,4], k = 5 Output: 20 Explanation: Increment the first number 5 times. Now nums = [5, 4], with a product of 5 * 4 = 20. It can be shown that 20 is maximum product possible, so we return 20. Note that there may be other ways to increment nums to have the maximum product.
Example 2:
1 2 3 4 5 6
Input: nums = [6,3,3,2], k = 2 Output: 216 Explanation: Increment the second number 1 time and increment the fourth number 1 time. Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216. It can be shown that 216 is maximum product possible, so we return 216. Note that there may be other ways to increment nums to have the maximum product.
Constraints:
1 <= nums.length, k <= 105
0 <= nums[i] <= 106
Medium，找到前k大的数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: intmaximumProduct(vector<int>& nums, int k){ longlong mod = 1e9 + 7; priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end()); for (int i = 0; i < k; i++) { int min_num = pq.top(); pq.pop(); pq.push(min_num + 1); } longlong res = 1; while (!pq.empty()) { res = res * pq.top() % mod; pq.pop(); } return res; } };
Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the ith garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target, full, and partial.
A garden is considered complete if it has at leasttarget flowers. The total beauty of the gardens is then determined as the sum of the following:
The number of complete gardens multiplied by full.
The minimum number of flowers in any of the incomplete gardens multiplied by partial. If there are no incomplete gardens, then this value will be 0.
Return the maximum total beauty that Alice can obtain after planting at mostnewFlowersflowers.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12
Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1 Output: 14 Explanation: Alice can plant - 2 flowers in the 0th garden - 3 flowers in the 1st garden - 1 flower in the 2nd garden - 1 flower in the 3rd garden The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers. There is 1 garden that is complete. The minimum number of flowers in the incomplete gardens is 2. Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14. No other way of planting flowers can obtain a total beauty higher than 14.
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12 13
Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6 Output: 30 Explanation: Alice can plant - 3 flowers in the 0th garden - 0 flowers in the 1st garden - 0 flowers in the 2nd garden - 2 flowers in the 3rd garden The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers. There are 3 gardens that are complete. The minimum number of flowers in the incomplete gardens is 4. Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30. No other way of planting flowers can obtain a total beauty higher than 30. Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
You are given a string s consisting of digits and an integer k.
A round can be completed if the length of s is greater than k. In one round, do the following:
Divides into consecutive groups of size k such that the first k characters are in the first group, the next k characters are in the second group, and so on. Note that the size of the last group can be smaller than k.
Replace each group of s with a string representing the sum of all its digits. For example, "346" is replaced with "13" because 3 + 4 + 6 = 13.
Merge consecutive groups together to form a new string. If the length of the string is greater than k, repeat from step 1.
Return safter all rounds have been completed.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: s = "11111222223", k = 3 Output: "135" Explanation: - For the first round, we divide s into groups of size 3: "111", "112", "222", and "23". Then we calculate the digit sum of each group: 1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5. So, s becomes "3" + "4" + "6" + "5" = "3465" after the first round. - For the second round, we divide s into "346" and "5". Then we calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5. So, s becomes "13" + "5" = "135" after second round. Now, s.length <= k, so we return "135" as the answer.
Example 2:
1 2 3 4 5 6
Input: s = "00000000", k = 3 Output: "000" Explanation: We divide s into "000", "000", and "00". Then we calculate the digit sum of each group: 0 + 0 + 0 = 0, 0 + 0 + 0 = 0, and 0 + 0 = 0. s becomes "0" + "0" + "0" = "000", whose length is equal to k, so we return "000".
classSolution { public: stringdigitSum(string s, int k){ while (s.length() > k) { string temp = ""; int sum = 0; for (int i = 0; i < s.length(); i++) { if (i != 0 && i % k == 0) { temp += to_string(sum); sum = s[i] - '0'; } else { sum += (s[i] - '0'); } } temp += to_string(sum); s = temp; } return s; } };
You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.
Return the minimum rounds required to complete all the tasks, or-1if it is not possible to complete all the tasks.
Example 1:
1 2 3 4 5 6 7 8
Input: tasks = [2,2,3,3,2,4,4,4,4,4] Output: 4 Explanation: To complete all the tasks, a possible plan is: - In the first round, you complete 3 tasks of difficulty level 2. - In the second round, you complete 2 tasks of difficulty level 3. - In the third round, you complete 3 tasks of difficulty level 4. - In the fourth round, you complete 2 tasks of difficulty level 4. It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.
Example 2:
1 2 3
Input: tasks = [2,3,3] Output: -1 Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.
You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.
Return the minimum rounds required to complete all the tasks, or-1if it is not possible to complete all the tasks.
You are given a 2D integer array grid of size m x n, where each cell contains a positive integer.
A cornered path is defined as a set of adjacent cells with at most one turn. More specifically, the path should exclusively move either horizontally or vertically up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the alternate direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.
The product of a path is defined as the product of all the values in the path.
Return the maximum number of trailing zeros in the product of a cornered path found ingrid.
Note:
Horizontal movement means moving in either the left or right direction.
Vertical movement means moving in either the up or down direction.
Example 1:
1 2 3 4 5 6 7 8
Input: grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]] Output: 3 Explanation: The grid on the left shows a valid cornered path. It has a product of 15 * 20 * 6 * 1 * 10 = 18000 which has 3 trailing zeros. It can be shown that this is the maximum trailing zeros in the product of a cornered path.
The grid in the middle is not a cornered path as it has more than one turn. The grid on the right is not a cornered path as it requires a return to a previously visited cell.
Example 2:
1 2 3 4
Input: grid = [[4,3,2],[7,6,1],[8,8,8]] Output: 0 Explanation: The grid is shown in the figure above. There are no cornered paths in the grid that result in a product with a trailing zero.
You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.
You are also given a string s of length n, where s[i] is the character assigned to node i.
Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.
Example 1:
1 2 3 4
Input: parent = [-1,0,0,1,1,2], s = "abacbe" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned. It can be proven that there is no longer path that satisfies the conditions.
Example 2:
1 2 3
Input: parent = [-1,0,0,0], s = "aabc" Output: 3 Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.
You are given a string number representing a positive integer and a character digit.
Return the resulting string after removing exactly one occurrence ofdigitfromnumbersuch that the value of the resulting string in decimal form is maximized. The test cases are generated such that digit occurs at least once in number.
Example 1:
1 2 3
Input: number = "123", digit = "3" Output: "12" Explanation: There is only one '3' in "123". After removing '3', the result is "12".
Example 2:
1 2 3 4
Input: number = "1231", digit = "1" Output: "231" Explanation: We can remove the first '1' to get "231" or remove the second '1' to get "123". Since 231 > 123, we return "231".
Example 3:
1 2 3 4
Input: number = "551", digit = "5" Output: "51" Explanation: We can remove either the first or second '5' from "551". Both result in the string "51".
You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.
Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.
Example 1:
1 2 3
Input: cards = [3,4,2,3,4,7] Output: 4 Explanation: We can pick up the cards [3,4,2,3] which contain a matching pair of cards with value 3. Note that picking up the cards [4,2,3,4] is also optimal.
Example 2:
1 2 3
Input: cards = [1,0,5,3] Output: -1 Explanation: There is no way to pick up a set of consecutive cards that contain a pair of matching cards.
Constraints:
1 <= cards.length <= 105
0 <= cards[i] <= 106
Medium，保存每个最后出现的字母个数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intminimumCardPickup(vector<int>& cards){ unordered_map<int, int> last; constint n = cards.size(); int res = n + 1; for (int i = 0; i < n; i++) { if (last.find(cards[i]) != last.end()) { res = min(res, i - last[cards[i]] + 1); } last[cards[i]] = i; } if (res == n + 1) { return-1; } else { return res; } } };
Given an integer array nums and two integers k and p, return the number of distinct subarrays which have at mostkelements divisible byp.
Two arrays nums1 and nums2 are said to be distinct if:
They are of different lengths, or
There exists at least one index i where nums1[i] != nums2[i].
A subarray is defined as a non-empty contiguous sequence of elements in an array.
Example 1:
1 2 3 4 5 6 7 8
Input: nums = [2,3,3,2,2], k = 2, p = 2 Output: 11 Explanation: The elements at indices 0, 3, and 4 are divisible by p = 2. The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are: [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2]. Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once. The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
Example 2:
1 2 3 4 5 6
Input: nums = [1,2,3,4], k = 4, p = 1 Output: 10 Explanation: All element of nums are divisible by p = 1. Also, every subarray of nums will have at most 4 elements that are divisible by 1. Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
Constraints:
1 <= nums.length <= 200
1 <= nums[i], p <= 200
1 <= k <= nums.length
Mediu，以字符串形式保存每个符合要求的子数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intcountDistinct(vector<int>& nums, int k, int p){ unordered_set<string> visited; for (int left = 0; left < nums.size(); left++) { int count = 0; string temp = ""; for (int right = left; right < nums.size(); right++) { if (nums[right] % p == 0) { count++; } if (count > k) break; temp += to_string(nums[right]) + "#"; visited.insert(temp); } } return visited.size(); } };
The appeal of a string is the number of distinct characters found in the string.
For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.
Given a string s, return the *total appeal of all of its \substrings*.**
A substring is a contiguous sequence of characters within a string.
Example 1:
1 2 3 4 5 6 7 8 9
Input: s = "abbca" Output: 28 Explanation: The following are the substrings of "abbca": - Substrings of length 1: "a", "b", "b", "c", "a" have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5. - Substrings of length 2: "ab", "bb", "bc", "ca" have an appeal of 2, 1, 2, and 2 respectively. The sum is 7. - Substrings of length 3: "abb", "bbc", "bca" have an appeal of 2, 2, and 3 respectively. The sum is 7. - Substrings of length 4: "abbc", "bbca" have an appeal of 3 and 3 respectively. The sum is 6. - Substrings of length 5: "abbca" has an appeal of 3. The sum is 3. The total sum is 5 + 7 + 7 + 6 + 3 = 28.
Example 2:
1 2 3 4 5 6 7 8
Input: s = "code" Output: 20 Explanation: The following are the substrings of "code": - Substrings of length 1: "c", "o", "d", "e" have an appeal of 1, 1, 1, and 1 respectively. The sum is 4. - Substrings of length 2: "co", "od", "de" have an appeal of 2, 2, and 2 respectively. The sum is 6. - Substrings of length 3: "cod", "ode" have an appeal of 3 and 3 respectively. The sum is 6. - Substrings of length 4: "code" has an appeal of 4. The sum is 4. The total sum is 4 + 6 + 6 + 4 = 20.
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
Hard，其实可以很简单，保存每个字母当前位置，以及以当前位置结尾的子数组的个数
1 2 3 4 5 6 7 8 9 10 11 12
classSolution { public: longlongappealSum(string s){ longlong res = 0, cur = 0, prev[26] = {}; for (int i = 0; i < s.size(); i++) { cur += i + 1 - prev[s[i] - 'a']; prev[s[i] - 'a'] = i + 1; res += cur; } return res; } };
You are given a string num representing a large integer. An integer is good if it meets the following conditions:
It is a substring of num with length 3.
It consists of only one unique digit.
Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.
Note:
The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
A subtree of root is a tree consisting of root and all of its descendants.
Example 1:
1 2 3 4 5 6 7 8
Input: root = [4,8,5,0,1,null,6] Output: 5 Explanation: For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4. For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5. For the node with value 0: The average of its subtree is 0 / 1 = 0. For the node with value 1: The average of its subtree is 1 / 1 = 1. For the node with value 6: The average of its subtree is 6 / 1 = 6.
Example 2:
1 2 3
Input: root = [1] Output: 1 Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.
In order to add a letter, Alice has to press the key of the corresponding digit i times, where i is the position of the letter in the key.
For example, to add the letter 's', Alice has to press '7' four times. Similarly, to add the letter 'k', Alice has to press '5' twice.
Note that the digits '0' and '1' do not map to any letters, so Alice does not use them.
However, due to an error in transmission, Bob did not receive Alice’s text message but received a string of pressed keys instead.
For example, when Alice sent the message "bob", Bob received the string "2266622".
Given a string pressedKeys representing the string received by Bob, return the total number of possible text messages Alice could have sent.
Since the answer may be very large, return it modulo109 + 7.
Example 1:
1 2 3 4 5 6
Input: pressedKeys = "22233" Output: 8 Explanation: The possible text messages Alice could have sent are: "aaadd", "abdd", "badd", "cdd", "aaae", "abe", "bae", and "ce". Since there are 8 possible messages, we return 8.
Example 2:
1 2 3 4 5
Input: pressedKeys = "222222222222222222222222222222222222" Output: 82876089 Explanation: There are 2082876103 possible text messages Alice could have sent. Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.
Constraints:
1 <= pressedKeys.length <= 105
pressedKeys only consists of digits from '2' - '9'.
A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:
It is ().
It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
It can be written as (A), where A is a valid parentheses string.
You are given an m x n matrix of parentheses grid. A valid parentheses string path in the grid is a path satisfying all of the following conditions:
The path starts from the upper left cell (0, 0).
The path ends at the bottom-right cell (m - 1, n - 1).
The path only ever moves down or right.
The resulting parentheses string formed by the path is valid.
Return trueif there exists a valid parentheses string path in the grid. Otherwise, return false.
Example 1:
1 2 3 4 5 6
Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]] Output: true Explanation: The above diagram shows two possible paths that form valid parentheses strings. The first path shown results in the valid parentheses string "()(())". The second path shown results in the valid parentheses string "((()))". Note that there may be other valid parentheses string paths.
Example 2:
1 2 3
Input: grid = [[")",")"],["(","("]] Output: false Explanation: The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] is either '(' or ')'.
Hard，三重DP，我的命门，又是DFS超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: boolhasValidPath(vector<vector<char>>& grid){ int m = grid.size(), n = grid[0].size(), maxk = (m + n + 1) / 2; vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(maxk + 10))); dp[0][0][1] = 1; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int k = 1; k <= maxk; k++) { dp[i][j + 1][k] |= dp[i][j][k + (grid[i][j] == '(' ? -1 : 1)]; dp[i + 1][j][k] |= dp[i][j][k + (grid[i][j] == '(' ? -1 : 1)]; } return dp[m][n - 1][1]; } };
You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.
In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and deletewords[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.
Return wordsafter performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".
Example 1:
1 2 3 4 5 6 7 8 9 10 11
Input: words = ["abba","baba","bbaa","cd","cd"] Output: ["abba","cd"] Explanation: One of the ways we can obtain the resultant array is by using the following operations: - Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2]. Now words = ["abba","baba","cd","cd"]. - Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1]. Now words = ["abba","cd","cd"]. - Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2]. Now words = ["abba","cd"]. We can no longer perform any operations, so ["abba","cd"] is the final answer.
Example 2:
1 2 3 4
Input: words = ["a","b","c","d","e"] Output: ["a","b","c","d","e"] Explanation: No two adjacent strings in words are anagrams of each other, so no operations are performed.
Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.
You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.
Return the maximum number of consecutive floors without a special floor.
Example 1:
1 2 3 4 5 6 7
Input: bottom = 2, top = 9, special = [4,6] Output: 3 Explanation: The following are the ranges (inclusive) of consecutive floors without a special floor: - (2, 3) with a total amount of 2 floors. - (5, 5) with a total amount of 1 floor. - (7, 9) with a total amount of 3 floors. Therefore, we return the maximum number which is 3 floors.
Example 2:
1 2 3
Input: bottom = 6, top = 8, special = [7,6,8] Output: 0 Explanation: Every floor rented is a special floor, so we return 0.
Constraints:
1 <= special.length <= 105
1 <= bottom <= special[i] <= top <= 109
All the values of special are unique.
Medium，排序记录上一个楼层，注意一下边界。同样因为没搞清题意错了一次
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
class Solution { public: int maxConsecutive(int bottom, int top, vector<int>& special) { sort(special.begin(), special.end()); int res = 0; int prev = bottom - 1; for (int sp: special) { if (sp - prev - 1 > res) { res = sp - prev - 1; } prev = sp; } if (top - prev > res) res = top - prev; return res; } };
Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.
You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.
Return the maximum number of consecutive floors without a special floor.
The bitwise AND of an array nums is the bitwise AND of all integers in nums.
For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
Also, for nums = [7], the bitwise AND is 7.
You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.
Return the size of the largest combination ofcandidateswith a bitwise AND greater than0.
Example 1:
1 2 3 4 5 6 7
Input: candidates = [16,17,71,62,12,24,14] Output: 4 Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0. The size of the combination is 4. It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0. Note that more than one combination may have the largest size. For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.
Example 2:
1 2 3 4
Input: candidates = [8,8] Output: 2 Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0. The size of the combination is 2, so we return 2.
classSolution { public: intlargestCombination(vector<int>& candidates){ int res = 0; vector<int> count(25, 0); for (int candidate: candidates) { int i = 0, cur = 1; while (candidate != 0) { if (candidate & cur) { count[i]++; candidate ^= cur; } i++; cur <<= 1; } } for (int i = 0; i < 25; i++) { if (count[i] > res) res = count[i]; } return res; } };
Explanation CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. countIntervals.add(2, 3); // add [2, 3] to the set of intervals. countIntervals.add(7, 10); // add [7, 10] to the set of intervals. countIntervals.count(); // return 6 // the integers 2 and 3 are present in the interval [2, 3]. // the integers 7, 8, 9, and 10 are present in the interval [7, 10]. countIntervals.add(5, 8); // add [5, 8] to the set of intervals. countIntervals.count(); // return 8 // the integers 2 and 3 are present in the interval [2, 3]. // the integers 5 and 6 are present in the interval [5, 8]. // the integers 7 and 8 are present in the intervals [5, 8] and [7, 10]. // the integers 9 and 10 are present in the interval [7, 10].
Constraints:
1 <= left <= right <= 109
At most 105 calls in total will be made to add and count.
classCountIntervals { private: map<int, int> intervals; int len = 0; public: CountIntervals() { } voidadd(int left, int right){ auto iter = intervals.upper_bound(right); if (iter == intervals.begin()) { intervals[left] = right; len += right - left + 1; return ; } iter--; while(true) { if (iter->second < left) break; len -= (iter->second - iter->first + 1); left = min(left, iter->first); right = max(right, iter->second); iter = intervals.erase(iter); if (iter == intervals.begin()) break; else iter--; } intervals[left] = right; len += right - left + 1; } intcount(){ return len; } };
/** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */
Given a string s and a character letter, return the percentage of characters insthat equalletter *rounded down to the nearest whole percent.*
Example 1:
1 2 3 4
Input: s = "foobar", letter = "o" Output: 33 Explanation: The percentage of characters in s that equal the letter 'o' is 2 / 6 * 100% = 33% when rounded down, so we return 33.
Example 2:
1 2 3 4
Input: s = "jjjj", letter = "k" Output: 0 Explanation: The percentage of characters in s that equal the letter 'k' is 0%, so we return 0.
Constraints:
1 <= s.length <= 100
s consists of lowercase English letters.
letter is a lowercase English letter.
Easy，很简单的计数
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intpercentageLetter(string s, char letter){ constint n = s.size(); int count = 0; for (int i = 0; i < n; i++) { if (s[i] == letter) { count++; } } return count * 100 / n; } };
You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.
Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.
Example 1:
1 2 3 4 5 6 7 8 9
Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 Output: 3 Explanation: Place 1 rock in bag 0 and 1 rock in bag 1. The number of rocks in each bag are now [2,3,4,4]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that there may be other ways of placing the rocks that result in an answer of 3.
Example 2:
1 2 3 4 5 6 7 8 9
Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 Output: 3 Explanation: Place 8 rocks in bag 0 and 2 rocks in bag 2. The number of rocks in each bag are now [10,2,2]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that we did not use all of the additional rocks.
You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:
Return the minimum number of lines needed to represent the line chart.
Example 1:
1 2 3 4 5 6 7 8 9
Input: stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]] Output: 3 Explanation: The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price. The following 3 lines can be drawn to represent the line chart: - Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4). - Line 2 (in blue) from (4,4) to (5,4). - Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1). It can be shown that it is not possible to represent the line chart using less than 3 lines.
Example 2:
1 2 3 4
Input: stockPrices = [[3,4],[1,2],[7,8],[2,3]] Output: 1 Explanation: As shown in the diagram above, the line chart can be represented with a single line.
As the ruler of a kingdom, you have an army of wizards at your command.
You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the ith wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:
The strength of the weakest wizard in the group.
The total of all the individual strengths of the wizards in the group.
Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo109 + 7.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Input: strength = [1,3,1,2] Output: 44 Explanation: The following are all the contiguous groups of wizards: - [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1 - [3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9 - [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1 - [2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4 - [1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4 - [3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4 - [1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3 - [1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5 - [3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6 - [1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7 The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: strength = [5,4,6] Output: 213 Explanation: The following are all the contiguous groups of wizards: - [5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25 - [4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16 - [6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36 - [5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36 - [4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40 - [5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60 The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.
You are given two 0-indexed strings s and target. You can take some letters from s and rearrange them to form new strings.
Return the maximum number of copies oftargetthat can be formed by taking letters fromsand rearranging them.
Example 1:
1 2 3 4 5 6 7
Input: s = "ilovecodingonleetcode", target = "code" Output: 2 Explanation: For the first copy of "code", take the letters at indices 4, 5, 6, and 7. For the second copy of "code", take the letters at indices 17, 18, 19, and 20. The strings that are formed are "ecod" and "code" which can both be rearranged into "code". We can make at most two copies of "code", so we return 2.
Example 2:
1 2 3 4 5 6
Input: s = "abcba", target = "abc" Output: 1 Explanation: We can make one copy of "abc" by taking the letters at indices 0, 1, and 2. We can make at most one copy of "abc", so we return 1. Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of "abc".
Example 3:
1 2 3 4 5
Input: s = "abbaccaddaeea", target = "aaaaa" Output: 1 Explanation: We can make one copy of "aaaaa" by taking the letters at indices 0, 3, 6, 9, and 12. We can make at most one copy of "aaaaa", so we return 1.
Constraints:
1 <= s.length <= 100
1 <= target.length <= 10
s and target consist of lowercase English letters.
Easy，统计各字符数量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intrearrangeCharacters(string s, string target){ vector<int> index(26); for (char c: s) { index[c - 'a']++; } vector<int> t(26); for (char c: target) { t[c - 'a']++; } int res = s.size(); for (char c: target) { int diff = c - 'a'; res = min(res, index[diff] / t[diff]); } return res; } };
A sentence is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign '$'. A word represents a price if it is a non-negative real number preceded by a dollar sign.
For example, "$100", "$23", and "$6.75" represent prices while "100", "$", and "2$3" do not.
You are given a string sentence representing a sentence and an integer discount. For each word representing a price, apply a discount of discount% on the price and update the word in the sentence. All updated prices should be represented with exactly two decimal places.
Return a string representing the modified sentence.
Example 1:
1 2 3 4 5 6
Input: sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50 Output: "there are $0.50 $1.00 and 5$ candies in the shop" Explanation: The words which represent prices are "$1" and "$2". - A 50% discount on "$1" yields "$0.50", so "$1" is replaced by "$0.50". - A 50% discount on "$2" yields "$1". Since we need to have exactly 2 decimal places after a price, we replace "$2" with "$1.00".
Example 2:
1 2 3 4 5 6
Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100 Output: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$" Explanation: Applying a 100% discount on any price will result in 0. The words representing prices are "$3", "$5", "$6", and "$9". Each of them is replaced by "$0.00".
Constraints:
1 <= sentence.length <= 105
sentence consists of lowercase English letters, digits, ' ', and '$'.
sentence does not have leading or trailing spaces.
All words in sentence are separated by a single space.
All prices will be positive integers without leading zeros.
classSolution { public: inttotalSteps(vector<int>& nums){ int res = 0; stack<int> stk; int n = nums.size(); vector<int> dp(n); for (int i = 0; i< n; i++) { int cur = 0; while (!stk.empty() && nums[i] >= nums[stk.top()]) { cur = max(cur, dp[stk.top()]); stk.pop(); } if (!stk.empty()) { dp[i] = cur + 1; res = max(res, cur + 1); } stk.push(i); } return res; } };
You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
0 represents an empty cell,
1 represents an obstacle that may be removed.
You can move up, down, left, or right from and to an empty cell.
Return the minimum number of obstacles to remove so you can move from the upper left corner(0, 0)to the lower right corner(m - 1, n - 1).
Example 1:
1 2 3 4 5
Input: grid = [[0,1,1],[1,1,0],[1,1,0]] Output: 2 Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2). It can be shown that we need to remove at least 2 obstacles, so we return 2. Note that there may be other ways to remove 2 obstacles to create a path.
Example 2:
1 2 3
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] Output: 0 Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
You are given a 0-indexed integer array nums whose length is a power of 2.
Apply the following algorithm on nums:
Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.
For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).
For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).
Replace the array nums with newNums.
Repeat the entire process starting from step 1.
Return the last number that remains innumsafter applying the algorithm.
Example 1:
1 2 3 4 5 6 7
Input: nums = [1,3,5,2,4,8,2,2] Output: 1 Explanation: The following arrays are the results of applying the algorithm repeatedly. First: nums = [1,5,4,2] Second: nums = [1,4] Third: nums = [1] 1 is the last remaining number, so we return 1.
Example 2:
1 2 3
Input: nums = [3] Output: 3 Explanation: 3 is already the last remaining number, so we return 3.
Constraints:
1 <= nums.length <= 1024
1 <= nums[i] <= 109
nums.length is a power of 2.
Easy，模拟法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: intminMaxGame(vector<int>& nums){ int n = nums.size(); while (n != 1) { bool isMin = true; for (int i = 0; i < n / 2; i++) { if (isMin == true) { nums[i] = min(nums[2 * i], nums[2 * i + 1]); } else { nums[i] = max(nums[2 * i], nums[2 * i + 1]); } isMin = !isMin; } n /= 2; } return nums[0]; } };
You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.
Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at mostk.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
1 2 3 4 5 6 7
Input: nums = [3,6,1,2,5], k = 2 Output: 2 Explanation: We can partition nums into the two subsequences [3,1,2] and [6,5]. The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2. The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1. Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.
Example 2:
1 2 3 4 5 6 7
Input: nums = [1,2,3], k = 1 Output: 2 Explanation: We can partition nums into the two subsequences [1,2] and [3]. The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1. The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0. Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].
Example 3:
1 2 3 4 5 6 7 8
Input: nums = [2,2,4,5], k = 0 Output: 3 Explanation: We can partition nums into the three subsequences [2,2], [4], and [5]. The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0. The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0. The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0. Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
0 <= k <= 105
Medium，排序+贪心
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: intpartitionArray(vector<int>& nums, int k){ sort(nums.begin(), nums.end()); int pre = 0, ans = 1; for (int i = 1; i < nums.size(); i++) { if (nums[i] - nums[pre] > k) { pre = i; ans++; } } return ans; } };
You are given a 0-indexed array nums that consists of ndistinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operations[i][0] with operations[i][1].
It is guaranteed that in the ith operation:
operations[i][0]exists in nums.
operations[i][1] does not exist in nums.
Return the array obtained after applying all the operations.
Example 1:
1 2 3 4 5 6 7
Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]] Output: [3,2,7,1] Explanation: We perform the following operations on nums: - Replace the number 1 with 3. nums becomes [3,2,4,6]. - Replace the number 4 with 7. nums becomes [3,2,7,6]. - Replace the number 6 with 1. nums becomes [3,2,7,1]. We return the final array [3,2,7,1].
Example 2:
1 2 3 4 5 6 7
Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]] Output: [2,1] Explanation: We perform the following operations to nums: - Replace the number 1 with 3. nums becomes [3,2]. - Replace the number 2 with 1. nums becomes [3,1]. - Replace the number 3 with 2. nums becomes [2,1]. We return the array [2,1].
Design a text editor with a cursor that can do the following:
Add text to where the cursor is.
Delete text from where the cursor is (simulating the backspace key).
Move the cursor either left or right.
When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.
Implement the TextEditor class:
TextEditor() Initializes the object with empty text.
void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.
int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.
string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.
string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.
Explanation TextEditor textEditor = new TextEditor(); // The current text is "|". (The '|' character represents the cursor) textEditor.addText("leetcode"); // The current text is "leetcode|". textEditor.deleteText(4); // return 4 // The current text is "leet|". // 4 characters were deleted. textEditor.addText("practice"); // The current text is "leetpractice|". textEditor.cursorRight(3); // return "etpractice" // The current text is "leetpractice|". // The cursor cannot be moved beyond the actual text and thus did not move. // "etpractice" is the last 10 characters to the left of the cursor. textEditor.cursorLeft(8); // return "leet" // The current text is "leet|practice". // "leet" is the last min(10, 4) = 4 characters to the left of the cursor. textEditor.deleteText(10); // return 4 // The current text is "|practice". // Only 4 characters were deleted. textEditor.cursorLeft(2); // return "" // The current text is "|practice". // The cursor cannot be moved beyond the actual text and thus did not move. // "" is the last min(10, 0) = 0 characters to the left of the cursor. textEditor.cursorRight(6); // return "practi" // The current text is "practi|ce". // "practi" is the last min(10, 6) = 6 characters to the left of the cursor.
Constraints:
1 <= text.length, k <= 40
text consists of lowercase English letters.
At most 2 * 104 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.
classTextEditor { string s; int pos ; public: TextEditor() { pos = 0; } voidaddText(string text){ s.insert(pos, text); pos += text.size(); // cout << "add" << endl; } intdeleteText(int k){ int ans = 0; while (pos != 0 && ans < k) { s.erase(pos - 1, 1); pos--; ans++; } // cout << "delet" << endl; return ans; } stringcursorLeft(int k){ // cout << "r" << endl; pos = max(pos - k, 0); string res; for (int i = pos - 10; i < pos; ++i) if (i >= 0) res += s[i]; return res; } stringcursorRight(int k){ // cout << "R" << endl; pos = min(pos+k, int(s.size())); string res; for (int i = pos - 10; i < pos; ++i) if (i >= 0) res += s[i]; return res; } };
/** * Your TextEditor object will be instantiated and called as such: * TextEditor* obj = new TextEditor(); * obj->addText(text); * int param_2 = obj->deleteText(k); * string param_3 = obj->cursorLeft(k); * string param_4 = obj->cursorRight(k); */
classTextEditor { stack<char> left; stack<char> right; public: TextEditor() { } voidaddText(string text){ for(auto &c : text){ left.push(c); } } intdeleteText(int k){ int cnt=0; while(!left.empty() and k>0){ left.pop(); cnt++; k--; } return cnt; } stringcursorLeft(int k){ while(!left.empty() and k>0){ char c = left.top();left.pop(); right.push(c); k--; } // returning the last min(10, len) characters to the left of the cursor return cursorShiftString(); } stringcursorRight(int k){ while(!right.empty() and k>0){ char c = right.top();right.pop(); left.push(c); k--; } // returning the last min(10, len) characters to the left of the cursor return cursorShiftString(); } // function to return the last min(10, len) characters to the left of the cursor stringcursorShiftString(){ string rtn = ""; int cnt=10; while(!left.empty() and cnt>0){ char c = left.top();left.pop(); rtn += c; cnt--; } reverse(rtn.begin(),rtn.end()); for(int i=0;i<rtn.size();i++){ left.push(rtn[i]); } return rtn; } };
You are given a 0-indexed 2D integer array brackets where brackets[i] = [upperi, percenti] means that the ith tax bracket has an upper bound of upperi and is taxed at a rate of percenti. The brackets are sorted by upper bound (i.e. upperi-1 < upperi for 0 < i < brackets.length).
Tax is calculated as follows:
The first upper0 dollars earned are taxed at a rate of percent0.
The next upper1 - upper0 dollars earned are taxed at a rate of percent1.
The next upper2 - upper1 dollars earned are taxed at a rate of percent2.
And so on.
You are given an integer income representing the amount of money you earned. Return the amount of money that you have to pay in taxes. Answers within 10-5 of the actual answer will be accepted.
Example 1:
1 2 3 4 5 6 7
Input: brackets = [[3,50],[7,10],[12,25]], income = 10 Output: 2.65000 Explanation: The first 3 dollars you earn are taxed at 50%. You have to pay $3 * 50% = $1.50 dollars in taxes. The next 7 - 3 = 4 dollars you earn are taxed at 10%. You have to pay $4 * 10% = $0.40 dollars in taxes. The final 10 - 7 = 3 dollars you earn are taxed at 25%. You have to pay $3 * 25% = $0.75 dollars in taxes. You have to pay a total of $1.50 + $0.40 + $0.75 = $2.65 dollars in taxes.
Example 2:
1 2 3 4 5 6
Input: brackets = [[1,0],[4,25],[5,50]], income = 2 Output: 0.25000 Explanation: The first dollar you earn is taxed at 0%. You have to pay $1 * 0% = $0 dollars in taxes. The second dollar you earn is taxed at 25%. You have to pay $1 * 25% = $0.25 dollars in taxes. You have to pay a total of $0 + $0.25 = $0.25 dollars in taxes.
Example 3:
1 2 3 4
Input: brackets = [[2,50]], income = 0 Output: 0.00000 Explanation: You have no income to tax, so you have to pay a total of $0 dollars in taxes.
Constraints:
1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi is sorted in ascending order.
All the values of upperi are unique.
The upper bound of the last tax bracket is greater than or equal to income.
Easy，累进税制计算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: doublecalculateTax(vector<vector<int>>& brackets, int income){ double res = 0.0; int pre = 0; for (auto &bracket: brackets) { if (income <= bracket[0]) { res += (double)(income - pre) * bracket[1] /100; break; } res += (double)(bracket[0] - pre) * bracket[1] /100; pre = bracket[0]; } return res; } };
You are given a 0-indexedm x n integer matrix grid consisting of distinct integers from 0 to m * n - 1. You can move in this matrix from a cell to any other cell in the next row. That is, if you are in cell (x, y) such that x < m - 1, you can move to any of the cells (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1). Note that it is not possible to move from cells in the last row.
Each possible move has a cost given by a 0-indexed 2D array moveCost of size (m * n) x n, where moveCost[i][j] is the cost of moving from a cell with value i to a cell in column j of the next row. The cost of moving from cells in the last row of grid can be ignored.
The cost of a path in grid is the sum of all values of cells visited plus the sum of costs of all the moves made. Return the minimum cost of a path that starts from any cell in the first row and ends at any cell in the last row.
Example 1:
1 2 3 4 5 6 7
Input: grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]] Output: 17 Explanation: The path with the minimum possible cost is the path 5 -> 0 -> 1. - The sum of the values of cells visited is 5 + 0 + 1 = 6. - The cost of moving from 5 to 0 is 3. - The cost of moving from 0 to 1 is 8. So the total cost of the path is 6 + 3 + 8 = 17.
Example 2:
1 2 3 4 5 6
Input: grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]] Output: 6 Explanation: The path with the minimum possible cost is the path 2 -> 3. - The sum of the values of cells visited is 2 + 3 = 5. - The cost of moving from 2 to 3 is 1. So the total cost of this path is 5 + 1 = 6.
Constraints:
m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid consists of distinct integers from 0 to m * n - 1.
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag. You are also given an integer k that denotes the number of children to distribute all the bags of cookies to. All the cookies in the same bag must go to the same child and cannot be split up.
The unfairness of a distribution is defined as the maximumtotal cookies obtained by a single child in the distribution.
Return the minimum unfairness of all distributions.
Example 1:
1 2 3 4 5 6 7
Input: cookies = [8,15,10,20,8], k = 2 Output: 31 Explanation: One optimal distribution is [8,15,8] and [10,20] - The 1st child receives [8,15,8] which has a total of 8 + 15 + 8 = 31 cookies. - The 2nd child receives [10,20] which has a total of 10 + 20 = 30 cookies. The unfairness of the distribution is max(31,30) = 31. It can be shown that there is no distribution with an unfairness less than 31.
Example 2:
1 2 3 4 5 6 7 8
Input: cookies = [6,1,3,2,2,4,1,2], k = 3 Output: 7 Explanation: One optimal distribution is [6,1], [3,2,2], and [4,1,2] - The 1st child receives [6,1] which has a total of 6 + 1 = 7 cookies. - The 2nd child receives [3,2,2] which has a total of 3 + 2 + 2 = 7 cookies. - The 3rd child receives [4,1,2] which has a total of 4 + 1 + 2 = 7 cookies. The unfairness of the distribution is max(7,7,7) = 7. It can be shown that there is no distribution with an unfairness less than 7.
classSolution { public: intdistributeCookies(vector<int>& cookies, int k){ int n = cookies.size(), res = INT_MAX; vector<int> count(k, 0); dfs(cookies, count, 0, n, k, res); return res; } voiddfs(vector<int>& cookies, vector<int>& count, int index, int n, int k, int &res){ if (index == n) { int maxNum = count[0]; for (int i = 1; i < k; i++) { if (count[i] > maxNum) { maxNum = count[i]; } } if (maxNum < res) { res = maxNum; } return; } for (int i = 0; i < k; i++) { count[i] += cookies[index]; dfs(cookies, count, index + 1, n, k, res); count[i] -= cookies[index]; } } };
You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:
Choose 2 distinct names from ideas, call them ideaA and ideaB.
Swap the first letters of ideaA and ideaB with each other.
If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.
Otherwise, it is not a valid name.
Return the number of distinct valid names for the company.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Input: ideas = ["coffee","donuts","time","toffee"] Output: 6 Explanation: The following selections are valid: - ("coffee", "donuts"): The company name created is "doffee conuts". - ("donuts", "coffee"): The company name created is "conuts doffee". - ("donuts", "time"): The company name created is "tonuts dime". - ("donuts", "toffee"): The company name created is "tonuts doffee". - ("time", "donuts"): The company name created is "dime tonuts". - ("toffee", "donuts"): The company name created is "doffee tonuts". Therefore, there are a total of 6 distinct company names.
The following are some examples of invalid selections: - ("coffee", "time"): The name "toffee" formed after swapping already exists in the original array. - ("time", "toffee"): Both names are still the same after swapping and exist in the original array. - ("coffee", "toffee"): Both names formed after swapping already exist in the original array.
Example 2:
1 2 3
Input: ideas = ["lack","back"] Output: 0 Explanation: There are no valid selections. Therefore, 0 is returned.
Constraints:
2 <= ideas.length <= 5 * 104
1 <= ideas[i].length <= 10
ideas[i] consists of lowercase English letters.
All the strings in ideas are unique.
Hard，保存首字母对应的单词
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public: longlongdistinctNames(vector<string>& ideas){ longlong res = 0; unordered_set<string> s(begin(ideas), end(ideas)); int cnt[26][26] = {}; for (auto i = 0; i < ideas.size(); ++i) { char first = ideas[i][0]; for (char ch = 'a'; ch <= 'z'; ++ch) { ideas[i][0] = ch; cnt[ch - 'a'][first - 'a'] += s.count(ideas[i]) == 0; } } for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) res += cnt[i][j] * cnt[j][i]; return res; } };
Given a string of English letters s, return the greatest English letter which occurs as both a lowercase and uppercase letter ins. The returned letter should be in uppercase. If no such letter exists, return an empty string.
An English letter b is greater than another letter a if b appears aftera in the English alphabet.
Example 1:
1 2 3 4
Input: s = "lEeTcOdE" Output: "E" Explanation: The letter 'E' is the only letter to appear in both lower and upper case.
Example 2:
1 2 3 4 5
Input: s = "arRAzFif" Output: "R" Explanation: The letter 'R' is the greatest letter to appear in both lower and upper case. Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.
Example 3:
1 2 3 4
Input: s = "AbCdEfGhIjK" Output: "" Explanation: There is no letter that appears in both lower and upper case.
Constraints:
1 <= s.length <= 1000
s consists of lowercase and uppercase English letters.
Given two integers num and k, consider a set of positive integers with the following properties:
The units digit of each integer is k.
The sum of the integers is num.
Return the minimum possible size of such a set, or-1if no such set exists.
Note:
The set can contain multiple instances of the same integer, and the sum of an empty set is considered 0.
The units digit of a number is the rightmost digit of the number.
Example 1:
1 2 3 4 5 6
Input: num = 58, k = 9 Output: 2 Explanation: One valid set is [9,49], as the sum is 58 and each integer has a units digit of 9. Another valid set is [19,39]. It can be shown that 2 is the minimum possible size of a valid set.
Example 2:
1 2 3
Input: num = 37, k = 2 Output: -1 Explanation: It is not possible to obtain a sum of 37 using only integers that have a units digit of 2.
Example 3:
1 2 3
Input: num = 0, k = 7 Output: 0 Explanation: The sum of an empty set is considered 0.
Constraints:
0 <= num <= 3000
0 <= k <= 9
Medium，数学计算未化简
1 2 3 4 5 6 7 8 9 10 11 12
classSolution { public: intminimumNumbers(int num, int k){ if (num == 0) return0; for (int i = 1; i <= 10 && k * i <= num; i++) { if ((num - k * i) % 10 == 0) { return i; } } return-1; } };
You are given a binary string s and a positive integer k.
Return the length of the longest subsequence ofsthat makes up a binary number less than or equal tok.
Note:
The subsequence can contain leading zeroes.
The empty string is considered to be equal to 0.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1:
1 2 3 4 5
Input: s = "1001010", k = 5 Output: 5 Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal. Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively. The length of this subsequence is 5, so 5 is returned.
Example 2:
1 2 3 4
Input: s = "00101001", k = 1 Output: 6 Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal. The length of this subsequence is 6, so 6 is returned.
Constraints:
1 <= s.length <= 1000
s[i] is either '0' or '1'.
1 <= k <= 109
Medium，动态规划当前结果不超过k的长度数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: intlongestSubsequence(string s, int k){ int n = s.size(); int dp[1001] = {}, j = 0; for (char c: s) { if (dp[j] * 2 + (c - '0') <= k) dp[++j] = dp[j] * 2 + (c - '0'); for (int i = j; i > 0; --i) dp[i] = min(dp[i], dp[i - 1] * 2 + c - '0'); } return j; } };
You are given two integers m and n that represent the height and width of a rectangular piece of wood. You are also given a 2D integer array prices, where prices[i] = [hi, wi, pricei] indicates you can sell a rectangular piece of wood of height hi and width wi for pricei dollars.
To cut a piece of wood, you must make a vertical or horizontal cut across the entire height or width of the piece to split it into two smaller pieces. After cutting a piece of wood into some number of smaller pieces, you can sell pieces according to prices. You may sell multiple pieces of the same shape, and you do not have to sell all the shapes. The grain of the wood makes a difference, so you cannot rotate a piece to swap its height and width.
Return the maximum money you can earn after cutting anm x npiece of wood.
Note that you can cut the piece of wood as many times as you want.
Example 1:
1 2 3 4 5 6 7 8
Input: m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]] Output: 19 Explanation: The diagram above shows a possible scenario. It consists of: - 2 pieces of wood shaped 2 x 2, selling for a price of 2 * 7 = 14. - 1 piece of wood shaped 2 x 1, selling for a price of 1 * 3 = 3. - 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2. This obtains a total of 14 + 3 + 2 = 19 money earned. It can be shown that 19 is the maximum amount of money that can be earned.
Example 2:
1 2 3 4 5 6 7 8
Input: m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]] Output: 32 Explanation: The diagram above shows a possible scenario. It consists of: - 3 pieces of wood shaped 3 x 2, selling for a price of 3 * 10 = 30. - 1 piece of wood shaped 1 x 4, selling for a price of 1 * 2 = 2. This obtains a total of 30 + 2 = 32 money earned. It can be shown that 32 is the maximum amount of money that can be earned. Notice that we cannot rotate the 1 x 4 piece of wood to obtain a 4 x 1 piece of wood.
Constraints:
1 <= m, n <= 200
1 <= prices.length <= 2 * 104
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 106
All the shapes of wood (hi, wi) are pairwise distinct.
Hard，二维动态规划
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
class Solution { public: long long sellingWood(int m, int n, vector<vector<int>>& prices) { long long dp[201][201] = {}; for (auto& p: prices) dp[p[0]][p[1]] = p[2]; for (int w = 1; w <= m; w++) { for (int h = 1; h <= n; h++) { for (int a = 1; a <= w / 2; a++) dp[w][h] = max(dp[w][h], dp[a][h] + dp[w - a][h]); for (int a = 1; a <= h / 2; a++) dp[w][h] = max(dp[w][h], dp[w][a] + dp[w][h - a]); } } return dp[m][n]; } };
A square matrix is said to be an X-Matrix if both of the following conditions hold:
All the elements in the diagonals of the matrix are non-zero.
All other elements are 0.
Given a 2D integer array grid of size n x n representing a square matrix, return trueifgridis an X-Matrix. Otherwise, return false.
Example 1:
1 2 3 4 5
Input: grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]] Output: true Explanation: Refer to the diagram above. An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0. Thus, grid is an X-Matrix.
Example 2:
1 2 3 4 5
Input: grid = [[5,7,0],[0,3,1],[0,5,0]] Output: false Explanation: Refer to the diagram above. An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0. Thus, grid is not an X-Matrix.
Constraints:
n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 105
Easy，直接一个单元一个单元比较
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: boolcheckXMatrix(vector<vector<int>>& grid){ int n = grid.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j || i + j == n - 1) { if (grid[i][j] == 0) returnfalse; } else { if (grid[i][j] != 0) returnfalse; } } } returntrue; } };
There is a street with n * 2plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.
Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo109 + 7.
Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith plot on the other side of the street.
Example 1:
1 2 3 4 5 6 7 8
Input: n = 1 Output: 4 Explanation: Possible arrangements: 1. All plots are empty. 2. A house is placed on one side of the street. 3. A house is placed on the other side of the street. 4. Two houses are placed, one on each side of the street.
Example 2:
1 2 3
Input: n = 2 Output: 9 Explanation: The 9 possible arrangements are shown in the diagram above.
You are given two 0-indexed integer arrays nums1 and nums2, both of length n.
You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].
For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,**12,13**,4,5] and nums2 becomes [11,**2,3**,14,15].
You may choose to apply the mentioned operation once or not do anything.
The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.
Return the maximum possible score.
A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).
Example 1:
1 2 3 4
Input: nums1 = [60,60,60], nums2 = [10,90,10] Output: 210 Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,90,60] and nums2 = [10,60,10]. The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.
Example 2:
1 2 3 4
Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20] Output: 220 Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30]. The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.
Example 3:
1 2 3 4
Input: nums1 = [7,11,13], nums2 = [1,1,1] Output: 31 Explanation: We choose not to swap any subarray. The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:
Get the XOR of all the values of the nodes for each of the three components respectively.
The difference between the largest XOR value and the smallest XOR value is the score of the pair.
For example, say the three components have the node values: [4,5,7], [1,9], and [3,3,3]. The three XOR values are 4 ^ 5 ^ 7 = **6**, 1 ^ 9 = **8**, and 3 ^ 3 ^ 3 = **3**. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 3 = 5.
Return the minimum score of any possible pair of edge removals on the given tree.
Example 1:
1 2 3 4 5 6 7 8
Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 9 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10. - The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1. - The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5. The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9. It can be shown that no other pair of removals will obtain a smaller score than 9.
Example 2:
1 2 3 4 5 6 7 8
Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]] Output: 0 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0. - The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0. - The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0. The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0. We cannot obtain a smaller score than 0.
classSolution {vector<bool> visited; vector<vector<int>> pc, adj; // pc is the parent child edge in our dfs vector<vector<bool>> childs; // 2D array to store that i is a parent of j vector<int> child_xor, nums, par; // child_xor to store result of xors of a child node and par is a gloable array to track the parents of a node in dfs intdfs(int i){ int ans = nums[i]; visited[i] = true; for (int p: par) childs[p][i] = true; // Defining this node as the child of all its parents par.push_back(i); for (int child: adj[i]) if (!visited[child]) { pc.push_back({i, child}); ans ^= dfs(child); // Recurcively calculating xors } par.pop_back(); return child_xor[i] = ans; } public: intminimumScore(vector<int>& nums, vector<vector<int>>& edges){ // Initialising gloable variables int n = nums.size(), ans = INT_MAX; visited = vector<bool>(n); pc = vector<vector<int>>(); adj = vector<vector<int>>(n); child_xor = vector<int>(n, 0); childs = vector<vector<bool>>(n, vector<bool>(n, false)); this->nums = nums; par = vector<int>(); // Creating an adjacency matrix for (vector<int> &edge: edges) adj[edge[0]].push_back(edge[1]), adj[edge[1]].push_back(edge[0]); dfs(0); for (int i = 0; i < pc.size(); i++) for (int j = i + 1; j < pc.size(); j++) { // removing an edge i and j int a = pc[i][1], b = pc[j][1]; // node that will come below when you delete an edge i and j int xa = child_xor[a], xb, xc = child_xor[0]; if (childs[a][b]) { xb = child_xor[b]; xc ^= xa; xa ^= xb; } else { xb = child_xor[b]; xc ^= xa; xc ^= xb; } ans = min(max(xa, max(xb, xc)) - min(xa, min(xb, xc)), ans); } return ans; } };
You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:
Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
Align the substitution table with the regular English alphabet.
Each letter in message is then substituted using the table.
Spaces ' ' are transformed to themselves.
For example, given key = "**hap**p**y** **bo**y" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').
Return the decoded message.
Example 1:
1 2 3 4
Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv" Output: "this is a secret" Explanation: The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".
Example 2:
1 2 3 4
Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb" Output: "the five boxing wizards jump quickly" Explanation: The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".
Constraints:
26 <= key.length <= 2000
key consists of lowercase English letters and ' '.
key contains every letter in the English alphabet ('a' to 'z') at least once.
1 <= message.length <= 2000
message consists of lowercase English letters and ' '.
You are given two integers m and n, which represent the dimensions of a matrix.
You are also given the head of a linked list of integers.
Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1.
Return the generated matrix.
Example 1:
1 2 3 4
Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0] Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]] Explanation: The diagram above shows how the values are printed in the matrix. Note that the remaining spaces in the matrix are filled with -1.
Example 2:
1 2 3 4
Input: m = 1, n = 4, head = [0,1,2] Output: [[0,1,2,-1]] Explanation: The diagram above shows how the values are printed from left to right in the matrix. The last space in the matrix is set to -1.
Constraints:
1 <= m, n <= 105
1 <= m * n <= 105
The number of nodes in the list is in the range [1, m * n].
You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards.
Given an integer n, return the number of people who know the secret at the end of dayn. Since the answer may be very large, return it modulo109 + 7.
Example 1:
1 2 3 4 5 6 7 8 9
Input: n = 6, delay = 2, forget = 4 Output: 5 Explanation: Day 1: Suppose the first person is named A. (1 person) Day 2: A is the only person who knows the secret. (1 person) Day 3: A shares the secret with a new person, B. (2 people) Day 4: A shares the secret with a new person, C. (3 people) Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people) Day 6: B shares the secret with E, and C shares the secret with F. (5 people)
Example 2:
1 2 3 4 5 6 7
Input: n = 4, delay = 1, forget = 3 Output: 6 Explanation: Day 1: The first person is named A. (1 person) Day 2: A shares the secret with B. (2 people) Day 3: A and B share the secret with 2 new people, C and D. (4 people) Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)
You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.
Return the number of strictlyincreasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo109 + 7.
Two paths are considered different if they do not have exactly the same sequence of visited cells.
Example 1:
1 2 3 4 5 6 7
Input: grid = [[1,1],[3,4]] Output: 8 Explanation: The strictly increasing paths are: - Paths with length 1: [1], [1], [3], [4]. - Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4]. - Paths with length 3: [1 -> 3 -> 4]. The total number of paths is 4 + 3 + 1 = 8.
Example 2:
1 2 3 4 5 6
Input: grid = [[1],[2]] Output: 3 Explanation: The strictly increasing paths are: - Paths with length 1: [1], [2]. - Paths with length 2: [1 -> 2]. The total number of paths is 2 + 1 = 3.
classSolution { int mod = 1e9 + 7; int dirs[5] = {0, -1, 0, 1, 0}; public: intcountPaths(vector<vector<int>>& grid){ int m = grid.size(), n = grid[0].size(); int res = 0; int f[m][n]; memset(f, -1, sizeof(f)); function<int(int, int)> dfs = [&](int i, int j) -> int { if (f[i][j] != -1) return f[i][j]; int res = 1; for (int k = 0; k < 4; k++) { int x = i + dirs[k], y = j + dirs[k + 1]; if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] > grid[i][j]) { res = (res + (dfs(x, y))) % mod; } } return f[i][j] = res; }; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { res = (res + dfs(i, j)) % mod; } } return res; } };
