刘新宇

  • 关注
  • 短消息
  • 送银子
文章
3
评论
2
推荐
0
收藏
0
社区会龄
10 个月
个人网站
--
个人简介

《算法新解》作者

  • 刘新宇 2推荐

    枚举组合

    枚举从n个元素中选取k个元素的所有组合 在《算法新解》一书的附录中(第529-530页),我们给出了如何从n个元素中选取k个元素进行排列的方法。和排列不同,组合并不关心元素间的先后顺序。记n个元素的列表为:{x1 , x2 , ..., xn}。从第一个元素x1开始,我们有两…...

  • 刘新宇 8推荐

    寻找被篡改的数

    这一趣题和《算法新解》前言中的“最小可用Id”问题具有很多类似的地方。 有个从1到n的数字列表,经过某些处理后,发生了两点变化。1)序列的顺序被打乱了;2)其中一个数字x被篡改成了数字y,其中x和y都在1到n之间。能否找到一个线性时间,常数空间的方法,找出丢失的x和重复的y呢…...

  • 刘新宇 9推荐

    最小可用Id的命令式解法

    在《算法新解》的前言中,我们只给出了使用分而治之策略的线性时间O(n),常数空间O(1)的解法。这里我们给出另外两种命令式解法,它们都可以达到同样的性能。 首先我们先回顾一下书中讨论的一个重要性质 1 <= answer <= n + 1 其中n是序列的长度,…...

评论了

  • 今年 10-15 15:44
    刘新宇 评论了图书 算法新解

    将命令式删除算法作为附录单独提供。请参考这一pdf: https://github.com/liuxinyu95/AlgoXY/files/1385252/rbt-del-zh-cn.pdf

  • 今年 10-05 20:02
    刘新宇 评论了图书 算法新解

    @刘新宇 大家可以从这个连接获取目前修改过的红黑树一章的pdf: https://github.com/liuxinyu95/AlgoXY/files/1359197/rbtree-zh-cn.pdf

  • 今年 10-05 18:53
    刘新宇 评论了图书 算法新解

    收到这样的评论,我是非常感谢这位读者的。因为这样才能促成进步。我最近正在大幅度修改《算法新解》红黑树这一章,你可以在github上看到,最近的commit都是针对红黑树的。 首先谈谈第一个问题“红黑树到底复不复杂?”——简短的回答是这样的:如果你用functional实现,它一点也不复杂,全部插入算法只有16行。是世界上迄今为止最短的红黑树实现。如果你用传统的imperative实现,它的确真的很复杂。我们找遍互联网、各种论文、各种教科书也不可能在十几行内实现。 接着谈谈第二个问题,为什么不该出红黑树删除的实现和代码。——你观察的没有错,4本书都没有关于删除的实现。这不是偶然,而是有原因的。我先说说functional的红黑树为何不给出删除的算法。Chris Okasaki有一个文章:Chris Okasaki. ``Ten Years of Purely Functional Data Structures''. http://okasaki.blogspot.com/2008/02/ten-years-of-purely-functional-data.html特别讲到了这点。这是2008年的文章了,到现在已经有近20年了。如果研究Haskell的标准库,会发现不仅是红黑树,functional的各种树都很少给出删除。因为纯函数意味着不可变,所以应用的时候是一次性构造好树,然后进行频繁的查找。所谓删除,在函数式的场景是把key标记为删除,但并不真的移除。当有超过50%的key都被标记为移除后,再进行一次重新构建树。《算法新解》中给出红黑树的functional删除已经是很少见了。因为用pattern matching的方式,可以大大降低代码的复杂度。即使是这样,我也并不希望读者认为:“所有纯函数式算法的标准库中的红黑树删除就是这样的。”,这仅仅是展示如果想删除的话,算法可以是什么样子。 如果你真的希望获得imperative方式删除的详细讲解和例子代码,你可以在本书的例子代码中获得: https://github.com/liuxinyu95/AlgoXY/blob/jvm/datastruct/tree/red-black-tree/src/java/IntRBTree.java 以及测试: https://github.com/liuxinyu95/AlgoXY/blob/jvm/datastruct/tree/red-black-tree/src/java/IntRBTreeTest.java 但是,对于imperative删除算法的详细介绍,并不是我想做的,我觉得其他书籍会做得比我好。我认为这一章的价值仍然在于对函数式红黑树的介绍。我希望读者在看到16行的红黑树插入算法后能够理解这一点。 我仍然在大幅度修改红黑树的一章,等修改完毕后,我会单独把这一章的pdf发给大家。AVL树的章节我会后继再进行修订。 再次感谢desent的斧正!大家的批评是我继续修改的最大动力。

  • 今年 07-11 05:16
    刘新宇 评论了图书 算法新解

    非常感谢指出这个问题。如果y.right非空,的确需要其父节点设置正确。这两处修改可以合并在一起。即在删除y之前: if y.right is not None: y.right.parent = y.parent 请参考 https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/tree/binary-search-tree/src/bstree.py#L136

  • 今年 06-04 07:00
    刘新宇 评论了图书 算法新解

    这个建议很好。对于非论文注释,我接下来在原稿上加入参考文献中的页码,方便查看引用。