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

---

Integer to Roman

Problem

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

---

Idea

定义好radix和symbol很重要

---

Solution

---

Populating Next Right Pointers in Each Node

Problem

Too long. Check the 传送们:

---

Idea

完全binary tree节点数n和层数h的关系

n = 2^(h)-1;     （h从1开始）

先把每一层的最右边的next = NULL设置好，然后遍历每一层，起点是每层最左边的点，遍历每个点，把这个点下面的左孩子和右孩子连起来，然后再遍历一次，把不是同一个parent的两个相邻点连起来

---

Solution

---

Binary Tree Inorder Traversal

Problem

Given a binary tree, return the inorder traversal of its nodes' values.

For example:

---

Idea

Use stack. Push left child to stack ＆nbsp > ＆nbsp push_back(parent->val) to result ＆nbsp > ＆nbsp push right child to stack.

---

Solution

---

Binary Tree Level Order Traversal II

Problem

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

---

Idea

做法与binary tree level order traversal 类似。不同的地方是别忘记把结果倒过来.

---

Solution

---

Binary Tree Preorder Traversal

Problem

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
  1
   \
    2
   /
  3
return [1,2,3].

---

Idea

stack 实现根 左 右。

---

Solution

---

Best Time to Buy and Sell Stock 3

Problem

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Idea

---

Solution

---

Binary Tree Level Order Traversal

Problem

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

---

Idea

BFS can solve this problem.

---

Note

C++ queue

Solution

---

Unique Binary Search Tree

Problem

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

---

Idea

如果把上例的顺序改一下,就可以看出规律了。

比如,以 1 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 0 个元素的树, 右子树是 2 个元素的树。以 2 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 1 个元素的树,右子树也是 1 个元素的树。依此类推。
当数组为 1, 2, 3, ..., n 时,基于以下原则的构建的 BST 树具有唯一性:以 i 为根节点的树,其左 子树由 [1, i-1] 构成,其右子树由 [i+1, n] 构成。

定义 f (i) 为以 [1, i] 能产生的 Unique Binary Search Tree 的数目,

则 如果数组为空,毫无疑问,只有一种 BST,即空树,f(0) = 1。 如果数组仅有一个元素 1,只有一种 BST,单个节点,f(1) = 1。 如果数组有两个元素 1,2,那么有如下两种可能 f(2) = f(0) ∗ f(1) ,1 为根的情况 + f(1) ∗ f(0) ,2 为根的情况

再看一看 3 个元素的数组,可以发现 BST 的取值方式如下:
f(3) = f(0)*f(2), 1为根的情况
+ f(1) ∗ f(1) ,2 为根的情况
+ f(2) ∗ f(0) ,3 为根的情况
所以,由此观察,可以得出 f 的递推公式为
f(i) = sum(f(k − 1) × f(i − k)) k: from 1 to i

---

Solution

---

Add Binary

Problem

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

---

Idea

---

Note

Convert char to int

Convert int to string

---

Solution

---

Minimum Depth of Binary Tree

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

---

Idea

DFS 遍历树， 方法是用栈，压入root,1。 然后每次都先弹出然后压入其left和right。

---

Note

如何制作一个pair压入栈中

---

Solution

---

Maximal Rectangle

Problem

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

---

Idea

已被折磨疯了，给两个链接参考
http://www.xiaoyingedu.com/report?pid=74
http://www.cnblogs.com/TenosDoIt/p/3454877.html
思路是先用dp解出每一行最长连续点的数量，然后基于这个结果用O(n^3)的方法解，从(i,j)出发每个小矩形的面积

---

Solution

---

Palindrome Partition 2

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

---

Idea

给这个题跪的妥妥的. 感谢水中的鱼，下面是思路
凡是求最优解的，一般都是走DP的路线。这一题也不例外。首先求dp函数，
定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度
此时 D[i,n] = min(D[i, j] + D[j+1,n]) i<=j< n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] ) i<=j
有个转移函数之后，一个问题出现了，就是如何判断[i,j]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
P[i][j] = true if [i,j]为回文

那么
P[i][j] = str[i] == str[j] && P[i+1][j-1];

---

Solution

---

Maximum Subarray

Problem

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

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

---

Idea

当我们从头到尾遍历这个数组的时候,对于数组里的一个整数,它有几种选择呢?它只有两种
选择:1、加入之前的 SubArray;2. 自己另起一个 SubArray。那什么时候会出现这两种情况呢?

