It's the Xinrui Ma

Blog

Author: admin

322. Coin Change – JavaScript Solution

Posted by in LeetCode on

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

思路:
这个肯定一看就感觉想要用贪心法去做,但是,贪心法做出来是错的。
那么,我们试试DP怎么样?

我们用DP[i]来表示如果总数为I的钱的情况下,使用的最少钱币数, 那么DP[amount]就是我们要求的结果
如果我们能够从DP[0]推出来,DP[1], DP[2] … DP[i]… DP[i + 1], 那就解决了问题

OK, 接下来想想转化公示;
对于coins里面的每一个coin来说,就两种状态,用 还是不用。
不用,那DP[i]就还是DP[i],
用了,那DP[i] = DP[i – coin] + 1

所以我们可以推导出
DP[i] = Math.min(DP[i], DP[i – coin] + 1)

我们对所有的coins都进行这样的遍历,就可以求出来当前的DP[i]的最小值。

我们再对i从0 到amount进行同样的操作,那么我们只要看看最后DP[amount]等于什么就行了

注意最后有可能没有结果 要返回-1, 那么我们就要一个值来标注这个情况下我凑不到这个数,那么什么数你永远凑不到呢?

对于数额为5的面额来说,你最少的硬币数,不可能是6.。。因为最小面额为1,你就是每个都用1毛,那也是5个就完事了。

所以,我们初始化数组的时候,给每个I都赋值I+1,

我们初始条件就很简单喽,DP[0] = 0

Solution:

N-ary Tree Preorder Traversal

Posted by in LeetCode on

Given an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Follow up:

Recursive solution is trivial, could you do it iteratively?

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

 

Constraints:

  • The height of the n-ary tree is less than or equal to 1000
  • The total number of nodes is between [0, 10^4]
Solution 1: Solution 2:

119. Pascal’s Triangle II

Posted by in LeetCode on

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.


In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Solution:

Start to fill the array from end to beginning, that’s the key

result[j] = result[j-1]+result[j]

So j depends on the previous element in the array, if we fill the array from beginning to end, the previous element will be changed, if we start from the end, and result[j] all set to 0 at first except result[0] = 1, result[j]’s value won’t get changed during the loop.

Space complexity is O(k), time complexity is O(n2).

JavaScript:

Number of Lines To Write String

Posted by in LeetCode on

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

 

Example :
Input: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation: 
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
Example :
Input: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation: 
All letters except 'a' have the same length of 10, and 
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.

 

Note:

  • The length of S will be in the range [1, 1000].
  • S will only contain lowercase letters.
  • widths is an array of length 26.
  • widths[i] will be in the range of [2, 10].

Solution:

Longest Palindromic Substring

Posted by in LeetCode on

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution 1:
Use O(N) time complexity and O(1) space complexity to find the palindromic.
Start from the longest possible substring, once it find a match, return that result

Top K Frequent Elements

Posted by in LeetCode on

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Solution: (key idea, sort the hashtable)
1. create a hashtable, key is the number in array, value is how many times they appear in the array.
2. create an array based on the hashtable, sort the array based on the value
3. slice the array to k size
4. generate the result array

Product of Array Except Self

Posted by in LeetCode on

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:
1. Since we can’t use divide, we will calculate two parts, the left product and the right product, separate by the current index i
2. We first calculate the left product , store them to res array. so res[i] means the left product for the current number i. Note: res[0] = 1 ( To future me: Figure this out yourself pls)
3. We can calculate from right side of the array, calculate the right product of the current index i , store them to a variable right;
4. res[i] = res[i] * right;
5. update right = right * nums[i]