[LeetCode] Longest Palindromic Substring

Link : Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analysis:

First thought is brute force. For every kind selection of start point and end point, there are totally O(N*N) and each palindrome recognition is O(N). And total time complexity is O(N^3). Test proved it's too slow.

Second try. Because Palindrome has special property, symmetric. If a long string is a Palindrome, the sub-string in its center has to be a sub-string. Or in another way, if its sub-string in the middle is not a palindrome, the large one cannot be, thus avoiding a lot of unnecessary comparison.

[LeetCode] Longest Consecutive Sequence

Link : Longest Consecutive Sequence 

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.

[LeetCode] Valid Palindrome

Link : Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

[LeetCode] Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Analysis:

Get lines passing every two, and compare.

If we get all of them n*(n-1)/2, then we still need compare them all. that will be O(n^4).

By using map, and round function, we need to check just the lines with the same property.

But to store a line, at least two property are needed, either two points, or slope and intersect. And compare them is still boring and time consuming. we could use nested map, but we try to avoid that.

what about calculating all line passing by the same point, store those lines' slope in map and check for only once.O(n) for each node. And O(n^2) totally. Not a bad idea. Let's try it.

[LeetCode] Gray Code

Link : Gray Code

Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given n, a gray code sequence is not uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

[LeetCode] Clone Graph

Link : Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. OJ's undirected graph serialization: Nodes are labeled uniquely. We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}. The graph has a total of three nodes, and therefore contains three parts as separated by #. First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

[LeetCode] Insertion Sort List

Link : Insertion Sort List

Sort a linked list using insertion sort.

Analysis:
Quite straight-forward, create a new linked list header,
a) get a list node in original list,
b) find the place to insert it
c) and insert it

Code says!

[LeetCode] LRU Cache

Link : LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[LeetCode] Trapping Rain Water

Link : Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

[LeetCode] Valid Parentheses

Link : Valid Parentheses

Analysis:
At first, I try to count number of each kind of parentheses in a variable, when meeting left part, increase by 1, and when meeting paired right part, decrease by 1.  If any variable below 0, return false. And if any count is not equal to 0, it is not a valid-parentheses string.

But the problem is the order of occurrence of different kind of parentheses. Counting only makes sure right part doesn't appear before left part, but cannot guarantee ([)] will return false.

I refer to http://blog.unieagle.net/2012/11/06/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Avalid-parentheses/.

[LeetCode] Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.
For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Hi GEEKs, bored with LeetCode? Look at this!

The beauty of combination, Math & Algorithm

http://projecteuler.net/

[LeetCode] Search in Rotated Sorted Array II

Link : Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

[LeetCode] Search in Rotated Sorted Array

Link : Search in Rotated Sorted Array

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