LeetCode | Learn for Master

Leetcode – Palindrome Permutation

August 6, 2016 Author: david
No comment yet

Given a string, determine if a permutation of the string could form a palindrome.

For example, “code” -> False, “aab” -> True, “carerac” -> True.

Hint:

Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Analysis

A native solution is to generate the permutation of the string, then check whether it is a palindrome.

A better solution is suggested from the above hint.
[Read More...]
LeetCode – Logger Rate Limiter

August 6, 2016 Author: david
No comment yet

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string “foo” at timestamp 1
logger.shouldPrintMessage(1, “foo”); returns true;

// logging string “bar”
[Read More...]
LeetCode – Moving Average from Data Stream

August 6, 2016 Author: david
No comment yet

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Analysis

We can use a bounded queue to record the last n integers in the window, and define a variable sumN to record the sum of the numbers in the window.

Each time when a new number is registered,
[Read More...]
Leetcode – Nim Game

August 6, 2016 Author: david
No comment yet

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1,
[Read More...]
Leetcode – Permutations ( Java)

July 27, 2016 Author: david
No comment yet

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

1
2
3
4
5
6
7
8
9

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Analysis

I will use an example to illustrate how to generate all the permutation of an array.

Given a list [1, 2, 3, 4], all the permutations consists of the four sets:
the permutations starts with 1: {1} + {permutations of array [2, 3, 4]}
the permutations starts with 2,
the permutations starts with 3,
the permutations starts with 4,

Suppose we have a function called search to generate permutations for the subarray nums[start .. end].
[Read More...]
Leetcode – Search for a Range (Java)

July 27, 2016 Author: david
No comment yet

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:

This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array.

For instance, given a sorted array [1,
[Read More...]
Remove Element from an Array (Java)

July 26, 2016 Author: david
No comment yet

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.
[Read More...]
Remove Duplicates from Sorted Array (Java)

July 26, 2016 Author: david
No comment yet

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.
[Read More...]
Leetcode – Remove Nth Node From End of List (Java)

July 26, 2016 Author: david
No comment yet
Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,
```
   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
```
Note:
Given n will always be valid.
Try to do this in one pass.

Analysis:

The key to solve this problem is to use two pointers: pre and cur. The pre pointer moves N steps in the first place,
[Read More...]
Leetcode – Longest common prefix

July 26, 2016 Author: david
No comment yet

Longest common prefix

Write a function to find the longest common prefix string amongst an array of strings.

Pay attention to the corner case: strs can be empty.

Analysis

We define cur to record the char at current round that is recorded by si.

If si equals to the current string’s length, we return the substring from 0 to si.

At the beginning of each round, cur is set as null.

So when cur is null, we know this is the first string to check in current round. We set cur as the letter of the current string at index si

For the following string,
[Read More...]