Becomin' Charles

作为程序员工作十几年了，Shell 编程这项技能，就好像“你永远得不到的爸爸”一样，每次想用的时候，都觉得自己从来没学会过。本文的编写作为一篇学习笔记，或者一个备忘录，或者一个作弊小抄，我会在每次遇到的时候，不断前来添砖加瓦，说不定有朝一日，能有望凑成一本秘籍。虽然网上类似的内容很多了，但是那些终究是别人的东西，自己用着总是不得劲，所以，做笔记这项技能总是伴随着人类的发展。

大家有没有发现，有些技术点，我们每次想用的时候，都不会用，然后学会了，用一次，又很久不用，然后到了要用的时候，又开始新一轮的循环。比如 git 的 submodule，对我来说就是这样一个技术点。

PopClip 是我非常喜欢也非常依赖的一个软件，属于 “润物细无声” 这个类目的软件。

软件的功能是，当你用鼠标选中一个文本的时候，弹出来一个浮动菜单，提供一系列的快捷小功能。缺省的功能有，搜索引擎，相当于划词搜索，还有字典查询，可以立刻激活系统的字典，还有拼写检查等。

Docker 一旦设置好了环境，日常就只要使用简单命令就可以运行和停止。

于是，我每次用的时候，都想不起来一些关键性的命令到底怎么用，特此记录。

指令式编程，Imperative Programming，是一种编程泛型，通过编程指令，告诉计算机，每个步骤执行的命令，计算机按照代码的指令，逐行执行，就能得到最终结果。

指令式编程的优点是非常符合直觉，代码发出命令，计算机执行。所以，这种编程泛型也非常容易学习，我们入门学习的 C 语言，Java 语言等等，都是支持指令式编程的，也是这类语言的主要编程泛型。

面向对象编程，也是一种编程泛型，同时，面向对象编程泛型，也是一种指令式编程泛型的特例。所以，指令式编程，是一个更抽象的概念。

声明式编程，Declarative Programming，顾名思义，这种编程泛型，更倾向于告诉计算机，“是什么”，由计算机自行决定如何操作。

邮箱里看到了技术文章推送的邮件，提到了数据湖、湖仓一体等等概念，我有点好奇到底是什么东西。

初步看了两篇文章，我感觉，这个“数据湖”又是一个热门潮流概念吧。没想到 Martin Fowler 大叔也撰文专门描写了数据湖。

“回溯法”（Backtracking）和“深度优先搜索”（Depth First Search-DFS），看起来名字截然不同，字面意思也没什么相似的，不过，如果你经常刷题，渐渐就不免会注意到这个问题。为什么这两者会凑到一起去了？

我最早注意到这个问题，是观看题解的示范代码，示范代码是一道使用“回溯法”解决的题目，可是很奇怪，函数却并命名为 dfs，明明是回溯法，怎么用 dfs 来命名函数呢？为啥不用 backtracking 命名函数呢？

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

回溯法是一种通用的算法，用于找到一些计算问题所有的（或者部分的）解，尤其是约束满足类问题，该算法逐渐构建潜在的解，一旦确认潜在的解无法满足，则立刻抛弃。

回溯法一个最经典的例题是“八皇后”问题，在一个国际象棋棋盘上，尝试放 8 个皇后，这 8 个皇后不能互相攻击，尝试找到一种或所有的解。8 个皇后不能在在同一行，同一列，或者同一对角线上。

回溯法解题的步骤大概是，首先在第一行挑选一个位置防止一个皇后，然后在第二行，放置皇后的时候，就不能产生攻击，一旦发现第 8 个皇后已经放置完毕，则搜索到了一个解。如果还没有放足 8 个，就发现已经无处可以放置了，则返回上一行，将上一行的皇后换一个位置放置（回溯）。

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

深度优先搜索，是一种用于遍历或者搜索树或者图数据结构的算法。算法从树的根节点开始（或者图的任意节点），然后沿着连接节点的边，尽可能深的遍历图，直到回溯。

在深度优先遍历的定义里，出现了回溯这个词。不难想象，假设有一颗树，我们从根节点开始深度优先遍历，那么会从根节点，一直向下深入，直到叶子节点，这时候如果想继续遍历，则必须返回父节点，这样才能寻找兄弟节点进行遍历。这个“返回” 的过程，就根回溯极其类似。

