The sum incrementally minimizes the positive numbers

















Give you an integer array nums. You can pick any positive startValue as the initial value.



You need to traverse the NUMS array from left to right and append the startValues to the values in the NUMS array.



Select a minimum positive number as startValue, while ensuring that the sum is always greater than or equal to 1.



Example:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you select startValue = 4, on the third summation, the sum is less than 1.
Cumulative sum
startValue = 4 | startValue = 5 | nums
(4-3) = 1 | | (5-3) = 2-3
(1 + 2) = 3 | | 2 (2 + 2) = 4
(3-3) = 0 | | (4-3) = 1-3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2








To solve this problem, we need to grasp the following two conditions:

  • Make sure the current value is greater than or equal to 1 during the summation

  • The end result should be a positive integer

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










And the minimum number of Fibonacci numbers for K

















Given the number k, return the minimum number of Fibonacci numbers that sum to k, where each Fibonacci number can be used multiple times.
Fibonacci numbers are defined as:



F1 = 1
F2 = 1
Fn = fn-1 + fn-2, where n > 2.
The data guarantees that for a given k, a feasible solution can be found.



Example:
Enter k = 7
Output: 2
Explanation: Fibonacci numbers are: 1,1,2,3,5,8,13
For k = 7, you get 2 plus 5 is equal to 7








Step 1: Calculate Fibonacci numbers not greater than k.

Step 2: Using greedy strategy, choose the largest Fibonacci number first.

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










A happy string of length N

















A happy string is defined as:



Contains only lowercase letters [‘a’, ‘b’, ‘c’].
For all I between 1 and S. length-1, such that s[I]! = s[I + 1] (string subscripts start at 1).
For example, the strings’ ABC ‘, ‘ac’, ‘b’ and ‘abcbabCBcb’ are happy strings, but ‘aa’, ‘baa’ and ‘ababbc’ are not happy strings.



Given two integers n and k, you need to sort all happy strings of length n lexicographically.



Return the KTH sorted happy string, or an empty string if there are less than k happy strings of length n.



Example:
Input: n = 1, k = 3
Output: ‘c’
Explanation: The list [‘a’, ‘b’, ‘c’] contains all happy strings of length 1. The third string in lexicographical order is ‘c’.








In this problem, the range of n is [1, 10], so it is perfectly possible to BFS all cases in lexicographical order.

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










Return an array

















A program is supposed to output an array of integers. But the program forgot to print Spaces and instead printed a numeric string. All we know is that all integers in the array are between [1, k], and none of the numbers in the array has a leading 0.



I give you the string S and the integer k. There may be many different array restoration results.



Following the above procedure, return the number of array schemes that could output the string s.



Since the number of array schemes can be large, return the result of mod 10^9 + 7.



Example:
Enter: s = ‘1000’, k = 10000
Output: 1.
Explanation: Number of possible solutions [1000]








This problem uses dynamic programming to solve.

Define state: dp[I] represents the number of schemes that can be printed from I to n (end of string).

State transition equation: dp[I] = DP [I + 1] + DP [I + 2]… + dp[I + j] (I + j <= n).

For any DP [I + j], the following two conditions need to be satisfied:

  • S [I] is not zero

  • ParseInt (s[I, j]) is not greater than k

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










Highlights from the past






  • LeetCode Tour for front End Engineers — Night Meow 23

  • LeetCode Tour for front End Engineers – Night Meow 22

  • LeetCode Tour for front End Engineers — Night Meow 21

  • LeetCode Tour for front End Engineers — Night Meow 20

  • JavaScript AC solutions to problems on LeetCode