Implement Trie

Implement Trie 问题是让我们实现一个字典树（Trie），那么什么是字典树呢？就是根据输入的字符串的前缀来构建树，比如输入是”aba”,”abc”，那么从树的根节点出发（根节点什么也没有，从它出发可以访问所有一个字符的节点），两个字符串共享节点a。接着节点a出发，可以

Jul 27 2015

在VS Code下运行python

在VS Code下运行python 今天发现了一个编辑代码的神器，叫VS Code(Visual Studio Code)，是在2015年微软Build大会上发布的编辑器，目前还属于preview阶段，可以在这里下载 这里它各种NB的功能我就不介绍了，我就介绍一下它Task功能，

Jul 24 2015

VS2013+Python

VS2013+Python 我们可以在VS2013上编写python代码，需要用到VS2013、Python、PTVS 我用的IDE是VS2013 express，这个可以在官网上下载。 Python的话，可以在这里下载 PTVS全称是Python Tools for VS，它们

Jul 24 2015

Maximum Product SubArray

Maximum Product SubArray 问题是求出一个整形矩阵中，最大的连续乘积，比如[2,3,-2,4]，那么将会返回2*3=6。 这道题目我用了两个方法来做，第一个是动态规划，第二个是找出矩阵中的非正数下标。 动态规划 我们每次需要记录最大的数，也需要记录最小的负数

Jul 23 2015

Longest Valid Parentheses

Longest Valid Parentheses 问题是找出一个由’(‘和’)’组成的字符串中最长可匹配的()字符串，比如’(()’就会返回2，’(()))’就会返回4。 我的方法是用栈来记录子串开始的下标。比如对)()()，栈会记录第一个)，接着当找到可以匹配的()时，子串的

Jul 21 2015

Maximal Square

Maximal Square 问题是给定一个二维矩阵，由’0’,’1’字符填充。现在要求出可以构造的最大矩形面积。 我们构建d[i][j]表示以(i,j)为右下角的矩形的最大长度。那么它取决于斜上构建的矩形，左边和上边的矩形。如果以(i,j)构造的图形能够构成矩形，那么它的斜上、

Jul 20 2015

House Robber II

House Robber II 问题是之前的House Robber类似，只是将房屋连成了环。这道题目可以这样来做，我们的动态规划还是原来的动态规划，但是可以求两种情况，一种第一个房屋的钱肯定抢走，那么dp[0]和dp[1]的初始状态就是nums[0]，那么只返回dp[size-

Jul 20 2015

Maximum Subarray

Maximum Subarray 找出给定数组中连续子数组的最大和。比如给定数组[−2,1,−3,4,−1,2,1,−5,4]，那么将返回[4,-1,2,1]，最大和为6。 这道题目可以这样做，从头扫一遍数组，如果前两项的和为负数，说明该数在当前情况下不会做出贡献，所以我们将可能

Jul 19 2015

Minimum Path Sum

Minimum Path Sum 给定一个m*n的矩阵，填满了非负数（如果存在负数呢？可以抽象成图，接着利用BellmanFord来求），求从左上角到右下角的最短路径和是多少。 设d[i][j]表示到达grid[i][j]的最短路径和，那么d[i][j] = matrix[i][

Jul 19 2015

Triangle

Triangle 给定一个三角形的矩阵，求从上到下最小的路径和，只能走与节点相邻的节点。 这道题目可以用动态规划来做，利用d[MaxSize]来记录，每行的路径和。那么d[i]就是d[i] + min(matrix[i-1][j],matrix[i-1][j+1])

Jul 19 2015

Unique Binary Search Trees

Unique Binary Search Trees 这道题目是给定一个值n，求出有n个节点的二叉搜索树。 这道题目是用动态规划来做，设d[i]表示有i个节点的BST个数。0个节点的时候为1，1个节点的时候为1，2个节点的时候为2。 我们可以从左右子树的角度来思考问题，d[i]的

Jul 18 2015

Unique Path II

Unique Path II 这个问题和上一道问题很像，只是这次加入了限制，如果这个m*n中存在“障碍”，那么这个坐标是不能到达的。 所以我们只需要在动态规划的时候判断当前坐标是否为障碍，如果是障碍的话，d[i][j]就为0，为什么没有路径可以到达坐标。

Jul 18 2015

Unique Paths

Unique Paths 问题就是给定m*n的空间，求从(0,0)坐标到(m-1,n-1)的路径数，只能向下或者向右走。 这道题目是典型的动态规划，设d[i][j]表示到(i-1,j-1)的路径数，在初始化的时候可以将第一行和第一列都初始化为1。 d[i][j]取决于d[i-1]

Jul 18 2015

Regular Expression Matching

Regular Expression Matching 这道题目和之前的一道Wildcard-Matching问题类似，只是这次的含义变成了，可以匹配0个或多个号之前的元素，比如在字符串中出现了b*，表示可以出现0个b，1个b，2个b… 我采用的方法仍然是动态规划，输入是两个字符

Jul 17 2015

Wildcard Matching

Wildcard Matching 问题是判断两个字符串是否匹配，但其中一个字符串中包括?和*字符，?表示可以匹配任何一个单个字符，*表示可以匹配任何连续字符，包括空字符。 比如: isMatch("aa","a") -> false

Jul 16 2015