Übung macht den Meister

Posted on Word count in article: 4.7k Reading time ≈ 8 mins.

二叉树的遍历直观的解法是使用递归求解，不过同样也可使用非递归方式求解。

前序遍历

先来看前序遍历的递归求解：

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
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        values = []

        self._preorder_traversal(root, values)

        return values

    def _preorder_traversal(self, root: TreeNode, values: List[int]) -> None:
        if not root:
            return

        values.append(root.val)

        self._preorder_traversal(root.left, values)
        self._preorder_traversal(root.right, values)

对于如下的二叉树：

alt

其调用链为：

1
2
3
4
5
_preorder_traversal(1)
    _preorder_traversal(2)
        _preorder_traversal(4)
        _preorder_traversal(5)
    _preorder_traversal(3)

可以看到越深的节点对应的函数调用越先返回，对应先进后出的模型，即栈，所以递归转非递归可借助栈实现。

由于前序遍历是先访问根节点，所以对于每个子树，可以先将根节点入栈，然后依次弹出栈顶的节点，从而实现先访问根节点，然后将左右子树的根节点入栈，由于左子树需要先于右子树被访问，所以右子树的根节点要先入栈，然后再入栈左子树的根节点：

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
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        values = []
        stack = [root]

        while stack:
            current = stack.pop()
            values.append(current.val)

            if current.right:
                stack.append(current.right)

            if current.left:
                stack.append(current.left)

        return values

中序遍历

在递归的方案下，前序遍历改为中序遍历只需改变 values.append(root.val) 的执行位置即可，而在非递归方案下，并不能通过直接改变 values.append(current.val) 的执行位置来实现，因为不管放到哪个位置，都会提前访问到根节点。

中序遍历下，最左下方的节点是最先被访问的，沿着左子树的根节点这条线，等同于一个单链表的倒序访问，单链表的倒序如果用栈来实现则是将单链表的所有节点从链表头开始遍历依次放入栈，然后再依次出栈，类似的，只要当前节点存在左子树，则持续将左子树的根节点压入栈，这样下次出栈时，就会先访问最左下方的节点。当某个节点出栈时，由于上述的操作，它必然是某个子树的最左下方的节点，此时需要转到该节点的右子树重复上述流程从而访问右子树的全部节点：

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
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        values = []
        stack = []
        current = root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            values.append(current.val)
            current = current.right

        return values

虽然前序遍历的非递归方案不适用于中序遍历，不过中序遍历的递归方案可略微修改适用于前序遍历，只需将 values.append(current.val) 放在不断入栈左子树的循环中即可：

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
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        values = []
        stack = []
        current = root

        while current or stack:
            while current:
                values.append(current.val)
                stack.append(current)
                current = current.left

            current = stack.pop()
            current = current.right

        return values

后序遍历

后序遍历和中序遍历相同，最先访问的都是最左下方的节点，所以对左子树不断入栈这段逻辑不变，不同的是当出栈时，当前出栈的节点有可能存在右子树，而右子树还还没有被访问，所以当前节点还不能出栈。因此，需要先判断栈顶的节点是否存在右子树，以及右子树是否被访问过，如果存在右子树且未被访问则转向右子树重复上述流程，否则可弹出栈顶节点。而判断栈顶的右子树是否被访问可通过比较栈顶的右子树和上一个被访问的节点来实现，如果两者相等，说明栈顶的右子树刚被访问过，否则未被访问过：

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
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        prev = None
        current = root
        stack = []
        values = []

        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            top = stack[-1]

            if top.right and prev != top.right:
                current = top.right
            else:
                current = stack.pop()
                values.append(current.val)
                prev = current
                current = None

        return values

通用模板

上述各非递归方案各不相同，是否存在和递归方案类似的通用模板方案？这里 给出了一种通用方案，首先需要额外引入一个数据结构来标记节点是否被访问过：

1
2
3
4
5
6
7
8
9
private class Pair {
    boolean visited;
    TreeNode node;

    Pair(TreeNode node, boolean visited) {
        this.node = node;
        this.visited = visited;
    }
}