结合维基百科的定义和两个算法的基本描述，我们不难发现这两个算法的相同之处，通俗点说，都是选定一种策略，一条路走到黑，如果走入死路，就退回来，重新选择。

这“两种”算法的另一个相同之处是，都是遍历解空间的一种策略，说直白点，都是“穷举”的算法，只不过，穷举解空间也好，穷举图也好，都需要选定一个策略，才能没有遗漏和没有重复的完成穷举。

所以，我自己更倾向于认为，这两者，其实是同一种算法，只是从不同角度出发去称呼他们。事实上，我打开了好几本中文版算法书，《算法 4》，《算法导论》之类的，《算法竞赛入门经典》《算法竞赛进阶指南》等等，几乎就没找到过关于“回溯法” 的介绍和定义。难怪那些搞竞赛的，遇到回溯法，都会用 dfs 去命名函数。

通过在 StackOverflow 搜索，还真有人问这个问题。

For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.

So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.

这个回答认为，回溯法，处理了隐式树，而 DFS 则处理显示的树。这看起来平凡，但是也意味深长。当使用回溯法遍历一个问题的搜索空间时，隐式树在遍历的过程中，进行剪枝。但是，DFS 算法则不同，显示的树或者图已经被构造出来了，那些不可达的节点，或者不可能的情况，此时已经被排除在外了，只要按部就班全部遍历即可。所以，他认为，回溯法就是隐式树/图的深度优先搜索，而 DFS 就是没有剪枝的回溯法。

当然，也有很多回答认为是两种不同的算法，只是我比较倾向于这个答案。也有从字面去解释的，我觉得也可以听听，比如有人说，回溯法是解决问题的方法论，而 DFS 是算法。隐式图，显示图什么的，也不那么难以理解。事实上，我认为现实世界里，只有隐式图，真正的显示图是很罕见的。正因为我们对现实世界进行了抽象，才出现了显示图这种东西。

比如，使用回溯法常见的一类问题就是排列组合问题。例如经典的，使用 n 对括号，能排列出多少种合法的括号串（括号必须配对）。这是经典的需要回溯法解决的问题，你能把这个问题想象成图么？不管如何，如果你能把这个问题写成一个递归函数来解决，至少在递归深入到下一层和回来的过程，都绘制成节点和边的话，这个可视化出来的东西，就是一棵树（树是图的特例）。

所以，不用在纠结“深度优先搜索”和“回溯法”有什么区别了，只要知道，这两者就是一体两面，或者你认为根本是一回事也不为过。显示图和隐式图也没任何区别。只是隐式图更贴近显示世界，而显示图更贴近抽象世界。如此而已。

刷题到现在，不知不觉过了 500 大关后，真的不能再随随便便了，要认真起来了。就好像写博客，坚持了几年后，你就不自觉地内化了这个行为，好像自己隔了一段日子，就一定要写点什么了。

之前 500 纪念的文章里，也说了，明确感受到了瓶颈。好像自己刷题没什么长进了。幸好一个朋友提点，要逐个点击破来提高了。这两天就开始留意了。方法很简单，就是之前不会做就跳过的东西，现在就要求自己一定要看懂，不能随便跳过任何东西。不惜代价也要搞明白再往后。就发现，其实自己掌握的东西还是千疮百孔的。

小目标

其实目标是最重要的东西，就是到底想通过刷题获得什么？这样才能决定做法。如果说，刷题是为了找工作，应该刷《剑指》，反反复复刷，知道随机跳题都能秒做对。当然，这不是我的目标，因为之前也说了，35+ 找工作的时候，刷题只是获得一个聊天的机会，并不能帮助我了。

我现在定个小目标是，能在周赛妥妥 3 道题。很多同学可能觉得这很容易，当然我打心眼里也没觉得有多难，所以只能是一个小目标了。只是，以此为目标的时候，我能清晰定位到，自己缺少多少知识。也是自己之前可以忽略的东西。

短板

