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

---

Subsets 2

Problem

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,

---

Idea

把S排序，然后通过判断S[i]!=S[i-1]去掉重复
递归的方法求解.每次插入tmp,就把tmp加到result中.

---

Solution

---

Intersection of Two Linked List

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists: begin to intersect at node c1.
Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

---

Idea

统计两个链表的长度
以短的为基准对齐两个链表的start node
从新的起点开始，两个链表遍历，找第一个相同的元素

---

Solution

---

Longest Common Prefix

Problem

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

---

Idea

找到最小的串，然后判断这个串的每个字符是否在其他串中的相同位置出现.

---

Solution

---

Path Sum 2

Problem

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

---

Idea

DFS

---

Solution

---

Spiral Matrix II

Problem

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

---

Idea

---

Solution

---

Multiply Strings

Problem

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

---

Idea

模拟乘法的过程

---

Solution

---

Count and Say

Problem

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

---

Idea

---

Solution

---

Convert Sorted List to Binary Search Tree

Problem

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

---

Idea

递归的方法解这个题目，注意递归的终止条件，左子树和右子树递归的边界

---

Solution

---

Insert Interval

Problem

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

---

Idea

暴力，先确定newStart的位置，再确定newEnd的位置，然后考虑是否有Overlap和overlap的位置.

---

Solution

---

Unique Paths II

Problem

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[ [0,0,0], [0,1,0], [0,0,0] ]
The total number of unique paths is 2.
Note: m and n will be at most 100.

---

Idea

dp，有点感觉了。dp[i][j]表示到grid[i][j]的unique path的数量. 需要注意的是如果grid[i][j]==1 那么dp[i][j]=0

---

Solution

---

Subsets

Problem

Given a set of distinct integers, S, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:

---

Idea

递归来做就可以，其实对于每一个s[i]来说，只有两个操作，子集包含s[i]和子集不包含s[i].

---

Solution

---

Unique Binary Search Trees II

Problem

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

---

Idea

思路看这里

---

Solution

---

Flatten Binary Tree to Linked List

Problem

Given a binary tree, flatten it to a linked list in-place.

For example,
Given
The flattened tree should look like:

---

Idea

二叉树的先根遍历

---

Solution

---

Spiral Matrix

Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:
You should return [1,2,3,6,9,8,7,4,5].

---

Idea

细节实现题，没什么好办法，就是一圈一圈的往result里压

对于行数m，列数n, 总圈数是(min(n,m)+1) / 2

---

Solution

---

Populating Next Right Pointers in Each Node II

Problem

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, After calling your function, the tree should look like:

---

Idea

用队列来帮助遍历，用NULL来隔断每一层

---

Solution

---

Merge Intervals

Problem

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

---

Idea

先把interval按照start排序，把第一个压入结果result中,遍历后面的如果发现conflict则更新result.back的end，若没有conflict则继续压。

---

Solution

---

Length of Last Word

Problem

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

---

Idea

扫一遍，记录每个word的长度

---

Solution

---

Pascal's Triangle II

Problem

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

---

Idea

这个题目要求memory O(k)。所以只能用1维数组来做。发现row[i] = row[i]+row[i-1] 左边是下一行的row[i]，右边是上一行的row[i]和row[i-1]

---

Solution

---

Combinations

Problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

---

Idea

dfs一次得到一个解.

---

Solution

---

Sum Root to Leaf Numbers

Problem

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.

For example,
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

---

Idea

dfs没啥说的

---

Solution

---

String to Integer (atoi)

Problem

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

---

Idea

Return 0 when input is not valid (Empty or wrong format)

Return LONG_MAX when input string overflows

Return LONG_MIN when input string underflows

Input String is allowed to have additional character after a valid substring that can form a long number. (e.g. +123+)

Input can have many whitespaces before the first non-whitespace character. (e.g. " 123")

---

Solution

---

ZigZag Conversion

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

---

Idea

先处理第一行，再处理中间行，然后处理最后一行。中间行的规律在这里

---

Solution

---

Path Sum

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

---

Idea

dfs遍历每条路径. 注意: 节点可以是负数。 只有到了叶子的时候才判断长度是否为sum

---

Solution

---

Distinct Subsequences

Problem

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.

---

Idea

动态规划，跪了。
动态规划，设dp[i][j]是从字符串S[0...i]中删除几个字符得到字符串T[0...j]的不同的删除方法种类，有上面递归的分析可知，动态规划方程如下

如果S[i] = T[j], dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

如果S[i] 不等于 T[j], dp[i][j] = dp[i-1][j]

初始条件：当T为空字符串时，从任意的S删除几个字符得到T的方法为1

---

Solution

---

Implement strStr()

Problem

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

---

Idea

暴力暴力

---

Solution

---

Minimum Path Sum

Problem

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

---

Idea

DP. 注意初始化的值

---

Solution

---

N-Queens ||

Problem

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

---

Idea

---

Solution

---

Clone Graph

Problem

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.

---

Idea

dfs用在给新的node加neighbor的时候. 定义map来判断这个node是不是已经被copye过了.

---

Solution

---

Edit Distance

Problem

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

---

Idea

设状态为 f[i][j],表示 A[0,i] 和 B[0,j] 之间的最小编辑距离。设 A[0,i] 的形式是 str1c,B[0,j] 的形式是 str2d,

