Neil Ding
Neil Ding
使用MergeSort的in-place做法： ``` java static ListNode sort(ListNode root) { if (root == null) return null; if (root.next == null) { return root; } // find the middle node by two pointers...
好样的 On Jan 23, 2014 7:03 PM, "gj835" [email protected] wrote: > 是说我应该先占个沙发什么的= = > > — > Reply to this email directly or view it on GitHubhttps://github.com/GingerBear/IS-Job-Hunting/issues/13#issuecomment-33183756 > .
最基础的动态规划题，动规的思想是把中间结果保存起来（缓存），留着以后用，从而大大减少不必要的重复计算。 ### Recursion DP 递归做法比较直观地使用了动规，用一个整型数组保存每次计算的结果，如果在某次递归中发现曾经计算过，立即返回保存着数组中的结果。同时利用了数组的引用传值，保证在层层递归中，只有一个公用的缓存。 时间复杂度为O(n)，还不知如何分析是好。 空间复杂度O(n)，因为额外使用了用来保存结果的数组，数组长度就是n。同时递归的深度最深为n，所以空间同样是n。 ``` java static int fib_rec(int i) { if (i
@dianadujing 其实还有一个矩阵的作法，但没什么意思，主要是希望能从这题里总结一下递归和动态规划的基础的东西。
@dianadujing 有没有更好地方法？试着总结一下，分析一下复杂度？
@dianadujing Why not share your own understanding here?
@allen6432 欢迎怡波童鞋的加入，数学系出身的分析起来果然高大上，你能不能发一个新的issue跟我们讲讲如何用正确地方法分析一个算法的**时间复杂度**和**空间复杂度**？ 感觉不少同学包括我都不是很清楚怎么做复杂度分析，平时分析起来总是只有一个泛泛感觉在哪里，很难做出令人信服的分析。
@dianadujing 没有用过Java的assert，最近看JavaScript和Ruby on Rails的书才意识到test的必要性，我的做法是自定义一个简单的simpleAssert()，就是在true和false的打印不同的值，带上msg。 ``` java static void simpleAssert(Boolean ifSuccess, String msg){ if (ifSuccess) { System.out.println("SUCCESS:\t" + msg); }else{ System.out.println("FAILS:\t" + msg); } } ``` 使用起来也很简单： ``` java simpleAssert(fib2(1) ==...
@dianadujing 非常NB！请分析一下复杂度？
开了一个新贴总结Heap这个数据结构，包括了用Heap来解决这道问题的方法 #10