Code

祸从天降的一天。 早上起不来，于是刷手机清醒一下，突然看到一个 ACMer 楼主提到自己没有刷过 Leetcode，面试的时候差点儿被打脸了。 看了一下题目，要求是 O(logn) 的复杂度，默默想了想，没有特别清晰的思路。 结果翻了翻评论，很多人都在蜻蜓点水般地表示二分查找不断分割就可以了。 要那么简单还用你说吗？起床了起床了。 题目是这样的： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 我本来的想法是归并之后计算中位数，但只能做到 O(m+n)，再优化感觉只能二分了。 于是又开始想分别取两个数组的中位数，比较之后就可以各扔掉一半，然后对两个折半的数组继续取中位数比较。 比如一开始找到的中位数是这样：[…5…], […10…]，那么 5 的左边和 10 的右边就可以丢掉了，因为最终的中位数肯定在 5 和 10 中间。 如果接下来是这样：[5..8…], […7..10]，那么 8 的右边和 7 的左边也可以丢掉，因为比 8 大的元素数量达不到这两个小数组的一半，所以中位数不会在里面，比 7 小的同理。 一直重复这个流程，最后得到的肯定就是一个或两个数，平均下就好了，时间复杂度也是符合要求的 O(logn). 结果等到看完标答后我才反应过来自己错在哪里了，这是后话。（因为 m 和 n 不一定一样大，所以显然折半的逻辑不对） 最优的解决方案是可以做到 O(log min(m, n)) 的，核心也是二分法，不过思路要复杂一些： 首先明确中位数的定义。对于奇数个数字来说是最中间的元素，偶数则是中间两个元素的平均值。 要做的是将两个数组各分一刀，假设划分的下标分别是 i 和 j，那么 nums1 被分成 nums1[0, i], nums1[i:]，而 nums2 分为 nums2[0, j], nums2[j:]....

近来刷题，觉得递归实在神奇。对于有的题目，用循环实现思路很清晰，改成递归却变得非常抽象；另一些相反，递归的做法既简洁又容易理解，但换成迭代就怎样都不明白了。经过几次痛苦的思考之后，我发现其中还是有迹可循的，按照套路来做，至少思路不会走得太偏。 在维基上面发现的关于递归的笑话： To understand recursion, you must understand recursion. Write Recursion 审题分析过后，如果选择用递归，需要先明确两个最重要的组成部分： 边界条件，保证函数能够返回，不会无限递归下去 递进关系，也就是上下层递归调用结果的等式规律 比如求 factorial： def factorial(n): if n <= 2: return n return factorial(n - 1) * n 如果必要的话，还得考虑的是如何维护上下文的状态信息，目的是计算最终的返回值，有两种办法： 使用全局（outer scope）变量 利用参数进行传递 下面的写法就是利用了参数来保存中间的计算结果： def factorial(n, res): if n <= 2: return res * n return factorial(n - 1, res * n) 也就是所谓的尾递归，对于可以优化尾递归的语言确实可以看成这种方式是从上至下的，而常规的递归则是从下到上。但我理解递归都是先下去再上来的，尾递归只是选择了一去不返而已。 上面的例子比较简单，反转链表的代码就比较难理解一点： def reverse_list(head): if not head or not head....

这是一篇使用（过） Linux Xorg without any DE 以及笔记本外接键盘的人才能理解其中辛酸苦痛的抒情科普文。 TL;DR 外接键盘不要开蓝牙，直接插线，除非你乐意折腾 使用 setxkbmap 而不是 xmodmap 来做 key remapping 不要用 Xorg The Irrational Part 上午十点零一分，端坐到显示器前，深呼吸两次。 Ok，回滚内核版本之后 Screen Lock 卡死的问题果然消失了，我们继续。 进入系统，先看一下昨晚的日志吧： ... 需求目标： 1. 交换 L-Ctrl & Caps-Lock 2. 交换 Win & Alt 当前方案： 使用 xmodmap 自定义配置文件，在 startx 时执行 已知问题： 1. 系统挂起或蓝牙睡眠导致的 keyboard reconnection 会 reset 掉 Win&Alt 的交换 2. 之后重新执行 xmodmap 会导致 L-Ctrl&Caps-Lock 交换回原状，必须执行两次 后续跟进： 1. TTY console switch 快捷键不可用 2. Terminate X 快捷键 CAB(Ctrl-Alt-Backspace) 不可用 3....

