ARTS-Week 8

每周至少写一道算法题，阅读并点评至少一篇英文文章，学习至少一个技术技巧，分享一篇有观点和思考的技术文章。这周算法完成了 leetcode 的 289、263和264题，翻译继续上周的未完成的项目，Tip 中是这一周遇到的 python 的库的使用，一个关于文件目录的 pathlib ，另外一个是 clieck 实现控制台命令的神器，最后的 share 是火绒实验室发表的一篇文章。

Algorithm

289. Game of Life

细胞生命游戏的一个算法题，算是简化版本，大致的意思就是一个细胞，周围（九宫格，其余的 8 个格子）只要有小于 2 个或者大于 3 个，该细胞死亡；如果周围有 2 个或 3 个细胞，该细胞继续存活；如果恰好周围有 3 个细胞，则该位置的死细胞复活，所有细胞的状态都是同时发生，也就是一个细胞的状态改变不影响同一时期的其他细胞的变化，细胞的复活和死亡是同时发生的。

基于以上规则，给出一个初始状态，求接下来的状态，要求使用原地排序算法，也就是不额外开辟空间使用。

这个时候就可以考虑设计标志的方式，进行两轮遍历获取结果。

from typing import List

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
          # 获得数组的长宽
        row, col = len(board), len(board[0])
        # 设计标记，下标0和1就表示原来和改变之后都是0和1，下标2表示1->0，下标3表示0->1
        tar_map = [0, 1, 0, 1]

        def count(num_i, num_j):
            num = 0
            # 遍历周围 8 个细胞，计算数量
            for r in [-1, 0, 1]:
                for c in [-1, 0, 1]:
                      # 中间的细胞不参与条件的判断，跳过
                    if r == 0 and c == 0:
                        continue
                    if 0 <= num_i+r < row and 0 <= num_j+c < col:
                        if board[num_i+r][num_j+c] <= 1:
                            num += board[num_i+r][num_j+c]
                        # 遇到下标2表示原来的是1，需要加1
                        elif board[num_i+r][num_j+c] == 2:
                            num += 1
                        # 下标为3的表示原来为0，直接跳过不管
            return num

        for i in range(len(board)):
            for j in range(len(board[0])):
                  # 计算周围细胞数量
                cell_num = count(i, j)
                # 依据不同条件进行标识的赋值
                if cell_num == 2:
                    if board[i][j] == 0:
                        board[i][j] = 0
                    else:
                        board[i][j] = 1
                elif cell_num == 3:
                    if board[i][j] == 0:
                        board[i][j] = 3
                    else:
                        board[i][j] = 1
                else:
                    if board[i][j] == 0:
                        board[i][j] = 0
                    else:
                        board[i][j] = 2
                # 根据标记的位置，统一取出改变后的状态
        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] = tar_map[board[i][j]]

首先根据题目的意思，一共有四种状态，0变1，1变0，或者0和1都不改变，依据这四种状态设置四个标志，以数组的方式保存 tar_map = [0, 1, 0, 1] ，也就是0和1不变的状态就对应着数据下标的位置，之后下标2表示1变0，下标3表示0变1，即标志数组中的值保存的是改变后的值，这样对于每次对周围细胞统计的时候就能知道改变前和改变后的状态。

所以第一轮循环就根据细胞周围的数量，赋值标志数组的下标，第二轮循环就依据数组下标取出改变后的值。这样通过设置标志的方式就可以避免创建新的数组空间保存改变前的状态了。

263. Ugly Number

这题很简单，大概题目的意思是求出一个数，如果质因数全部都是由 2, 3, 5 组成的数，就被称为丑数，1表示为丑数。

class Solution:
    def isUgly(self, num: int) -> bool:
        # 2, 3, 5
        if num <= 0:
            return False
        while num != 1:
            if num % 2 == 0:
                num /= 2
            elif num % 3 == 0:
                num /= 3
            elif num % 5 == 0:
                num /= 5
            else:
                return False
        return True

思路就是每次都除以 2, 3, 5 其中的一个，只要出现不能整除的情况，就表示是丑数，如果一直除到 1 退出循环，则表示该数是丑数。

这道题是倒叙的，也就是知道该数字的情况下，一直推到前面的一个数，这题还有一个变体，就是求出第 n 个是丑数的数是什么。

264. Ugly Number II

这道题与上一道题不同的是，这个需要从 1 开始，求出第 n 位的丑数是什么，思路与上一题相反，这题是一个不断乘的过程。其中 n 最大为 1690，并且只需要求出那个数字，不需要知道前面的数。

大致思路就是从 1 开始，每次都取最小的数乘上 2，3，5 获得新的三个数放入，作为一轮循环，之后第 n 轮之后获得的最小那个数就是所求，所以有一点需要注意，就是重复问题，在获取其中最小的数进行下一轮循环的时候，要注意重复问题。

首先，利用 Python 的 set ，写一个最简单的代码：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        num_set = set([1])
        while n > 1:
            min_num = min(num_set)
            num_set.remove(min_num)
            num_set.add(min_num*2)
            num_set.add(min_num*3)
            num_set.add(min_num*5)
            n -= 1
        return min(num_set)

因为 set 本身就是不重复的，所以可以一直在里面添加元素，不用管是否重复的问题，并且每次都是用 min 函数获取 set 中最小的数，在处理过后将这个最小的元素丢弃，最后得到结果，注意元素 1 就算第一个丑数，所以初始值有 1 的时候，遍历循环的时候需要减少一次。

