Maximum Product Subarray

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6

---

Idea

---

Solution

---

Excel Sheet Column Number

Problem

Given a column title as appear in an Excel sheet, return its corresponding column number.

---

Idea

---

Solution

---

Excel Sheet Column Title

Problem

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:

---

Idea

这个题目的难点是z为26，且没有0

---

Solution

---

Majority Element

Problem

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

You may assume that the array is non-empty and the majority element always exist in the array.

---

Idea

hash map 解决这个问题. 别忘记考虑只有1个元素的情况

---

Solution

---

Compare Version Numbers

Problem

Compare two version numbers version1 and version1.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

---

Idea

先把小数点左边的算出来，比较大小，再把小数点右边的算出来，比较大小

---

Solution

---

Restore IP Addresses

Problem

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)

---

Idea

---

Solution

---

Word Break

Problem

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

---

Idea

---

Solution

---

Longest Palindromic Substring

Problem

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.

---

Idea

---

Solution

---

Scramble String

Problem

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":
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".
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".
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.

---

Idea

如果两个string：s1和s2可以满足在某一个位置i,满足以下任意一种情况：
1. s1[0-i]和s2[0-i]相等或者互为scramble, 且s1[i+1, n]和s2[i+1,n]相等或互为scramble
2. s1[0-i]和s2[n-i, n]相等或者互为scramble， 且s1[i+1,n]和s2[0, n-i-1]相等或互为scramble

---

Solution

---

Find Minimum in Rotated Array2

Problem

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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).

Find the minimum element.
The array may contain duplicates.

---

Idea

---

Solution

---

Word Ladder

Problem

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

---

Idea

---

Solution

---

Min Stack

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

---

Idea

两个stack,一个用来存最小的stack,一个用来存正常的stack

---

Solution

---

Binary Tree Zigzag Level Order Traversal

Problem

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:

---

Idea

用两个栈实现,依次往s1,s2插入，一个先插左子树再右子树，一个先插右子树再左子树，最后就能得到zigzag的遍历效果

---

Solution

---

Permutation ||

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

---

Idea

---

Solution

---

Palindrome Number

Idea

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

---

Idea

假设负数不是palindrome. 思路是截取最左边和最右边的两个digit比较，直到比较所有digit
每次比较之后用x = (x%d)/10 把左右两边的digit去掉

---

Solution

---

Find Peak Element

Problem

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.

---

Idea

peak 一定在这样的一个[left,right]区间内, num[left] > num[left - 1] 且 num[right] > num[right + 1]
下面看一下如何update left和right.
mid = (left+right)/2

---

Solution

---

Find Minimum in Rotated Sorted Array

Problem

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).
Find the minimum element.
You may assume no duplicate exists in the array.

---

Idea

用二分查找[left,right], 每次二分的那个点pivot，一定会把数组分成一个有序的和一个无序的，最小值永远都在无序的那个里

---

Solution

---

Combination Sum ||

Problem

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]

---

Idea

剪枝+dfs

---

Solution

---

Palindrome Partition

Problem

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

---

Idea

首先对字符串的所有子串判断是否是回文，设f[i][j] = true表示以i为起点，长度为j的子串是回文,等于false表示不是回文，那么求f[i][j]的动态规划方程如下：

当j = 1，f[i][j] = true;
当j = 2，f[i][j] = (s[i]==s[i+1]),其中s是输入字符串
当j > 2, f[i][j] = f[i+1][j-2] && (s[i] == s[i+j-1])（即判断s[m..n]是否是回文时：只要s[m+1...n-1]是回文并且s[m] = s[n]，那么它就是回文，否则不是回文）

---

Solution

---

Valid Palindrome

Problem

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.

---

Idea

考虑大小写转化，以及数字的case例如: A2a,和 1a3

---

Solution

---

Word Search

Problem

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

---

Idea

DFS, 一次搜索上下左右,注意不能重复

---

Solution

---

Regular Expression Matching

Problem

Implement regular expression matching with support for '.' and '*'.

---

Idea

思路

---

Solution

---

Simplify Path

Problem

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

---

Idea

---

Solution

---