如果之前 SubArray 的总体和大于 0 的话,我们认为其对后续结果是有贡献的。这种情况下我们选择加入之前的 SubArray

如果之前 SubArray 的总体和为 0 或者小于 0 的话,我们认为其对后续结果是没有贡献,甚至是有害的(小于 0 时)。这种情况下我们选择以这个数字开始,另起一个 SubArray.

设状态为 f[j],表示以 S[j] 结尾的最大连续子序列和,则状态转移方程如下:

f [j] = max {f [j − 1] + S[j], S[j]} , 其中1 ≤ j ≤ n

target = max {f [j]} , 其中1 ≤ j ≤ n

---

Solution

---

Triangle

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

---

Idea

从下往上扫描, 递推公式: f(x,y) = min(f(x+1,y+1), f(x+1,y))+ triangle[x][y]
f(x,y)表示从底到点(x,y)的最短路长.

---

Solution

---

Container with Most Water

Problem

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

---

Idea

这个题和算矩阵面积那个不同，这个一旦有短板，则围城的面积一定小于没有短板的。
另外那个水槽的题则是求能呈水的总量

---

Solution

---

Longest Substring Without Repeating Characters

Problem

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.

---

Idea

用个数组pos[]记录每个字符上次出现的位置，然后用start记录子串的起始，当pos[s[i]] >= start时表明重复，则计算长度，知道最后一个子串
输入数据可能存在除了英文字母以外的数据

---

Solution

---

Best Time to Buy and Sell Stock ii

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

---

Idea

相邻两个价格差一下，然后把》0的加起来。为啥？ 因为如果第二天价格低了，第二天再买就肯定能达到最大profit，所以第一天就不要了

---

Solution

---

Best Time to Buy and Sell Stock

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

---

Idea

用一个变量minVal记录当前最小的value, profit记录当前最大的差价。 遍历整个List, 对于每一个prices[i]比较 profit和pricesp[i]-minVal谁大。 并更新minVal和profit.

---

Solution

---

Jump Game 2

Problem

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

---

Idea

不太好理解，见代码。 大体思路是对于每一个能找到的最大区间，继续寻找在区间内能走到的最远距离.

---

Solution

---

Jump Game

Problem

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.
Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

---

Idea

设状态为 f[i],表示从第 0 层出发,走到 A[i] 时剩余的最大步数,则状态转移方程为:
f [i] = max(f [i − 1], A[i − 1]) − 1, i > 0

---

Solution

---

Sqrt(x)

Problem

Implement int sqrt(int x).
Compute and return the square root of x.

---

Idea

二分查找，注意溢出，注意结束的时候返回值

---

Solution

---

Pow(x,y)

Problem

Implement pow(x, n).

---

Idea

递归，每次计算n/2次方.注意:

n可能为负数

n可能为奇数或者偶数

---

Solution

---

Search 2D Matrix

Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
Given target = 3, return true.

---

Idea

用二分查找来做

mid = first+(last-first)/2

midMatrix = matrix[mid/column][mid%column]

---

Solution

---

Search Insert Position

Problem

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

---

Idea

None

---

Solution

---

Search for a Range

Problem

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

---

Idea

search lower bound from left->right; then search upper bound from right->left

当ector里没有元素时不能通过数组来赋值

---

Solution

---

First Missing Positive

Problem

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.

---

Idea

首先确定最后的missing positive一定是 在[1...n-1]之间

用A[i]记录i+1， 因为0不算正数

对于每一个A[i]， 如果不等于i+1,则和A[A[i]-1]换位置。

最后遍历一遍，找不是i+1的。

---

Solution

---

Sort List

Problem

Sort a linked list in O(n log n) time using constant space complexity.

---

Idea

Use merge sort ideas to solve. Use two pointer to find the mid position of list. And sort the left and right recursively. Then merge them together.

---

Solution

---

Sort Colors

Problem

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

---

Idea

两个Index,一个指向红色的最后一个(redIndex)， 一个指向蓝色的第一个(blueIndex)， 两个指针分别从两端起始

对于每个A[i] 若A[i]是红色则把他与A[redIndex] 交换并且i 和 redIndex加一

若A[i]是蓝色则把他与A[blueIndex]交换，但是只减blueIndex，i不变。

白色的话则只i++

---

Solution

