算法练习 Leetcode 力扣 1203. Sort Items by Groups Respecting Dependencies 解法

这题还是挺难写对的。经过几番尝试以后,发现最好理解的算法就是先对group做一次拓扑排序。然后按group的顺序,对每个group里的items的做拓扑排序。这题增加另一难点在于gorup是-1的情况。其实相当于每个-1都是自己的新group。于是大量的工作其实在建立group的dependency graph上。拓扑排序的函数可以写一次反复重用。Python解法如下:

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

        cur_group = m + 1
        for i in range(len(group)):
            if group[i] == -1:
                group[i] = cur_group
                cur_group += 1

        group_ids = set(group)

        itemLevelBeforeGroups = []
        for i in range(len(beforeItems)):
            each_node_before_groups = [group[before] for before in beforeItems[i]]
            each_node_before_groups = list(filter(lambda x: x != i, each_node_before_groups))
            itemLevelBeforeGroups.append(each_node_before_groups)

        # beforeGroups
        beforeGroups = {g: set() for g in group}
        for i in range(len(itemLevelBeforeGroups)):
            beforeGroups[group[i]].update(itemLevelBeforeGroups[i])
            beforeGroups[group[i]] = beforeGroups[group[i]].difference([group[i]])
        # print(f'beforeGroups = {beforeGroups}')

        groupToItems = {g: [] for g in group}
        for i in range(len(group)):
            groupToItems[group[i]].append(i)
        # print(f'group to items: {groupToItems}')

        cache = {}
        group_order = []
        itemLevelBeforeGroups

        def dfs(start, cache, order, before_nodes):
            # print(f'start =  {start}')
            if start in cache:
                return cache[start]
            cache[start] = False
            for before in before_nodes[start]:
                # print(f'  before = {before}')
                if not dfs(before, cache, order, before_nodes):
                    # print('found loop!')
                    return False
            # print('  {before} done')
            cache[start] = True
            order.append(start)
            return True

        for g in group_ids:
            if not dfs(g, cache, group_order, beforeGroups):
                return []
        # print(f"group_order = {group_order}")

        item_order = []
        item_cache = {}
        for g in group_order:
            for node in groupToItems[g]:
                if not dfs(node, item_cache, item_order, beforeItems):
                    return []

        # print(f"item order = {item_order}")
        return item_order

本题是复合题,三个点:
1. 拓扑排序本身,然后分别用在group level和每个group的item level
2. 建立group dependency
3. handle group == -1的情况,就是给每个这种item assign新group

算法练习 Leetcode 力扣 329. Longest Increasing Path in a Matrix 解法

这题不知道为什么被标记为topological sort,但其实和topological sort没什么关系,只是DFS。Implementation确实和DFS的topological sort有点像,但是因为没有graph的dependency关系,其实还是不一样的。不过cache的使用上确实有相似性。以下是我写得比较满意的python解法

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if (matrix is None or len(matrix) == 0 or  
                matrix[0] is None or len(matrix[0]) == 0):
                return 0
        lines = len(matrix)
        cols = len(matrix[0])
        
        cache = [[0] * len(line) for line in matrix]
        
        def is_valid(i, j):
            return i >= 0 and i < lines and j >= 0 and j < cols
        
        max_l = 0
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        
        def dfs(i: int, j: int) -> int:
            if cache[i][j] > 0:
                return cache[i][j]
            for d in dirs:
                i2 = i + d[0]
                j2 = j + d[1]
                if is_valid(i2, j2) and matrix[i2][j2] > matrix[i][j]:
                    cache[i][j] = max(cache[i][j], dfs(i2, j2))
            cache[i][j] += 1
            nonlocal max_l
            max_l = max(max_l, cache[i][j])
            return cache[i][j]
        
        for i in range(lines):
            for j in range(cols):
                dfs(i, j)
                
        return max_l

