LeetCode Array

[zxw018018]

LeetCode Array

Array

1. Initialize

int[] a0 = new int[5];
int[] a1 = {1, 2, 3};

2. Get Length

a1.length

3. Access Element

a1[0]

4. Iterate all Elements

for (int i = 0; i < a1.length; ++i) {
    System.out.print(" " + a1[i]);
}
for (int item: a1) {
    System.out.print(" " + item);
}

5. Modify Element

a1[0] = 4;

6. Sort

Arrays.sort(a1);

Dynamic Array

1. initialize

List<Integer> v0 = new ArrayList<>();
List<Integer> v1;     // v1 == null

2. cast an array to a vector

Integer[] a = {0, 1, 2, 3, 4};
v1 = new ArrayList<>(Arrays.asList(a));

3. make a copy

List<Integer> v2 = v1;                      // another reference to v1
List<Integer> v3 = new ArrayList<>(v1);     // make an actual copy of v1

4. get length

v1.size()

5. access element

v1.get(0)

6. modify element

v2.set(0, 5);       // modify v2 will actually modify v1

7. sort

Collections.sort(v1);

8. add new element at the end of the vector

v1.add(-1);
v1.add(1, 6);

9. delete the last element

v1.remove(v1.size() - 1);

Problems

26. Remove Duplicates from Sorted Array

Description

• Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
• Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Analysis

• Use two pointers

27. Remove Element

Description

• Given nums = [0,1,2,2,3,0,4,2], val = 2,
• Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
• Note that the order of those five elements can be arbitrary.
• It doesn't matter what values are set beyond the returned length.

Analysis

• Use two pointers

54. Spiral Matrix

Description

• Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Analysis

• Solve it layer by layer
  
  time O(n), space O(n)

66. Plus One

Description

Given a number represented as an array of digits, plus one to the number.

Analysis

• System.arraycopy()

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

70. Climbing Stairs

Description

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Analysis

• It is a Fibonacci sequence. f(n)=f(n-1)+f(n-2)
• Iteration O(n)
• Fibonacci Formula O(1)

final double s = Math.sqrt(5);
return (int)Math.floor((Math.pow((1+s)/2, n+1) + Math.pow((1-s)/2, n+1))/s + 0.5);

73. Set Matrix Zeroes

Description

Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Analysis

• space O(m+n) Set two boolean arrays. One represents row, and the other one represents column.
  Arrays.fill
• space O(1) Reuse the first row and the first column

80. Remove Duplicates from Sorted Array II

Description

• Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
• Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Analysis

• Just need to skip one item during every iteration.

118. Pascal's Triangle

Description

• Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
  

Analysis

time O(n^2), space O(n^2)

119. Pascal's Triangle II

Description

• 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.

Analysis

• Through each iteration, add 1 to the front of the arrayList.
  time O(n^2), space O(n)

134. Gas Station

Description

• There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
  You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
  Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
  Note: The solution is guaranteed to be unique.

Analysis

• Set two variables. sum is to check the validity of current pointer, and total is to check the validity of whole array.

135. Candy

Description

• There are N children standing in a line. Each child is assigned a rating value.
• You are giving candies to these children subjected to the following requirements:
  Each child must have at least one candy.
  Children with a higher rating get more candies than their neighbors.
• What is the minimum candies you must give?

Analysis

• recursion
  time O(n), space O(n)

167. Two Sum II - Input array is sorted

Description

• Given an array of integers that is already sorted in ascending order, 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.

Analysis

• Use two pointer, one from the beginning and the other from the end
  time O(n), space O(1)

169. Majority Element

Description

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

Analysis

• Arrays.sort()
• The middle one is the majority element

189. Rotate Array

Description

• Rotate an array of n elements to the right by k steps.
• For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Analysis

• Reverse left n-k items and right k items.
• Then reverse all items.

209. Minimum Size Subarray Sum

Description

• Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Analysis

• Use two pointers. One iterates through the array and the other one store the left index.
  time O(n), space O(1)

217. Contains Duplicate

Description

• 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.

Analysis

• Use HashSet, add items into it. If fails, return true.
  time O(n), space O(n)
• Sort first, check if adjacent items are the same.
  time O(nlogn), space O(1)

283. Move Zeroes

Description

• Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Analysis

• Same as move elements. Just set the remaining to 0.

485. Max Consecutive Ones

Description

• Given a binary array, find the maximum number of consecutive 1s in this array.

Analysis

• Use two pointers

498. Diagonal Traverse

Description

• Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Analysis

• row + column is even, move up
  rightmost, move down
  upmost, move right
• row + column is odd, move down
  downmost, move right
  leftmost, move down

561. Array Partition I

Description

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Analysis

• Sort and add pairs
  time O(nlogn), space O(1)

724. Find Pivot Index

Description

• Given an array of integers nums, write a method that returns the "pivot" index of this array.
• We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.
• If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Analysis

• Calculate sum and leftSum
• If leftSum == sum - leftSum - nums[i], that is the pivot
  time O(n), space O(1)

747. Largest Number At Least Twice of Others

Description

• In a given integer array nums, there is always exactly one largest element.
• Find whether the largest element in the array is at least twice as much as every other number in the array.
• If it is, return the index of the largest element, otherwise return -1.

Analysis

• Find maxIndex of the array
• If exists 2 * nums[i] > nums[maxIndex], return -1