Becomin' Charles

我敢说，来到 LeetCode 的人，大多数会从这道题开始，简直就是算法界的 Hello World 好不好，特别简单，直接就能做出来，自我感觉良好，可以继续了。但是，废渣如我，在这种题目上还是掉坑了，也是没谁了吧……

先来看看题目：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

53. 最大子序和 <– 传送门

一看到题目，我是懵逼的，完全不知道怎么做。我只知道穷举法，穷举完所有的子序列，并求和，就可以得到最大的值是多少。不过，当题目里出现了“最大”之类的字眼，然后，一看又需要穷举的情况，往往意味着，这道题目需要使用动态规划来求解。我们看看如果穷举的话，时间复杂度是多少，从第 0 个元素开始的子序列，有 n 个，从第 1 个元素开始的子序列，有 n - 1 个，……， 以此类推，总共 n ( n + 1 ) / 2 个子序列，时间复杂度是 O(n^2) ，很显然了。提示里说，数组长度不大于 3 万，平方一下就是 4.5 亿次求和，真穷举的话必然无法 AC 了。

复习一下动态规划的先决条件，重叠子问题，最优子结构，无后效性。我个人学习的感受是，我们往往很难写出合适的状态转移方程，其实就是不能把问题规约成规模更小的子问题。看官方题解，你总是会惊叹于，怎么会想到把子问题看成这个模样呢？我怎么想不到呢？

这个题目，我们来看看怎么解，比如我穷举总是会的：

穷举法

这个图，显示了我的穷举法，首先是第 1 个元素 4 开始的子序列，一共有 6 个，然后是第 2 个元素 -1 开始的子序列，一共有 5 个 ……

图里展示了穷举的前两次循环。然后我们发现一个问题，穷举第 2 个元素开始的所有子序列的 Sum 的计算，在穷举第 1 个的时候，又重新计算了一遍。如果，我们在计算第 2 个元素开始的所有子序列的和的时候，缓存下来结果，那么，计算第 1 个的时候，我们只要在利用缓存的结果，就可以大大节省求和的量。我们注意到，如果我们先算第 2 个元素开始的，再算第 1 个开始的，会比较容易一点。不过这需要倒序来穷举，倒也不难。

再进一步，我们目标是求最大值，是不是，只要缓存一个最大值就够了？例如图中，第 2 个元素开始的所有子序列里，Sum 最大的是 5，而第 1 个元素开始的所有子序列里，Sum 最大的显然就是 5 + 4 = 9 了。

使用缓存数组帮助求解，注意图里 i 是输入数组的下标

好，现在可以开始编写题解了。我们使用一个数组，记录第 i 个位置开始的所有子序列 Sum 的最大值，它左边，第 i - 1 个元素开始的子序列的最大值，就是再加上当前第 i - 1 个元素：

1
2
3
4
5
6
7
8
9
10

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 1:
            return nums[0]
        dp = []
        dp.append(nums[l - 1])
        for i in reversed(range(l - 1)):
            dp.append(dp[l - 2 - i] + nums[i])
        return max(dp)

从数组末尾开始，最后一个元素开始的最大子序和，就是它本身，所以，一开始我们把它加入到记录数组 dp 里（注意下标的问题，因为一开始 dp 是空的，所以第 0 个位置放的是我们想缓存的最后一个值，最后一个值的下标是 l - 1。接下来遍历的时候，为了计算第 i 个值，我们需要知道第 i - 1 个值，其下标是 l - 1 - i - 1，也即 l - 2 - i，这里有点绕）。然后，我们进行提交，就会发现，这个算法是错的。为什么呢？因为我们没有考虑负数带来的影响。

因为我们是倒着计算的，所以，每次计算第 i 个元素开始的所有子序和的时候，第 i - 1 个元素开始的所有子序和已经计算完了。我们不妨把第 i - 1 个元素开始的所有子序列，叫做第 i 个元素开始的所有子序列的后缀。那么，如果一个后缀的最大值是一个正数，那么第 i 个数加上这个后缀，一定变得更大，所以原来算法没问题。如果一个后缀是负数，那么第 i 个数加上负数后缀，就会变小，那么最大值反倒小了。这时候，最大值就是第 i 个元素本身，不用再加后缀了。

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 1:
            return nums[0]
        dp = []
        dp.append(nums[l - 1])
        for i in reversed(range(l - 1)):
            if dp[l - 2 - i] < 0:
                dp.append(nums[i])
            else:
                dp.append(dp[l - 2 - i] + nums[i])
        return max(dp)