要点总结:

  1. 用这种方式初始化cache比较简洁 ,新学到的 cache = [[0] * len(line) for line in matrix]
  2. 用nested function大大减少需要传递状态的参数
  3. nonlocal max_l可以让nested function直接改变外面的参数很方便,所以在外面call dfs的时候连return都不用处理
  4. dirs = [(1,0), (-1,0), (0,1), (0,-1)],i2 = i + d[0],j2 = j + d[1]处理方向。以前都是手写上下左右,太啰嗦而且容易出错。这种方法对2维DFS很适用。

算法练习 Leetcode 力扣 210. Course Schedule II 解法

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

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        edges = {c: set() for c in range(numCourses)}
        for pr in prerequisites:
            edges[pr[1]].add(pr[0])
            
        order = []
        seen = {}
        
        def dfs(start):
            if start in seen:
                return seen[start]
            seen[start] = False
            for nxt in edges[start]:
                if not dfs(nxt):
                    return False
            seen[start] = True
            order.insert(0, start)
            return True
            
        if not all(dfs(start) for start in range(numCourses)):
            return []
        return order

算法练习 Leetcode 力扣 207. Course Schedule 解法

这题以前觉得特别难,其实是简化版的topological sort,也就是只需要判断有没有环(circular dependency)和省掉了sort部分。可以用269 alien dictionary同样的DFS思路加以简化而成。

这是最近写得比较满意的python解法。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        edges = {c: set() for c in range(numCourses)}
        for prereq in prerequisites:
            edges[prereq[1]].add(prereq[0])
        
        seen = {}
        
        def dfs(start):
            if start in seen:
                return seen[start]
            seen[start] = False
            for nxt in edges[start]:
                if not dfs(nxt):
                    return False
            seen[start] = True
            return True
        
        if not all(dfs(start) for start in range(numCourses)):
            return False
        return True

对比一下大概半年前写得当时比较满意版本,其实算法差不多。有如下小改进让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。用函数内定义函数可以少写很多用来传递状态的参数。

class Solution(object):
    def __init__(self):
        self.UNKNOWN = 0
        self.VISITED = 1
        self.CANTAKE = 2
        
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        deps = {}
        for pre in prerequisites:
            if pre[0] in deps:
                deps[pre[0]].add(pre[1])
            else:
                deps[pre[0]] = {pre[1]}
                
        status = [self.UNKNOWN] * numCourses
        for i in range(numCourses):
            if self.okToTake(i, status, deps) == False:
                return False
        return True
        
    def okToTake(self, i, status, deps):
        if status[i] == self.CANTAKE:
            return True
        elif status[i] == self.VISITED:
            return False
        status[i] = self.VISITED
        if i not in deps:
            status[i] = self.CANTAKE
            return True
        for dep in deps[i]:
            if self.okToTake(dep, status, deps) == False:
                return False
        status[i] = self.CANTAKE
        return True
    

算法练习 Leetcode 力扣 269. Alien Dictionary 解法

这题本质上是一个拓扑排序topological sort,需要判断有没有环来处理无效input,难度主要来自这部分。Topological sort可以用dfs解决,但是没练习过还不不容易写对的。先上一个我比较满意的python解法。

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        edges = {c: [] for word in words for c in word}
        for word1, word2 in zip(words, words[1:]):
            if len(word1) > len(word2) and word1.startswith(word2):
                return ''
            for c1, c2 in zip(word1, word2):
                if c1 != c2:
                    edges[c1].append(c2)
                    break
        
        seen = {}
        order = []
        def dfs(start):
            if start in seen:
                return seen[start]
            seen[start] = False
            for nxt in edges[start]:
                if not dfs(nxt):
                    return False
            order.insert(0, start)
            seen[start] = True
            return True
        
        if not all(dfs(start) for start in edges):
            return ''
        return ''.join(order)

总结一下要点。
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 schedule就容易多了。