• 如果 c==d,则 f[i][j]=f[i-1][j-1];
• 如果 c!=d,
• 如果将 c 替换成 d,则 f[i][j]=f[i-1][j-1]+1;
• 如果在 c 后面添加一个 d,则 f[i][j]=f[i][j-1]+1; // 这里为什么是f[i][j-1]，因为f[i][j]表示的是a[0,i],b[0,i]之间最小距离，若选择添加一个d,那么这个操作的上一步的数组应该是a[0,i],b[0,i-1]，a是不能动的，因为a[i]还没匹配呢.
• 如果将 c 删除,则 f[i][j]=f[i-1][j]+1; 若删除c，则是b[j]不动，因为还没匹配.

---

Solution

---

Anagrams

Problem

Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.

---

Idea

Anagram(回文构词法)是指打乱字母顺序从而得到新的单词,比如 "dormitory" 打乱字母顺序会变成 "dirty room" ,"tea" 会变成"eat"。
回文构词法有一个特点:单词里的字母的种类和数目没有改变,只是改变了字母的排列顺序。因此,将几个单词按照字母顺序排序后,若它们相等,则它们属于同一组 anagrams 。

unordered_map 使用总结

---

Solution

---

Generate Parentheses

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

---

Idea

dfs暴力搜索，解的长度为2n，当找到2n长的一个solution后判断其是否valid

---

Solution

---

Morris 二叉数遍历

Idea

空间复杂度O(1), 遍历二叉数,参考这里

---

Solution

---

Recover Binary Search Tree

Problem

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

---

Idea

把BST树转入数组，然后从前往后扫数组，找到第一个顺序不对的数，然后从后往前扫，找到第二个顺序不对的。交换两个的val就ok了.

---

Solution

---

Permutations

Problem

Given a collection of 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], and [3,2,1].

---

Idea

dfs, 依次处理num[]的每一个,递归的时候先检查num[i]是不是已经出现过了，如果没有然后插入.

How to find an element in vector

---

Solution

---

Pascal's Triangle

Problem

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

---

Idea

从第3行开始，对于每一行，第一个是1，最后一个是1，其他的 a[i][j] = a[i-1][j-1]+a[i-1][j];

---

Solution

---

Binary Tree Postorder Traversal

Problem

Given a binary tree, return the postorder traversal of its nodes' values. For example:

---

Idea

使用stack实现，压栈时先压右子树再压左子树，只有找到叶子节点时才弹栈，压栈的时候注意把curNode与左右子树分开，这样才能保证从树底返回树顶。

---

Solution

---

N-Queens

Problem

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

---

Idea

合法的queue放置

当前放置位置的同一行、同一列、两条对角线上都不存在皇后

数组state[i]记录第i行皇后在哪一列

判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等；

判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1-row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置

---

Solution

---

Letter Combinations of a Phone Number

Problem

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

---

Idea

dfs暴力搜索，注意递归的参数设置。

---

Solution

---

Unique Paths

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

---

Idea

DP的思路解, a[i][j]表示在第i,j个方格时有多少中情况,第0行和第0列全都设成0, a[1][1]=1 以后每项a[i][j] = a[i-1][j]+a[i][j-1]

---

Solution

---

Symmetric Tree

Problem

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

For example, this binary tree is symmetric:
But the following is not:

---

Idea

dfs， 对于每个iteration, 两个pointer分别遍历right_sub和left_sub。 然后比较。

---

Solution

---

Validate Binary Search Tree

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

---

Idea

这个题一定要注意，判断bst并不是只检查以下当前节点和其左右子树是否正确。 应该确保每个节点都不大于当前子树的最大值和最小值。举个例子

---

Solution

---

Roman to Integer

Problem

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

---

Idea

一定要注意好radix和symbol两个数组的顺序，依次遍历s，把找到的子串删掉，然后继续，并更新result.

---

Solution

---

Construct Binary Tree from Inorder and Postorder Traversal

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

---

Idea

和之前那个inorder和preorder建树的思路一样，在preorder里找根，在inorder里找左子树右子树.

---

Solution

---

Balanced Binary Tree

Problem

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

---

Idea

深度优先遍历，得到每个点的左子树和右子树高度，然后比较。

---

Solution

---

Construct Binary Tree from Preorder and Inorder Traversal

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

---

Idea

Preorder那个数组找到根，inorder那个数组找到根的位置，然后左边为左子树，右边为右子树。

---

Solution

---

Convert Sorted Array to Binary Search Tree

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

---

Idea

就是二分法.找到num的中间元素, 然后二分去build左子树与右子树

---

Solution

---

Combination Sum

Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

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 2,3,6,7 and target 7,

A solution set is:
[7]
[2, 2, 3]

---

Idea

本质上是DFS，查找所有可行解的范围

To search for all combination, we use a backtracking algorithm. Here, we use the above example of candidate={2,3,6,7} and target=7.

First, we start with a sum of 0. Then, we iterate over all possibilities that can be added to sum, which yields the possible set of sum={2,3,6,7}. Assume now that sum=2, we continue adding all possible candidate numbers {2,3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an array to keep track of all the indices of candidate numbers that add to the current sum, so that we can print the combination later. The next case would be sum=3. We look at all possible candidate numbers {3,6,7} to be added to sum=3, which yields sum={6,9,10}. Note that there is no need to look backward (ie, candidate numbers that are smaller than 3), as this would only yield duplicate results. We keep doing this recursively, until we reach the conditions below, where we stop.

---

Solution

---