前面花了很多篇幅去讲了 IoC 这个概念的问题，最后，还是要落实到实现上。通过分析和推理，我们了解到 IoC 的本质还是为了解耦和复用，而这个核心，最后落实到而组件和对象的创建和组装上面。
了解了这些，就不会“乱花渐欲迷人眼”，无论是 Spring 强调的 IoC Container 也好，还是 Martin 老爷说的 Service Locator，Dependency Injection，其背后，目的是统一的。无非是手段是多样的。那么，我们只要逐一去了解这些手段即可。
这个题目特别长，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
40class 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
4class 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 倍。可见，编写代码是一种技艺， 是可以无限锤炼的。
上一篇文章洋洋洒洒介绍了一些关于我对 IoC 的学习和理解，这篇文章继续来说说这个话题。认识一个事物，常用的方法就是 5W1H 法，这个方法提醒我们，尽可能全面去认识，不要遗漏某些方面，这里，最最重要的，可能就是 Why，也就是为什么。
这其实是一个非常艰难的话题，我只能硬着头皮来写写，因为能参考的东西实在是不多，就算是 Martin 老爷，也更多谈及了 What 的问题，比较少谈及了 Why，对于他来说，似乎是不言自明的。但是，说实在的，我不明白。比如说，我不明白，我们为什么要 IoC？如果不使用 IoC 的话，我们还有什么选择？IoC 和其他选择之间，优劣如何？
如果细看 Martin 老爷的文章，话里话外似说，其实所有的框架都是 IoC 的。我们似乎不能去对比 IoC 和非 IoC 的框架。等于就失去了和从差异去认识的机会了。
局限于英文水平和对软件工程“学术界”了解的浅薄，我对 Inverstion of Control —— 中文或许可以翻译成“反向控制” —— 的理解，总是停滞在一种似是而非的程度。我尝试通过搜索来学习，发现我能搜到的中文文章，都不能给我很大的帮助，有的在大谈特谈 Spring 框架如何如何；有的又说，想搞清楚 IoC，你先要理解 DIP …… ；也有的，干脆就说，所谓的 IoC 根本就是 DI。一时间，各种术语满天飞，越发让我觉得糊涂了。
不得已，我又开始搜寻英文资料，发现基本也是各种意见都有，但是无一例外都会指向一个地方，就是 Martin Fowler（马丁・福勒）的文章（很感谢国外这些博客的作者，都有良好的习惯，让人比较容易找到一个概念的发展脉络）。通过学习和对比各种国内的文章，我似乎对这个概念更加清晰了一些，不敢说全懂了，但是总算比以前明了了一点。特此记录。
简述一下题目的意思：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
这个题目的全文太长了，我就不全部挪过来了，就是提示一下这个意思就行了。具体可以去 LC 上查看。
这个题目感觉和 26 题极其相似，我第一个想到的就是“双指针”，第一个指针标记筛后的数组的末位，第二个指针指向筛前数组的开头。然后，两个指针的初始化都在 0，我们这么考虑问题，从筛选前的数字的第一个元素开始，如果这个元素没命中 target 就拷贝到筛选后数组的最后一位，如果命中了，就跳过看第二个元素。
因为筛选用的那个指针移动速度大于等于筛选后的那个指针，所以这个算法会没有重复和遗漏地结束。写出来是：1
2
3
4
5
6
7
8
9class 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
也是非常短的。写完我看了下答案，原来还有优化的空间，就是我这个算法，拷贝的次数比较多，因为如果整个数组都没有命中的数字，那么每个数字都要被原地赋值一次，确实如此。
如果我们不纠结元素的顺序，可以使用交换法，还是双指针，一个初始化在筛后数字的开头，一个指向筛前数组的末位，就是倒着筛，筛到就交换。这样就极大减少了赋值的次数，提高了效率。很有意思。
知识点：无新的知识点。
这是一个非常经典的库函数吧，在一个长字符串（haystack）中，搜索一个字符串（needle），如果包含了就返回起始的位置，如果没有包含，就返回 -1。
看了这个题目，我想到的唯一办法就是暴力算，先做一头对齐，然后逐个比较，找到了返回下标，没找到就移动一格重复这个过程，直到无法移动为止：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class 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
30class 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
看了很久，我最后还是没写出来，这是从知乎上一个回答里面拷贝过来的。我自己还是没有掰明白的，我决定还是放一放先。先不要纠结了，后面回过头来再说吧。
在一个给定的排序数组里，找到一个目标数字的位置，如果没有，就给出插入的位置。
这个题目，一看就是二分查找法的应用，但是我写了两次没写对，二分查找法主要是处理边界的问题，还是有很多细节的，我先写了一个 O(N) 的搜索法：1
2
3
4
5
6class 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
10class 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 就是我们要找的解。
真是活久见了，当我使用 yum update 命令的时候，发现竟然报错了：1
2
3
4
5
6
7
8yum 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。
这个原题目可以去 LC 看。我看到这个题目的想法就是硬做，无非是数相同的数字有几个的问题，然后用两个数字描述：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
say, i, new = "1", 1, ""
while i < n:
num = say[0]
count = 0
for j in range(len(say)):
if num == say[j]:
count += 1
else:
new += str(count) + num
count = 1
num = say[j]
new += str(count) + num
say, new = new, ""
i += 1
return say
这是我写的代码，就是迭代的去逐个计算。
我看了一下题解，有提到查表法的，这个当然是正确的解法，这个题目，有非常小的问题空间 1 <= n <= 30 一共才30个，当然，生成 30 个答案，还是要靠算法去计算，用查表法，只是增加了喜剧效果和真的很省时间，可以 Beats 100%。
另外，值得一提的是，有不少人提到了递归法，这个题目显然具备了递归的结构，比如，计算第 n 个串，本质上就是对第 n - 1 个串的描述。所以，可以用递归法，不过这个题目的特殊之处在于，用递归写，也并没有简单多少，反倒增加了栈的成本。没什么意思，其实栈里只是存储了 n - 1 个串的表达而已，用一个变量就可以存了。像我上面写的代码一样。
这个题目就像标题一样直接，第一步，找到最后一个单词，第二步，计算长度。
我就写了这样的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution:
def lengthOfLastWord(self, s: str) -> int:
idx = len(s) - 1
flag = False
count = 0
while idx >= 0:
if s[idx] == " ":
if not flag:
idx -= 1
continue
else:
break
flag = True
count += 1
idx -= 1
return count
写完看了题解，发现我写得还是比较啰嗦的，多用了很多的变量。题解里有一些解法，上来先处理尾空格，然后再开一个循环开始计数，原理是一样的，但是写起来简洁了很多，我个人觉得很好。
另外有人提到，为啥不用 trim，是呀，题目也没说不可以用 trim，如果对类库很熟的话，完全可以用 trim，不能因为是算法题，就陷入思维定势吧…… 也是蠢得可爱……1
2
3
4
5
6
7
8
9
10
11class Solution:
def lengthOfLastWord(self, s: str) -> int:
s = s.strip()
idx, count = len(s) - 1, 0
while idx >= 0:
if s[idx] != " ":
count += 1
else:
return count
idx -= 1
return 0
用 Python 的 strip() 函数，精简了一下，去掉尾空格后，数数，遇到空格停止。
