Monthly Archive: June 2020

这题还是挺难写对的。经过几番尝试以后，发现最好理解的算法就是先对group做一次拓扑排序。然后按group的顺序，对每个group里的items的做拓扑排序。这题增加另一难点在于gorup是-1的情况。其实相当于每个-1都是自己的新group。于是大量的工作其实在建立group的dependency graph上。拓扑排序的函数可以写一次反复重用。Python解法如下： 本题是复合题，三个点：1. 拓扑排序本身，然后分别用在group level和每个group的item level2. 建立group dependency3. handle group == -1的情况，就是给每个这种item assign新group

这题不知道为什么被标记为topological sort，但其实和topological sort没什么关系，只是DFS。Implementation确实和DFS的topological sort有点像，但是因为没有graph的dependency关系，其实还是不一样的。不过cache的使用上确实有相似性。以下是我写得比较满意的python解法 要点总结： 用这种方式初始化cache比较简洁 ，新学到的 cache = [[0] * len(line) for line in matrix] 用nested function大大减少需要传递状态的参数 nonlocal max_l可以让nested function直接改变外面的参数很方便，所以在外面call dfs的时候连return都不用处理 dirs = [(1,0), (-1,0), (0,1), (0,-1)]，i2 = i + d[0]，j2 = j + d[1]处理方向。以前都是手写上下左右，太啰嗦而且容易出错。这种方法对2维DFS很适用。

这题基本和269 alien dictionary一样，难度为medium。其实269 alien dictionary比这题多了就是建graph的过程而这题的graph基本是已经给定的。重点还是topological sort部分。比207. Course Schedule多了两行handle sort部分。以下为同样思路的python解法，比较简短，容易写对。

这题以前觉得特别难，其实是简化版的topological sort，也就是只需要判断有没有环(circular dependency)和省掉了sort部分。可以用269 alien dictionary同样的DFS思路加以简化而成。 这是最近写得比较满意的python解法。 对比一下大概半年前写得当时比较满意版本，其实算法差不多。有如下小改进让code更短了：1. seen用了Tree和False表示走通了的和当前正在走的路径，比原来的更省事。看来2种状态是判断环和避免重新走原来走过的路所必要的。2. 节点全部写进edges里面，edges = {c: set() for c in range(numCourses)} ，不管有没有dependency，省了 if i not in deps: 判断3. 需要order的话，dfs参数start, edges, seen order。不需要的话order的话就省掉order，只要start, edges, seen。用函数内定义函数可以少写很多用来传递状态的参数。

这题本质上是一个拓扑排序topological sort，需要判断有没有环来处理无效input，难度主要来自这部分。Topological sort可以用dfs解决，但是没练习过还不不容易写对的。先上一个我比较满意的python解法。 总结一下要点。1. edges = {c: [] for word in words for c in word} 这种一行两个循环建map的方式我也是新学的，很方便。这个map key是排前面的字母，value是排后面的字母。而且不管有没有后面的，key都加上了，这样省了另一个变量存字母表，可以对比我之前一个写对不那么好的解法。2. 用zip遍历pair很好用，减少了出index bug的可能3. len(word1) > len(word2) and word1.startswith(word2)，这是一个特殊的case。比如abc排在ab前面，不管什么字母表顺序，就是c排在空前面，那是无效的。4. seen的利用，这是最巧妙的地方。写了几种尝试，发现环不太容易。如果只用一个set记录visited，就无法区分是一条已经走通的路还是当前这条路又回到某个之前经过的一点。解法方法可以用一个set记录visited，只加不减，另一个set记录当前这条路的路径，回溯时要更新，比较麻烦。这种解法利用了False和True两种states，False代表正在走的路，True代表以前已经走到底能走通的路。非常深刻，我想了很久才算大概理解。5. if not all(dfs(start) for start in edges)，all是个我新学的function，input是collection或者更准确说是可以iterable的东西，就是要每个元素都是true就是true。换句话说就像开关串联。本来我写得是all([dfs(start) for start in edges])，后来发现代表list的方括号可以省略，估计是些语法糖。Python里面确实有很多我不知道的语法糖。6. dfs是函数内定义的函数，可以省了self和用内函数外的变量保存状态，不用每个recursion call都pass一次。 做完这题后，重新做course…
Read more

到python官方网站，下载macOS 64-bit installer 。 下载完成后双击.pkg文件安装既可 我这原来的/usr/bin/python3 还是3.7 怎样在pycharm里使用？ Setting里面（cmd + ,) search interpreter，选project interpreter 添加成功后 怎样创建virtual environment? python 3.8.3有什么新特性？ 新添了类型提示。

和add binary基本一样。 关键点：从右边开始加把长的input作为第一个，给最左边加0用来进位（如果需要的话），最后看要不要去掉python里面要用ord，chr 来做char/ascii转换 python解法

和add strings基本一样。 关键点：从右边开始加把长的input作为第一个，给最左边加0用来进位（如果需要的话），最后看要不要去掉python里面要用ord，chr 来做char/ascii转换 python解法

会把这个key加入到unordered_map里面，value是数据类型的default值。比如int就是0，string就是””。