Becomin' Charles

算法 | LNMP | Flutter | Mac

Becomin' Charles

发表于 分类于 本文字数： 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 倍。可见，编写代码是一种技艺， 是可以无限锤炼的。

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

上一篇文章洋洋洒洒介绍了一些关于我对 IoC 的学习和理解，这篇文章继续来说说这个话题。认识一个事物，常用的方法就是 5W1H 法，这个方法提醒我们，尽可能全面去认识，不要遗漏某些方面，这里，最最重要的，可能就是 Why，也就是为什么。

这其实是一个非常艰难的话题，我只能硬着头皮来写写，因为能参考的东西实在是不多，就算是 Martin 老爷，也更多谈及了 What 的问题，比较少谈及了 Why，对于他来说，似乎是不言自明的。但是，说实在的，我不明白。比如说，我不明白，我们为什么要 IoC？如果不使用 IoC 的话，我们还有什么选择？IoC 和其他选择之间，优劣如何？

如果细看 Martin 老爷的文章，话里话外似说，其实所有的框架都是 IoC 的。我们似乎不能去对比 IoC 和非 IoC 的框架。等于就失去了和从差异去认识的机会了。

阅读全文 »

发表于 分类于 ， ， 本文字数： 2.8k 阅读时长 ≈ 10 分钟

局限于英文水平和对软件工程“学术界”了解的浅薄，我对 Inverstion of Control —— 中文或许可以翻译成“反向控制” —— 的理解，总是停滞在一种似是而非的程度。我尝试通过搜索来学习，发现我能搜到的中文文章，都不能给我很大的帮助，有的在大谈特谈 Spring 框架如何如何；有的又说，想搞清楚 IoC，你先要理解 DIP …… ；也有的，干脆就说，所谓的 IoC 根本就是 DI。一时间，各种术语满天飞，越发让我觉得糊涂了。

不得已，我又开始搜寻英文资料，发现基本也是各种意见都有，但是无一例外都会指向一个地方，就是 Martin Fowler（马丁・福勒）的文章（很感谢国外这些博客的作者，都有良好的习惯，让人比较容易找到一个概念的发展脉络）。通过学习和对比各种国内的文章，我似乎对这个概念更加清晰了一些，不敢说全懂了，但是总算比以前明了了一点。特此记录。

阅读全文 »

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

简述一下题目的意思：给你一个数组 nums 和一个值 _val_，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

这个题目的全文太长了，我就不全部挪过来了，就是提示一下这个意思就行了。具体可以去 LC 上查看。

这个题目感觉和 26 题极其相似，我第一个想到的就是“双指针”，第一个指针标记筛后的数组的末位，第二个指针指向筛前数组的开头。然后，两个指针的初始化都在 0，我们这么考虑问题，从筛选前的数字的第一个元素开始，如果这个元素没命中 target 就拷贝到筛选后数组的最后一位，如果命中了，就跳过看第二个元素。

因为筛选用的那个指针移动速度大于等于筛选后的那个指针，所以这个算法会没有重复和遗漏地结束。写出来是：

1
2
3
4
5
6
7
8
9
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i, j = 0, 0
        while j < len(nums):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
            j += 1 
        return i

也是非常短的。写完我看了下答案，原来还有优化的空间，就是我这个算法，拷贝的次数比较多，因为如果整个数组都没有命中的数字，那么每个数字都要被原地赋值一次，确实如此。

如果我们不纠结元素的顺序，可以使用交换法，还是双指针，一个初始化在筛后数字的开头，一个指向筛前数组的末位，就是倒着筛，筛到就交换。这样就极大减少了赋值的次数，提高了效率。很有意思。

知识点：无新的知识点。

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

这是一个非常经典的库函数吧，在一个长字符串（haystack）中，搜索一个字符串（needle），如果包含了就返回起始的位置，如果没有包含，就返回 -1。

看了这个题目，我想到的唯一办法就是暴力算，先做一头对齐，然后逐个比较，找到了返回下标，没找到就移动一格重复这个过程，直到无法移动为止：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i, j = len(haystack), len(needle)
        if j == 0:
            return 0
        x, y = 0, 0
        while x <= i - j:
            for y in range(j):
                if haystack[x + y] != needle[y]:
                    break
            if needle[y] == haystack[x + y]:
                return x
            else:
                x += 1
        return -1

其实没啥难的，就是很多边界条件，很难写，我提交错了 5 回才写对。（泪奔……

然后我看了题解，暴力算是比较普遍的解法，我的也不算太偏。看到了一个让我皱眉头的算法，叫 KMP，大学时候我学过，完全没有学会过。这次我就认真学学。

