ARTS #47

Algorithm

本周选择的算法题是：N-Queens

规则如下：

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution

Runtime：132 ms，快过 30.83%。

Memory：14.1 MB，低于 5%。

原始解法：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n == 0: return [[]]
        matrix = [["."] * n for _ in range(n)]
        ans = []

        def can_be_here(i, j) -> bool:
            for row in range(i):
                if matrix[row][j] == 'Q': return False
                if j-i+row >= 0 and matrix[row][j-i+row] == 'Q': return False
                if j+i-row < n and matrix[row][j+i-row] == 'Q': return False

            return True

        def dfs(i, j):
            if can_be_here(i, j):
                matrix[i][j] = 'Q'

                if i == n - 1:
                    ans.append(["".join(row) for row in matrix])
                else:
                    for k in range(n):
                        dfs(i + 1, k)
                matrix[i][j] = '.'

        for j in range(n):
            dfs(0, j)

        return ans

可以看到在时间和空间上都有明显的优化空间：

空间上 - 由于每行每列只会有一个 Q，所以没必要保存完整的矩阵，只需要记录 Q 所在的列即可
时间上 - can_be_here 方法用于检查 (i, j) 所处的位置能不能放 Q，配合上述的空间优化，可以通过记录列上的对角线优化成 \(O({1})\)

优化后

Runtime：64 ms，快过 77.34%。

Memory：14.1 MB，低于 5%。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n == 0: return [[]]
        matrix, diagonal_left, diagonal_right = [-1] * n, set(), set()
        ans = []
        
        def can_be_here(i, j) -> bool:
            if j in matrix or (j - i) in diagonal_left or (j + i) in diagonal_right:
                return False
            return True

        def dfs(i, j):
            if can_be_here(i, j):
                matrix[i] = j
                diagonal_left.add(j-i)
                diagonal_right.add(j+i)

                if i == n - 1:
                    ans.append(['.' * column + 'Q' + '.' * (n-column-1) for column in matrix])
                else:
                    for k in range(n):
                        dfs(i + 1, k)
                diagonal_right.remove(j+i)
                diagonal_left.remove(j-i)
                matrix[i] = -1

        for j in range(n):
            dfs(0, j)

        return ans

进一步优化后

Runtime：52 ms，快过 93.37%。

Memory：13.9 MB，低于 5%。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n == 0: return [[]]
        ans = []

        def dfs(matrix, diagonal_left, diagonal_right):
            i = len(matrix)
            if i == n:
                ans.append(['.' * column + 'Q' + '.' * (n-column-1) for column in matrix])
                return

            for j in range(n):
                if j not in matrix and (j - i) not in diagonal_left and (j + i) not in diagonal_right:
                    dfs(matrix + [j], diagonal_left + [j-i], diagonal_right + [j+i])

        dfs([], [], [])

        return ans

这次优化的主要操作有：

diagonal_left 和 diagonal_right 作为临时参数传递，因为用变量要不断的做「添加、回滚」，更繁琐，不如直接用临时变量的方式传递
can_be_here 中的循环休被干掉后，没有必要单独做成一个方法了
干掉最外层的循环，两层循环合并后，对时间复杂度没有影响，但是代码会更简洁

Review

Introduction to Dart VM

一篇介绍 Dart VM 整体设计的文章，作者似乎不再更新了。。。

深入浅出，介绍的很详细；有些地方看的不是太理解，先让自己有个初步的印象。

Tip

在 return 的位置设置断点：

br set -p return

配合 Step out 可以查看 return 的内容。

好的组件间通信方案的 Checklist：

支持简单参数和复杂参数的传递，对收发双方而言均能正确解析
组件彼此之间是弱关联关系，除了在代码层面隔离开，数据层面也要隔离开
有正确的调用上下文，对调用者来说，实现是一个黑盒子
避免侵入式的设计，接口暴露的方式不会污染响应者，并且不会对响应者的迭代、维护造成影响
支持对调用参数做检查
对 OC 而言：
- 组件提供的能力不需要注册，不需要额外的内存存储
- 支持 Universal Link 和 Deep Link 的外部调用，外部调用是作为整体组件间通信方案的拓展功能

Algorithm

Solution

Review

Tip

Share