最近碰到一个服务器处理请求报错，但是本身的代码逻辑没有问题，排查后发现原来是参数中包含了 emoji，导致向 MySQL 插入数据时失败了。 解决起来倒是不麻烦，因为业务上不要求做相关的支持，所以捕捉异常之后返回错误码也就好了。但是好奇之下，做了个 MySQL 插入 emoji 的实验，发现里面还是有不少门道的。 What’s emoji 🧐 以前的粗浅理解就是由 unicode 支持的表情字符，这次认真查了下，找到了一篇讲解很详尽的文章：Everything you need to know about emoji 根据里面的介绍，关于 emoji 比较官方的解释： Emoji are pictographs (pictorial symbols) that are typically presented in a colorful form and used inline in text. They represent things such as faces, weather, vehicles and buildings, food and drink, animals and plants, or icons that represent emotions, feelings, or activities. 而 emoji 是怎么来的呢：...

最近读了《编写可读代码的艺术》这本书，感觉收获良多。如果早点了解的话，可能以前就不会犯那么多新手错误了，不过话说回来，理论总是要配合实践才能内化成自己的东西，而且书中的内容适合反复温习，一定常读常新。 整本书的核心都在于一个原则：代码应当易于理解。所以作者在开篇就提出了可读性的概念： 代码的写法应当使别人理解它所需要的时间最小化。 其中可读性很容易与代码长度混淆，因为代码本身的精简达到一定程度，就难免涉及到晦涩的逻辑压缩和语言用法，而这恰恰是和易读性相悖的。另外代码是写给人看的，这里指的不一定是别人，在实际工作中更有可能是若干天后的自己，所以保证可读性不仅利人，同样利己。 以此为中心，可以发散到编码过程中的很多方面，比如基础的变量命名、代码注释、函数定义以及开发后期的文档维护、解耦重构等等。 One of the hard things There are only two hard things in Computer Science: cache invalidation and naming things. – Phil Karlton 这句名言一句道破天机，万物皆从命名始，起名字的能力实在是太重要了。不论是变量常量，还是方法类名，一旦确定名称，代码的整体风格就开始受到影响，并且一直持续下去。 记得刚写代码的时候，并没有觉得合适的变量名称很重要，后来时间长了，慢慢开始琢磨起什么名字好，然后发现换来换去都不合适，为此绞尽脑汁，耗费的时间甚至比开发都长。现在熟练了不少，虽然有时还要再思索几下，但是命名已经比以前清晰很多了。反观周围的同事们，越是高手，在 naming 上也越得心应手，可能这也是编码能力发展的自然规律吧。 书里介绍的各种技巧，基本都围绕在信息量和准确性两点。前者可以保证名称是足够有意义的，同时也在检验变量存在的必要性；而后者能够减少代码中重复或混淆的定义，甚至提供了借助命名 debug 的可能性。 另外让我印象深刻的是，英文单词量有时候也会成为命名能力的瓶颈。比如对于常用的 make 来说，作为动词来描述一个操作可能并不足够清晰，更好的选择可以是 create/generate/setup/compose 等，但是英文不熟练或者词汇量有限的话，就难以在合适的时候想起来，或者要去专门查询才行。不知道未来会不会普及中文编程，不过那样难度仍在，只是从英语课切换成语文课了。 It’s not just about code 在代码里加注释是一件很有争议的事情，因此作者也提到了很重要的一点，要明确什么时候是不需要注释的。好的代码如同优秀的文章，自成一体，但这不影响添加一些额外的说明和解释可以提高阅读理解的效率。 广义上想，注释其实也算是另一种形式的文档。一行代码的注释，对象换成函数方法、模块文件或整个工程的话，就会演变成文字片段、README 甚至是单独的 DOCBOOK。而这些对于不需要了解逻辑细节的人来说，是比代码本身更高效的入口。 回想自己在工作日常中，写文档的时间并不比开发少，但两者其实并不冲突，归根到底都是要把任务描述清楚，一个写给人，另外一个给机器。代码写得清晰，文档维护也会非常轻松。 而在其他的场景中，比如开源的工具库，使用者对文档的关注度会更高，一方面会从文档的质量上评判整个项目，另一方面在使用中大部分情况也是阅读文档，而非源代码。 Be wise, not smart 每种编程语言都少不了流程控制的部分，再加上特有的语法糖，想写出精巧的代码并不是难事。 Oneliner 非但不难，还很容易有成就感，尤其是成功地把冗长的逻辑压缩在一行空间内。 但是这种做法的后果可能是灾难性的。抛开可读性原则不谈，这样的写法在新增 feature 和 debug 时会带来额外的成本，尤其是后者。因为排查错误的时候往往需要快速的定位和修复，而碰上复杂的条件分支和循环语句时，一是逻辑拆解浪费时间，再者想做改动也可能很困难，因为代码已经变得像个精 致的花瓶，一碰就碎了。 不得不说没有实际的经历，很难体会到这里面的道理，看似矛盾，实则展现了一个 coder 的成长过程：一开始专注于逻辑堆叠，后期追求奇技淫巧的写法，最终回归质朴的实现方式。...