自然而然写的那个算法，里面其实存在重复，因为目标字符串，每次搜索失败，我们只移动一个位置，其实，搜索过程中，可能已经比较了好几个字符了，都白比较了。所以，类似 KMP 这样的算法，本质上，就是希望已经比较过的部分，希望能利用起来，减少重复的运算，从而提高了效率。

自然而然写的算法，复杂度大概是 O(M(N-M))，但是 KMP 算法，通过预处理，时间换空间，可以做到 O(N) 的时间复杂度。

它的原理，简单来说，就是已经扫描过的被搜索串，应该是完整的目标搜索串的子串，这个子串的后缀同时也是这个子串的前缀的话，那么我们就可以节省移动的距离。这么说是非常绕的，我是看了很久很久才看懂的。

《字符串匹配的KMP算法》阮一峰

《KMP算法详解》 labuladong

《[如何更好的理解 KMP 算法](http://如何更好地理解和掌握 KMP 算法? - 海纳的回答 - 知乎 https://www.zhihu.com/question/21923021/answer/281346746)》知乎

上面两篇是我认真看了的网络文章，此外我还翻阅了《算法导论》，多种材料混合下，还是看懂了一点的。我估计过个不久就还是会忘记的，所以，我打算，按照自己已经理解的部分来实现一下 KMP 算法，如果能写对，我估计印象可以久一点。

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
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0:
            return 0
        i, j = 0, 0
        pie = self.pie(needle)

        while i < len(haystack) and j < len(needle):
            if j == -1 or haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                j = pie[j]
        if j == len(needle):
            return i - j
        return -1
    
    def pie(self, needle: str) -> List[int]:
        pie = [0] * len(needle)
        pie[0] = -1
        i, j = 0, -1
        while i < len(needle) :
            if j == -1 or needle[i] == needle[j]:
                i += 1
                j += 1
                if i < len(needle):
                    pie[i] = j
            else:
                j = pie[j]
        return pie

看了很久，我最后还是没写出来，这是从知乎上一个回答里面拷贝过来的。我自己还是没有掰明白的，我决定还是放一放先。先不要纠结了，后面回过头来再说吧。

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

在一个给定的排序数组里，找到一个目标数字的位置，如果没有，就给出插入的位置。

这个题目，一看就是二分查找法的应用，但是我写了两次没写对，二分查找法主要是处理边界的问题，还是有很多细节的，我先写了一个 O(N) 的搜索法：

1
2
3
4
5
6
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if target <= nums[i]:
                return 0 if i == 0 else i
        return len(nums)

很短，很容易写，一下就写对了。然后，我看了题解，还是借机会练习一下二分查找法比较好一点。

所谓的插入位置是什么意思呢？

一般来说，我们把一个数字放入数组的第 0 个位置，则原来在 0 这个下标的数字，会往右移，下标变为 1。所以，这道题，我们真正要找的那个下标是，该下标位置的数字，大于或者等于 target 目标值。

这个在 Python 类库里，其实就是 bisect_left 这个方法。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

这是一个二分法的实现。这里比较 tricky 的部分，就是处理边界移动和最终返回值的地方。注意看这句 nums[mid] < target ，满足这个条件的时候，我们把左边界往右移了一格，移动后，nums[left] ≥ target ，所以，left 就是我们要找的解。

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

真是活久见了，当我使用 yum update 命令的时候，发现竟然报错了：

1
2
3
4
5
6
7
8
yum update
error: rpmdb: BDB0113 Thread/process 4196/140144005818432 failed: BDB1507 Thread died in Berkeley DB library
error: db5 error(-30973) from dbenv->failchk: BDB0087 DB_RUNRECOVERY: Fatal error, run database recovery
error: cannot open Packages index using db5 -  (-30973)
error: cannot open Packages database in /var/lib/rpm
CRITICAL:yum.main:

Error: rpmdb open failed

都怪我之前写了各种自动守护脚本，导致服务器上跑的各种服务长久都没什么抖动，于是乎，我很久也不用登录了，不过今天还是跑飞了，上去看看，服务死了，而且 systemd 没有拉起来，太奇怪了。

手动执行了 systemctl restart 后，我想起来久没上来，应该更新一下子，就报错了。从来没见过这个错误，这次可能真的一年多没更新了吧。

搜到了解决方案：

1
2
3
4
5
6
7
8
9
# 第一步，备份文件，建议做备份
mkdir /root/backups.rpm.mm_dd_yyyy/
cp -avr /var/lib/rpm/ /root/backups.rpm.mm_dd_yyyy/

# 第二步，删除错误的文件，开始重建
rm -f /var/lib/rpm/__db*
db_verify /var/lib/rpm/Packages
rpm --rebuilddb
yum clean all

一次尝试成功，可以愉快的 yum update 了。

当然以上解决方案来自 SO。