You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water.
You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.
Example 1:
1 2 3 4 5 6 7 8
Input: amount = [1,4,2] Output: 4 Explanation: One way to fill up the cups is: Second 1: Fill up a cold cup and a warm cup. Second 2: Fill up a warm cup and a hot cup. Second 3: Fill up a warm cup and a hot cup. Second 4: Fill up a warm cup. It can be proven that 4 is the minimum number of seconds needed.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: amount = [5,4,4] Output: 7 Explanation: One way to fill up the cups is: Second 1: Fill up a cold cup, and a hot cup. Second 2: Fill up a cold cup, and a warm cup. Second 3: Fill up a cold cup, and a warm cup. Second 4: Fill up a warm cup, and a hot cup. Second 5: Fill up a cold cup, and a hot cup. Second 6: Fill up a cold cup, and a warm cup. Second 7: Fill up a hot cup.
Example 3:
1 2 3
Input: amount = [5,0,0] Output: 5 Explanation: Every second, we fill up a cold cup.
Explanation SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made. smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set. smallestInfiniteSet.addBack(1); // 1 is added back to the set. smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and // is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
Constraints:
1 <= num <= 1000
At most 1000 calls will be made in total to popSmallest and addBack.
classSmallestInfiniteSet { stack<int> stk; public: SmallestInfiniteSet() { stk.push(1); } intpopSmallest(){ int res = stk.top(); stk.pop(); if (stk.size() == 0) stk.push(res + 1); return res; } voidaddBack(int num){ stack<int> tmp; while (stk.size() && stk.top() < num) { tmp.push(stk.top()); stk.pop(); } if (stk.size() > 0) { if (stk.top() > num) { stk.push(num); } } while (tmp.size()) { stk.push(tmp.top()); tmp.pop(); } } };
/** * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet* obj = new SmallestInfiniteSet(); * int param_1 = obj->popSmallest(); * obj->addBack(num); */
/** * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet* obj = new SmallestInfiniteSet(); * int param_1 = obj->popSmallest(); * obj->addBack(num); */
classSmallestInfiniteSet { public: set<int>s; SmallestInfiniteSet() { s.clear(); for(int i = 1; i <= 1010; i++) s.insert(i); } intpopSmallest(){ int x = *s.begin(); s.erase(s.begin()); return x; } voidaddBack(int num){ s.insert(num); } };
/** * Your SmallestInfiniteSet object will be instantiated and called as such: * SmallestInfiniteSet* obj = new SmallestInfiniteSet(); * int param_1 = obj->popSmallest(); * obj->addBack(num); */
You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:
The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.
Return trueif it is possible to obtain the stringtargetby moving the pieces of the stringstart *any number of times*. Otherwise, return false.
Example 1:
1 2 3 4 5 6 7
Input: start = "_L__R__R_", target = "L______RR" Output: true Explanation: We can obtain the string target from start by doing the following moves: - Move the first piece one step to the left, start becomes equal to "L___R__R_". - Move the last piece one step to the right, start becomes equal to "L___R___R". - Move the second piece three steps to the right, start becomes equal to "L______RR". Since it is possible to get the string target from start, we return true.
Example 2:
1 2 3 4
Input: start = "R_L_", target = "__LR" Output: false Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_". After that, no pieces can move anymore, so it is impossible to obtain the string target from start.
Example 3:
1 2 3
Input: start = "_R", target = "R_" Output: false Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.
Constraints:
n == start.length == target.length
1 <= n <= 105
start and target consist of the characters 'L', 'R', and '_'.
You are given two integers n and maxValue, which are used to describe an ideal array.
A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:
Every arr[i] is a value from 1 to maxValue, for 0 <= i < n.
Every arr[i] is divisible by arr[i - 1], for 0 < i < n.
Return the number of distinct ideal arrays of lengthn. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
1 2 3 4 5 6 7 8 9
Input: n = 2, maxValue = 5 Output: 10 Explanation: The following are the possible ideal arrays: - Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5] - Arrays starting with the value 2 (2 arrays): [2,2], [2,4] - Arrays starting with the value 3 (1 array): [3,3] - Arrays starting with the value 4 (1 array): [4,4] - Arrays starting with the value 5 (1 array): [5,5] There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.
Example 2:
1 2 3 4 5 6 7 8 9 10
Input: n = 5, maxValue = 3 Output: 11 Explanation: The following are the possible ideal arrays: - Arrays starting with the value 1 (9 arrays): - With no other distinct values (1 array): [1,1,1,1,1] - With 2nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2] - With 2nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3] - Arrays starting with the value 2 (1 array): [2,2,2,2,2] - Arrays starting with the value 3 (1 array): [3,3,3,3,3] There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.
classSolution { constint MOD = 1000000007; vector<longlong> inv;
// O(b) 求组合数 longlongC(int a, int b){ if (b > a) return0; longlong ret = 1; for (int i = 1; i <= b; i++) ret = (ret * (a - i + 1) % MOD * inv[i]) % MOD; return ret; }
public: intidealArrays(int n, int K){ // nlnn 进行质因数分解，f[i] 的元素表示 i 的每种质因数的指数 vector<vector<int>> f(K + 1); int mx = 0; for (int i = 2; i <= K; i++) if (f[i].empty()) for (int j = i; j <= K; j += i) { int x = j, y = 0; for (; x % i == 0; x /= i) y++; f[j].push_back(y); mx = max(mx, y); }
// 线性求逆元 inv.resize(mx + 5); inv[1] = 1; for (int i = 2; i <= mx; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
// 统计答案 longlong ans = 0; for (int i = 1; i <= K; i++) { longlong t = 1; for (int x : f[i]) t = (t * C(n + x - 1, x)) % MOD; ans = (ans + t) % MOD; } return ans; } };
You are given a 0-indexed integer array nums. In one operation, you may do the following:
Choose two integers in nums that are equal.
Remove both integers from nums, forming a pair.
The operation is done on nums as many times as possible.
Return a 0-indexed integer arrayanswerof size2whereanswer[0]is the number of pairs that are formed andanswer[1]is the number of leftover integers innumsafter doing the operation as many times as possible.
Example 1:
1 2 3 4 5 6 7
Input: nums = [1,3,2,1,3,2,2] Output: [3,1] Explanation: Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2]. Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2]. Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2]. No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.
Example 2:
1 2 3 4
Input: nums = [1,1] Output: [1,0] Explanation: Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = []. No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.
Example 3:
1 2 3
Input: nums = [0] Output: [0,1] Explanation: No pairs can be formed, and there is 1 number leftover in nums.
You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].
Return the maximum value ofnums[i] + nums[j]that you can obtain over all possible indicesiandjthat satisfy the conditions.
Example 1:
1 2 3 4 5 6
Input: nums = [18,43,36,13,7] Output: 54 Explanation: The pairs (i, j) that satisfy the conditions are: - (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54. - (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50. So the maximum sum that we can obtain is 54.
Example 2:
1 2 3
Input: nums = [10,12,19,14] Output: -1 Explanation: There are no two numbers that satisfy the conditions, so we return -1.
You are given a 0-indexed array of strings nums, where each string is of equal length and consists of only digits.
You are also given a 0-indexed 2D integer array queries where queries[i] = [ki, trimi]. For each queries[i], you need to:
Trim each number in nums to its rightmosttrimi digits.
Determine the index of the kith smallest trimmed number in nums. If two trimmed numbers are equal, the number with the lower index is considered to be smaller.
Reset each number in nums to its original length.
Return an arrayanswerof the same length asqueries, whereanswer[i]is the answer to theithquery.
Note:
To trim to the rightmost x digits means to keep removing the leftmost digit, until only x digits remain.
Strings in nums may contain leading zeros.
Example 1:
1 2 3 4 5 6 7 8
Input: nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]] Output: [2,2,1,0] Explanation: 1. After trimming to the last digit, nums = ["2","3","1","4"]. The smallest number is 1 at index 2. 2. Trimmed to the last 3 digits, nums is unchanged. The 2nd smallest number is 251 at index 2. 3. Trimmed to the last 2 digits, nums = ["02","73","51","14"]. The 4th smallest number is 73. 4. Trimmed to the last 2 digits, the smallest number is 2 at index 0. Note that the trimmed number "02" is evaluated as 2.
Example 2:
1 2 3 4 5 6
Input: nums = ["24","37","96","04"], queries = [[2,1],[2,2]] Output: [3,0] Explanation: 1. Trimmed to the last digit, nums = ["4","7","6","4"]. The 2nd smallest number is 4 at index 3. There are two occurrences of 4, but the one at index 0 is considered smaller than the one at index 3. 2. Trimmed to the last 2 digits, nums is unchanged. The 2nd smallest number is 24.
You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.
Return the minimum number of deletions such that the smallest element innums *divides all the elements of* numsDivide. If this is not possible, return -1.
Note that an integer x divides y if y % x == 0.
Example 1:
1 2 3 4 5 6 7
Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15] Output: 2 Explanation: The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of numsDivide. We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums = [3,4,3]. The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide. It can be shown that 2 is the minimum number of deletions needed.
Example 2:
1 2 3 4 5
Input: nums = [4,3,6], numsDivide = [8,2,6,10] Output: -1 Explanation: We want the smallest element in nums to divide all the elements of numsDivide. There is no way to delete elements from nums to allow this.
Given a string s consisting of lowercase English letters, return the first letter to appear twice.
Note:
A letter a appears twice before another letter b if the second occurrence of a is before the second occurrence of b.
s will contain at least one letter that appears twice.
Example 1:
1 2 3 4 5 6 7 8
Input: s = "abccbaacz" Output: "c" Explanation: The letter 'a' appears on the indexes 0, 5 and 6. The letter 'b' appears on the indexes 1 and 4. The letter 'c' appears on the indexes 2, 3 and 7. The letter 'z' appears on the index 8. The letter 'c' is the first letter to appear twice, because out of all the letters the index of its second occurrence is the smallest.
Example 2:
1 2 3 4
Input: s = "abcdd" Output: "d" Explanation: The only letter that appears twice is 'd' so we return 'd'.
Initializes the system. The food items are described byfoods,cuisinesandratings, all of which have a length ofn.
foods[i] is the name of the ith food,
cuisines[i] is the type of cuisine of the ith food, and
ratings[i] is the initial rating of the ith food.
void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.
Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.
Explanation FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]); foodRatings.highestRated("korean"); // return "kimchi" // "kimchi" is the highest rated korean food with a rating of 9. foodRatings.highestRated("japanese"); // return "ramen" // "ramen" is the highest rated japanese food with a rating of 14. foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16. foodRatings.highestRated("japanese"); // return "sushi" // "sushi" is the highest rated japanese food with a rating of 16. foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16. foodRatings.highestRated("japanese"); // return "ramen" // Both "sushi" and "ramen" have a rating of 16. // However, "ramen" is lexicographically smaller than "sushi".
Constraints:
1 <= n <= 2 * 104
n == foods.length == cuisines.length == ratings.length
1 <= foods[i].length, cuisines[i].length <= 10
foods[i], cuisines[i] consist of lowercase English letters.
1 <= ratings[i] <= 108
All the strings in foods are distinct.
food will be the name of a food item in the system across all calls to changeRating.
cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.
At most 2 * 104 calls in total will be made to changeRating and highestRated.
voidchangeRating(string food, int newRating){ string cuisine = foodDic[food].second; int rate = foodDic[food].first; cuisineDic[cuisine].erase(make_pair(rate, food)); cuisineDic[cuisine].insert(make_pair(newRating, food)); foodDic[food]= make_pair(newRating, cuisine); }
stringhighestRated(string cuisine){ return cuisineDic[cuisine].begin()->second; } }; /** * Your FoodRatings object will be instantiated and called as such: * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings); * obj->changeRating(food,newRating); * string param_2 = obj->highestRated(cuisine); */
You are given a 0-indexed positive integer array nums and a positive integer k.
A pair of numbers (num1, num2) is called excellent if the following conditions are satisfied:
Both the numbers num1 and num2 exist in the array nums.
The sum of the number of set bits in num1 OR num2 and num1 AND num2 is greater than or equal to k, where OR is the bitwise OR operation and AND is the bitwise AND operation.
Return the number of distinct excellent pairs.
Two pairs (a, b) and (c, d) are considered distinct if either a != c or b != d. For example, (1, 2) and (2, 1) are distinct.
Note that a pair (num1, num2) such that num1 == num2 can also be excellent if you have at least one occurrence of num1 in the array.
Example 1:
1 2 3 4 5 6 7
Input: nums = [1,2,3,1], k = 3 Output: 5 Explanation: The excellent pairs are the following: - (3, 3). (3 AND 3) and (3 OR 3) are both equal to (11) in binary. The total number of set bits is 2 + 2 = 4, which is greater than or equal to k = 3. - (2, 3) and (3, 2). (2 AND 3) is equal to (10) in binary, and (2 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3. - (1, 3) and (3, 1). (1 AND 3) is equal to (01) in binary, and (1 OR 3) is equal to (11) in binary. The total number of set bits is 1 + 2 = 3. So the number of excellent pairs is 5.
Example 2:
1 2 3
Input: nums = [5,1,1], k = 10 Output: 0 Explanation: There are no excellent pairs for this array.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 60
Hard，其实就是求每个数有多少1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: longlongcountExcellentPairs(vector<int>& nums, int k){ longlong res = 0; unordered_map<int, int> bitCounts; for (int num: unordered_set<int>(nums.begin(), nums.end())) { bitCounts[__builtin_popcount(num)]++; } for (auto &[cx, ccx] : bitCounts) { for (auto &[cy, ccy] : bitCounts) { if (cx + cy >= k) { res += ccx * ccy; } } } return res; } };
You are given a non-negative integer array nums. In one operation, you must:
Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
Subtract x from every positive element in nums.
Return the minimum number of operations to make every element innumsequal to0.
Example 1:
1 2 3 4 5 6
Input: nums = [1,5,0,3,5] Output: 3 Explanation: In the first operation, choose x = 1. Now, nums = [0,4,0,2,4]. In the second operation, choose x = 2. Now, nums = [0,2,0,0,2]. In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].
Example 2:
1 2 3
Input: nums = [0] Output: 0 Explanation: Each element in nums is already 0 so no operations are needed.
You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions:
The sum of the grades of students in the ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last).
The total number of students in the ith group is less than the total number of students in the (i + 1)th group, for all groups (except the last).
Return the maximum number of groups that can be formed.
Example 1:
1 2 3 4 5 6 7
Input: grades = [10,6,12,7,3,5] Output: 3 Explanation: The following is a possible way to form 3 groups of students: - 1st group has the students with grades = [12]. Sum of grades: 12. Student count: 1 - 2nd group has the students with grades = [6,7]. Sum of grades: 6 + 7 = 13. Student count: 2 - 3rd group has the students with grades = [10,3,5]. Sum of grades: 10 + 3 + 5 = 18. Student count: 3 It can be shown that it is not possible to form more than 3 groups.
Example 2:
1 2 3
Input: grades = [8,8] Output: 1 Explanation: We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.
Constraints:
1 <= grades.length <= 105
1 <= grades[i] <= 105
Medium，关键得找到数目也是增序这一条件。
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intmaximumGroups(vector<int>& grades){ int n = grades.size(); int total = 0, cur = 0; while (total + cur + 1 <= n) { total += ++cur; } return cur; } };
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.
The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from i, then edges[i] == -1.
You are also given two integers node1 and node2.
Return the index of the node that can be reached from bothnode1andnode2, such that the maximum between the distance fromnode1to that node, and fromnode2to that node is minimized. If there are multiple answers, return the node with the smallest index, and if no possible answer exists, return -1.
Note that edges may contain cycles.
Example 1:
1 2 3 4
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1 Output: 2 Explanation: The distance from node 0 to node 2 is 1, and the distance from node 1 to node 2 is 1. The maximum of those two distances is 1. It can be proven that we cannot get a node with a smaller maximum distance than 1, so we return node 2.
Example 2:
1 2 3 4
Input: edges = [1,2,-1], node1 = 0, node2 = 2 Output: 2 Explanation: The distance from node 0 to node 2 is 2, and the distance from node 2 to itself is 0. The maximum of those two distances is 2. It can be proven that we cannot get a node with a smaller maximum distance than 2, so we return node 2.
You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.
The graph is represented with a given 0-indexed array edges of size n, indicating that there is a directed edge from node i to node edges[i]. If there is no outgoing edge from node i, then edges[i] == -1.
Return the length of the longest cycle in the graph. If no cycle exists, return -1.
A cycle is a path that starts and ends at the same node.
Example 1:
1 2 3 4
Input: edges = [3,3,4,2,3] Output: 3 Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2. The length of this cycle is 3, so 3 is returned.
Example 2:
1 2 3
Input: edges = [2,-1,3,1] Output: -1 Explanation: There are no cycles in this graph.
classSolution { public: intlongestCycle(vector<int>& edges){ int n = edges.size(); vector<int> inDegree(n, 0); for (int i = 0; i < n; i++) { if (edges[i] != -1) { inDegree[edges[i]]++; } } vector<bool> isVisited(n, true); int count = 0; for (int i = 0; i < n; i++) { if (inDegree[i] > 0) { isVisited[i] = false; count++; } } int ans = -1; int index = 0; while (count > 0 && index < n) { while (isVisited[index] == true && index < n) { index++; } if (index == n) break; int cur = index; unordered_map<int, int> route; int order = 0; while (cur != -1) { if (route.count(cur)) { ans = max(ans, order - route[cur]); break; } route[cur] = order; order++; if (isVisited[cur]) { break; } else { isVisited[cur] = true; count--; } cur = edges[cur]; } } return ans; } };
You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:
i < j < k,
nums[j] - nums[i] == diff, and
nums[k] - nums[j] == diff.
Return the number of unique arithmetic triplets.
Example 1:
1 2 3 4 5
Input: nums = [0,1,4,6,7,10], diff = 3 Output: 2 Explanation: (1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3. (2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.
Example 2:
1 2 3 4 5
Input: nums = [4,5,6,7,8,9], diff = 2 Output: 2 Explanation: (0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2. (1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.
Constraints:
3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums is strictly increasing.
Easy，哈希
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intarithmeticTriplets(vector<int>& nums, int diff){ unordered_set<int> dic; for (int num: nums) { dic.insert(num); } int res = 0; for (int i = 0; i < nums.size() - 1; i++) { if (dic.count(nums[i] + diff) && dic.count(nums[i] + 2 * diff)) { res++; } } return res; } };
There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are 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. You are also given an integer array restricted which represents restricted nodes.
Return the maximum number of nodes you can reach from node0without visiting a restricted node.
Note that node 0 will not be a restricted node.
Example 1:
1 2 3 4
Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5] Output: 4 Explanation: The diagram above shows the tree. We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.
Example 2:
1 2 3 4
Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1] Output: 3 Explanation: The diagram above shows the tree. We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.
You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.
We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:
The subarray consists of exactly2 equal elements. For example, the subarray [2,2] is good.
The subarray consists of exactly3 equal elements. For example, the subarray [4,4,4] is good.
The subarray consists of exactly3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.
Return trueif the array has at least one valid partition. Otherwise, return false.
Example 1:
1 2 3 4
Input: nums = [4,4,4,5,6] Output: true Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6]. This partition is valid, so we return true.
Example 2:
1 2 3
Input: nums = [1,1,1,2] Output: false Explanation: There is no valid partition for this array.
You are given a string s consisting of lowercase letters and an integer k. We call a string tideal if the following conditions are satisfied:
t is a subsequence of the string s.
The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.
Return the length of the longest ideal string.
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.
Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of 'a' and 'z' is 25, not 1.
Example 1:
1 2 3 4
Input: s = "acfgbd", k = 2 Output: 4 Explanation: The longest ideal string is "acbd". The length of this string is 4, so 4 is returned. Note that "acfgbd" is not ideal because 'c' and 'f' have a difference of 3 in alphabet order.
Example 2:
1 2 3
Input: s = "abcd", k = 3 Output: 4 Explanation: The longest ideal string is "abcd". The length of this string is 4, so 4 is returned.
Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:
maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.
In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.
Return the generated matrix.
Example 1:
1 2 3 4
Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]] Output: [[9,9],[8,6]] Explanation: The diagram above shows the original matrix and the generated matrix. Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.
Example 2:
1 2 3
Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]] Output: [[2,2,2],[2,2,2],[2,2,2]] Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.
Constraints:
n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100
Easy，暴力
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: vector<vector<int>> largestLocal(vector<vector<int>>& grid) { int n = grid.size(); int n_dot = n - 2; vector<vector<int>> res (n_dot, vector<int>(n_dot, 0)); for (int i = 0; i < n_dot; i++) { for (int j = 0; j < n_dot; j++) { for (int l = 0; l <= 2; l++) { for (int m = 0; m <= 2; m++) { res[i][j] = max(res[i][j], grid[i + l][j + m]); } } } } return res; } };
You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge.
The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].
The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.
Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.
Example 1:
1 2 3 4 5 6 7 8
Input: edges = [1,0,0,0,0,7,7,5] Output: 7 Explanation: - The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10. - The node 0 has an edge pointing to node 1. The edge score of node 1 is 0. - The node 7 has an edge pointing to node 5. The edge score of node 5 is 7. - The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11. Node 7 has the highest edge score so return 7.
Example 2:
1 2 3 4 5 6
Input: edges = [2,0,0,2] Output: 0 Explanation: - The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3. - The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3. Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.
Constraints:
n == edges.length
2 <= n <= 105
0 <= edges[i] < n
edges[i] != i
Medium，统计每条边的入度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intedgeScore(vector<int>& edges){ int n = edges.size(); vector<longlong> inDegree(n, 0); for (int i = 0; i < n; i++) { inDegree[edges[i]] += i; } int maxCount = 0; for (int i = 1; i < n; i++) { if (inDegree[i] > inDegree[maxCount]) { maxCount = i; } } return maxCount; } };
You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.
A 0-indexed string num of length n + 1 is created using the following conditions:
num consists of the digits '1' to '9', where each digit is used at most once.
If pattern[i] == 'I', then num[i] < num[i + 1].
If pattern[i] == 'D', then num[i] > num[i + 1].
Return the lexicographically smallest possible stringnumthat meets the conditions.
Example 1:
1 2 3 4 5 6 7 8
Input: pattern = "IIIDIDDD" Output: "123549876" Explanation: At indices 0, 1, 2, and 4 we must have that num[i] < num[i+1]. At indices 3, 5, 6, and 7 we must have that num[i] > num[i+1]. Some possible values of num are "245639871", "135749862", and "123849765". It can be proven that "123549876" is the smallest possible num that meets the conditions. Note that "123414321" is not possible because the digit '1' is used more than once.
Example 2:
1 2 3 4 5
Input: pattern = "DDD" Output: "4321" Explanation: Some possible values of num are "9876", "7321", and "8742". It can be proven that "4321" is the smallest possible num that meets the conditions.
Constraints:
1 <= pattern.length <= 8
pattern consists of only the letters 'I' and 'D'.
Medium，使用栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: stringsmallestNumber(string pattern){ string res, stk; for (int i = 0; i <= pattern.length(); i++) { stk.push_back('1' + i); if (i == pattern.length() || pattern[i] == 'I') { while (!stk.empty()) { res.push_back(stk.back()); stk.pop_back(); } } } return res; } };
We call a positive integer special if all of its digits are distinct.
Given a positive integer n, return the number of special integers that belong to the interval[1, n].
Example 1:
1 2 3
Input: n = 20 Output: 19 Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
1 2 3
Input: n = 5 Output: 5 Explanation: All the integers from 1 to 5 are special.
Example 3:
1 2 3 4
Input: n = 135 Output: 110 Explanation: There are 110 integers from 1 to 135 that are special. Some of the integers that are not special are: 22, 114, and 131.
classSolution { public: intfact(int n){ if (n == 1 || n == 0) return1; return n * fact(n - 1); } intA(int m, int n){ return fact(m) / fact(m - n); }
intcountSpecialNumbers(int n){ string strN = to_string(n); int sz = strN.size();
int used[10] = {0}; int total = 0;
for (int i = 1; i < sz; i++) total += 9 * A(9, i - 1);
for(int i = 0; i < sz; i++){ int num = strN[i] - 48; for (int j = (i == 0 ? 1 : 0); j < num; j++){ if (used[j] != 0) continue; total += A(10 - 1 - i, sz - i - 1); } if(++used[num] > 1) break; if (i == sz - 1) total += 1; } return total; } };
You are entering a competition, and are given two positive integers initialEnergy and initialExperience denoting your initial energy and initial experience respectively.
You are also given two 0-indexed integer arrays energy and experience, both of length n.
You will face n opponents in order. The energy and experience of the ith opponent is denoted by energy[i] and experience[i] respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.
Defeating the ith opponent increases your experience by experience[i], but decreases your energy by energy[i].
Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.
Return the minimum number of training hours required to defeat allnopponents.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1] Output: 8 Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training. You face the opponents in the following order: - You have more energy and experience than the 0th opponent so you win. Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7. - You have more energy and experience than the 1st opponent so you win. Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13. - You have more energy and experience than the 2nd opponent so you win. Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16. - You have more energy and experience than the 3rd opponent so you win. Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17. You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8. It can be proven that no smaller answer exists.
Example 2:
1 2 3
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3] Output: 0 Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
You are given a string num consisting of digits only.
Return the largest palindromic integer (in the form of a string) that can be formed using digits taken fromnum. It should not contain leading zeroes.
Notes:
You do not need to use all the digits of num, but you must use at least one digit.
The digits can be reordered.
Example 1:
1 2 3 4 5
Input: num = "444947137" Output: "7449447" Explanation: Use the digits "4449477" from "444947137" to form the palindromic integer "7449447". It can be shown that "7449447" is the largest palindromic integer that can be formed.
Example 2:
1 2 3 4 5
Input: num = "00009" Output: "9" Explanation: It can be shown that "9" is the largest palindromic integer that can be formed. Note that the integer returned should not contain leading zeroes.
You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.
Each minute, a node becomes infected if:
The node is currently uninfected.
The node is adjacent to an infected node.
Return the number of minutes needed for the entire tree to be infected.
Example 1:
1 2 3 4 5 6 7 8 9
Input: root = [1,5,3,null,4,10,6,9,2], start = 3 Output: 4 Explanation: The following nodes are infected during: - Minute 0: Node 3 - Minute 1: Nodes 1, 10 and 6 - Minute 2: Node 5 - Minute 3: Node 4 - Minute 4: Nodes 9 and 2 It takes 4 minutes for the whole tree to be infected so we return 4.
Example 2:
1 2 3
Input: root = [1], start = 1 Output: 0 Explanation: At minute 0, the only node in the tree is infected so we return 0.
Constraints:
The number of nodes in the tree is in the range [1, 105].
You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.
We define the K-Sum of the array as the kthlargest subsequence sum that can be obtained (not necessarily distinct).
Return the K-Sum of the array.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Note that the empty subsequence is considered to have a sum of 0.
Example 1:
1 2 3 4 5
Input: nums = [2,4,-2], k = 5 Output: 2 Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order: - 6, 4, 4, 2, 2, 0, 0, -2. The 5-Sum of the array is 2.
Example 2:
1 2 3
Input: nums = [1,-2,3,4,-10,12], k = 16 Output: 10 Explanation: The 16-Sum of the array is 10.
classSolution { public: longlongkSum(vector<int>& nums, int k){ int n = nums.size(); // sm 表示所有数的和，neg 表示所有负数之和 longlong sm = 0, neg = 0; for (int i = 0; i < n; i++) { sm += nums[i]; if (nums[i] < 0) { neg += nums[i]; nums[i] = -nums[i]; } } sort(nums.begin(), nums.end());
// k = 1 时的答案，也就是空集的和 longlong ans = 0; priority_queue<pair<longlong, int>, vector<pair<longlong, int>>, greater<pair<longlong, int>>> pq; pq.push(make_pair(nums[0], 0)); for (int i = 2; i <= k; i++) { auto p = pq.top(); pq.pop(); // k = i 时的答案 ans = p.first; if (p.second == n - 1) continue; pq.push(make_pair(p.first + nums[p.second + 1], p.second + 1)); pq.push(make_pair(p.first - nums[p.second] + nums[p.second + 1], p.second + 1)); } return sm - (neg + ans); } };
You are given an integer array nums of length n, and an integer array queries of length m.
Return an arrayanswerof lengthmwhereanswer[i]is the maximum size of a subsequence that you can take fromnumssuch that the sum of its elements is less than or equal toqueries[i].
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
1 2 3 4 5 6
Input: nums = [4,5,2,1], queries = [3,10,21] Output: [2,3,4] Explanation: We answer the queries as follows: - The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2. - The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3. - The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.
Example 2:
1 2 3
Input: nums = [2,3,4,5], queries = [1] Output: [0] Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.
Constraints:
n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106
Easy，其实比较复杂，前缀和+二分查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: vector<int> answerQueries(vector<int>& nums, vector<int>& queries){ sort(nums.begin(), nums.end()); int n = nums.size(); vector<int> prefix(n, 0); prefix[0] = nums[0]; for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + nums[i]; } int m = queries.size(); vector<int> res(m, 0); for (int i = 0; i < m; i++) { res[i] = upper_bound(prefix.begin(), prefix.end(), queries[i]) - prefix.begin(); } return res; } };
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.
Example 1:
1 2 3 4 5 6 7
Input: s = "leet**cod*e" Output: "lecoe" Explanation: Performing the removals from left to right: - The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e". - The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e". - The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe". There are no more stars, so we return "lecoe".
Example 2:
1 2 3
Input: s = "erase*****" Output: "" Explanation: The entire string is removed, so we return an empty string.
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters and stars *.
You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith house. garbage[i] consists only of the characters 'M', 'P' and 'G' representing one unit of metal, paper and glass garbage respectively. Picking up one unit of any type of garbage takes 1 minute.
You are also given a 0-indexed integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1.
There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house 0 and must visit each house in order; however, they do not need to visit every house.
Only one garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks cannot do anything.
Return the minimum number of minutes needed to pick up all the garbage.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Input: garbage = ["G","P","GP","GG"], travel = [2,4,3] Output: 21 Explanation: The paper garbage truck: 1. Travels from house 0 to house 1 2. Collects the paper garbage at house 1 3. Travels from house 1 to house 2 4. Collects the paper garbage at house 2 Altogether, it takes 8 minutes to pick up all the paper garbage. The glass garbage truck: 1. Collects the glass garbage at house 0 2. Travels from house 0 to house 1 3. Travels from house 1 to house 2 4. Collects the glass garbage at house 2 5. Travels from house 2 to house 3 6. Collects the glass garbage at house 3 Altogether, it takes 13 minutes to pick up all the glass garbage. Since there is no metal garbage, we do not need to consider the metal garbage truck. Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.
Example 2:
1 2 3 4 5 6 7
Input: garbage = ["MMM","PGM","GP"], travel = [3,10] Output: 37 Explanation: The metal garbage truck takes 7 minutes to pick up all the metal garbage. The paper garbage truck takes 15 minutes to pick up all the paper garbage. The glass garbage truck takes 15 minutes to pick up all the glass garbage. It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.
Constraints:
2 <= garbage.length <= 105
garbage[i] consists of only the letters 'M', 'P', and 'G'.
You are given a positive integer k. You are also given:
a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].
The two arrays contain integers from 1 to k.
You have to build a k x k matrix that contains each of the numbers from 1 to kexactly once. The remaining cells should have the value 0.
The matrix should also satisfy the following conditions:
The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.
Return *any matrix that satisfies the conditions*. If no answer exists, return an empty matrix.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: k = 3, rowConditions = [[1,2],[3,2]], colConditions = [[2,1],[3,2]] Output: [[3,0,0],[0,0,1],[0,2,0]] Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions. The row conditions are the following: - Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix. - Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix. The column conditions are the following: - Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix. - Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix. Note that there may be multiple correct answers.
Example 2:
1 2 3 4
Input: k = 3, rowConditions = [[1,2],[2,3],[3,1],[2,3]], colConditions = [[2,1]] Output: [] Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied. No matrix can satisfy all the conditions, so we return the empty matrix.
You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactlytwice. You are also given a 0-indexed integer array distance of length 26.
Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, … , 'z' -> 25).
In a well-spaced string, the number of letters between the two occurrences of the ith letter is distance[i]. If the ith letter does not appear in s, then distance[i] can be ignored.
Return trueifsis a well-spaced string, otherwise returnfalse.
Example 1:
1 2 3 4 5 6 7 8
Input: s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: true Explanation: - 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1. - 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3. - 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0. Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored. Return true because s is a well-spaced string.
Example 2:
1 2 3 4 5
Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] Output: false Explanation: - 'a' appears at indices 0 and 1 so there are zero letters between them. Because distance[0] = 1, s is not a well-spaced string.
Constraints:
2 <= s.length <= 52
s consists only of lowercase English letters.
Each letter appears in s exactly twice.
distance.length == 26
0 <= distance[i] <= 50
Easy，保存每个字母出现的位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: boolcheckDistances(string s, vector<int>& distance){ vector<int> pre(26, -1); for (int i = 0; i < s.size(); i++) { int num = s[i] - 'a'; if (pre[num] == -1) { pre[num] = i; } else { if (i - pre[num] - 1 != distance[num]) returnfalse; } } returntrue; } };
You are given two positive integers startPos and endPos. Initially, you are standing at position startPos on an infinite number line. With one step, you can move either one position to the left, or one position to the right.
Given a positive integer k, return the number of different ways to reach the positionendPosstarting fromstartPos, such that you perform exactlyksteps. Since the answer may be very large, return it modulo109 + 7.
Two ways are considered different if the order of the steps made is not exactly the same.
Note that the number line includes negative integers.
Example 1:
1 2 3 4 5 6 7
Input: startPos = 1, endPos = 2, k = 3 Output: 3 Explanation: We can reach position 2 from 1 in exactly 3 steps in three ways: - 1 -> 2 -> 3 -> 2. - 1 -> 2 -> 1 -> 2. - 1 -> 0 -> 1 -> 2. It can be proven that no other way is possible, so we return 3.
Example 2:
1 2 3
Input: startPos = 2, endPos = 5, k = 10 Output: 0 Explanation: It is impossible to reach position 5 from position 2 in exactly 10 steps.
classSolution { public: int mod = 1e9 + 7; intnumberOfWays(int startPos, int endPos, int k){ if ((k - (endPos - startPos)) % 2 != 0 || abs(k) < abs(endPos - startPos)) return0; int pos = (endPos - startPos + k) / 2; int neg = k - pos; longlongint res = 1; int a = pos > neg ? neg : pos; for (int i = 0; i < a; i++) { res = res * (k - i) % mod; res = res * inv(i + 1) % mod; } return res; } longinv(long a){ if (a == 1) return1; return (mod - mod / a) * inv(mod % a) % mod; } };
You are given an array nums consisting of positive integers.
We call a subarray of numsnice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.
Return the length of the longest nice subarray.
A subarray is a contiguous part of an array.
Note that subarrays of length 1 are always considered nice.
Example 1:
1 2 3 4 5 6 7
Input: nums = [1,3,8,48,10] Output: 3 Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions: - 3 AND 8 = 0. - 3 AND 48 = 0. - 8 AND 48 = 0. It can be proven that no longer nice subarray can be obtained, so we return 3.
Example 2:
1 2 3
Input: nums = [3,1,5,11,13] Output: 1 Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Medium，滑动窗口+位运算，挨个统计位会超时
1 2 3 4 5 6 7 8 9 10 11 12 13
classSolution { public: intlongestNiceSubarray(vector<int>& nums){ int AND = 0, i = 0, res = 0, n = nums.size(); for (int j = 0; j < n; j++) { while ((AND & nums[j]) > 0) AND ^= nums[i++]; AND |= nums[j]; res = max(res, j - i + 1); } return res; } };
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval[a, b) is the interval between a and bincludinga and not includingb.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] Output: 0 Explanation: - At time 0, both rooms are not being used. The first meeting starts in room 0. - At time 1, only room 1 is not being used. The second meeting starts in room 1. - At time 2, both rooms are being used. The third meeting is delayed. - At time 3, both rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10). - At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11). Both rooms 0 and 1 held 2 meetings, so we return 0.
Example 2:
1 2 3 4 5 6 7 8 9 10 11
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1 Explanation: - At time 1, all three rooms are not being used. The first meeting starts in room 0. - At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1. - At time 3, only room 2 is not being used. The third meeting starts in room 2. - At time 4, all three rooms are being used. The fourth meeting is delayed. - At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10). - At time 6, all three rooms are being used. The fifth meeting is delayed. - At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12). Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.
boolcompare(vector<int>& v1, vector<int>& v2){ return v1[0] < v2[0]; } classSolution { public: intmostBooked(int n, vector<vector<int>>& meetings){ /* Sort the meetings based on start_time */ sort(meetings.begin(), meetings.end(), compare); /* Create a priority queue for engaged rooms. Each node of PQ will store {current_meeting_ending_time, room_number} */ priority_queue<pair<longlong, int>, vector<pair<longlong, int>>, greater<pair<longlong, int>>> engaged; /* Create a priority queue for non-engaged rooms. Each node of PQ will store {room_number} */ priority_queue<int, vector<int>, greater<int>> unused; /* Frequency map to store the frequency of meetings in each room */ unordered_map<int, int> freq; /* Currently all the rooms are mepty */ for (int i = 0; i < n; i++) { unused.push(i); } for (auto x:meetings) { int s = x[0], e = x[1]; /* Move the meeting rooms in engaged, with ending_time <= s, to unused */ while(engaged.size() > 0 && engaged.top().first <= s) { int room = engaged.top().second; engaged.pop(); unused.push(room); } /* If there are multiple empty rooms, choose the one with lower room_number */ if (unused.size() > 0) { int room = unused.top(); unused.pop(); freq[abs(room)]++; /* Mark the room as engaged */ engaged.push({e, room}); } /* If there are no empty rooms, wait for the engaged room with nearest ending time to empty */ else { pair<longlong, int> topmost = engaged.top(); engaged.pop(); freq[abs(topmost.second)] += 1; /* Since duration has to be the same, the newEnd will be sum(end_time_of_the_prev_meeting, duration) */ longlong newEnd = topmost.first; newEnd += (e - s); /* Mark the room as engaged */ engaged.push({newEnd, topmost.second}); } } /* Find the lowest room_number with maximum frequency */ int maxi = 0; for (int i = 1; i < n; i++) { if (freq[i] > freq[maxi]) maxi = i; } return maxi; } };
Given an integer array nums, return the most frequent even element.
If there is a tie, return the smallest one. If there is no such element, return -1.
Example 1:
1 2 3 4 5
Input: nums = [0,1,2,2,4,4,1] Output: 2 Explanation: The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most. We return the smallest one, which is 2.
Example 2:
1 2 3
Input: nums = [4,4,4,9,2,4] Output: 4 Explanation: 4 is the even element appears the most.
Example 3:
1 2 3
Input: nums = [29,47,21,41,13,37,25,7] Output: -1 Explanation: There is no even element.
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
Example 1:
1 2 3 4 5
Input: s = "abacaba" Output: 4 Explanation: Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba"). It can be shown that 4 is the minimum number of substrings needed.
Example 2:
1 2 3 4
Input: s = "ssssss" Output: 6 Explanation: The only valid partition is ("s","s","s","s","s","s").
Constraints:
1 <= s.length <= 105
s consists of only English lowercase letters.
Medium，双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: intpartitionString(string s){ int res = 1; vector<bool> window(26, false); window[s[0] - 'a'] = true; for (int i = 1; i < s.size(); i++) { if (window[s[i] - 'a'] == true) { res++; window.assign(26, false); } window[s[i] - 'a'] = true; } return res; } };
You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].
You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.
Return the minimum number of groups you need to make.
Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.
Example 1:
1 2 3 4 5 6 7
Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]] Output: 3 Explanation: We can divide the intervals into the following groups: - Group 1: [1, 5], [6, 8]. - Group 2: [2, 3], [5, 10]. - Group 3: [1, 10]. It can be proven that it is not possible to divide the intervals into fewer than 3 groups.
Example 2:
1 2 3
Input: intervals = [[1,3],[5,6],[8,10],[11,13]] Output: 1 Explanation: None of the intervals overlap, so we can put all of them in one group.
classSolution { public: intminGroups(vector<vector<int>>& intervals){ vector<vector<int>> A; for (auto& v : intervals) { A.push_back({v[0], 1}); A.push_back({v[1] + 1, -1}); } int res = 0, cur = 0; sort(A.begin(), A.end()); for (auto& v : A) res = max(res, cur += v[1]); return res; } };
You are given an integer array nums and an integer k.
Find the longest subsequence of nums that meets the following requirements:
The subsequence is strictly increasing and
The difference between adjacent elements in the subsequence is at mostk.
Return the length of the longestsubsequence that meets the requirements.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
1 2 3 4 5 6
Input: nums = [4,2,1,4,3,4,5,8,15], k = 3 Output: 5 Explanation: The longest subsequence that meets the requirements is [1,3,4,5,8]. The subsequence has a length of 5, so we return 5. Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.
Example 2:
1 2 3 4 5
Input: nums = [7,4,5,1,8,12,4,7], k = 5 Output: 4 Explanation: The longest subsequence that meets the requirements is [4,5,8,12]. The subsequence has a length of 4, so we return 4.
Example 3:
1 2 3 4 5
Input: nums = [1,5], k = 1 Output: 1 Explanation: The longest subsequence that meets the requirements is [1]. The subsequence has a length of 1, so we return 1.
voidmodify(int o, int l, int r, int i, int val){ if (l == r) { max[o] = val; return; } int m = (l + r) / 2; if (i <= m) modify(o * 2, l, m, i, val); else modify(o * 2 + 1, m + 1, r, i, val); max[o] = std::max(max[o * 2], max[o * 2 + 1]); }
// 返回区间 [L,R] 内的最大值 intquery(int o, int l, int r, int L, int R){ // L 和 R 在整个递归过程中均不变，将其大写，视作常量 if (L <= l && r <= R) return max[o]; int res = 0; int m = (l + r) / 2; if (L <= m) res = query(o * 2, l, m, L, R); if (R > m) res = std::max(res, query(o * 2 + 1, m + 1, r, L, R)); return res; }
public: intlengthOfLIS(vector<int> &nums, int k){ int u = *max_element(nums.begin(), nums.end()); max.resize(u * 4); for (int num: nums) { if (num == 1) modify(1, 1, u, 1, 1); else { int res = 1 + query(1, 1, u, std::max(num - k, 1), num - 1); modify(1, 1, u, num, res); } } return max[1]; } };
An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".
For example, "abc" is an alphabetical continuous string, while "acb" and "za" are not.
Given a string s consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.
Example 1:
1 2 3 4
Input: s = "abacaba" Output: 2 Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab". "ab" is the longest continuous substring.
Example 2:
1 2 3
Input: s = "abcde" Output: 5 Explanation: "abcde" is the longest continuous substring.
Constraints:
1 <= s.length <= 105
s consists of only English lowercase letters.
Medium，滑动窗口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intlongestContinuousSubstring(string s){ int res = 1; int pre = 0; int cur = 1; while (cur < s.size()) { while (cur < s.size() && s[cur] - s[cur - 1] == 1) { cur++; } res = max(res, cur - pre); pre = cur; cur++; } return res; } };
Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.
Example 1:
1 2 3 4 5
Input: root = [2,3,5,8,13,21,34] Output: [2,5,3,8,13,21,34] Explanation: The tree has only one odd level. The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
Example 2:
1 2 3 4
Input: root = [7,13,11] Output: [7,11,13] Explanation: The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
Example 3:
1 2 3 4 5 6
Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2] Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1] Explanation: The odd levels have non-zero values. The nodes at level 1 were 1, 2, and are 2, 1 after the reversal. The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
Constraints:
The number of nodes in the tree is in the range [1, 214].
You are given an array words of size n consisting of non-empty strings.
We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].
For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".
Return an arrayanswerof sizenwhereanswer[i]is the sum of scores of every non-empty prefix ofwords[i].
Note that a string is considered as a prefix of itself.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Input: words = ["abc","ab","bc","b"] Output: [5,4,3,2] Explanation: The answer for each string is the following: - "abc" has 3 prefixes: "a", "ab", and "abc". - There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc". The total is answer[0] = 2 + 2 + 1 = 5. - "ab" has 2 prefixes: "a" and "ab". - There are 2 strings with the prefix "a", and 2 strings with the prefix "ab". The total is answer[1] = 2 + 2 = 4. - "bc" has 2 prefixes: "b" and "bc". - There are 2 strings with the prefix "b", and 1 string with the prefix "bc". The total is answer[2] = 2 + 1 = 3. - "b" has 1 prefix: "b". - There are 2 strings with the prefix "b". The total is answer[3] = 2.
Example 2:
1 2 3 4 5
Input: words = ["abcd"] Output: [4] Explanation: "abcd" has 4 prefixes: "a", "ab", "abc", and "abcd". Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.
You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.
For each index i, names[i] and heights[i] denote the name and height of the ith person.
Return namessorted in descending order by the people’s heights.
Example 1:
1 2 3
Input: names = ["Mary","John","Emma"], heights = [180,165,170] Output: ["Mary","Emma","John"] Explanation: Mary is the tallest, followed by Emma and John.
Example 2:
1 2 3
Input: names = ["Alice","Bob","Bob"], heights = [155,185,150] Output: ["Bob","Alice","Bob"] Explanation: The first Bob is the tallest, followed by Alice and the second Bob.
Constraints:
n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.
Easy，排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { public: vector<string> sortPeople(vector<string>& names, vector<int>& heights){ vector<pair<int, int>> heightS; for (int i = 0; i < heights.size(); i++) { heightS.push_back({heights[i], i}); } sort(heightS.begin(), heightS.end()); vector<string> res; for (int i = heights.size() - 1; i >= 0; i--) { res.push_back(names[heightS[i].second]); } return res; } };
Consider a non-empty subarray from nums that has the maximum possible bitwise AND.
In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.
Return the length of the longest such subarray.
The bitwise AND of an array is the bitwise AND of all the numbers in it.
A subarray is a contiguous sequence of elements within an array.
Example 1:
1 2 3 4 5
Input: nums = [1,2,3,3,2,2] Output: 2 Explanation: The maximum possible bitwise AND of a subarray is 3. The longest subarray with that value is [3,3], so we return 2.
Example 2:
1 2 3 4 5
Input: nums = [1,2,3,4] Output: 1 Explanation: The maximum possible bitwise AND of a subarray is 4. The longest subarray with that value is [4], so we return 1.
You are given a 0-indexed integer array nums of size n and a positive integer k.
We call an index i in the range k <= i < n - kgood if the following conditions are satisfied:
The k elements that are just before the index i are in non-increasing order.
The k elements that are just after the index i are in non-decreasing order.
Return an array of all good indices sorted in increasing order.
Example 1:
1 2 3 4 5 6
Input: nums = [2,1,1,1,3,4,1], k = 2 Output: [2,3] Explanation: There are two good indices in the array: - Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order. - Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order. Note that the index 4 is not good because [4,1] is not non-decreasing.
Example 2:
1 2 3
Input: nums = [2,1,1,2], k = 2 Output: [] Explanation: There are no good indices in this array.
There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.
You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A good path is a simple path that satisfies the following conditions:
The starting node and the ending node have the same value.
All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node’s value should be the maximum value along the path).
Return the number of distinct good paths.
Note that a path and its reverse are counted as the same path. For example, 0 -> 1 is considered to be the same as 1 -> 0. A single node is also considered as a valid path.
Example 1:
1 2 3 4 5 6
Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]] Output: 6 Explanation: There are 5 good paths consisting of a single node. There is 1 additional good path: 1 -> 0 -> 2 -> 4. (The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.) Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].
Example 2:
1 2 3 4
Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]] Output: 7 Explanation: There are 5 good paths consisting of a single node. There are 2 additional good paths: 0 -> 1 and 2 -> 3.
Example 3:
1 2 3
Input: vals = [1], edges = [] Output: 1 Explanation: The tree consists of only one node, so there is one good path.
Given two positive integers a and b, return the number of common factors ofaandb.
An integer x is a common factor of a and b if x divides both a and b.
Example 1:
1 2 3
Input: a = 12, b = 6 Output: 4 Explanation: The common factors of 12 and 6 are 1, 2, 3, 6.
Example 2:
1 2 3
Input: a = 25, b = 30 Output: 2 Explanation: The common factors of 25 and 30 are 1, 5.
Constraints:
1 <= a, b <= 1000
Easy，最大公约数，应有更好的方法，找到后分解质因数
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: intcommonFactors(int a, int b){ int num = std::gcd(a, b); int res = 1; for (int i = 2; i <= num; i++) { if (num % i == 0) res++; } return res; } };
We define an hourglass as a part of the matrix with the following form:
Return the maximum sum of the elements of an hourglass.
Note that an hourglass cannot be rotated and must be entirely contained within the matrix.
Example 1:
1 2 3
Input: grid = [[6,2,1,3],[4,2,1,5],[9,2,8,7],[4,1,2,9]] Output: 30 Explanation: The cells shown above represent the hourglass with the maximum sum: 6 + 2 + 1 + 2 + 9 + 2 + 8 = 30.
Example 2:
1 2 3
Input: grid = [[1,2,3],[4,5,6],[7,8,9]] Output: 35 Explanation: There is only one hourglass in the matrix, with the sum: 1 + 2 + 3 + 5 + 7 + 8 + 9 = 35.
Constraints:
m == grid.length
n == grid[i].length
3 <= m, n <= 150
0 <= grid[i][j] <= 106
Medium，直接计算每个窗口之和，理论上可以使用滑动窗口优化
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: intmaxSum(vector<vector<int>>& grid){ int m = grid.size(), n = grid[0].size(); int res = 0; for (int i = 0; i < m - 2; i++) { for (int j = 0; j < n - 2; j++) { int num = grid[i][j] + grid[i][j + 1] + grid[i][j + 2] + grid[i + 1][j + 1] + grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2]; if (num > res) res = num; } } return res; } };
Given two positive integers num1 and num2, find the integer x such that:
x has the same number of set bits as num2, and
The value x XOR num1 is minimal.
Note that XOR is the bitwise XOR operation.
Return the integerx. The test cases are generated such that x is uniquely determined.
The number of set bits of an integer is the number of 1‘s in its binary representation.
Example 1:
1 2 3 4 5
Input: num1 = 3, num2 = 5 Output: 3 Explanation: The binary representations of num1 and num2 are 0011 and 0101, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 3 = 0 is minimal.
Example 2:
1 2 3 4 5
Input: num1 = 1, num2 = 12 Output: 3 Explanation: The binary representations of num1 and num2 are 0001 and 1100, respectively. The integer 3 has the same number of set bits as num2, and the value 3 XOR 1 = 2 is minimal.
classSolution { public: intminimizeXor(int num1, int num2){ vector<int> bin1(31, 0), bin2(31, 0); getBin(num1, bin1); getBin(num2, bin2); int count1 = std::accumulate(bin1.begin(), bin1.end(), 0); int count2 = std::accumulate(bin2.begin(), bin2.end(), 0); if (count1 == count2) return num1; vector<int> bin = bin1; if (count1 < count2) { int diff = count2 - count1; for (int i = 0; i < 31; i++) { if (bin1[i] == 0) { bin[i] = 1; diff--; if (diff == 0) { break; } } } } else { int diff = count1 - count2; for (int i = 0; i < 31; i++) { if (bin1[i] == 1) { bin[i] = 0; diff--; if (diff == 0) { break; } } } } return genNum(bin); } voidgetBin(int num, vector<int> &bin){ int count = 0; while (num != 0) { bin[count] = num & 1; count++; num = num >> 1; } } intgenNum(vector<int> &bin){ int res = 0, cur = 1; for (int i = 0; i < 31; i++) { if (bin[i] == 1) { res = res | cur; } cur = cur << 1; } return res; } };
同样的逻辑，看看人大佬写得多优雅
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: intminimizeXor(int num1, int num2){ int a = __builtin_popcount(num1), b = __builtin_popcount(num2), res = num1; for (int i = 0; i < 32; ++i) { if (a > b && ((1 << i) & num1) > 0) { res ^= 1 << i; a--; } if (a < b && ((1 << i) & num1) == 0) { res ^= 1 << i; a++; } } return res; } };
You are given a string s consisting of only lowercase English letters. In one operation, you can:
Delete the entire strings, or
Delete the firsti letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= i <= s.length / 2.
For example, if s = "ababc", then in one operation, you could delete the first two letters of s to get "abc", since the first two letters of s and the following two letters of s are both equal to "ab".
Return the maximum number of operations needed to delete all ofs.
Example 1:
1 2 3 4 5 6 7
Input: s = "abcabcdabc" Output: 2 Explanation: - Delete the first 3 letters ("abc") since the next 3 letters are equal. Now, s = "abcdabc". - Delete all the letters. We used 2 operations so return 2. It can be proven that 2 is the maximum number of operations needed. Note that in the second operation we cannot delete "abc" again because the next occurrence of "abc" does not happen in the next 3 letters.
Example 2:
1 2 3 4 5 6 7 8
Input: s = "aaabaab" Output: 4 Explanation: - Delete the first letter ("a") since the next letter is equal. Now, s = "aabaab". - Delete the first 3 letters ("aab") since the next 3 letters are equal. Now, s = "aab". - Delete the first letter ("a") since the next letter is equal. Now, s = "ab". - Delete all the letters. We used 4 operations so return 4. It can be proven that 4 is the maximum number of operations needed.
Example 3:
1 2 3
Input: s = "aaaaa" Output: 5 Explanation: In each operation, we can delete the first letter of s.
functiondup(s: string): boolean{ const len = s.length; for (let i = 1; i <= Math.floor(len / 2); i++) { if (len % i == 0) { let t = s.slice(0, i); let j = len / i; if (s === t.repeat(j)) { returntrue; } } } returnfalse; }
functiondeleteString(s: string): number{ let res: number = 0; while (s.length > 0) { const len = s.length; if (dup(s)) { for (let i = 1; i <= Math.floor(len / 2); i++) { if (len % i == 0) { let t = s.slice(0, i); let j = len / i; if (s === t.repeat(j)) { s = t; res += j - 1; break; } } } } else { let i = Math.floor(len / 2); for (; i >= 1; i--) { const t = s.slice(0, i); if (s.startsWith(t + t) && !dup(t)) { s = s.slice(i); res++; break; } } if (i == 0) { res++; break; } } } return res; };
