分享我的Lintcode题解，目前进度244/248

又被吞掉一题：Copy List with Random Pointer

zhuli19901106 发表于 2015-7-26 20:10
Minimum Path Sum
题意：Frequently Ask Question
解法：Frequently Answered Question

#312楼Minimum Path Sum这个题，如果题目允许朝上下左右4个方向前进的话，还能用DP来解决吗？如果不能的话，是因为什么原因不能呢？我感觉如果是4个方向都可以的话会造成死循环这是一方面，另外主要就是想问下，4个方向的话，有没有什么本质上的问题？就是不符合DP特性的问题？比如不存在最优子结构啥的这类违背使用DP原则来解题的问题呢？

水逼一枚 发表于 2015-7-26 23:44
#312楼Minimum Path Sum这个题，如果题目允许朝上下左右4个方向前进的话，还能用DP来解决吗？如果不能的 ...

如果允许四个方向，那就是单源最短路径了，已然不是一个问题，用Dijkstra算法的思想+BFS应该可以解决。
还是建议你动手多写点题吧，在题目还没做熟时就开始琢磨理论，个人觉得本末倒置了。这问题我无法解答，你得看看论文。
针对这个问题，这么看吧：DP得有递推关系，如果可以上下左右走，那递推关系里谁推出谁呢？所以得搜。深搜还是广搜呢？哪个好用就用哪个。

zhuli19901106 发表于 2015-7-25 00:57
Expression Evaluation
题意：hard难度。给定一个已经分割好的算术表达式，求值。
解法：首先，看见这题 ...

#243楼的 Expression Evaluation你说的非法case是指的
["(","(","(","(","(",")",")",")",")",")"]这种情况是吗？
这个题感觉就是得把中缀表达式转换后缀表达式的规则给记下来，才好针对这一类的题目有个通法，比如leetcode上的basic calculator I和II, 你觉得呢？

水逼一枚 发表于 2015-8-1 02:16
#243楼的 Expression Evaluation你说的非法case是指的
["(","(","(","(","(",")",")",")",")",")"]这种 ...

对，就是这个。这并不是合法的算术表达式。
在不知道转换规则的情况下，的确没法写。知道处理方法后，这一系列的题就都会做了，剩下的就是实现。都是同一套规则。

zhuli19901106 发表于 2015-7-22 03:29
Max Tree
题意：Cartesian tree
解法1：首先，构造笛卡尔树的关键是找到最大点。那么就在“找到最大”上 ...

solution 2 我先写了recursive的解法，后来用stack模拟整个recursion的过程就写出来了。。神奇的事这个代码和我的一模一样，只不过我用的是python。。我本来还想上来找找看有没有更优化的解法。。

小柯西 发表于 2015-8-3 22:57
solution 2 我先写了recursive的解法，后来用stack模拟整个recursion的过程就写出来了。。神奇的事这个代 ...

笛卡尔树的构造最优只能到O(N)了。如果第一次做这题就能独立想出最优解，那很厉害了~

zhuli19901106 发表于 2015-7-23 17:26
审核的人干嘛去了？在跟公务员比效率吗？审核五天之内不给通过的话，审核员全家都是孙子。有种删我贴啊~
...

This is the system problem, not one want to Shenhe your post. Just be calm. People are volunteer to manage  the bbs, not pay

同正在刷lintcode 20天基本刷完好快啊! 向lz看齐~~

zhuli19901106 发表于 2015-8-3 23:04
笛卡尔树的构造最优只能到O(N)了。如果第一次做这题就能独立想出最优解，那很厉害了~

196楼的Unique Binary Search Trees II这个题目，有几个疑问想请教下楼主。【1】如果给定的数字不是按顺序的1,2,3...n而是乱序的比如4,5,2,6,7,8,3,9...这种，那么同样的方法，实际上生成的就是所有unique的一般二叉树的情况了对吗？【2】你提到了记忆化保存中间结果来加速的方法，我想问下这个具体的思路是什么呢？是比如去保存以某个数字为root时，所能产生的所有子树的结果？还是说去保存的是一个数字范围比如2 to 5, 他们所能构成的子树的结果呢？谢谢啦。