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

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

另外请问楼主有没有做lc #241 different ways to add parentheses这个题目呢？想问下这个题目的时间复杂度和空间复杂度应该也是和unique BST II是一样的对吧？

zhuli19901106 发表于 2015-7-19 19:21
Product of Array Exclude Itself
题意：在不使用除法的情况下，算出对应每个位置的除了此位置外其他元素 ...

75楼 Product of Array Exclude itself, 所以楼主的理解是因为要考虑解集所在的空间，所以不是严格意义的O(1)对吗？

请问lz一天花多少时间刷lintcode?是全心投入刷题么？感觉进度好快啊

请问lz一天花多少时间刷lintcode?是全心投入刷题么？感觉进度好快啊

水逼一枚 发表于 2015-8-12 03:25
196楼的Unique Binary Search Trees II这个题目，有几个疑问想请教下楼主。【1】如果给定的数字不是按顺 ...

这个。。说实话，要讲清楚这问题比写出代码还复杂
我举个例子吧，比如给你前序遍历{2, 3}，你应该能唯一构造出一棵BST，对吧？
像这样：
   2
     \
      3
那么我们看，在所有1~n构成的BST中，这个{2,3}部分出现不会只有一次吧。如果我每次递归生成这些树时，都不做子树的记忆化，岂不是要生成很多个一模一样的{2,3}？浪费了时间和空间。另外，记忆化的hashkey用的是中序遍历里左右端的位置。这个是唯一的。

如果不做记忆化，我最后得到的，的确是一棵棵形态各异的树，任何两棵树都不共用任何节点。
那么做了记忆化之后呢？最后得到的，其实是一张很复杂的网，而且这张网有从上至下的方向。你从网的顶端任何一点（也就是所有树的根节点）出发，往下进行遍历得到的效果是一样的。因为在一棵树上感受不到其他树的存在，尽管他们共用着节点。

水逼一枚 发表于 2015-8-12 06:53
75楼 Product of Array Exclude itself, 所以楼主的理解是因为要考虑解集所在的空间，所以不是严格意义的 ...

如果你能在保存结果的空间里完成功能，那应该算是O(1)空间的。
空间复杂度应该是按“除了保存结果的空间以外的空间开销”来算。

kidzlike 发表于 2015-8-12 07:31
请问lz一天花多少时间刷lintcode?是全心投入刷题么？感觉进度好快啊

嗯，我那段时间在家无事，所以是全天刷题的。

水逼一枚 发表于 2015-8-12 03:41
另外请问楼主有没有做lc #241 different ways to add parentheses这个题目呢？想问下这个题目的时间复杂 ...

我最近不刷题了，在看算导

zhuli19901106 发表于 2015-7-25 23:13
Longest Increasing Continuous subsequence II
题意：hard难度。给定一个二维数组，允许你从其中一点出发 ...

又来问楼主问题了。#284 Longest Increasing Continuous subsequence II这个题目，我最初看标签说的是DP，当时在想试试用循环递推的实现方式吧，然后我的分析是这样的，由于这个题目LICS的定义允许有4个不同的方向，那么就在想我当前的某个状态[i,j]的解也完全可以有后面[i+1,j]或者[i,j+1]这些状态的解构建上来啊，可是后面的那些问题(未解决)并不是我当前的子问题的解，看上去应该是不满足DP的循环递推实现方式的解题条件啊，所以就没办法用这种方式来实现，只能考虑用分治递归+记忆化的DP实现方式来实现了，我这样分析对不对呢？

水逼一枚 发表于 2015-8-22 01:51
又来问楼主问题了。#284 Longest Increasing Continuous subsequence II这个题目，我最初看标签说的是DP ...

对啊，记忆化搜索也是DP的一种常见形式，这题就是的。