1. 双指针的应用，虽然知道一些双指针的原理，会写基本的，但是总是很难从题目中一眼就看出来双指针的模式，几乎想不起来去用，所以我对这个掌握还是有问题的；
2. 拓扑排序，这个概念很抽象，还不是很懂，有时候甚至是做出来了也不知道自己用到了相关知识，只是从感性层面自己找了个方法；
3. Trie 树，这肯定是一般面试企业的时候不会用到的超纲数据结构，但是在周赛里，很可能会遇到的。需要更多的了解和训练，这是存储字符串比较高效的数据结构；
4. 图算法，因为面试一般不会考到图，以前都刻意忽略了这方面的理解和训练，以至于这方面几乎都是空白的。尤其是拓扑排序，最近做不出的题目，都是频频遇到了这个领域的东西。
5. 动态规划，现在终于对动态规划有了一些感觉，但是动态规划有很多的细分，线性，非线性，树形，还有一些方法上的技巧，什么压缩之类，都还很懵懂，并没有掌握得很好；
6. 数论，上次双周赛里遇到求大数的前 5 位，尾 0 数量，后 5 位非零数字，我完全没思路的，不知道怎么着手，看别人的题解我甚至都有点看不懂，可见是自己完全空白的领域；
7. 计算几何，也一直是自己刻意规避的东西，因为觉得麻烦，所以看到这类题目总是上手抄答案，真在竞赛里遇到了，也确实 都是只能束手无策了。

当然，短板还是有很多很多的，只是这几个是我目前想到的，欠缺比较多的东西，如果有针对性地训练的话，可能会有比较大的成效，也即在这些领域投入，边际效益会大一点。那就把这几个定成这一轮的焦点问题，尝试比较集中去投入一些经历。

计划

目前，在参加一个 91 天学算法训练营，花了 10 块的，群里的人感觉比较基础，自理能力也一般，经常还在问群主一些网站登录不了怎么办的问题，GitHub 没法访问的问题。每天的题目按照数据结构的顺序在出，不过呢，几乎都没有挑战了，打算就做着每日打卡权当是查漏补缺了。

LC 的每日打卡还是要坚持打的，因为几乎可以认为是随机在跳题出来的，这样比较容易发现自己的短板的。

此外，还是应该找专题来做，集中攻破一个个点。然后，三到六个月来回顾。

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

300. 最长递增子序列 <– 传送门

这道题目是一道非常经典的基础算法题。

一个数组里包含多少个子序列呢？按照数组原有的顺序，每个元素我们可以选择删除或者保留，最后形成的序列，就是一个子序列。每个位置有“删除”或“保留” 2 种情况，所以，穷举的话，总共有 2^n 个子序列。

这些子序列的长度，从 0 到 n 不等，我们现在想求出，子序列中元素严格递增的序列，最长的长度是多少。不难得到，最短的严格递增子序列长度是 1，最长的可能性是 n。也同样不难想象，某一个长度的严格递增子序列，不止一条。

解法一，递归

我们尝试使用递归法，来设计一个算法，求解这道题。下面是推理过程：

步骤 1，递归假设。我们直接假设，可以求出长度为 n 的数组的最长递增子序列的长度，也即最终答案，用 f(n) 表示。

在这个基础上，我们来考察第 n + 1 个数，我们能否使用 f(n) 计算出来。一个数字能不能让一个递增序列的长度 +1，取决于这个数字是否大于序列中最大的数字（因为是要保持数组的原有顺序，不用考虑这个数字是否小于最小值的情况）。现有递归假设，不包含那个最大值，所以假设失败。

增强假设。我们除了能计算出最长子序列的长度，我们还能计算这个子序列的最大值。考虑到，同样长度的子序列很多个，那么这么多子序列的最大值，我们返回哪个呢？稍加思考，发现，我们可以返回这里最小的一个，记为 Xs。因为新来一个数字，只要比 Xs 大，就可以让最长子序列的长度 +1 了。

在新的假设基础上，我们考察第 n + 1 个数，如果这个数字大于 Xs，那么 f(n+1) 的最长子序列，就是 f(n) 的最长长度 +1。那么，新的最长子序列的最大值是多少呢？显然也是第 n + 1 个数。可是如果第 n + 1 个数，小于 Xs 怎么办？假如 f(n) 计算的最长子序列长度是 L，最大值是 Xs，第 n + 1 个数字小于 Xs，但是比长度 L-1 的子序列的最大值要大，就可以得到另一条长度 L 的子序列，那条子序列的最大值是第 n + 1 个数，这种情况，需要更新 Xs 为第 n + 1 个数。那还是同样的问题，如果小于又怎么办呢？还要用同样的办法再向前探索 L-2 的子序列最大值。

这一部分稍微有点点抽象，但是细想一下不难理解的。所以，我们目前的假设，还是不够强。

