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

---