ARTS #187 | 喂天鹅

Algorithm

本周选择的算法题是：Longest Path With Different Adjacent Characters。

规则

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example 1:

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

Example 2:

Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

Constraints:

n == parent.length == s.length
1 <= n <= 105
0 <= parent[i] <= n - 1 for all i >= 1
parent[0] == -1
parent represents a valid tree.
s consists of only lowercase English letters.

Solution

impl Solution {
    pub fn longest_path(parent: Vec<i32>, s: String) -> i32 {
        let mut ans = 0;
        let mut tree = vec![vec![]; parent.len()];
        for i in 1..parent.len() {
            tree[parent[i] as usize].push(i);
        }
        Solution::def(0, &tree, &s.chars().collect(), &mut ans);
        ans
    }

    fn def(node: usize, tree: &Vec<Vec<usize>>, s: &Vec<char>, ans: &mut i32) -> i32 {
        let (mut max1, mut max2) = (0, 0);
        for child in &tree[node] {
            let longest_child_path = Solution::def(*child, tree, s, ans);
            if s[*child] == s[node] { continue }

            if longest_child_path > max1 {
                max2 = max1;
                max1 = longest_child_path;
            } else if longest_child_path > max2 {
                max2 = longest_child_path;
            }
        }
        
        *ans = std::cmp::max(*ans, max1 + max2 + 1);
        max1 + 1
    }
}

Review

Score - One YAML to rule them all

Score 是音乐术语，表示乐谱或总谱，记录了每个表演者应该演奏什么以及合奏应该是什么。

这篇文章介绍的 Score 借用了该术语，它期望在云原生时代让开发者通过一个 “乐谱” 描述要用什么容器和资源提供服务。Score 有三个核心概念：

Score Specification - 即乐谱
Score Implementation - 一个 CLI 工具，用于将乐谱翻译为 score 支持的各类平台相关的配置文件，如 score-compose
Platform configuration file - 将 score 配置文件进一步翻译为具体平台的配置文件，如 docker-compose.yaml

借助 Score，开发人员不需要成为各种技术栈的专家（但或许需要成为 Score Specification 专家），就可以轻松完成复杂技术栈的编排工作，并可通过 Score 确保基于同一 Score Specification 生成的本地开发配置和共享开发环境的配置以及 serverless 平台配置的一致性，方便开发、部署和测试。

属于 platform engineering 范畴下的解决方案。

Tip

一个生成 SQL 的在线工具: AI Query，顾名思义，它用到了当前流行的 AI 技术。

分享一种另类的 shell 跨平台方案~

先简单介绍下 macOS 的 Terminal 和 Windows 的 Command Line 的区别：

macOS Terminal 使用 bash 作为默认的 shell，10.15 (Catalina) 调整为了 zsh，无论是 bash 还是 zsh，作为 “sh” 都有相同的基础语法，比如文件系统路径用 “/this/that”；PATH 使用 “:” 分隔；重定向使用 ”>“、”<“；后台运行用 “&”；多条命令使用 “;” 分隔等等
Windows Command Line 使用的是则是 CMD.COM 的派生物，它已发展成了 CMD.EXE，虽然基础语法在所有的 shell 中都差不多，但也有一些完全不同的部分，如路径使用 “\this\that”；PATH 使用 “;” 分隔；重定向与 “sh” 类似；后台运行使用内置命令；多条命令使用 “&” 分隔等等

可以看出一些字符被赋予了不同的语义，很不幸的导致 shell 程序很难在 macOS 和 Windows 之间复用。

除了语法不同，shell 的能力差异也限制了开发者使用它们的意图：

CMD.EXE 除了运行程序和将输出存储到指定文件外几乎毫无用处，只能利用不到 10% 的 OS 能力
macOS Terminal 完全相反，它在日常工作中被大量使用，绝大多数 OS 能力都可以访问

因此，如果你想要实现跨平台 shell 程序，大概有这么几种选择：

使用 PowerShell，然而要写出完全跨平台的 shell 程序并不容易，参考 Tips for Writing Cross-Platform PowerShell Code
使用 Python 这样的脚本语言
使用可编译为面向特定平台的语言

无论哪一种都需要调整已有程序的实现，如果程序中包含大量对环境变量的定义、继承、使用等场景，改写起来非常复杂且投入产出比不划算。

本文要分享的是一种另类的方式，不需要调整代码，没有语法不兼容的情况，也是 Git for Windows 采用的解决方案 - 集成一个 bash 和 sh 程序：

Git for Windows provides a BASH emulation used to run Git from the command line. *NIX users should feel right at home, as the BASH emulation behaves just like the “git” command in LINUX and UNIX environments.

但我们不需要自己集成，只要机器安装了 Git，再将 Git 的 bin 目录添加进环境变量，之后使用 Git 集成的 bash 和 sh 即可，问题解决。

Algorithm

规则

Solution

Review

Tip

Share