Combinations

Combinations 这道题目我一开始是用正常的递归回溯来得到所有的combination，但是效率不高。 看到一个解答是这样的 C(n,k) = C(n-1,k-1)+C(n-1,k) 第一个表示选定n后，在n-1中选择k-1个数；第二个表示不选n，在n-1个中选择k个数。

Aug 2 2016

Permutation

Permutation 我一开始是用一个nums大小的bool数组来储存该元素是否使用过，然后利用递归回溯来得到排列。 看了解答，发现可以用交换数字来得到排列。 比如一开始1 2 3，交换后面小的数，变成1 3 2.

Aug 2 2016

Minimum Size Subarray Sum

Minimum Size Subarray Sum 一开始把subarray看成不连续了，想直接排个序就可以了。 遍历数组，用left和right两个指针来记录subarray的长度，在循环中先找到一个候选的subarray，然后用left逐个减去元素，指导sum比s小。

Aug 2 2016

Subsets II

Subsets II 思路和combination sum II是一样的，先排序，再根据当前循环遍历的下标是否是第一个或者不是第一个且当前元素与前一个元素不同来进入递归。

Aug 1 2016

Word Search

Word Search 使用深搜和回溯来做这道题目。

Aug 1 2016

Combination Sum IV

Combination Sum IV 这道题目如果像combination I II III那样的递归回溯的方法就会超时。我们换个思路用动态规划的方法来实现，用长度为target+1的数组来作为动态规划的状态数组dp。 dp[i]表示组成和为i的方法由多少种，那么dp[i] =

Jul 31 2016

Combination Sum III

Combination Sum III 方法和combination sum II一样，而且不用排序和考虑重复的数的情况，把candidates变成1到9的数组传进去即可。 在最终要压入容器的地方，判断大小即可。

Jul 31 2016

Combination Sum II

Combination Sum II 思路和Combination Sum一样，只是得先排个序，然后再每次递归前判断一下，当前循环遍历的下标是否是第一个或者不是第一个且当前元素与前一个元素不同，那么就可以进入递归。

Jul 30 2016

Combination Sum

Combination Sum 使用递归回溯，传入的是index，求得到的和，储存数列的矩阵。 如果和等于target，那么就压入矩阵。 如果不想等，那么就遍历candidates，如果和加上candidates的元素小于等于target时，才能递归访问。

Jul 28 2016

Spiral Matrix

Spiral Matrix 和spiral matrix II的方法一样，利用direction来遍历数组。

Jul 28 2016

Spiral Matrix II

Spiral Matrix II 这道题目我先声明一个n*n的vector, vector<vector> v(n,vector(n))，这样的初始化会有效地提高速度。 接着用一个cnt从1到n*n遍历，用一个direction来表示移动的方向，另一个diff来表示目

Jul 28 2016

Next Permutation

Next Permutation 这道题目主要利用对数组的操作来实现。 比如 2 1 3 1 6 4 下一个的排列是 2 1 3 4 1 6； 可以从后面来观察数列，6 4构成了一个向上的坡度（从后向前看），到1的时候下去了，那么在1 4 6中第二小的是4,新的数列得以4开头，其

Jul 27 2016

Palindrome Partitioning

Palindrome Partitioning 这道题目可以用回溯来做，判断0到i前的子串是否是回文子串，如果是，那么就判断i+1到结尾的子串是否是回文子串。每次要保留储存字符串的容器。

Jul 27 2016

Set Matrix Zeroes

Set Matrix Zeroes 这道题目如果不用额外空间的话，可以这样做，就是用第一行和第一列来记录0所在位置的情况，比如元素[3][4]是0，那么[3][0]和[0][4]为0，这样我们在从第二行第二列开始遍历时，就可以去查看第1行和第1列是否是0来进行设置。但是这样还要注

Jul 17 2016

Guess Number Higher or Lower

Guess Number Higher or Lower 这道题目我就用常规的二分搜索来做，但是在碰到大数的时候会遇到问题，因为要找中间的数，那么中间的数是根据(start+end)，如果数很大的话就会越界。所以用long long来存这些变量即可。 (start+end)/2可

Jul 17 2016