然后我们把算法改成了这样，提交，oh yeah，这回就做对了！

到了这一步，我们心里压力已经解除了，因为题目做出来了。这个解法的时间复杂度是 O(n)。空间复杂度，也是 O(n)，因为使用了一个缓存数组。不过，我们注意到，最后我们返回了 max(dp)，意味着，其实我们只需要一个值，不必一个数组，只要始终保持最大值就可以了。另外，我们计算 dp[i] 的时候，我们还要依赖 dp[i-1]，所以我们再用一个变量记住它就可以了。

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 1:
            return nums[0]
        maxSum = preMax = nums[l - 1]
        for i in reversed(range(l - 1)):
            if preMax < 0:
                preMax = nums[i]
            else:
                preMax = preMax + nums[i]
            maxSum = max(preMax, maxSum)
        return maxSum

然后，代码被改成了这样。我们用 preMax 代替了 dp 数组，表示上一个位置的最大值，我们用 maxSum 记录了遍历过程中，出现过的最大值。空间复杂度被优化到了 O(1)。如此，我就展示了怎么从最朴素的穷举，推导出动态规划的过程。

在推理过程中，我们发现，倒序穷举的话，比正序穷举更能复用之前的计算结果。那么，我们现在是缓存了第 i 个元素开始的最大子序和，如果逆向思考一下，我们改为缓存第 i 个元素结束的最大子序和，代码会是什么样子呢？您可以自己写一下试试。

这个题目其实可以说是很多算法比赛训练的入门题目了，我一早就知道。

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

提示：

num1 和num2 的长度都小于 5100

num1 和num2 都只包含数字 0-9

num1 和num2 都不包含任何前导零

你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式

415. 求两数之和 <– 传送门

先来看题目的描述：

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

3. 注意空字符串可被认为是有效字符串。

20. 有效的括号 <– 点此传送

主要就是判断这个括号是否配对，麻烦点就是有三种括号，这个题目，直觉上，就是需要用到数据结构——栈（Stack），但是我好像不是很熟悉，在 Python 里，栈这个数据结构怎么写，应该是用个类库或者语言自带的某种数据结构来实现。这里暴露了我不熟悉 Python 的数据结构这件事情。

所以，我想到了，我先用递归算法，把这个问题给解决掉，然后，再看答案学习这个栈怎么用好了。这个题目显然具备某种递归结构，我们在整个串里搜索第一个配对的括号，然后去掉这一对括号后，剩余的字符串，应该仍然是合法的字符串，找不到，或者剩下的字符串不合法，那就一定是不合法的。

另外，如果整个串是合法的，至少有一对连续的两个字符，正好是配对的。于是我的算法就是先找到这一对挨着的，然后去掉，递归判断剩下的。

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

class Solution:
    def isValid(self, s: str) -> bool:
        if s == "" :
            return True
        mapping, i, l = {'(':')', '{':'}', '[': ']'}, 0, len(s)
        while i < l:
            if i + 1 < l and s[i+1] == mapping.get(s[i], ""):
                left = s[:i]
                right = ""
                if i + 2 <= l:
                    right = s[i+2:]
                return self.isValid(left+right)
            i += 1
        return False

做对题目后，我看了题解，原来 Python 的 stack 就是最简单的用 list 实现的，真是方便啊：

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

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {')': '(', '}': '{', ']': '['}
        stack = []
        for c in s :
            if c in mapping:
                top = stack.pop() if stack else '#'
                if mapping[c] != top:
                    return False
            else:
                stack.append(c)
        return not stack

知识点：

1. Python 的栈可以用 list 实现，压栈操作是 append，出栈是 pop；
2. list 变量可以直接在 if 条件中判断是否为空，空 list 为 False；
3. key in dict 语句，可以直接判断一个字典是否包含某个 key；

世上许多重要的转折是在意想不到时发生的，这是否意味着人对事物发展进程无能为力？请写一篇文章，谈谈你对这个问题的认识和思考。这是今年高考，上海卷语文作文题目。

看到这个题目的时候，我正好在重温计算机系统的基础知识，重新学习了 Amdahl 定律。这个定律讲的是，在一个系统中，如果我们改善了系统的一个部分的性能，那么整个系统的性能改善，会被这个被改善部分在整个系统中重要性占比给削弱。

