前面花了很多篇幅去讲了 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（马丁・福勒）的文章（很感谢国外这些博客的作者，都有良好的习惯，让人比较容易找到一个概念的发展脉络）。通过学习和对比各种国内的文章，我似乎对这个概念更加清晰了一些，不敢说全懂了，但是总算比以前明了了一点。特此记录。
我是一个 PHP 程序员，一直使用 Yii 框架，从 2.0 版本开始，就显式地出现了 DI 这个概念，不怕丢人，我就是看不懂，不过就像大多数情况一样，看不懂也根本不会影响使用。不过，时不时遇到的时候，还是觉得萦绕心头，偶尔搜些资料看看，才知道了 IoC，把 IoC 和 DI 联系在一起的人，是 Martin Fowler（中文版），就算他不是第一个，但是极有可能是影响力最大的一个。
对我来说，DI 和 Service Locator 之外，又出现了一个新概念，就自然而然顺藤摸瓜去了解，没想到我非但没有更清楚，反而更糊涂了，继而又陆续看了很多资料，才又出现了一丝丝清明。
日常我们用到的词汇里面，有一种很常见的情况，就是除了这个词汇本身的内涵，在使用过程中，其外延不断扩展，有些甚至出现了引申意义，于是经常使得自然语言变得隐晦难明，给 NLP 带来困难的同时，人类自己也负担不轻。
这个经常被缩写成 IoC 的术语，如果翻译成中文的话，字面意义就是“反向控制”，但是，一般人读到四个汉字，基本是莫名其妙的。如果你使用了百度去搜索中文资料，看了一堆网友写的文章，相信你就离其真实含义更加遥远了（也包括本文）。
如果你在认真阅读本文的话，我试图传递给你的一个建议就是，不要相信所有的资料，包括本文。这样，或许你真的可以建立一些对这个概念的准确理解。这恐怕就是道可道，非常道吧，哈哈。
关于 IoC 是什么，国内外网友也莫衷一是。有人说，这是一种设计模式，“设计模式” 是随着 GoF 的著作传开的一个专有名词，其实是描述了在面向对象软件设计（OOD）过程里，为了实现解耦与复用，软件工程界惯用的一些优秀的（起初识别了 23 个）类关系设计方案。每一个模式，都有其比较具体的场景，以及相对来说比较具体的设计模板，渐渐已经成为工程师交流的一套工具。从设计模式的特点来看，IoC 恐怕不能说是一种设计模式，因为，首先就没有比较具体的场景，也没有比较具体的设计模板，实现方案也有多种。所以，决不能称其为一种设计模式。
常见的一种说法，说 IoC 是一种设计原则，维基百科也如此定义。我想，这可能是比较接近事实的一个说法。但是，比起软件工程里其他一些更为显而易见的原则，比如 DRY 原则，SOLID 原则等等，IoC 的含义就显得模糊，尤其 SOLID 里面的 D 代表的依赖倒置（Dependency Inversion Principle，也叫 DIP），跟 IoC 看起来似乎又像一个意思。不少中文世界的博客，甚至就蠢蠢欲动地想要完成两者的替换，从而避免对其进行解释。
也有说 IoC 是一种实现。这可能是一种隐晦的表达。因为提及 IoC，不少人就要说 Spring，说起 IoC Container，这就使其变得非常具体，好像它是一个框架，或者甚至是一个类。我想，头脑稍微清明一点，不至于误解如此，但免不了，还是有人似是而非地如此认为。
Martin Fowler 在一篇词源追溯的文章里，对 IoC 的定义，是一种“现象”，或者说一种“特点”。介于他是这个领域最权威的专家和最早探讨这个概念的人之一，我个人比较倾向于相信他的话。其实我比较佩服的就是他的写作能力，他精挑细选地这两个词汇，避开了人云亦云的“Principle”或者“Pattern”，可以看出他的态度。
Inversion of Control is a common phenomenon that you come across when extending frameworks. Indeed it’s often seen as a defining characteristic of a framework.
—— bliki: InversionOfControl Martin Fowler
其实，在 Martin 老爷爷另一篇文章里，就是那篇著名地介绍了 Dependency Injection 的文章里，他也很巧妙地避免了混淆，那里他用了 IoC Container 和 DI 放在一起讨论，而不是 IoC 本身。IoC Container 和 IoC 不是一个概念，就算没有“雷锋”和“雷锋塔”区别那么大，其实也差不多了。
有个趣谈也值得在这里谈起，就是大家都不约而同提到了 “好莱坞原则”，其实就是一句话，“别给我打电话，我们会打给你的！”，如果是英语的话，会更形象一点，因为打电话的那个单词是 Call，和函数调用的英语单词 Call 是一样的，所以，是一语双关。当然，所有人都提及了，就说明这个好莱坞原则比较容易看懂，但不能代表二者完全等价。
这么说的原因是，IoC 是关乎 Control 这件事情，虽然也是 C，但是，Call 和 Control 显然是两码事情，好莱坞原则，应该也暗含了 IoC，所以，两者才拿来一起说，是为了帮助去理解 IoC 的，不能代替之。
有不少文章提到了，如果你想知道什么是“控制反转”，那么你先要知道什么是“控制”。这话说得大义凛然，然而到了具体分析什么叫控制的时候，没几篇文章给出让人眼睛一亮的答案。当然，我不能鄙视他们，因为我也给不出来，不过我还是能看出来他们给出的答案不够让人满意的。
Martin 老爷爷给举了一个例子，是这样的：1
2
3
4
5
6puts 'What is your name?'
name = gets
process_name(name)
puts 'What is your quest?'
quest = gets
process_quest(quest)
这是一段 Ruby 脚本，纯命令行的程序，模拟了一个交互式 Shell 命令的实现，这个例子用以说明什么叫“控制”，用以对比后面要给出的“反向控制”的例子。从这个例子里，我们看到程序员作为程序的编写者，控制了这个程序的执行流程，先询问用户的名字，然后等待用户输入，然后处理此输入，再询问用户的需求，等待用户的输入，然后处理用户的输入。
很显然，这是一个简单的“过程”，从编程范式来理解，这是过程式（指令式 Imperative）编程的产物。程序员从头到尾，用编程语言描述了事情发生的步骤，也叫 Control Flow。用户在使用这种应用程序的时候，必须按照预先设定的顺序来操作软件，完全被软件所引导进行操作。
然后，我们再来看看同一个例子改换一下样子：1
2
3
4
5
6
7
8
9
10
11require 'tk'
root = TkRoot.new()
name_label = TkLabel.new() {text "What is Your Name?"}
name_label.pack
name = TkEntry.new(root).pack
name.bind("FocusOut") {process_name(name)}
quest_label = TkLabel.new() {text "What is Your Quest?"}
quest_label.pack
quest = TkEntry.new(root).pack
quest.bind("FocusOut") {process_quest(quest)}
Tk.mainloop()
这是同一个功能的另一个图形界面的程序，在这里，我们看到，这回因为是图形界面，程序员通过给特定的事件“FocusOut”，绑定了一个闭包，来处理用户的输入。我们可以假想一下，在这个图形界面上，有两个输入框，同时出现在用户的面前，不像上面的例子，先出现第一个问题，再出现第二个问题，这次是一个平铺的表单，用户先填第一个也行，先填第二个也行。一旦填写了其中一个，对应的处理程序，就会被调用，被谁调用呢？被 mainloop() 这个程序调用。
在这个例子里面，传递给我们的 Inversion of Control 有两个层面。第一个层面是，原本应用程序的执行流程，由编写的程序员控制，由程序员决定，先执行哪个方法，再执行哪个方法，而在这个例子里，编程了事件驱动，用使用应用程序的用户去很大程度决定，先执行哪个部分，再执行哪个部分。
第二个层面，则是在这个例子里，出现了框架，就是 Tk，这个框架，通过一个 mainloop() 方法，来发射所有的事件，从而驱动不同的事件处理程序运转，虽然程序员编写了这个程序，但是 Control Flow，不由程序员决定，运行哪个处理程序，由框架层面决定。
看了上面的例子，你可能要想了，框架不都是这样的么？当我们使用框架进行编程的时候，都是我们实现一些特定的类，方法，业务逻辑，然后用配置组装起来，一旦框架运转起来，就会自动调用我们提供的那些类和方法。
没错，我想 Martin 老爷爷就是这个意思。所以，才说 IoC 其实是框架的 defining characteristic。正是因为框架这样设计，才使得框架区别于类库。对于类库来说，就是一系列设计完好的类，但是他们不会自动运行，需要程序员按照正确的顺序去构建对象并调用，而框架也同样是一群类，但是它们都实现约定了执行的顺序和方法，对程序员的扩展开放，但是修改封闭，程序员只能去扩展框架的功能，从而实现自己的业务目的，执行层面的控制由框架负责。
由此，IoC 成为了框架和类库的根本性的区别。
未完待续……
后续文章：
简述一下题目的意思：给你一个数组 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() 函数，精简了一下，去掉尾空格后，数数，遇到空格停止。