在 Python 中，可简单通过元组来实现，对应模板代码为：

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
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def xxxTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        stack = [(root, False)]
        values = []
        
        while stack:
            current, visited = stack.pop()
            
            if visited:
                values.append(current.val)
            else:
                # 在这里处理左子树，右子树，根节点的入栈顺序
                pass
        
        return values

对于三种遍历方式，上述模板方法仅在处理左子树，右子树，根节点的入栈顺序上不同，实际入栈顺序和遍历顺序相反：

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
# 前序遍历
if current.right:
    stack.append((current.right, False))

if current.left:
    stack.append((current.left, False))

stack.append((current, True))

# 中序遍历
if current.right:
    stack.append((current.right, False))

stack.append((current, True))

if current.left:
    stack.append((current.left, False))

# 后序遍历
stack.append((current, True))

if current.right:
    stack.append((current.right, False))

if current.left:
    stack.append((current.left, False))

从出栈的角度来说，上述方法和理论遍历顺序并不一致，每个节点会入栈两次，第二次入栈时才会设置 visited 为 True，但从 visited 的角度来说顺序是和理论遍历顺序一致的。

参考

Posted on Word count in article: 974 Reading time ≈ 2 mins.

Docker Hub 的免费账户已不再支持关联 GitHub 仓库并自动构建镜像的功能，不过可以通过 GitHub Actions 来自动构建和推送镜像。实现方式非常简单，Docker 官方已给出了示例（Build and push Docker images）：

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
name: ci

on:
  push:
    branches:
      - 'master'

jobs:
  docker:
    runs-on: ubuntu-latest
    steps:
      -
        name: Set up QEMU
        uses: docker/setup-qemu-action@v1
      -
        name: Set up Docker Buildx
        uses: docker/setup-buildx-action@v1
      -
        name: Login to DockerHub
        uses: docker/login-action@v1 
        with:
          username: ${{ secrets.DOCKERHUB_USERNAME }}
          password: ${{ secrets.DOCKERHUB_TOKEN }}
      -
        name: Build and push
        id: docker_build
        uses: docker/build-push-action@v2
        with:
          push: true
          tags: user/app:latest

一共有三处要注意，第一开头的 branches 下对于新建的仓库需要填写 main 而不是 master。

第二需要为 Login to DockerHub 阶段设置 Docker 的 Access Token，Access Token 可以通过 Docker Hub 的 Account Settings -> Security -> New Access Token 创建，然后通过 GitHub 仓库的 Settings -> Secrets -> New repository secret 分别创建 DOCKERHUB_USERNAME 和 DOCKERHUB_TOKEN。

第三最后的 tags: user/app:latest 中的 user 和 app 需要修改为实际的用户名和镜像名。

参考：

Posted on Word count in article: 172 Reading time ≈ 1 mins.

Commodity Hardware 指较为廉价的硬件设备，它具有如下特点：

  1. 价格相对低廉
  2. 易采购
  3. 和同类型的硬件可相互替换

由此相关的一个概念叫 commodity computing，即使用大量的廉价硬件来实现低成本、高性能的并行计算，与之相对的则是使用较少数高成本的超级计算机。

参考：

Posted on Word count in article: 662 Reading time ≈ 1 mins.

创建了 Azure MySQL 实例后（这里使用的是 Flexible Server），首先导出原始数据库的数据，因为用的是 Docker 所以通过以下方式导出：

1
docker exec ${container_id} /usr/bin/mysqldump -u ${user_name} --password=${password} ${database_name} > backup.sql

然后通过 Azure CLI 创建一个新的数据库：

1
az mysql flexible-server db create --resource-group ${resource_group} --server-name ${server_name} --database-name ${database_name}

最后通过 Azure CLI 导入数据：

1
az mysql flexible-server execute -n ${server_name} -u ${user_name} -p ${password} -d ${database_name} -f ${path_to_backup_sql_file}

参考：

Posted on Word count in article: 313 Reading time ≈ 1 mins.

在 Java 中，如果两个同名方法仅返回值类型不同，这是不允许的，即编译器不会认为这是方法重载，如下述类中的方法 f：

1
2
3
4
5
6
7
8
9
public class Demo {
    public int f() {
        return 0;
    }

