#1037 数字三角形

#1037 数字三角形 我的做法是用大小为高度的数组dp来存放当前层的最大值，dp[i]表示在某层的最大奖券数，那么在每一层时计算该层下的最大奖券数。 为了充分利用空间，我是从后往前遍历 dp[i] = max(dp[i-1],dp[i])+num[i]; 当i等于0的时候，dp

Aug 23 2016

#1049 后序遍历

#1049 后序遍历 这道题目就是给的中序和前序，求字符串的后序输出。 我是用递归来实现的。 中序的第一个字符肯定是根节点，那么在前序中找到该字符的位置，然后前序根节点左边的子串就是左子树，右边的子串就是右子树。然后就一直递归调用该函数，拼装后序遍历的字符串 1234567891

Aug 22 2016

Russian Doll Envelopes

Russian Doll Envelopes 这道题目我先对pair的first进行排序，接着利用动态规划dp[i]表示最大的套娃为envelopes[i]所能套的娃的个数，那么dp[i]就取决于0~i中能被envelopes[i]套中的娃的个数。

Aug 22 2016

#1304 搜索一 24点

#1304 搜索一 24点 这道题目我是用枚举来实现的，利用C++的next_permutation可以来枚举数列，接着就是根据提示中给出的两类运算 ( ((a#b) # c) #d) ( (a#b) # (c#d) ) 枚举3个运算符的位置，6类计算（+、-、*、/、 反/

Aug 21 2016

#1350 Binary Watch

#1350 Binary Watch 这道题目可以用一个60大小的数组来记录数与它二进制形式下1个数的映射。 接着两层循环遍历24和60，如果两数的1的个数的和等于输入的整数，那么就输出该时段。

Aug 20 2016

Coin Change

Coin Change 用dp[i]表示对i进行找零的最小花费，那么dp[i] = min{dp[i-coins[j]],j遍历coins}，最终返回dp[amount]

Aug 17 2016

Range Sum Query Immutable

Range Sum Query Immutable 一开始我是用一个二维数组来储存结果的，即dp[i][j]表示范围i到j的和。结果报了内存空间太大的错误，经改进，可以用一维数组来记录下标0到i的数的和，即dp[i+1]表示nums[0]+nums[1]+…+nums[i]的和。

Aug 17 2016

Word Ladder

Word Ladder 方法和思路是参考Word Ladder II,构建一个相差1个字符的图。

Aug 17 2016

Binary Search Tree Iterator

Binary Search Tree Iterator 我一开始是用队列来中序储存整棵树，但是这样的空间复杂度是O(n)。但是实际上只需要O(h)的空间，用栈来储存树节点，在初始化时先把所有左边的节点压入栈中，在弹栈时再调用该函数来压入所有的左节点。

Aug 17 2016

Unique Binary Search Trees II

Unique Binary Search Trees II 利用递归获取start到end的所有节点的集合。用i遍历从start到end，每次获取（start,i-1）作为i节点的左子树，(i+1，end)作为i节点的右子树。

Aug 16 2016

Recovery Binary Search Tree

Recovery Binary Search Tree 可以利用中序遍历的方法来获取在顺序中不对的两个元素，因为中序遍历一个BST就是顺序排列的。当最终找到两个位置不对的节点，再交换两个节点即可。

Aug 16 2016

Shuffle An Array

Shuffle An Array 这道题目我一开始是用map来记录随机过的下标，后来看到讨论里面可以这样来做，就是将随机出的位置和待交换的位置进行交换，这样下次只需要在剩下的集合中进行随机就可以了。

Aug 15 2016

Linked Random Nodes

Linked Random Nodes 这道题目看到有人用蓄水池抽样，这样就变成了一个数学概率问题。我的做法就是用容器把链表里的元素都存起来，然后随机取出一个元素。

Aug 15 2016

Wiggle Sort II

Wiggle Sort II https://discuss.leetcode.com/topic/32861/3-lines-python-with-explanation-proof

Aug 14 2016

Maximum Gap

Maximum Gap 我就调用algorithm中的sort，对数组排序后，然后遍历数组获取最大的差值。

Aug 14 2016