当然也可以利用数组来实现这个逻辑。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        num_list = [1]
        while n > 1:
            min_num = min(num_list)
            num_list.remove(min_num)
            if min_num * 2 not in num_list:
                num_list.append(min_num * 2)
            if min_num * 3 not in num_list:
                num_list.append(min_num * 3)
            if min_num * 5 not in num_list:
                num_list.append(min_num * 5)
            n -= 1
        return min(num_list)

不过这两个方式的速度都很慢，因为要求很多没有必要的数据，而且出现重复计算数据的情况，这个时候就出现了三指针的方法。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
          # 初始值 1 为丑数
        num_list = [1]
        # 三个指针初始值都指向数组的第一个元素
        i_2 = i_3 = i_5 = 0
        for i in range(1, n):
            num_2, num_3, num_5 = num_list[i_2]*2, num_list[i_3]*3, num_list[i_5]*5
            # 求出最小的数字
            min_num = min(num_2, num_3, num_5)
            # 将最小数字所对应的下标加 1 
            if min_num == num_2:
                i_2 += 1
            if min_num == num_3:
                i_3 += 1
            if min_num == num_5:
                i_5 += 1
            # 将求出的最小数字添加到数组中，而此时对应获得该数字的下标也同时指向该元素
            num_list.append(min_num)
        return num_list[-1]

也就是设计三个指针来计算乘上 2，3，5 之后的位置，首先初始值全部为 0 ，指向第一个数组的下标，之后分别乘上对应的数字，获得最小的那个值，将那个值添加到输出列表中，同时将对应的下标加 1 ，循环 n 次之后数组的最后一个值就是所求。

下面画了一个简单的流程图方便理解：

Review

这篇文章的作者是 Avram Joel Spolsky （汉文：周思博），是 Fog Creek Software 的 CEO，其中一个最出名的产品有 Stack Overflow 。

使错误的代码更容易看出错误，文章以作者面包店工作清洁机器为例子，讲述了内行人和外行人的不同见解，之后通过 XSS 攻击引出匈牙利表示法，并且介绍这表示法的使用方式。

文章尚未翻译完全，这里先行贴出：文章翻译 | Making Wrong Code Look Wrong

Tip

pathlib

面向对象的文件系统路径，这是 Python3 之后的一个内置库，相对于 os 模块的 path 方法，Python3 标准库 pathlib 模块的 Path 对路径的操作会更简单，而且完全是使用面向对象的编程方式，并且还提供一些 IO 操作。

继承关系如下图：

导入

from pathlib import Path

列出文件夹

p = Path('.')
# 列出当前目录下的子目录
for x in p.iterdir():
    if x.is_dir():
        print(x)

列出目录树下所有的 py 文件

list_py_file = p.glob('**/*.py')
for py_file in list_py_file:
    print(py_file)

查看文件属性

# 是否是文件夹
print(p.is_dir())
# 是否是文件
print(p.is_file())
# 目录是否存在
print(p.exists())

拼接路径

# 拼接路径，表示在 p 这层路径中回到上层，之后进入 leetcode 目录
p = p / '../leetcode'
# resolve 表示获取绝对路径
print(p.resolve())

打开一个文件

p = Path('./_pathlib.py')
with p.open() as f:
    print(f.readline())

上面提供了一些很常用的方法，快速入门，更多的函数需要参照官网。

clieck

Python 的一个第三方库，用于快速创建命令行，成为命令行神器。

安装

pip install click

快速入门

import click

# command 表示命令行函数的入口
@click.command()
@click.option('--name', '-n', type=str, help='input your name', prompt='must input your name')
@click.option('--age', type=int, help='your age', prompt='must input your age')
@click.option('--gender', type=click.Choice(['man', 'woman']))
@click.option('--text', '-t', help='text', )
def hello(name, age, gender, text="Hello"):
    click.echo("name={}, age={}, gender={}, {}".format(name, age-5, gender, text))


if __name__ == '__main__':
    hello()

之后的使用方式就类似于在命令行中使用一样。

>> python _clieck_lim.py --help
Usage: _clieck_lim.py [OPTIONS]

Options:
  -n, --name TEXT       input your name
  --age INTEGER         your age
  --gender [man|woman]
  -t, --text TEXT       text
  --help                Show this message and exit.

其中的一些参数说明：

• '--name', '-n' 表示输入命令用的前驱，可以有多个

>> python _clieck_lim.py -n lalala --age 12 --gender man -t heihei
name=lalala, age=7, gender=man, heihei

• type 表示输入的值是什么类型的
• help 在输入 --help 的时候会显示的参数的信息
• prompt 表示在命令行中没有输入相应的参数时，会根据 prompt 提示用户输入

>> python _clieck_lim.py -n lalala
must input your age: 12
name=lalala, age=7, gender=None, None

参考：

• 命令行神器 Click

Share

金山毒霸”不请自来” 背后竟有黑产推波助澜

这是一篇火绒的文章，讲述了金山毒霸使用病毒进行推广，文中详细着写出了金山软件使用了 Mint 病毒和BlackRain 病毒进行软件安装推广、快捷方式链接推广、广告弹窗和浏览器首页篡改等，并且详细分析了病毒代码以及推广流程，还给出了这两个病毒的 hash。我们在警惕各种病毒的同时也要反思这样的不正当竞争究竟正确与否，是否背离了一家安全厂商的本质。

图片来自：病毒推广流程图 ，侵删