---

Insertion Sort List

Problem

Sort a linked list using insertion sort.

---

Idea

对于每一个node， 从头便利找到插入的位置r，然后把node插到r

---

Solution

---

Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

---

Idea

如果使用merge 2 sorted lists的方法会TLE，所以这次需要使用堆这个数据结构, 设有k个list, 堆的size O(k)， 每次把所有lists的最小元素放入堆中，然后每次取出最小的元素，并把取出元素的下一个放入堆中。当所有元素都取完，则得到结果。

---

Note

C++中如何使用Heap

只有run一次 pop_head()， 那个堆顶的元素才会被放到back中去。

STL 重载的方法

---

Solution

---

Merge Two Sorted Lists

Problem

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

---

Idea

弄个新指针，然后把l1和l2中最小的节点挂在新指针后面

---

Solution

---

Merge Sorted Array

Problem

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

---

Idea

从A的m+n-1开始分配，A,B也分别指向最高位，把大的放到A里

---

Note

访问数组的优先级高于++

---

Solution

---

Evaluate Reverse Polish Notation

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

---

Idea

用stack来解，维护这个栈存储所有的number，如果碰到了操作符"+","-","*","/"则弹出两个栈里的数分别做右操作数和左操作数，然后把计算结果再压栈

---

Note

Convert string to int

Convert int to string

You cann't do switch-case statement on string by C++

Solution

---

Largest Rectangle in Histogram

Problem

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.

---

Idea

用一个stack来维护递增的bar的位置，碰到了小于栈顶的bar，则弹栈然后计算面积

• Create an empty stack.
• Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
• If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
• If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
• If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

---

Solution

---

Longest Valid Parentheses

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

---

Idea

一个stack记录所有没有匹配的{的位置

lastPos 记录上个}的位置.

碰到{就把位置插到stack，碰到}就先Pop,然后看看stack是否空，如果空则表示1个{对应1个},则length = i-lastPos。 如果stack不空,则length = i-lefts.top()

---

Solution

---

Valid Parentheses

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

---

Idea

依次检查string的每个字符，如果是（，{,[则压入堆栈，如果是),{,]则弹出栈顶元素，并检查是否匹配。

---

Note

如何遍历string里每个元素

string里的find

c++ Stack 用法

---

Solution

---

Reorder List

Problem

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→...

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

---

Idea

把链表拆开，然后后半截reverse，然后重新组合

---

Solution

---

Linked List Cycle ||

Problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

---

Idea

当 fast 与 slow 相遇时,slow 肯定没有遍历完链表,而 fast 已经在环内循环了 n 圈 (1 ≤ n)。假设 slow 走了 s 步,则 fast 走了 2s 步(fast 步数还等于 s 加上在环上多转的 n 圈),设环长为 r,则:
2s = s + nr
s = nr

设整个链表长 L,环入口点与相遇点距离为 a,起点到环入口点的距离为 x,则
x+a = nr = (n–1)r + r = (n − 1)r + L − x
x = (n − 1)r + (L–x–a)
L–x–a 为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于 n − 1 圈内环 + 相遇点到环入口点,于是我们可以从 head 开始另设一个指针 slow2,两个慢指针每次前进一步,它俩一定会在环入口点相遇。

---

Solution

---

Linked List Cycle

Problem

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

---

Idea

设置两个指针，一个每次移动2步，一个每次移动1步。 若最终相遇则有环，若一个指针走到了NULL,则没环

---

Solution

---

Copy List with Random Pointer

Problem

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.

---

Idea

• 把每个节点复制一遍， 分别插到原节点后, 新节点的random也指向对应的新节点的random
• 把复制的节点弄成串然后分离出来

---

Solution

---

Reverse Nodes in k-Group

Problem

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

---

Idea

• 每k个node是一个group
• 采用递归的思路, 其中有3个重要的变量 head:当前group的头, nextGroupHead: 当前iteration, 下一个group的头， newNextGroupHead: 整理过的group的头，若下一个group不许要reverse则nextGroupHead和newNextGroupHead是一样的。
• 每一次循环把当前group 倒过来即: 1->2->3->4 变成 1<-2<-3<-4 然后把1->next接到已经reverse的其他group前面

---

Solution

---

Swap Nodes in Pairs

Problem

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

---

Idea

Be careful with the pointer.

The number of nodes in the list may be odd.

---

Solution

---