昨天，我在一台 CentOS 6.10 上面编译 PHP 7.4.7 和编译前几个版本有很大的区别，PHP 7.4 开始使用了一个叫 pkg-config 的东西，有点先进，但是在老旧的系统上，真是无比痛苦的一个体验。

今天我尝试一下在 CentOS 7.8 上面编译一下，之前没有干过，我就记录一下过程，虽然无聊得很，但是记录下来，可以给以后节省点时间。

话说，不作死就不会死。

上一篇文章讲解了怎么老旧的 MacBook Pro 重新安装 MacOS 操作系统，我安装成功了，但是跑了一会儿以后，我发现我犯了一个严重的错误，我还是把固态硬盘当作了启动盘来安装系统。

当年，我自己动手，拆掉了 MacBook Pro mid 2009 的光驱，使用光驱位硬盘盒给自己扩展了一块 SSD 固态硬盘，镁光 M4，现在 10 年过去了，我自己密集使用了两年，转送老爸又用了两年多，然后又放了好几年，这块硬盘的可靠性已经是 0 了，就在上篇文章写完，我装成功 MacOS 后，运行不到 30 分钟，我发现 System Preferences 这个 App，也就是系统设置，无法正常打开了。虽然不知道哪里坏了，我猜就是硬盘，另外我想启动个 SSH 服务，发现也连不上去…… 当然了，这不能怪硬盘，还是我自己没设置对，可是设置 App 又不能正常运行，一怒之下关机拉倒了，懒得琢磨了，又萌生了再安装一次 Linux 的想法，不折腾不作死，就不会死啊。

话说，不作死就不会死。

我的第一台 MacBook Pro，是一台 2009 Mid，真是有年头了，后来我换了电脑，就给了老爸，后来我又换了电脑，就把第二台给了老爸，老爸说第一台也没用了，还你吧，于是我现在多了一台闲置的 MBP 出来，还是 2009 Mid。

我之前就在家里跑了个树莓派 1 代，挺 Happy，想着，用 MBP 这逆天的性能，跑个 Linux，岂不是无敌了，于是开始了我作死之旅。

写这个话题，我是忐忑的，因为我讲不清楚，其实比我一开始以为得要复杂一些，不过，迫于压力，我还是得尝试去说清楚这个问题，如果看到不对地方，希望读者可以不吝赐教，谢谢～

之前写了一篇文章讲《什么是 POS 机》其实也没讲清楚，不过说了个大概。清分这个问题，首先涉及到银行卡收单这个业务，是否可以衍生到网络支付上面，我还没有想得很清楚。不管如何，我们可以从银行卡线下收单业务来看这个问题的性质。

简化情况下的一清和二清的区别

什么是一清

申请 POS 机的，在交易流程里叫特约商户，一般特约商户在收单机构注册开户，然后，安装 POS 机，持卡人刷卡后，通过 POS 机将交易上送到收单机构，再从收单机构通过清算机构发往发卡行，如上图左侧的蓝色线条，这个蓝色线条，叫交易的信息流。发卡行确认信息后，通知收单机构，然后反馈给 POS 机，持卡人就看到了交易成功。

这个时候，特约商户，也就是零售的卖家，其实还没有收到现金。但是因为交易已经被确认，所以，这次购买销售行为可以正常完成。一般清算机构，每天会进行一次日终清算，通过清算，资金会划拨给收单机构，然后收单机构再划拨给特约商户，所以 POS 机经常就是 T+1 到帐的，这我们在《什么是 POS 机》也提到了。

什么是二清

我们再来看看什么是二次清分，看上面图的右边，有一些特约商户，申请到 POS 机以后，再向收单机构申请增机，然后这家商户就有很多台 POS 机，然后将增设的 POS 机租给更小的商户，当完成清算后，钱都会被结算给同一个特约商户，这家商户再通过支付的信息，将资金结算给租用 POS 机的商户。完成一个二次的清分。特此说明一下，二次清分在当下是违规行为。

上面不难看出一个问题，就是 POS 机 理论上都是直接向收单机构去上送交易信息的，那么二次清分机构是怎么做到二清 POS 机 展示正确的商户信息，以及怎样在二次清分时候，做到正确分账呢？

POS 机的安装部署和线下拓展商户，都是一个繁重和细致的工作，也有很强的地域性，所以，收单机构，不一定可以自己经营所有的线下商户，就不得不依赖代理商，代理商很多都是 POS 机设备的生产厂商，注意，他们没有收单的资质，但是生产一台电子设备是合法的。这里，二清机构其实很多都是 POS 机设备的代理商，或者跟 POS 机代理商合作。

这里一个显著的风险点就是，二清机构，并不持有支付牌照，也不受监管，如果捐款跑路，就给租用 POS 机的商户带来很大的风险。

以上说得，都是比较简单的二次清分，比较形象，具体，容易理解。其实真正的二次清分，不是这么定义的。上面的案例，集中在二清清分机构，获得了下属机构的资金，然后二次划拨资金，对资金安全产生了很大的危害。

信息二清

于是，就产生了一种新的形态，二清机构说，我不把下属客户的资金拿到我自己的账上，不碰资金，是不是就行了？于是，产生了二清机构和持牌收单机构合作，在持牌收单机构的账户内，开设虚拟账户，将二清机构的待结算资金停留，通过二清机构的指令（清算依据），直接从收单机构的账户，结算给下属的商户。

这种情况，看起来，资金已经不是从二清机构的账户上结算给下属的商户账户了，但是，在当前，这仍然构成了二次清分，也是央行重点禁止的业务。这里比较重要的一个界定标准，不是资金从哪个账户流出，也不是资金受谁控制，关键在于，谁可以事实上决定的资金的流向，第二种模式，也被业内叫做是“信息二清”，现在的一个趋势是，“资金二清” 也好，“信息二清” 也好，都被称作二清，都是监管打击的对象。

虽然，不合法，但是市场上还是非常需要二清这个方案，这是为什么呢？抛开一开始就诈骗、套现抱有恶意动机的行为不看。合法经营的是否需要二清？

二清存在有其刚性需求

依据我个人的理解，信息中介型的企业，都潜在有二清的使用场景。我们常见的案例是电商平台。电商平台本质上是一种信息中介行为，这种平台往往相比于单个电商卖家，有更多的客户，所以，电商卖家更希望通过平台来获得客户，形成交易。

电商平台的建立，能提供一个虚拟的规模化的交易市场，上面入驻的商户，一般都依托平台的支付体系，所以往往就是消费者把钱先划转到了电商平台的账户上，再由平台结算给每个入驻的商户，这就构成了事实的二清。

我们再抽象点来看，一个信息中介，掌握着交易双方一方的资源，或者两方资源。这是中介赖以生存的核心优势，肯定不愿意将自己的资源直接输送给另一方，必然是愿意自己经营一个平台（市场），让双方在上面完成交易。这个平台不可能允许每个参与者自带一套支付体系，这样对买方极其不友好，而且，不掌握交易数据，对中介方来说，也不能建立长期有效的竞争壁垒。

所以，最后，这个商业模式都会导向二清这个行为。中介方有很强动机掌握交易的具体信息，完成资金的清算结算。所以，抛开违法的部分看，二清有其存在的必然需求。

国家现在打击二清，当然是整顿了市场，规避了系统性风险和信息安全，但是一种很有活力的商业模式，也受到了发展的制约。从长远看，是不能持久的，现在市场上就在提出各种各样的二清解决方案。本质上，需求还是刚性的，大家还在想各种办法来在监管的夹缝里求生存。

不过，终究不是长远的解决办法，还是希望监管政策层面，能推出比较明确的细则，区分对待，让正常做生意的人，有个出口。

POS 的英文是 Point of Sales，字面意思是销售点，百度百科也说是“销售点情报管理系统”，本质上来说，是一套系统，有很多的组成部分。

POS 系统

这套系统，大家见得比较多，主要用于零售点的收银，是零售业门店管理的重要组成部分。

这里面融合了库存，价格，收银，出纳等等功能。基本原理是这样的，门店的商品和信息被录入到系统中，然后需要一个条码读取器，可以扫描商品，统计订单金额，然后生成收银请求，配合银行卡读卡器，完成交易（无现金），也可以弹出一个抽屉，完成现金交易的收钱，找零等。

不过，咱们一般提到 POS 机，指的都是桌上那个小东西，就是 POS 刷卡机。因为这个东西能够从银行卡进行扣款转账，是一次销售行为中最重要的部分，所以刷卡机就往往被称作是 POS 机了。当然，众所周知的，也可以脱离开这个场景使用 :) 具体用途就不解释了。

POS 刷卡机，简称 POS 机，背后对应的业务，专业上叫银行卡线下收单业务。主要是银行类机构，以及第三方支付公司（又称非金融机构）经营的业务。对银行来说，不是主要的业务，但是对第三方支付公司来说，是主要经营的一种业务。

POS 机的持有者，专业上叫特约商户，一般来说，是一个零售型企业。他们为什么要安装 POS 机呢？主要是因为顾客是上帝，顾客更喜欢使用 POS 机进行支付。顾客在专业上叫持卡人，主要持有银行机构发行的储蓄卡，信用卡。银行机构，在这个场景里，叫发卡行。POS 机的作用就是从发卡行发行的卡账户上，将资金扣转并转移到特约商户的账户上。

如果，持卡人持有的卡，不是本行发行的卡，那么需要通过跨行结算组织，完成跨行资金结算，这个跨行结算组织，就是银联。

对于银行来说，去对接海量的线下零售型商户，显然是一个低效益并且也不可能完成的任务，所以，更多的 POS 线下收单业务，都由第三方支付公司经营。第三方支付公司，需要持有经营此项业务的牌照，也就是支付牌照。

对于第三方支付公司来说，经营 POS 线下收单业务，是其特许经营的业务，需要处理好与各种银行机构或者清算组织的业务，以及保障好交易的安全。拓展线下商户的任务，对其来说，是一个低效益的事情。所以，这里又出现了一个角色，就是代理商。

代理商的主要业务是，拓展线下商户，安装和部署 POS 机，维护客户的关系。代理商公司，不具备经营线下收单业务的资格，也即没有支付牌照。所以，其业务得以开展，主要还是依托支付公司的牌照。通过通信技术和计算机系统，完成与支付公司的对接，并在自己的信息系统上管理海量的特约商户客户。

因为涉及到跟清算组织的连接，所以，第三方支付公司的结算，也要符合清算组织的规则，所以，往往，POS 机都是 T+1 结算的。这主要受限于银联的业务规则。当然，这体验不好。于是，代理商公司为了优化自己客户的体验，就想出一个办法，自己设立一家特约商户，然后，生产很多 POS 机，然后把这个 POS 机分发给自己的客户商户，这样客户商户不需要跟支付公司签约，支付给每个商户的钱，都会支付给代理商公司，这个代理商公司再根据每个订单，把钱分给客户商户。这个过程就叫做“二清”，是二次清分的意思。

在二清的场景下，第三方支付公司会把所有的订单支付都结算给代理商公司，然后代理商公司再次把钱分给底下的商户。这里，如果代理商公司，垫付一笔资金，就可以先行将资金垫付给商户，然后等 T+1 的时候，支付公司自然会结算这笔钱。这就优化了客户的体验。

当然，这里存在巨大的安全隐患，如果代理商公司不给客户商户结算，自己拿着支付公司结算的款项跑路，这就带来了巨大的风险。所以，二清是不合规的。对于特约商户来说，如果安装使用了二清的 POS 机也是有巨大的风险的。

使用 POS 机进行收款，是需要支付手续费的。手续费的主要分成方是发卡行，银联，第三方支付公司，以及代理商。手续费的费率是不一样的，到了特约商户这里，可能各不相同。就是因为这里面，第三方支付公司，或者代理商有一定的费用融合在里面，尤其是代理商，其不是金融机构，不接受监管。费用的设置，主要是依赖市场竞争来调节。所以特约商户拿到的 POS 机费率各不相同。各个行业也有不同，一般消费类的场景，现在的行情是 0.6% 左右，如果特别低，可能存在猫腻。

以上知识，主要来自搜索、知乎，不确保准确无误。下面附上一幅图解释一次 POS 机刷卡的业务流程，原图来自网络，不清楚，进行了重绘。

一次完整的POS机刷卡流程

上图中，蓝色的线条代表信息流，红色的线条代表资金流。绿色的是参与方。收单行，也叫收单机构，可以是银行，也可以是第三方支付公司。商户在收单机构处开设有结算账户。如果收单机构是银行，则结算账户本身就是银行账户，但是也极可能是专用的。如果是第三方支付公司，则结算账户可能是某种虚拟账户，在第三方支付公司的托管系统中。从结算账户到商户的一般企业账户，可能还需要一次提现，在图中都被省略。

图中清算账户管理系统是个比较神秘的系统，我猜可能是银联这样的清算组织管理各方结算账户的系统。值得一提的是，这个图里说明，从收单行进行大额清算结束后，再把钱清算到商户的账户，使用的是央行小额系统完成的。对这一点，并没有进一步的信息以印证，大家就看个意思就行了。