继续增强假设。假设我们能计算出，长度从 1 到 L 的每种长度的子序列的最大值（里面的最小的一个）。

在这个最新的假设下，考察第 n + 1 个数。通过第 n + 1 个数与整个数组的每一个数，从后往前逐个判断，就能决定是追加到最后面，还是替换其中的一个。不难证明，返回的这 L 个数字，是从小到大严格递增的（所以可以用二分法找到替换的位置）。最后这个数组的长度 L 正是最后的答案。

基于上面的推理，我们写出递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def lis(i: int) -> List[int]:
            if i == 0: return [nums[i]]
            res = lis(i - 1)
            # 以下使用二分法，确认替换的位置
            j = bisect.bisect_left(res, nums[i])
            if j == len(res): # 比最大的还大，就追加到末尾
                return res + [nums[i]]
            else:             # 否则就替换
                res[j] = nums[i]
                return res
        return len(lis(len(nums) - 1)

算法复杂度分析，每一轮递归里，问题规模减小 1，总递归 n 层，并且每层进行了一次二分查找。所以总时间复杂度是 O(n logn)。空间复杂度是 O(n)。

通过递归假设和不断增强假设，我们设计出了递归算法来求解最长递增子序列。这道题也可以很轻松写成迭代的写法，请读者自己动手完成。

解法二、动态规划

当然，这也是一道典型的动态规划的题型，可以用动态规划来求解。假设我们可以设状态为以第 i 个数字结尾的最长子序列，长度为 Li。对于第 i + 1个数字，我们可以检查每个数字 i ，如果大于它，新子序列的长度 Li + 1，这里的最大值就是以第 i + 1 个数字结尾的最长递增子序列长度。

因为，最长子序列不一定是以哪个值结尾的，所以最后整个 dp 数组的最大值就是最终答案。

写出代码就是：

1
2
3
4
5
6
7
8

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums) # 不难想象，最短的递增子序列长度是 1，当作初始值
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

该算法的时间复杂度是 O(n^2)，因为每个数字，我们都要考察前面所有的数字的情况。空间复杂度是 O(n)。

– END –

又有许久不曾写过题解了，题目一直还在做着，就是懒得写题解，主要最近家里事有点让我烦心，心绪不宁无法安心写作。今天我猛然一看，统计数字 498 了，赶快找两道简单水题，凑个整，算是突破了 500 大关。当然，这对我个人来说，或者毫无意义，总是一个付出的明证吧。

LeetCode 刷题统计

从做题结构看，还是简单题偏多，你就可以想见，这个数字还是挺水的。含金量不像数字那么敦实。花了多久做了这么多题目呢？大概可以认为是 8 个月多吧。

LeetCode 打卡热力图

其实第一次尝试刷题是 2020 年 8 月开始，只在工作日，每天做 1 道，这样坚持了一个半月，放弃了，当时刷了 100 多道吧。今年的 2 月，又开始第 2 波了，上次使用 Go 刷的，这次是用 Python 刷的。两次都重开了做题计划，所以，第二次其实是把第一次的题都又做了一遍的。即这 500 题有 100 多道我是用 Go 做过一遍的。

如何看待刷题这个事情？

刷题大体来说还是快乐的，因为简单。这话不是凡尔赛，真实的个人体会。题目都是那么纯粹，有些题甚至是为了做题而出题，就更显得纯粹。你不懂的时候，可能会让你暴躁得抓头发，那只能是你的见识太少了。因为这些题并不难，只是没见过而已。

比起生活中遇到的那些无解的困难，比起工作上的这些困境。刷题相比之下只是一个纯粹而快乐的过程。刷题不能解决我的问题，但是可以让我从痛苦的生活中逃离一小会儿，用能获得的进步给自己一点点安慰。我想这和那些沉溺在游戏里打怪的人没有太多的区别，只是这个上瘾程度有限。

刷题有什么好处？

我加过各种群，自己也有个小群，都是大家一起刷题的。大部分人比我年轻 10 岁以上。对他们来说，刷题是很实在的，因为现在找工作，想去个好点的公司，都要考算法题的。刷题最大的好处是，让大家有所准备，能够胜任 Code Challenge，获得心仪的 offer，确实还是有效的。

于我而言，只是增加了我的些许自信。毕竟刷题不是面试的全部。对我来说，更大的好处是，增加了我日常工作中解决难题的信心。我们都知道，工作中可能没有算法题，不过工作中可能会有很多很麻烦的场景。那不是说问题多困难，就是十分麻烦，我感觉刷题训练让我更加耐烦。

