Palindrome Partitioning (Java)

LeetCode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Recursion

declare start point st, make it move from 0-> s.length(), for each st, check every substring generated by st and i, st+1<=i<=s.length(), if the substring is a palindrome then put it into ArrayList<String>  partition, if st reach s.length() mean we got a valid partition for given string s, then put it into ArrayList<ArrayList<String>> result;

Edit Distance (Java)

LeetCode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Reverse Nodes in k-Group (Java)

LeetCode

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5  




solution to solve this question is easy to come out(just reverse list in 

certain range),however, coding this question elegantly is not a easy task. 

I spend much time on writing this question, but the code is not easy for 

reading. After search Internet, I find an very good version below.  

http://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html

Longest Substring Without Repeating Characters (Java)

Leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Distinct Subsequences (Java)

LeetCode

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Solution: when see question about two strings , DP should be considered first. we can abstract this question to calculate appear times for string T with length i in string S with length j, which can be represented by numbers[i][j], then through observation and thinking , we can know for numbers[i][j] it should at least equal the numbers[i][j-1] and if T.charAt(i)==S.charAt(j) , numbers[i][j] should also be add numbers[i-1][j-1]

Combination Sum II (Java)

LeetCode

Given a collection of candidate numbers (C) and a target number (T), 

find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

Solution: DFS

     Apply DFS continually check every combination, if any one meet the target put it into result arraylist.

Jump Game II (java)

LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Solution: Greedy

At first, I try to solve this problem with DFS, but exceeded the time limitation, then I search the Internet find a very good solution for this question - Greedy Algorithm. the main idea is try to find the longest distance by each jump can reach and check if this distance can pass the total length of this array, of course we should have a variable to keep record of the current steps. if this distance cannot pass the total length of this array, then we should go through all the position within this distance to see if it can pass the array by jumping from there

I think code should be more clear than my description 

Add Two Numbers (Java)

LeetCode

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution: use two references point to the head of each list and add them and carry one by one. 

Sqrt(x) (Java)

Leetcode

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: remember that the sqrt of an number must less than  its half, than we we can apply binary search to find our target. pleas don't forget the overflow risk

First Missing Positive (Java)

LeetCode

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Rotate List (Java)

LeetCode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Solution: when see  an ListNode question, recursion, two pointers  and link head and tail are always common ways to considered about.

In this question, link head and tail is a good choice. First, use an extra reference to go from head to tail meanwhile count the length of this list. once we got the length and the tail , we can do two things, one is linked the tail with head, another is calculate k depend on given n and the length of list, k is how many nodes should be move right. k=len-n%len; After we finished these two things, 

we can place an preHead reference at tail and let it go next k steps, then preHead will be the point just ahead our target head. then return break the list here and return our target head. 

Valid Palindrome (Java)

LeetCode

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.

Solution: Two Pointers 

when you see this question, you should intuitively come out an two pointers solution, however, only alphanumeric characters need be considered depend on the question's description,  so we should use relative elegant way to check the validity of each character. 

Scramble String (Java)

Scramble String

 Total Accepted: 3103 Total Submissions: 15043

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Maximal Rectangle (Java)

LeetCode

Maximal Rectangle

 Total Accepted: 2599 Total Submissions: 12591

Given a 2D binary matrix filled with 0's and 1's,

 find the largest rectangle containing all ones and 

return its area.

Similar question with largest rectangle in histogram but 

more tough.

we can apply a helper table to convert matrix to another

int[][] helper with calculate the current height for 1 at each 

column until current row.

Such as

char[][] matrix       -> int[][] helper

0,0,0,1,0                   0,0,0,1,0

0,1,1,0,1                   0,1,1,0,1

0,1,1,1,0                   0,2,2,1,0

0,0,1,0,1                   0,0,3, 0,1

then we can apply the method used in largest rectangle in

histogram to get max area which used current row as bottom

then keep updating max area.

Copy List with Random Pointer (Java)

LeetCode

Copy List with Random Pointer

Total Accepted: 4935 Total Submissions: 24214

A linked list is given such that each node contains an additional random pointer which could point to

 any node in the list or null.

Return a deep copy of the list.

Similar problem(Clone Graph)

Solution: 

This is an interesting question. Deep copy a single linked list with only next reference is easy. 

but, the tricky point is how to connect the random reference, we can not know if the node connected by the random reference exists or not when we copy node one by one. So to solve this problem, I think hashmap should be a good solution. With hashMap,do first while loop,  we copy every node in given list and keep them as a <originalNode, copiedNode> pair. then do another while loop connect these copied nodes together.

Insert Interval (Java)

[LeetCode]

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

      This question is very similar with merge intervals. because the intervals is initially sorted according to their start times, so what we should do is just go through every interval in intervals list and put the smaller un-overlap interval into result list and updated current newInterval until to the end. But do not forget to add last newInterval into result list. See code below

Implement strStr(). Java

LeetCode

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Sudoku Solver (Java)

LeetCode

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Solution: declare a function called isValid used to check if num from 1->9 will not conflict with nums which were already existed in the board, if it isValid, then recursively  call solved function to check if the board can be finally filled.

Clone Graph (Java)

LeetCode

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

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: DFS traverse all nodes, meanwhile use HashMap to record the node which has been cloned. use label as key and the new created node as value

Merge Intervals (Java)

LeetCode

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

Sort the list base on start valuable in an interval, then a while loop merge every overlap interval.

Restore IP Addresses (Java)

LeetCode

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

DFS to combine each possible result, meanwhile skip all impossible combination for result, such as

rest letters in s can not be more than 3* rest parts and rest letters can not be less than rest parts.

Valid Number ( Java )

LeetCode

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

This is really a trivial question, a lot of corner cases need to be found, just like the Stirng to Integer question.

Largest Rectangle in Histogram (Java)

LeetCode

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution:

similar questions(Longest Valid Parentheses, Maximal Rectangle)

Maintain a stack which used to record bar's indexes, in order to reach max increasing  bars until an shorter bar come,  then we calculate the  area of each situation consist by the bars in our stack. Because there may a coupe bars left in our stack, so don't forget calculate  them after first while loop.