目录
每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。本周的算法以经典的组合问题来学习回溯法的运用，之后学习了 Avram Joel Spolsky （汉文：周思博，Stack Overflow 的 CEO ）写的文章，关于如何使得代码的错误更容易发觉，之后的 Tips 是关于使用 Puppeteer 来解决滑动验证问题的解决方案，最后的 Share 是在学习过程中发现的两个算法和 Chrome 开发者工具的学习网站。
Algorithm
组合问题，根据这道题学习一下回溯的基本用法。
回溯法
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
self.find(1, [], ans, k, n)
return ans
def find(self, index, arr: List, ans: List, k, n):
if len(arr) == k:
# 如果长度满足k，就把值添加到ans中
ans.append(arr[:])
else:
# 因为是组合问题，不能重复，遍历的时候要从当前位置开始
for i in range(index, n+1):
# 满足条件的添加
arr.append(i)
# 进入下一层循环选择
self.find(i+1, arr, ans, k, n)
# 去掉这次的尝试
arr.pop()
采用递归的方式来解决问题，这是一道典型的回溯法的运用，大的主旨相当于一颗树的遍历，当满足长度为 k 的时候，将结果添加进 ans 中，之后返回到上一层。
以 n=4, k=2 为例子，第一层遍历 1 到 4 这四个数字，也就是一开始 index=1 ，当第一次进入 for 循环的时候，arr 添加了 1 这个元素，之后进入递归，此时 arr=[1] 不满足 k 的长度，继续循环，不过当时的 index 就变成了 2 ，也就是之前的元素全部不要要从上层循环的元素的后面开始，也是从元素 2 开始遍历，这个时候将 2 添加到 arr 中，进入下层递归，此时 arr=[1, 2] ，满足 k 的长度，添加到 ans 中，返回到上层，arr 此时为 arr=[1, 2] ，所以需要将元素 2 弹出，继续元素 3 的判断，以此类推，按这样的递归方式，就能将所有的元素的组合求出。
这个时候有个问题，就是第一层当判断到元素 4 的时候，其实没有必要继续往下递归，以 n=4, k=3 为例子，当第一层遍历到元素 2 的时候，后面的元素 3 和元素 4 都没有遍历递归的价值，因为即使将后面所有的元素全部加起来，长度都不会大于 k ，这个时候就需要有剪枝的操作，就是避免多余的递归。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
self.find(1, [], ans, k, n)
return ans
def find(self, index, arr: List, ans: List, k, n):
if len(arr) == k:
ans.append(arr[:])
else:
# 修改循环的结束判断
for i in range(index, n-(k-len(arr))+2):
arr.append(i)
self.find(i+1, arr, ans, k, n)
arr.pop()
这里注意 for 循环的结束条件，不再是从当前位置 index 遍历到最后一个元素，而是 n-(k-len(arr))+2 ，其中 k-len(arr) 就是判断还有多少个可以选择，因为总体需要选择 k 个元素，k 减去当前已经选择的元素就是剩下还有多少个元素可以选，而 n-(k-len(arr)) 则表示以当前的位置 index 来算，最多只能遍历到 n-(k-len(arr)) 就不能再增加了，最后的 2 是需要包括当前元素以及 range 的特性，这样的话就能去除多余的递归条件增加算法运行速度。
举个例子，以 n=4, k=3 来说，当进行到 index 为 3 的时候，也是此时元素 1 、2 的条件都进行过判断，开始对 3 进行判断的时候，此时的 arr=[] （因为又开始第一层的关系，所以没有元素），4-(3-0)+2=3 而 for 循环的 range(3, 3) 函数就会停止循环，也就是剩下第一层中的元素 3 和元素 4 都不会继续遍历了。
Python 库
对于这基本的算法问题，python 封装了库供我们使用。
from typing import List
import itertools
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = itertools.combinations(list(range(1, n + 1)), k)
return [list(t) for t in res]
也就是 itertools 这个迭代工具库，其中的 combinations 这个方法将 list 和组合的长度传入，就能返回组合的迭代类型。
Review
这篇文章的作者是 Avram Joel Spolsky （汉文：周思博），是 Fog Creek Software 的 CEO，其中一个最出名的产品有 Stack Overflow 。
使错误的代码更容易看出错误，文章以作者面包店工作清洁机器为例子，讲述了内行人和外行人的不同见解，来思考代码编码的时候的规范以及一些不明显的，容易误导的错误的解决方案。
（文章比较长，这里只翻译了上半部分，下半部分在下周贴出）
Tip
这个文章介绍的是怎么使用 Puppeteer 解决滑动解锁，Puppeteer 又可以叫做木偶，是谷歌团队做出来的一个无界（Headless）浏览器，是一个 Node 库，提供高级的 API 接口来控制 Chrome。Puppeteer 可以生成页面截图和 PDF ，抓取 SPA 和想要的内容，表单填写、UI 测试、键盘输入等，也可以创建自动化测试，使用最新的浏览器和 JavaScript 的功能来直接在 Chrome 上运行测试。
对于解决滑动解锁的方式大致就是找到对应的位置，按住鼠标、移动鼠标、松开鼠标的方式。当然，最近也出了例如拼块的的滑动，需要滑动到固定的位置，而不是直接滑动到底，这个时候需要借助 Rembrandt.JS 来比较图片，也就是这一部分可以不用 ML 或者 OCR 这样的方式，就是单纯的一点点滑动，直至滑动到某个地方的时候图片能匹配的上（图片相差最小）的时候就松开鼠标，以这样的方式解决这个滑动解锁。
Share
哈希算法的实际应用，讲述了当我们需要将大量的数据均匀存储到多台机器的时候的解决方案，并且还讲述了当增加减少机器的时候的处理。
一个很有意思的组合数学中的一个十分实用的算法，在很多组合问题中都可以见到这个算法的身影。
Google 提供的 Chrome 开发者工具的学习网站，里面十分详细的讲述了开发者工具的使用方式，包括 JS 断点调试等功能，十分有用，并且有些案例还有对应的视屏讲解，对前段开发者和爬虫工作者都有很大的帮助。
0 条评论