ARTS - week 8 补打卡

Algorithm

题目链接

https://leetcode-cn.com/problems/find-eventual-safe-states/

找到最终安全状态

在有向图中，从某个节点和每个转向处开始出发，沿着图的有向边走。如果到达的节点是终点（即它没有连出的有向边），则停止。

如果从起始节点出发，最后必然能走到终点，就认为起始节点是 最终安全 的。更具体地说，对于最终安全的起始节点而言，存在一个自然数 k ，无论选择沿哪条有向边行走 ，走了不到 k 步后必能停止在一个终点上。

返回一个由图中所有最终安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-eventual-safe-states

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

设置四个状态，unvisted, visiting, unsafe, visited.

对于一个节点，首次访问设置节点 X 为 visiting, 并对后续未访问节点 Y 进行深度优先搜索。后续节点 Y 经过深度优先搜索，状态可能 visiting, unsafe, visited。如果后续节点 Y 是 unsafe, 毫无疑问，当前节点也会变为 unsafe, 如果后续节点是 visiting, 说明是当前链路中访问的节点，也就是存在环，此时 X 和 Y 都为 unsafe, 如果后续节点 Y 状态为 visited, 说明该节点是安全的。如果所有 X 的后续节点均为安全的，则 X 也是安全的。

当对某节点 X 完成 dfs 操作，仅会有两种状态，visited 或者 unsafe。

代码实现

// 状态转移方法class Solution {public:    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {        vector<int> visited(graph.size(), 0);        for(int i = 0; i < graph.size(); i++){            if(visited[i] == 0){                dfs(graph, i, visited);            }        }        vector<int> result;        for(int i = 0; i < graph.size(); i++){            if(visited[i] == 3){                result.push_back(i);            }        }        return result;    }
    void dfs(vector<vector<int>> &graph, int v, vector<int>& visited){        visited[v] = 1;        for(auto nxt: graph[v]){            if(visited[nxt] == 0){                dfs(graph, nxt, visited);            }            if(visited[nxt] != 3){                visited[nxt] = 2;                visited[v] = 2;            }        }
        if(visited[v] != 2){            visited[v] = 3;        }    }};



Review

How to make an awesome Python package in 2021 | Anton Zhiyanov, 这篇文章是介绍如何发布 python package 的，以前一直以为是一件很困难的事情。通过作者介绍，发现整个过程没太困难，因此推荐这篇文章，能够省去很多搜索踩坑时间。具体工具和步骤如下

1. 创建文件目录和虚拟环境；

2. 安装 flit, 是这个工具让 python package 变得简单, 安装后创建基本的 package 信息

pip install flit

3. 在 TestPyPi, PyPi 两个网站注册用户，两个网站账户系统独立，因此需要注册两次；

4. 通过 linter 和 tests 进行代码风格规范和代码测试， tox 能够控制所有 lint, test 流程

pip install black coverage flake8 mccabe mypy pylint pytest tox

5. 接下来可以设置在 github 上， 每次 commit 进行 cloud test

6. github 可以进行 flit publish

按照上述流程，就可以发布自己的程序，代码清晰，测试充分，有文档。本文具有很强的参考意义，使得之前觉得很困难的事情变得容易，每个人也可以发布自己的 package, 推荐阅读。

Tips

python staticmethod 和 class method 用法，这个是在 python 编程过程中不可避免的一个困惑。也是社区激烈讨论的问题，在此处我给出自己的想法，也欢迎评论区讨论。

首先，从实用角度而言，两者功能基本可以 90%互相替代。

10%的差异主要在于，@staticmethod 不包含隐式的参数（如 self）, 但是 @classmethod 使得该函数的第一个参数是该函数所在的类（注意：不是该类的实例）。这样导致用法上面，@staticmethod 是用于程序的结构的整齐，将属于该类的方法放到这个类里面，是出于逻辑关系的考虑。鉴于 python 是通过 file 来进行模块分割，staticmethod 和 module function 功能相差无几，就是能够阐述逻辑关系。@classmethod 则不同，如果想让某个函数成为类的 factory, 或者实现多态机制， classmethod 会是更好选择，因为第一个参数会是该函数的所在类。

如下面代码,注意如果用 staticmethod, 会调用父类的对应函数，然后输出 None,但是 classmethod 没有这个困扰。

具体讨论请参考 https://stackoverflow.com/questions/136097/difference-between-staticmethod-and-classmethod

Share

本周分享的观点是关于技术模块化的变更指南。首先说明，这个观点是从《技术的本质》这本书里获得的，感觉用于无论软件还是制造业都可以，通过 spaceX 的研发过程，也说明了这一点。技术的模块化可以更好地预防不可预知的变动，同时简化了设计流程。但是模块不是一成不变的，如软件当中的库，如硬件当中的激光雷达或者导航系统，何时进行变更呢？如果够稳，暂时不要变更，只有当某个模块被反复使用足够多的次数的时候，才值得考虑进行切割为更小的技术单元。切割的原因很简单，技术是自然现象通过组合来完成的，无论多么高精尖的技术，本质上都是自然现象的组合。当切割为更小单元的时候，就是可能发生技术突变的时候。