- For the LeetCode problem “Licopqibaling,” a recursive solution can pass all test cases.
- Given a string consisting of 01, find the shortest string containing k number of 1s. If the lengths are the same, find the one representing the smallest number.
Approach: Traverse the string, record the position of each 1 in array v. Then iterate through v, for every k numbers, find the minimum of v[i+k-1] - v(i) (which is the value of length - 1). - There are 112 domino pieces, how many ways can they fill a 22n well? Result should be modulo (1e9+7).
Approach: dp(i) = 3dp[i-1] + 3dp[i-2] - dp[i-3], initial values are provided in the problem. - Given a series of strings, such as “10th Jan 2022,” convert it to “2022-01-10.”
My approach (not sure if it will timeout, couldn’t debug the last few cases):
First, iterate through each edge, add the two people corresponding to each interest to a set, one set for each interest. Then build an adjacency matrix where vertices are people and edges represent the number of interests. Bruteforce by iterating through the sets of people and incrementing the edge weight (interest count).
Heard problems:
- Input: s = “|**|**|||”, v1 = {0, 1, 2}, v2 = {8, 9, 10}; Find the number of stars between v1 and v2 in the bars.
Approach: O(size(s)+size(v1))
Traverse s from left to right, use a prefix sum array to record the number of *. Record the position of the left bar at a certain position using the leftBar array.
Traverse s from right to left, record the position of the right bar at a certain position using the rightBar array.
Simultaneously iterate through v1 and v2, calculate res(i) = preSum[leftBar[v2(i)]] - preSum[rightBar[v1(i)]]; (res is 0 when leftBar[v2(i)]<=rightBar[v1(i)])
(Variant in descending order)
My approach: O(size2)
Choose numbers from [1, size-1] as the middle number, for each position, calculate the number of elements smaller than it before and the number of elements greater than it after, res += m*n; (consider using unordered_set to avoid duplicates)
3. For the LeetCode problem “Liqoyisanba,”