会让你写麻烦烧脑，容易写错，难于调试的场景时候，更有信心一点，即使写不出来，也不会气恼，删掉重写就是，这种打击在刷题的过程中早已习惯了。

刷题有什么诀窍？

没有太好的。很多同学分享经验我都看了。有几个，我觉得挺认同。刷题呢，不要纠结于非要自己做出来，刚开始很多同学就会沉溺在这个误区里。看题解不丢人。其实这是非常重要的一点，很多人比如我，很晚才领悟这一点。

刷题呢，专项密集训练效果是不错的，就是把相近题，相同考点的题，堆在一起，一顿猛刷，这样效果好。一个主题完了，再去下一个主题。不是随机拉个单子刷，那样效果不好。举个不恰当的例子吧，比如你去健身房健身。你可能会看到眼花缭乱的器械。不过你请过教练，你就会发现，那么多器械，只是少量几个跟你有关。你每次去用的器械不会超过三种。这次去，深蹲，腿弯举，腿屈伸，倒登机。全部虐腿。下次去了，高位下拉，悍马机，引体，全是虐背。刷题也差不多，这个礼拜全是位运算，下个礼拜全是动态规划。

刷题呢，也会倦怠，需要休息。我第一轮刷题，什么都不懂的，就天天随机做，当时不懂回溯，就死磕了几天回溯，连续做了十几道，然后有点感觉了。第二轮刷题，隔了三四个月多吧，我发现但凡看到题目可能可以用回溯解的，我似乎都有点感觉，写个回溯也自然了许多。可见知识技巧，需要沉淀和发酵，有时候你需要的时间地积淀。一顿猛学后，休息几个月，捡起来，反倒觉得似乎脑袋更清楚了。

刷题呢，反复做相同的题目也是有效果的。比如，你看我做了 500 题，其实这里，很多题是做了不止一遍的，其中有一道题，我看到自己有 7 次正确的提交，都在不同的日期里。有不少同学分享经验，按照一些榜单去刷，比如 Hot 100 列表啊，Top 200 列表啊什么的。还有学习专区，有很多专项，动态规划，二分法，堆等等，专项里和列表里，重复其实很高的。但是你重复做也不用担心的，你再次遇到的时候，还真的未必会做的。我们掌握的知识可能没有自己想象的那么扎实。一些很基础的题目条件反射秒写对后，你才能在一些复杂的场景下，水到渠成写出来。再举个不恰当的例子就是，你盖房子的时候，砖块水泥沙子钢筋，最后房子塌了，你怎么确定砖块的问题，还是钢筋的问题，还是你房子结构设计的问题？谁的错？最后可能是沙子用得不够。所以反复做一些基础题，做到倒背入流随手就来，你就知道你的房子砖块水泥都没问题，就是结构不对。能帮你快速排除一些错误的猜测。

我现在什么水平？

很遗憾，我还是水平很低的，就好像上面说的，我刷题的结构里，太多简单题了。就是灌水成分大了点。我现在的水平就是简单题，大多数可以想出来，中等题，我大概 70% 把握，困难题，我大概 40% 把握，也即一多半做不出。

前天晚上周六，正好没有双周赛，我就开了个模拟周赛试试。最后 1 个半小时的时候，我做对了两道。又加了 5 分钟，终于第三道做出来了。第四道我都没读题目，时间耗完了。我历史上参加过 9 次周赛，6 次我做出来 2 道，2次只做出来 1 道，还有 1 次做出来 3 道，高兴坏了，那次也是我最后一次参加周赛。

未来

刷题是需要长期坚持的，跟健身又很像，你一顿操作猛如虎，一看效果二百五。还不如细水长流，常年坚持。可能不需要很卖力，就是时不时练练，可以保持健康。在市场不断内卷的当下，保持头脑健康是很重要的。

现在我的水平已经进入瓶颈，每天这么做着也没啥长进。朋友说，你需要画个脑图一个点一个点细细去补那些漏洞了（数据结构和基础算法的漏洞，故意忽略的那些知识点），另外以前不曾踏足的领域也要逐步尝试，拓宽面，这样才可能在竞赛里做出好成绩。总之，是进入了一个边际效益很低的区段了。后续怎么做，还是要看自己的目的，想通过刷题得到什么。

– END –