    public String f() {
        return "";
    }
}

编译器会提示 'f()' is already defined in 'Demo'。假设编译器支持这种方式的方法重载，会有什么问题？在某些情况下，编译器无法区分调用的是哪个方法，例如当调用 f() 却忽略返回值时：

1
f();

所以仅返回值类型不同不能作为方法重载的形式。

参考：

  • Thinking in Java

Posted on Word count in article: 435 Reading time ≈ 1 mins.

和常见的语言不同，Python 的 for/while 可以配合 else 使用。简单来说，当 for/while 循环体中没有执行 break 时，就会执行 else 中的代码。假设需要判断数组中是否存在某个数，如果不存在的话则抛出异常，一种可能的写法是：

1
2
3
4
5
6
7
8
9
10
11
target = 10
found = False

for i in range(5):
    if i == target:
        found = True

        break

if not found:
    raise Exception('not found')

借助 for/while else 可改写成：

1
2
3
4
5
6
7
target = 10

for i in range(5):
    if i == target:
        break
else:
    raise Exception('not found')

虽然代码少了几行，但是对于不熟悉该语法特性的人来说可能无法一眼看穿代码的意图。

参考：

Posted on Word count in article: 971 Reading time ≈ 2 mins.

使用 Python 的 heapq 模块时，如果处理的是较为复杂的数据结构，则需要实现自定义比较器来比较两个元素的大小。

使用元组

如果 heapq 中放入的是元组，那么元组的第一个元素会用于大小比较。假设有这样一个问题，给定一个数组，返回前 k 小的数字所在数组中的位置。Top k 的问题的一个解法是使用堆，但是这里要求的是数字在数组中的位置而不是数字本身，所以不能直接将数组堆化，可以先将数组中的每个数字转换成一个包含2个元素的元组，元组的第一个元素是数字本身，第二个元素则是数字在数组中的位置。

1
2
3
4
5
6
7
8
9
10
import heapq

def top_k(numbers, k):
  heap = [(n, i) for i, n in enumerate(numbers)]
  heapq.heapify(heap)

  return list(map(lambda x: heapq.heappop(heap)[1], range(k)))

if __name__ == '__main__':
  print(top_k([5, 4, 3, 2, 1], 3)) # [4, 3, 2]

实现自定义比较器

当放入堆中的是自定义类时，可以通过实现 __lt__ 方法来比较元素大小。假设有一个自定义类为 Node，它包含一个 value 属性，现在问题改为给定一个 Node 的数组，返回前 k 小的 Node 的值，可通过实现 __lt__ 方法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq

class Node:
  def __init__(self, value):
    self.value = value

  def __lt__(self, other):
    return self.value < other.value

def top_k(nodes, k):
  heap = [node for node in nodes]
  heapq.heapify(heap)

  return list(map(lambda x: heapq.heappop(heap).value, range(k)))

if __name__ == '__main__':
  print(top_k([Node(5), Node(4), Node(3), Node(2), Node(1)], 3)) # [1, 2, 3]

参考

Posted on Word count in article: 2.1k Reading time ≈ 3 mins.

日常随着 Docker 的使用，Docker 会逐渐占用磁盘空间，通过 docker system df 可查看 Docker 所占用的空间：

1
2
3
4
5
TYPE            TOTAL     ACTIVE    SIZE      RECLAIMABLE
Images          20        14        22.21GB   17.07GB (76%)
Containers      29        0         6.743GB   6.743GB (100%)
Local Volumes   2         0         417MB     417MB (100%)
Build Cache     0         0         0B        0B

其中 Images 表示镜像，Containers 表示容器，Local Volumes 表示本地卷，Build Cache 表示构建缓存。

整体清理

可以通过 docker system prune 进行一次空间清理：

1
2
3
4
5
6
7
WARNING! This will remove:
  - all stopped containers
  - all networks not used by at least one container
  - all dangling images
  - all dangling build cache

Are you sure you want to continue? [y/N]

该操作会删除所有停止的容器，所有未被至少一个容器使用的网络，所有的 dangling 镜像（在构建镜像时产生的 tag 为 none 的镜像，没有和任何其他有 tag 的镜像有关联），所有的 dangling 构建缓存（和 dangling 镜像同理）。

