ARTS #163

Algorithm

本周选择的算法题是：Max Area of Island。

规则

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

Solution

impl Solution {
    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let mut max_area = 0;
        let (m, n) = (grid.len(), grid[0].len());
        let mut seen = vec![vec![false; n]; m];

        for i in 0..m {
            for j in 0..n {
                if seen[i][j] || grid[i][j] == 0 { continue; }
                seen[i][j] = true;

                let mut area = 0;
                let mut stack = vec![(i, j)];

                while let Some((x, y)) = stack.pop() {
                    area += 1;

                    for (dx, dy) in [(x+1, y), (((x as isize)-1) as usize, y), (x, y+1), (x, ((y as isize)-1) as usize)] {
                        if dx < m && dy < n && grid[dx][dy] == 1 && !seen[dx][dy] {
                            stack.push((dx, dy));
                            seen[dx][dy] = true;
                        }
                    }
                }
                max_area = max_area.max(area);
            }
        }
        
        max_area
    }
}

Review

The purpose of testing

测试在不同行业、公司会用不同的方法，有些领域（如银行业、航空业），一个小错误都有可能引发一连串的大问题，对这些领域来说，测试至关重要，需要制定严格的测试程序。

测试流程其实和做饭很像：

首先分析食物配方
准备食材
做的过程，尝一尝味道，咸不咸、比例是否合适
尝第二次，看看时间是否合适，或许还需要 5 分钟
几分钟后，尝第三次，现在刚刚好

这套流程和测试方法，被前辈总结成了测试驱动开发 (TDD)：

专业的测试需要专业知识，但更重要的是测试心态，不一定要有独立的测试部门，只要团队有强大的测试心态也能构建出高质量的产品。

Tip

Termius 太好用了~

尝试 Rust 后的一些感想，分为语言层面和工具层面吧。

语言层面

Rust 语法结构简单，代码可读性很好，而且有 map、filter、find 这类函数式编程的功能，定义高阶函数、传递闭包容易而自然，虽然不如 Ruby，但也很接近了，特别是相对 C/C++ 来说。

Rust 强制开发者思考内存问题，没得选，想写出邋遢的代码不太轻松，逻辑正确的好代码反而更容易写出来，线程安全的代码同样如此。

Trait 提供了现代编程抽象，而零开销抽象特点使得代码好的同时没有额外的性能开销。

Rust 代码是安全的，只要避免使用 unsafe 关键字或者调用不安全的 C 库。

Result、Option 提供了更好的方式处理函数的返回值和变量，在以往 C、C++ 和 Java 的实践中，如果一个函数没有东西可返回则会返回一个空指针，多数情况下，如果有意外发生，问题排查的成本很高。

上面是好的方面，不好的方面则是有时候 unwrap、as_ref、borrow 会显得罗嗦，我觉得如果有语法糖节省此类调用的频率就好了。

编译器为了在合理的时间成功编译代码，做了一些取舍，比如 rustc 在某些情况下无法推断出类型，此时就需要人工介入，我发现有时候很难弄清楚编译器想要什么，可能还需要更长的时间来理解。

罗嗦 again，str 与 String 需要显式转换，我相信编译器对此肯定有充分的理由，毕竟 rustc 要确保绝对正确。

Result 确实很好，但为了正确处理每个函数调用的返回不得不做一些单调乏味的工作，引入 ? 操作符使处理简洁了一些，但仍然缺少通用的错误处理机制，我们必须要为每一种可能的错误情况显式地定义错误类型。

Rust 的宏略显复杂（与其他语言相比），或许我将来会改变看法，但现在我会竭力避免接触它们，就像避免接触新冠病毒一样。

工具层面

Rust 的工具生态很强大，借助 RLS 可方便地将 lint、代码完成、语法检查、格式化等接入到像 VS Code、Xcode 这样的 IDE 中。

Cargo 是很优雅的包管理工具，其提供了大量类似 code coverage 的插件扩展；Cargo 也是一个构建系统，它可以执行单元测试和集成测试，项目配置和依赖通过 TOML 配置文件管理；Cargo 还集成了 crates.io，就像 Python 的 PyPI，发布库、找库很容易。

rustup 是管理 Rust 安装环境的首选工具，可以方便的选择稳定版、测试版或 nightly，还可以通过它安装像 clippy 这样的组件。

clippy 是很棒的 linter，能帮开发者用 Rust 的方式写代码，有时候我知道怎么解决问题，但不知道这是否是最佳实践，clippy 在这种情况下很有帮助，多人协作的福音。

上面是好的方面，不好的方面则是编译很慢…

Rust 生态的确很强，基本上如果要找什么库总有多种选择，但其中也难免有完成度不高的、不够成熟的或缺少维护的库，Rust 社区还处于早期阶段，但它每天都在成长。

太多的选择也会带来烦恼，比如日志库，这个列表不算短，Java 生态也类似，Java 的日志库有 java.util.logging、log4j、logback、log4j2、slf4j 和 tinylog，直到今天，也没法说选择哪个 Java 日志库是绝对正确的，对于 Rust，或许我能用 env_logger，仅仅因为它是列表中的第一个选项。

虽然没有 Node.js 的生态那么糟糕，但 Rust 库的依赖列表变得越来越长了，认真看下你引入的库的依赖项，你会感到惊讶的，这暗示了生态系统中存在碎片化和重复的情况，或许可以通过将一些通用的能力沉到标准库中以改善此情况。

最后

Rust 是一门很棒的语言，我对尝试 Rust 的过程感到很兴奋，如果你也热衷编程，请尝试一下，希望你会喜欢它。

Algorithm

规则

Solution

Review

Tip

Share

语言层面

工具层面

最后