The smallest sequence in a non-increasing order

















Given an array nums, extract a subsequence from which the sum of the elements is strictly greater than the sum of the elements not contained in the subsequence.

If more than one solution exists, simply return the smallest subsequence. If there are still multiple solutions, return the subsequence with the largest sum of elements.
Unlike subarrays, “subsequences of arrays” do not emphasize the continuity of elements in the original array, that is, it can be obtained by separating some (or not) elements from the array.

Note that the problem data guarantees that the solution that satisfies all the constraints is unique. Also, the answers returned should be in non-ascending order.

Example:
Input: nums = [4,3,10,9,8]
Output: [10, 9]
Explanation: the subsequences [10,9] and [10,8] are the smallest such that the sum of the elements is greater than the sum of the other elements. But the sum of the elements [10,9] is the largest.








In this case, a greedy algorithm is required: the maximum sum value and the shortest subsequence length can be guaranteed only when the largest value is guaranteed first.

The next step is to compare the current cumulative sum to the sum in the traversal process.

Time complexity O(nlogn), space complexity O(n)










The number of steps to reduce binary to 1

















I give you a number s in binary form. Return the number of steps required to reduce it to 1 as follows:

If the current number is even, divide it by 2.

If the current number is odd, add one to it.
They guarantee that you can always change the test case to 1 by following the rules above.
Example:
Enter: s = ‘1101’
Output: 6
Explanation: ‘1101’ represents the decimal number 13.
13 is odd. Add 1 to get 14
14 is even. Divide by 2 and you get 7
If 7 is odd, add 1 to get 8
8 is even. Divide 2 by 4
4 is even. Divide by 2 and you get 2
If 2 is even, divide by 2 and you get 1








The string length in this problem is in the range [1, 500], so you cannot decimal the string directly with number. parseInt.

Then you need to simulate binary division and addition for strings.

In binary operations, to divide by 2 is to move the binary number one bit to the right, where you simply remove the last bit of the string.

The increment operation is a bit more complicated, requiring the carry to be processed from low to high.

Now, just follow the rules.

Time complexity O(n^2), space complexity O(n).










Longest happy string

















A string is a “happy string” if it does not contain any strings like ‘AAA’, ‘BBB’ or ‘CCC’ as substrings.

Given three integers a, b, and c, return any string S that meets all of the following criteria:

S is a happy string as long as possible.
S contains a maximum of a letters’ A ‘, B letters ‘b’, and C letters’ C ‘.
S contains only ‘A’, ‘b’ and ‘C’.
If no such string s exists, return an empty string ”.

Example:
Input: A = 1, b = 1, c = 7
Output: ‘ccaccbcc’
Explanation: ‘ccbccacc’ is also the correct answer








This problem also requires a greedy algorithm: the largest number of characters are selected first.

But in the selection process needs to be full of details:

  • Records the status of the previous character to avoid three consecutive character occurrences

  • Record the number of previous characters. If the number is greater than the number of current characters, then only one character should be taken this time, making sure that the following character helps the previous character to split, thus ensuring that the length is as long as possible

Time complexity O(n), space complexity O(1).










Stone Games III

















Alice and Bob are playing a game with piles of stones. A row of pebbles, each with a score, is given by the array stoneValue.

Alice and Bob take turns picking pebbles, with Alice always starting first. In each player’s turn, that player can take the first 1, 2, or 3 piles of stones remaining. The game continued until all the stones were removed.

Each player’s final score is the sum of the scores for each pile of stones he has picked up. Each player’s initial score is 0. The goal of the game is to determine the highest score. The player with the highest score will win the game, or the game may end in a tie.

Suppose Alice and Bob both play the optimal strategy. Returns ‘Alice’ if Alice wins, ‘Bob’ if Bob wins, and ‘Tie’ if the score is equal.

Example:
Enter: values = [1,2,3,7]
Output: ‘Bob’
Explanation: Alice always loses, her best option is to take the first three piles and get a 6. But Bob’s score is 7, and Bob wins.








This problem can be solved by dynamic programming. The state dp[I] is defined to represent the maximum difference generated from the selection of subscript I. (Both players adopt the best strategy)

There are three cases for any subscript I:

  • The player only takes the first heap at subscript I, where the difference is stoneValue[I] -dp [I + 1]

  • The player takes the first two heaps at subscript I, where the difference is stoneValue[I] + stoneValue[I + 1] -dp [I + 2]

  • The player takes the first three heaps at subscript I, where the difference is stoneValue[I] + stoneValue[I + 1] + stoneValue[I + 2] -dp [I + 3].

So dp[I] should be the maximum in all three cases.

Since Alice wins first, she can win if dp[0] is greater than zero.

Time complexity O(n), space complexity O(n).










Highlights from the past






  • LeetCode Tour for front End Engineers — Week 182

  • Front End Engineer’s LeetCode Journey — Week 181

  • LeetCode Tour for front End Engineers — Week 180

  • LeetCode Tour for front End Engineers – Week 179

  • LeetCode Tour for Front End Engineers – Week 178

  • JavaScript AC solutions to problems on LeetCode