更激进一点，还可以执行 docker system prune -a，该操作还会删除没有和运行中的容器有关联的镜像。

镜像清理

Docker 镜像是某个应用（如数据库、某个程序语言的运行时）的磁盘快照，可以通过 docker image ls -a 查看所有的镜像（活跃的以及 dangling 的镜像）：

1
2
REPOSITORY    TAG       IMAGE ID       CREATED        SIZE
hello-world   latest    d1165f221234   4 months ago   13.3kB

可以通过 docker image rm <name_or_id> 来删除某个镜像，支持批量删除多个镜像，多个镜像 id 之间使用空格分隔即可。不过，删除镜像要求该镜像没有被某个容器所使用，否则会提示下述类似错误：

1
2
Error response from daemon: conflict: unable to delete 4cdc5dd7eaad (must be forced) - image is being used by stopped container 3d9f62acc483
Error response from daemon: conflict: unable to delete d1165f221234 (must be forced) - image is being used by stopped container 57027ba35bdd

可以通过在执行时增加 -f 来强制删除镜像。

容器清理

容器是某个镜像的一个运行实例，可以通过 docker container ls -a 查看所有的容器：

1
2
CONTAINER ID   IMAGE          COMMAND                  CREATED          STATUS                      PORTS     NAMES
3d9f62acc483   4cdc5dd7eaad   "/docker-entrypoint.…"   11 minutes ago   Exited (0) 11 minutes ago             sleepy_babbage

要删除一个容器必须要先停止该容器（docker container stop <name_or_id>），然后通过 docker container rm <name_or_id> 删除，同样的，和删除镜像类似，该命令支持批量删除多个容器，多个容器 id 之间使用空格分隔。

网络清理

Docker 网络用于容器间的通信，它们都是一些配置文件，并不会占用多大空间，可以通过 docker network ls 查看所有的网络：

1
2
3
4
NETWORK ID     NAME      DRIVER    SCOPE
b96312481a51   bridge    bridge    local
85a64f881d4d   host      host      local
e6808b80f888   none      null      local

可以通过 docker network rm <name_or_id> 来删除一个网络。

数据卷清理

Docker 数据卷用于持久化容器运行时保存的数据，例如通过 Docker 运行 MySQL 时指定数据卷，从而对 MySQL 的数据进行备份，可以通过 docker volume ls 查看所有的数据卷：

1
2
DRIVER    VOLUME NAME
local     test-volume

同样的，可以通过 docker volume rm <name> 来删除指定的数据卷，或者使用 docker volume prune 来删除所有未和运行中的容器关联的数据卷，以及通过 docker volume prune -a 删除所有的数据卷。

最后，docker system prune -a --volumes 是在 docker system prune -a 的基础上删除所有未使用的卷。

参考

Posted on Word count in article: 575 Reading time ≈ 1 mins.

使用 SSH 连接到 Azure 的虚拟机时遇到错误：

1
2
3
4
5
6
7
8
9
➜  ~ ssh -i /path/to/some.pem xxx@x.x.x.x
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         WARNING: UNPROTECTED PRIVATE KEY FILE!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Permissions 0644 for '/path/to/some.pem' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
Load key "/path/to/some.pem": bad permissions
xxx@x.x.x.x: Permission denied (publickey).

这是因为创建虚拟机时从 Azure 下载的私钥默认权限太大，需要将其权限改为只读且仅当前用户可见：

1
chmod 400 some.pem

参考：

Posted on Word count in article: 241 Reading time ≈ 1 mins.

如果一个数除了1和它本身外，没有其他约数，我们称这个数为质数，但在这个定义下，1却不是质数。要回答这个问题需要先了解质数的作用，质数的主要作用在于构建欧几里得的算数基本定理：

任何一个大于1的自然数都可以唯一分解成有限个质数的乘积。

如果把1列为质数，就会破坏这种唯一性，因为在这种情况下每个自然数都有无限种分解方式，即在原有分解的基础上再乘以任意个数的1，所以1不作为质数。

参考：

0%