LeetCode – Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Analysis

This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array. 

Leetcode: Remove Duplicates from Sorted Array

Given a sorted array, 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 in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

 Analysis
 

We defined two indexes: pre and cur.

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

　　(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

　　You are given a target value to search. If found in the array return its index, otherwise return -1.

　　You may assume no duplicate exists in the array.

Using the idea of binary search, we can reduce the search space based on which range the target value is located. 

We first get the mid index of the array,

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

How many different ways do you know to solve this problem?

Analysis

It is easy to use an intermediate array to solve this problem. Suppose the original array is A, the new array is B, we will copy 

A[0:n-k -1] to B[k:n-1], and A[n – k:n-1] to B[0:k – 1], then we copy all the elements in B back to Array A using System.arrayCopy.

[LeetCode] Evaluate Reverse Polish Notation (RPN)
 Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

Analysis

Evaluate RPN is the second step to build a calculator. Once we have converted the infix expression into the RPN,  we need to evaluate RPN to get the result. 

The basic idea to evaluate reverse polish notation is to use a stack to process the strings.

We scan the array of the RPN expression.

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

 Analysis
This problem can be easily solved using a recursive algorithm.  We defined a method with the following signature:
 
equal(left, right)

then we recursively call equal(left.left, right.right) and equal(left.right, right.left). 

The method returns false as long as only one of the two nodes is null,

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see thek numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Shuffle a set of numbers without duplicates.

Example:

 
Java Solution
 

Shortest Word Distance I

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

Note

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Analysis

We can scan the list and use two pointers to record the most recent indexes of the two words.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as “[1,2,3,null,null,4,5]”,