It's the Xinrui Ma

Blog

Tag: Array

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:

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]

11. Container With Most Water

Posted by in LeetCode on

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

We can start from the most width to least width:

Brute Force Solution:

Better Two Pointer Solutio: (Start from the longest width, then move the short line pointer inner towards higher line):

88. Merge Sorted Array

Posted by in LeetCode on

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Hint: IWhat if you fill the longer array from the end instead of start?

Given two strings s and t, write a function to determine if t is an anagram of s

Posted by in LeetCode on

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Solution in Java:

Majority Element: Answers in Java & JavaScript

Posted by in LeetCode on

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution one using Hashtable in Java:

Since the element which appears for more than n/2 times in the array, it should always appear at the middle of a sorted one. After we sort it, simply return the number in the middle will solve the problem.

Two Sum

Posted by in LeetCode on

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution in Java, version 1:
Time complexity in worst case: O(n^2).

Better Solution in Java, using HashTable.

Time complexity depends on the put and get operations of HashMap which is normally O(1).

Time complexity of this solution is O(n).

LeeCode: Summary Ranges answer in JavaScript and Java

Posted by in LeetCode on

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

LeeCode: contains any duplicates in Java and JavaScript

Posted by in LeetCode on

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Soluton in JavaScript:

Solution in Java Using HashTable: