Becomin' Charles

算法 | LNMP | Flutter | Mac

Becomin' Charles

发表于 分类于 本文字数： 192 阅读时长 ≈ 1 分钟

这道题目，我直接想到的就是双指针算法了，一个指针从头往后找，一个指针从后往头找，然后找到元音后停下来，然后，交换，继续循环。

关键是循环终止的位置，应该是头尾两个指针碰到的时候。我就写出了这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def reverseVowels(self, s: str) -> str:
        ss = [ x for x in s ]
        i = 0
        l = len(ss)
        j = l - 1
        vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        while i < j:
            while i < l and ss[i] not in vowels:
                i += 1
            while j > 0 and ss[j] not in vowels:
                j -= 1

            if i <= j:
                ss[i], ss[j] = ss[j], ss[i]
                i += 1
                j -= 1
        return "".join(ss)

我先把字符串转换成了 list，因为我发现字符串里的字符不能更改，记得 Python 的 string 是 immutable 的。所以换了。

这个算法的复杂度理论上是 O(n) 的，不过在尾指针那里，往头部找元音的时候，如果最坏情况，可能会是重复搜索，可以增加一个条件，就是 j >= i 避免无畏地搜索。

发表于 分类于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

从 Git 出来，到我逐渐用上，过去了多年，我搜了一下，这个博客上竟然写了很多关于 Git 的文章，于是我打算做个合集，把关于 Git 的内容汇总一下，便于大家查看。

《签名你的每个 Git Commit》

Git 有个功能，可以对每次的 commit 进行签名防伪，GitHub 上会为这样的 commit 展示一个 Verified 标签，这篇文章介绍了，如何在本地配置 GPG key，并配置 git 来实现给每一个 commit 签名。

《[Git]分支的意义》

介绍了我对代码版本控制过程中，分支的理解，也谈及了一些 Git 分支的优势和用法。

《git术语解释staging，index，cache》

Git 文档和书籍里面多次出现了 staging area 这个属于，而 git 的命令行参数里也有 index 和 cache 的字样，如果不弄清楚这三个概念的意思，就始终觉得模模糊糊的心里不通透，于是我在网上各种搜，找到了这几个概念的缘由，记录在这篇文章里面。

《我为什么更喜欢用 git》

这篇文章介绍了我爱 git 的几个理由。在 git 早期的时候，还是有不少人没有切换过来的。现在基本已经全民 git 了。可能这篇文章就不那么有意义了。

《SVN 为什么比 git 更好》

在 git 出现早期，各个大公司还没有跟进，还在普遍选用 SVN，而整个程序员群体，也还没能熟练使用 git，而 git 本身也不像现在那么完善，对应的工具链也好，研发管理流程也好，都还不成熟，那个时候，我更推荐小团队或者创业公司选用 SVN，因为有更少的管理成本而人员摩擦，小团队找不到高素质的人，SVN 的多年成熟，市场上的程序员普遍会用。不过，中文互联网圈的人看了我的文章，说我在一本正经地胡说八道。其实你一个人开发，爱用什么用什么，当你组织团队生产的时候，你不得不降低自己的标准，因为不可能所有人都有相同的理解力和执行力啊。

《[Git] 如何批量删除远程的tag》

遇到这个问题是因为我们的研发流水线使用一个图形化界面的上线系统。这个系统每次需要用下拉列表展示待上线的 tag，我们是用 tag 管理线上版本的。结果因为天长日久积累了太多的 tag，导致这个下拉列表渲染极其缓慢。Gitlab 的 tag 页面也都展示不正常了，不得不去删除一些 tag 来解决问题。

《[Git]代码提交》

这篇文章用文字描述了 Git 代码提交的过程，以及在 Git 里提交代码时候的一些概念。此外，还对比了 Git 与 SVN 的不同。

《[Git]使用 Git 的第一个任务》

使用文字介绍了使用 Git 时候，你将会接触到了第一个命令 clone 的一些用法和解释。并且把 clone 与 SVN 的 checkout 命令进行了比较，分析了两者的异同，帮助读者理解这个 git 特有的概念。

《[Git]Git是什么？Git不是什么？》

本文是对版本控制工具 Git 的简介。

《[Howto]在Git中怎么回滚》

本文介绍了在 Git 中，怎么回滚变更。因为在 Git 中，代码所处的状态有很多种，所以，从每种状态中，回滚代码的操作都不一样。更为关键的是，理解每种状态的原理和设置原因，才能用正确的命令去回滚它们。

《[How To] 使用Git的时候，如何撤销本地更改》

介绍了一个基础操作，怎么撤销本地的更改。

《分布式版本控制系统Git入门 》–（1）（2）

尝试从 0 开始介绍 Git 版本控制系统的使用，似乎当时想写一本介绍 Git 的书来着，然而，并没有坚持下去，就也放在这里吧。这篇精华帖子看，我还是写了很多内容的，凑齐来也差不多够本小书了。

《我们为什么需要版本控制系统？》

直击灵魂的根本性问题，我们到底为什么需要版本控制系统？VCS，被发明出来的根本原因，我们为什么需要保持代码的多个版本？因为长久以来这就是一个毫无疑问要遵守的惯例，以至于我们根本想不起来是什么原因了。这个篇文章为您解惑。

发表于 分类于 本文字数： 192 阅读时长 ≈ 1 分钟

今天的题目是矩阵的转置。题目懒得抄了，帖个图吧。

矩阵转置示意图

其实，例子里这个图给得不是很好的，因为这正好是一个特殊的矩阵，叫方阵，行和列是一样多的，实际上，我们遇到的矩阵未必是方形的。

其实矩阵转置根据直觉做就可以了，没什么难点。核心就一句话：

result[j][i] = matrix[i][j]

什么意思呢？就是把某个元素的二维下标两个下标交换一下位置。所以，我写了下面这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len( matrix )
        n = len( matrix[0] )
        result = []
        for i in range( n ):
            result.append( [0] * m )
        
        for i in range( m ):
            for j in range( n ):
                result[j][i] = matrix[i][j]
        
        return result

先测量长度，然后生成结果矩阵，然后逐一遍历，然后交换下标。打完收工。时间复杂度是 O(m・n)。

发表于 分类于 本文字数： 203 阅读时长 ≈ 1 分钟

给定一个排序数组，要求把重复项删掉，然后返回新的去重数组的长度。要求空间复杂度 O(1)，其实发现一个重复的，就把后面的挪上来。这个题目直觉上就没有什么特殊的，硬做：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0 or l == 1:
            return l
        r = 0
        p = r + 1
        while p < l:
            if nums[p] != nums[r]:
                nums[r+1] = nums[p]
                r += 1
            p += 1
        return r + 1

我写出了这样的方法，就是第一个指针指着开始位置，第二个指针指后面一个，然后往后挪第二个指针，如果遇到不重复的，就拷贝到第一个指针后面一个位置，遇到重复的就一直往后挪第二个指针。

提交后，这个算法通过了。看了题解，这个方法叫双指针。前面一个叫慢指针，后面一个叫快指针。

知识点：

  1. 数组；
  2. 双指针算法。

发表于 分类于 本文字数： 2.1k 阅读时长 ≈ 8 分钟

这是一道打卡题，没想到难度是“困难”，每次看到红色的“困难”，我还是菊花一紧的，感觉很多脑细胞要死亡了。

题目规则很简单，就是大信封能套小信封，然后，问最多能套多少层。信封用 [w, h] 来标记宽度和长度。比如在宽度和长度都更大的前提下才能套入。

因为有两个维度，就显得有些复杂，我的第一个直觉就是排序。至少先按照其中一个维度比如宽度，进行排序。完事后，对长度开始穷举。穷举自然就是回溯法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        self.envelopes = sorted(envelopes, key = lambda x : x[0])
        self.l = len(envelopes)
        if self.l < 2:
            return self.l
        self.visited = [0] * self.l
        self.max_env = 0
        self.dfs(0, 0, 0)
        return self.max_env

    def dfs(self, start: int, maxW: int, maxH: int):
        if start == self.l:
            self.max_env = max(self.max_env, sum(self.visited))
        else:
            for i in range(start, self.l):
                env = self.envelopes[i]
                if env[0] <= maxW or env[1] <= maxH:
                    continue
                self.visited[i] = 1
                self.dfs(i + 1, env[0], env[1])
                self.visited[i] = 0
            self.max_env = max(self.max_env, sum(self.visited))

我写出了这样的代码，回溯的时候，用一个状态组记住一个信封有没有被套入，用 maxW 和 maxH 记录套到此时此刻，最大的 (w, h) 是多少，这样好判断下一个能不能套。因为要严格递增，w 又是有序的，那么我们可以把那些 w 相等的信封跳过，相当于剪枝了。所有信封都检查过，或者后面已经没有任何满足条件的信封时，就搜索到了结局，visited 里用到的信封总数，就是最长值。

第一个信封选择，理论上有 N 种，而第二个信封选择，理论上有 N - 1 种。只有 w 值相等时候才能剪枝。这就看出来，上面的算法，时间复杂度是 O( n! )。果然是无法 AC 的，超出了时间限制。

我的智慧估计就到这里了，能写出来不错了，还没有能力想到更短的算法。然后看了官方解法。我们设想，w 有序后，我们彻底摒弃 w 这个维度的影响，单纯看 h 这个维度的影响，应该怎么做呢？其实就是求剩下 h 的序列里，最长严格递增子序列。但是，这里其实有个问题，就是如果在 w 值相等的情况下，h 的最长严格递增子序列长度是错的。解决方法也很简单，在 w 相等的时候，h 按降序排列，就好了，这样就无法形成严格递增子序列了，只能在 w 不同的情况下增加子序列长度。

到了这一步，就可以设计一个动态规划的算法，其实，这里也是递推法。状态怎么转换的呢？第 i 个状态，就是前 i 个数构成的最长严格递增子序列长度。这时候，新来的第 i + 1 个数，就要去和前 i 个数里的每个数去比，如果更大，就能得到一个比当前这个状态长 1 的子序列，这里最大的一个，就是第 i + 1 个状态的值。太绕了，举个例子：

对于一个序列 6, 5, 1, 2，第 1 个状态是 1，一个数字的子串长度只能是 1，第 2 个状态是 1，因为 5 比 6 小，所以这两个数字构成的最长递增子串长度还是 1，以此类推，第 3 个还是 1，第 4 个是 2，因为 2 比 1 大，所以可以构成一个 2 个数字的递增子串，此时的状态数组就是 1，1，1，2。设想，现在下一个数字是 7。7 比 6 大，所以能构成 2 个数字的递增子串，对于后续的 5 和 1 来说也是如此，但是对于 2 来说，之前 2 已经可以构成一个长度为 2 的子串了，这时候来了 7 就能得到 3 个数字的最长子串了，所以下一个状态的值是 3。扫描到 7 的时候，状态数组变成了：1，1，1，2，3。基于这个原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        self.l = len(envelopes)
        if self.l < 2:
            return self.l
        
        def cmp(x, y):
            if x[0] < y[0]:
                return -1
            elif x[0] > y[0]:
                return 1
            else:
                if x[1] < y[1]:
                    return 1
                elif x[1] > y[1]:
                    return -1
                else:
                    return 0
        self.envelopes = sorted(envelopes, key = functools.cmp_to_key(cmp))

        dp = [1] * self.l
        for i in range(self.l):
            for j in range(i):
                if self.envelopes[j][1] < self.envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

忽略上面乱七八糟的 cmp 函数，就是为了排序而已。关注 21 - 25 行。就是上面说的推导下一个状态的过程。这里算法，我们可以看到，每扩展一个新状态，需要扫描前面 n - 1 个状态。所以，时间复杂度是 O( n^2 )，这比起 O( n! ) 已经好了很多了。然而，悲摧的是，仍然不能 AC，还是超时，我看了这次超时的用例，更长了～

这个递推法比回溯法优秀到哪里了呢？其实在回溯法里，每出现一个子串，我们不但计算出了子串的长度，还计算出了子串的排列。visited 数组就给出了哪几个信封够成了该子串。而这本是没必要算出来的。在递推法里，我们只关心能构成的子串中长度最大的那个的长度是多少，其他都不关心了。所以节省了很多。

再来看最后一个解法，官方解法的说明，说实在的太抽象了，都是用的代数，我看不懂。我自己想了个。我们朴素来想想，如果我们想要套得更多层，到底怎么挑选信封比较有效呢？比如第一个信封是 (w:1, h:1)，这时候第二个信封有两个选择(w:2, h:5)和 (w:2, h:2)，你选哪个呢？不傻的话，都会选后者吧，因为 h 更小，意味着将来可以被下一个信封套进去的概率更大。

这个新的动态规划算法，状态这样设计的，假如，我想组成一个层数为 i 的套娃，那么用到的最小的那个信封高度，记为第 i 个状态值。注意这个算法仍然建立在 w 已经是升序，而 h 是降序的基础上。这时候，新来一个信封。如果它的高度，比 i 大，那只能套在 i 的外面，其高度变成第 i + 1 个状态。如果其高度比 i 小的时候呢？注意我们的策略，组成一个套娃的时候，尽可能选满足条件最小的一个信封，将来套入新信封的概率才会变大。所以，如果其高度比 i 小的话，理论上我们应该把第 i 个状态的值调小，也即没有扩展新状态。不过，我们真应该更新第 i 个么？如果前面还有比这个值大的呢？那这个肯定是套不上去的，所以得往前找一个位置，正好是前一个状态比它小，后一个状态比它大，然后把比它大的那个给更新了。这个位置可以用 二分查找 来搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [envelopes[0][1]]
        for i in range(1, n):
            if (num := envelopes[i][1]) > f[-1]:
                f.append(num)
            else:
                index = bisect.bisect_left(f, num)
                f[index] = num
        
        return len(f)

于是，我们得到了这个算法，这是我抄的，不是我自己手撸的。我们可以看看这个算法的复杂度是什么，排序是 O( n logn )，二分查找是 O( logn )，所以动态规划的过程，复杂度还是 O( n logn )，总的时间复杂度是 O( n logn )。比上一个算法又进步了。

那么这个算法到底节省了什么东西呢？上一个算法里，出现了 i 个数字的时候，我们记录了每个数字能组成最长子序列长度。还拿那个 6, 5, 1, 2 来举例，其状态数组是：1, 1, 1, 2。这里我们看到，6，5，1 三个数字，其能形成的最长子序列都是 1，被记录了 3 次。其实，6 和 5 如果能跟后续新出现的数字，比如 7 ，组成更长子序列的话，1 也一样可以，因为 1 更小，适应性更强。在新算法里，我们就把 6，5 的状态值，都给抛弃了，只保留了 1。这样，如果新出现一个数字的时候，显然我们需要遍历的状态就更少了。于是将 O( n^2 ) 节省到了 O( n logn )，终于 AC 了。

问题总结：

第一，我对 Python 的排序还是太不熟悉了，查了文档，还是写出了那么 Ugly 的排序，其实 List 自己就有 sort 方法，而且，对于 List 是有默认多级排序的，不用自己写 Comparator，尤其我还不熟悉 Python3 怎么利用 Comparator；

第二，才知道，还有个类库 biset，可以直接二分查找，比如这个题的考点不是写二分，完全可以直接用现成算法，来集中注意力研究场景。

发表于 分类于 本文字数： 345 阅读时长 ≈ 1 分钟

题目简述一下，就是给定两个升序有序链表，然后合并它们。

昨天看到这个题目，我的大脑一片空白，其实这个题目没什么难的，就是单纯地考察对一个数据结构链表的掌握程度，单链表。

太久没有写了，真的写不出，我就看了答案，意思我是完全知道的，但是就是写不出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = ListNode(-1)

        point = result

        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l2.next
            point = point.next
        
        point.next = l1 if l1 is not None else l2

        return result.next

以上是看完答案默写的，首先是声明两个新的指针，一个指向最后结果的链表头，另一个是用作游标，然后就是迭代，注意看里面 next 也是一个指针，也利用到了。

这个题目还可以写出其递归算法，其具有的递归结构是这样的，在给定的两个链表里，找到一个最小的节点后，去掉这个节点，剩下的问题跟原理的问题是一致的，递归调用原来的解法就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        result = ListNode(-1)
        if l1.val <= l2.val:
            result.next = l1
            l1.next = self.mergeTwoLists(l1.next, l2)
        else:
            result.next = l2
            l2.next = self.mergeTwoLists(l1, l2.next)
        return result.next

先找到最小的节点，然后，把剩下的递归解决。写完看了下，发现 result 是完全多余的，去掉也可以。就跟官方给的题解一样了。

知识点：

  1. 链表的数据结构的特点；
  2. Python 里一个类变量是引用类型的；
  3. 可以用 is None 和 is not None 这样的运算来判空。

发表于 分类于 本文字数： 318 阅读时长 ≈ 1 分钟

今天的打卡题，我一看，是一道“中等”难度的题，心里一咯噔，一般我不太能做出来的。不过细看了一下还好，今天的题目，我刚好会做，这个是一个二维矩阵的题目，给定左上角和右下角的座标，求框定区域内的数字总和。

题目提示是会多次查询，其实就是提醒你，不要用两层循环去做，因为那样单次计算的时间复杂度是 O((row2 - row1 + 1) * (col2 - col1 + 1))，相当于 2 次多项式时间。那么我们的做法，唯有事先做一次字典，然后每次去查表，我们用一个和 matrix 同等维度的二维字典，每个元素存储的值就是矩阵对应位置的到左上角，也就是（0，0）这个二维区域内的数字总和。

就是计算上图中黄色的区域的面积

那么，计算指定区域面积，就成了一个O(1)的算法。如上图，就是计算图中黄色区域的面积，等于整个彩色区域面积，减去蓝色，减去红色，加上左上角暗红色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.matrix = matrix
        self.sumdict = []
        for i in range(len(matrix)):
            sumcol = 0
            coldict = []
            for j in range(len(matrix[i])):
                sumcol += matrix[i][j]
                tmp = sumcol
                if i > 0:
                    tmp += self.sumdict[i-1][j]
                coldict.append(tmp)
            self.sumdict.append(coldict)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = self.sumdict[row2][col2]
        sum_up = 0
        sum_left = 0
        sum_up_left = 0
        r, c = 0, 0
        if row1 > 0:
            sum_up = self.sumdict[row1 - 1][col2]
        if col1 > 0:
            sum_left = self.sumdict[row2][col1 - 1]
        if row1 > 0 and col1 > 0:
            sum_up_left = self.sumdict[row1 - 1][col1 - 1]

        res = res - sum_up - sum_left + sum_up_left
        return res



# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

我写出了如上的算法，一次提交就过了。心情不错:)

发表于 分类于 本文字数： 516 阅读时长 ≈ 2 分钟

这个题目要求，编写一个函数，查找输入的字符串数组的元素的最长公共前缀。所有的元素都是由小写字母组成的。

这个题目，初一看，就是一个两重循环的遍历算法。每个字符串的每个字母，一个一个比较过来就可以了，最自然的算法就是，第一个字符串的第一个字母，和第二个字符串的第一个字母，……，一直到最后，如果都一样，就找到了第一个前缀字母，以此类推，一旦遇到一个不一样的，循环就结束了。

这个算法两重循环，显然复杂度是字符串的长度乘以字符串的个数 O(mn)。我写出了这样的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        l = len(strs)
        if l == 0 :
            return ""
        if l == 1 :
            return strs[0]
        common = ""
        for i in range(len(strs[0])):
            for j in range (len(strs)) :
                if i >= len(strs[j]) or strs[j][i] != strs[0][i] :
                    return common
            common += strs[0][i]
        return common

这个算法是正确的，已经被 Accept 了。我看了题解，我这个叫纵向比较，还可以横向比较，就是前两个串的最长公共串，再去和第三个比较，计算公共串，一直计算到最后一个。叫横向比较。

看到横向比较的算法，我就很容易发现这个题目的递归结构，这个问题可以递归解决的。N 个字符串的最长公共前缀，是 N - 1 个字符串的最长公共前缀和最后一个字符串的公共前缀。于是我们可以写个递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        l = len(strs)
        if l == 0 :
            return ""
        if l == 1 :
            return strs[0]
        common = ""
        sub = self.longestCommonPrefix(strs[1::])
        for i in range(len(sub)):
            if i >= len(strs[0]) or strs[0][i] != sub[i]:
                return common
            common += sub[i]
        return common

这个算法也是正确的，但是并没有更简洁一点 [捂脸笑着洒泪…… 就是意识到这个问题是递归结构的，就尝试一下写出其递归的算法，递归算法的时间复杂度，并不会更优秀，这个题目的问题在于，最小化子问题的解决编写起来和遍历解决，并没有什么显著的差异，所以递归算法并不显得简洁。仅作为一种练习吧。

知识点：

  1. 递归思想
  2. Python 的类方法怎么递归，需要使用 self 才能递归调用

发表于 分类于 本文字数： 2k 阅读时长 ≈ 7 分钟

前面花了很多篇幅去讲了 IoC 这个概念的问题，最后，还是要落实到实现上。通过分析和推理，我们了解到 IoC 的本质还是为了解耦和复用，而这个核心，最后落实到而组件和对象的创建和组装上面。

《什么是 Inversion of Control？》

《为什么需要 Inversion of Control？》

了解了这些，就不会“乱花渐欲迷人眼”，无论是 Spring 强调的 IoC Container 也好，还是 Martin 老爷说的 Service Locator，Dependency Injection，其背后，目的是统一的。无非是手段是多样的。那么，我们只要逐一去了解这些手段即可。

阅读全文 »

发表于 分类于 本文字数： 584 阅读时长 ≈ 2 分钟

这个题目特别长，I 代表 1 ，V 代表 5，X 代表 10 ，以此类推，输入一个罗马数字，怎么转换成整数，这里比较难处理的就是 4 和 9 ，40 和 90 …… 等的表达。

这道题，一看就有点让人不想动手做，其实没有丝毫难点，但是很繁琐和琐碎。但是，考虑到自己立下了一天写一道题的 flag，还是要写的，我想了一想，耐烦是冯唐说的成大事的必要素质，怕也是程序员的必要素质，耐烦，所以，就是很烦的代码，你要不要写？还是要的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def romanToInt(self, s: str) -> int:
        mapping = {'I':1, 'V': 5, 'X': 10, 'L': 50, 'C':100, 'D': 500, 'M': 1000}
        i = 0
        result = 0
        l = len(s)
        while i < l :
            if s[i] == 'I' :
                if i + 1 < l and s[i+1] == 'V' :
                    result += 4
                    i += 1
                elif i + 1 < l and s[i+1] == 'X':
                    result += 9
                    i += 1
                else:
                    result += 1
                
            elif s[i] == 'X':
                if i + 1 < l and s[i+1] == 'L':
                    result += 40
                    i += 1
                elif i + 1 < l and s[i+1] == 'C':
                    result += 90
                    i += 1
                else:
                    result += 10

            elif s[i] == 'C':
                if i + 1 < l and s[i+1] == 'D':
                    result += 400
                    i += 1
                elif i + 1 < l and s[i+1] == 'M':
                    result += 900
                    i += 1
                else:
                    result += 100
            else:
                result += mapping[s[i]]
            i += 1
        return result

我就写了上面的代码，果然极其乏味，我以此写对了，不用 mapping 也是可以的，用了也没节省很多。从中，我学到了一个点，就是 Python 是没有 switch 语句的，只能用 if 来代替，那也没什么。

然后我还是看了看评论和题解，果然，就是这么无聊的题目，有人也能给你写出一朵花来：

1
2
3
4
class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
        return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))

来赏析一个老哥的作品，Python，两行搞定。简直了。同样是使用 dict 数据结构做了个映射，看看这个老哥的功力，对 api 熟悉到了一定的境界，让我叹为观止。这里用到了 dict 的一个 api，get 方法，这个方法允许输入第二个参数，参数的作用是一旦没有取到，就用第二个参数作为缺省值来返回。老哥利用了这一点，每次迭代都尝试从串里取两位出来，如果取到了合法值，就查表取得数值，如果没有取到合法值，就用第二个位的字母的值代替，真是巧妙，省掉了多少个 if 条件啊，妙，实在是妙！

再看 max 函数的用法，迭代的过程中，每次需要取两个出来，但是第一个字符的时候，只能取一个，用了一个 max，当下标为负数的时候，就只取一位数字，又是妙到颠毫。还展示了一个 enumerate 方法迭代 dict 的用法，就相对来说比较平淡了。

熟练到一定境界，写的代码就比我短 20 倍。可见，编写代码是一种技艺， 是可以无限锤炼的。