下面是一个我之前写得比较长,很容易出bug的版本,可以对比一下。

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        if len(words) == 0:
            return ''
        if len(words) == 1:
            return ''.join(set([c for c in words]))
        edges = {}
        voca = set()
        for i in xrange(len(words) - 1):
            for j in xrange(i + 1, len(words)):
                if len(words[i]) > len(words[j]) and words[i].startswith(words[j]):
                    return ''
                self.addEdge(words[i], words[j], edges, voca)
        
        visited = set()
        order = []
        for c in voca:
            # c = voca.pop()
            this_visit = set()
            noloop = self.dfs(c, edges, visited, this_visit, order)
            if not noloop:
                return ''
        return ''.join(order)
    
    def dfs(self, start, edges, visited, this_visited, order):
        if start in this_visited:
            return False

        if start in visited:
            return True

        visited.add(start)
        this_visited.add(start)

        if start not in edges:
            order.insert(0, start)
            this_visited.remove(start)
            return True

        for nxt in edges[start]:
            noloop = self.dfs(nxt, edges, visited, this_visited, order)
            if not noloop:
                return False
        order.insert(0, start)
        this_visited.remove(start)
        return True

    def addEdge(self, word1, word2, edges, voca):
        voca.update([c for c in word1])
        voca.update([c for c in word2])
        for i in xrange(min(len(word1), len(word2))):
            if word1[i] != word2[i]:
                if word1[i] in edges:
                    edges[word1[i]].add(word2[i])
                else:
                    edges[word1[i]] = set([word2[i]])
                break

怎样在macbook安装python 3.8.3 | how to install python 3.8.3 on macbook

python官方网站,下载macOS 64-bit installer

下载完成后双击.pkg文件安装既可

% python3
Python 3.8.3 (v3.8.3:6f8c8320e9, May 13 2020, 16:29:34)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>>

% which python3
/Library/Frameworks/Python.framework/Versions/3.8/bin/python3

我这原来的/usr/bin/python3 还是3.7

% /usr/bin/python3
Python 3.7.3 (default, Apr  7 2020, 14:06:47)
[Clang 11.0.3 (clang-1103.0.32.59)] on darwin
Type "help", "copyright", "credits" or "license" for more information.

怎样在pycharm里使用?

Setting里面(cmd + ,) search interpreter,选project interpreter

点击”+”
填入vevn里面的python3 path

添加成功后

怎样创建virtual environment?

python3 -m venv <path>

python 3.8.3有什么新特性?

新添了类型提示

算法练习 Leetcode 力扣 415. Add Strings 解法

add binary基本一样。

关键点:
从右边开始加
把长的input作为第一个,给最左边加0用来进位(如果需要的话),最后看要不要去掉
python里面要用ord,chr 来做char/ascii转换

python解法

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if num1 is None or len(num1) == 0:
            return num2
        if num2 is None or len(num2) == 0:
            return num1
        if len(num1) < len(num2):
            return self.addStrings(num2, num1)
        n1 = ['0'] + [c for c in num1]
        n2 = [c for c in num2]
        i = len(n1) - 1
        j = len(n2) - 1
        while i >= 0:
            if j >= 0:
                n1[i] = chr(ord(n1[i]) + ord(n2[j]) - ord('0'))
            if n1[i] > '9':
                n1[i] = chr(ord(n1[i]) - 10)
                n1[i - 1] = chr(ord(n1[i - 1]) + 1)
            i -= 1
            j -= 1
        ans = ''.join(n1)
        if ans[0] == '0':
            return ans[1:]
        return ans

算法练习 Leetcode 力扣 67. Add Binary 解法

add strings基本一样。

关键点:
从右边开始加
把长的input作为第一个,给最左边加0用来进位(如果需要的话),最后看要不要去掉
python里面要用ord,chr 来做char/ascii转换

python解法

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if a is None or len(a) == 0:
            return b
        if b is None or len(b) == 0:
            return a
        if len(a) < len(b):
            return self.addBinary(b, a)
        n1 = ['0'] + [c for c in a]
        n2 = [c for c in b]
        
        i = len(n1) - 1
        j = len(n2) - 1
        while i >= 0:
            if j >= 0:
                n1[i] = chr(ord(n1[i]) + ord(n2[j]) - ord('0'))
            if n1[i] > '1':
                n1[i] = chr(ord(n1[i]) - 2)
                n1[i - 1] = chr(ord(n1[i - 1]) + 1)
            i -= 1
            j -= 1
        ans = ''.join(n1)
        if ans[0] == '0':
            return ans[1:]
        return ans