TagWideFirst

# 994. Rotting Oranges
# In a given grid, each cell can have one of three values:

# 0 --- empty cell;
# 1 --- fresh orange;
# 2 --- rotten orange.
# Every minute, adjacent fresh to rotten
# minimum minutes till no fresh orange.

class Solution:
    def orangesRotting(self, G: List[List[int]]) -> int:
        M, N, S, E, c = len(G), len(G[0]), [], sum(G,[]).count(1), 0
        R = [(i,j) for i,j in itertools.product(range(M),range(N)) if G[i][j] == 2]
        # product(list1, list2) 依次取出list1中的每1个元素，与list2中的每1个元素，组成元组， 
        # 然后，将所有的元组组成一个列表，
        while E != 0:
            for [i,j] in R:
                for a,b in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                    if 0 <= a < M and 0 <= b < N and G[a][b] == 1: 
                        G[a][b], E, _ = 2, E - 1, S.append([a,b])
            if len(S) == 0: return -1
            R, S, c = S, [], c + 1
        return c

# 127. Word Ladder
# Only one letter can be changed at a time.
# beginWord and endWord; dictionary's word list
# length of shortest transformation begin to end;

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        wordList = set(wordList) #字典
        queue = collections.deque([[beginWord, 1]]) #
        # collections.deque
        while queue:
            word, length = queue.popleft() # 
            if word == endWord:
                return length
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in wordList:
                        wordList.remove(next_word)
                        queue.append([next_word, length + 1])
        return 0

# collections 是 python 内建的一个集合模块，里面封装了许多集合类；
# 其中队列相关的集合只有一个：deque；
# deque 是双边队列（double-ended queue），具有队列和栈的性质；
# 在 list 的基础上增加了移动、旋转和增删等；
    
# d = collections.deque([])
# d.append('a') # 在最右边添加一个元素，此时 d=deque('a')
# d.appendleft('b') # 在最左边添加一个元素，此时 d=deque(['b', 'a'])
# d.extend(['c','d']) # 在最右边添加所有元素，此时 d=deque(['b', 'a', 'c', 'd'])
# d.extendleft(['e','f']) # 在最左边添加所有元素，此时 d=deque(['f', 'e', 'b', 'a', 'c', 'd'])
# d.pop() # 将最右边的元素取出，返回 'd'，此时 d=deque(['f', 'e', 'b', 'a', 'c'])
# d.popleft() # 将最左边的元素取出，返回 'f'，此时 d=deque(['e', 'b', 'a', 'c'])
# d.rotate(-2) # 向左旋转两个位置（正数则向右旋转），此时 d=deque(['a', 'c', 'e', 'b'])
# d.count('a') # 队列中'a'的个数，返回 1
# d.remove('c') # 从队列中将'c'删除，此时 d=deque(['a', 'e', 'b'])
# d.reverse() # 将队列倒序，此时 d=deque(['b', 'e', 'a'])