It's the Xinrui Ma

Blog

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]

Add Two Numbers from linked list

Posted by in LeetCode on

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:
Easy, but need to watch out for the last carry;

merge two sorted linked list Iteratively and Recursively

Posted by in LeetCode on

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Recursively:

Iteratively: