邊聽館長罵人編寫code的直播(不過因為版權所以沒聲音XD)

1150. Check If a Number Is Majority Element in a Sorted Array (easy)
      https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/
      Submission：https://leetcode.com/submissions/detail/853637853/

Given an integer array nums sorted in non-decreasing order and an integer target, return true if target is a majority element, or false otherwise.
A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.
檢查target出現的次數是否大於nums.length/2

class Solution:
    #檢查target出現的次數是否大於nums.length/2
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        nL = len(nums)
        nC = Counter(nums)
        if nC[target] > nL/2:
            return 1
        return 0

1133. Largest Unique Number (easy)
      https://leetcode.com/problems/largest-unique-number/
      Submission：https://leetcode.com/submissions/detail/853637373/
      Given an integer array nums, return the largest integer that only occurs once. If no integer occurs once, return -1.
      回傳只出現一次的最大整數

class Solution:
    #回傳只出現一次的最大整數
    def largestUniqueNumber(self, nums: List[int]) -> int:
        C = Counter(nums)
        ans = -1
        for k,v in C.items():
            if v == 1:
                ans = max(k,ans)
        return ans

542. 01 Matrix (medium)
     https://leetcode.com/problems/01-matrix/
     Submission：https://leetcode.com/submissions/detail/853890283/
     Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
     The distance between two adjacent cells is 1.

這題我解比較久一點，首先出發點的不同，可以從1開始也可以從0開始，但一開始寫，兩種寫法都TLE。
後來是修改成裡面有step，邊走邊紀錄，解決了這個麻煩
一開始寫這兩種寫法都TLE

class Solution:
    #原矩陣裡面只會有0跟1
    #找出1離0的最近距離為多少
    #用矩陣輸出每個1與0的距離
    #阿幹，這題用dfs不好算
    
    #用1開始跑TLE
    #有沒有辦法在跑的時候就紀錄呢？因為從遠的1到近的1再到0，路徑會是一樣的
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        length,width = len(mat),len(mat[0])
        ansMatrix = [[0]*width for i in range(length)]
        movement = [(0,1),(1,0),(0,-1),(-1,0)]
        def bfs(x,y,matrix):
            queue = deque()
            queue.append((x,y,0))
            ans = float("inf")
            while queue:
                x,y,step = queue.popleft()
                for i in movement:
                    newX,newY = x+i[0],y+i[1]
                    if 0<=newX<length and 0<=newY<width and matrix[newX][newY] != -1:
                        if matrix[newX][newY] == 0:
                            ans = min(ans,step+1)
                            return ans
                        matrix[newX][newY] = -1
                        queue.append((newX,newY,step+1))
            
        for i in range(length):
            for j in range(width):
                if mat[i][j] == 1:
                    ansMatrix[i][j] = bfs(i,j,deepcopy(mat))#直接丟list進去會中坑
        return ansMatrix
    #TLE
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        length,width = len(mat),len(mat[0])
        ansMatrix = [[float("inf")]*width for i in range(length)]
        movement = [(0,1),(1,0),(0,-1),(-1,0)]
        def bfs(x,y,matrix):
            ansMatrix[x][y] = 0
            queue = deque()
            queue.append((x,y,0))
            ans = float("inf")
            flag = 0
            while queue:
                x,y,step = queue.popleft()
                for i in movement:
                    newX,newY = x+i[0],y+i[1]
                    if 0<=newX<length and 0<=newY<width and matrix[newX][newY] != -1:
                        # print(ansMatrix[newX][newY])
                        if matrix[newX][newY] == 0:
                            ansMatrix[newX][newY] = 0
                        else:
                            ansMatrix[newX][newY] = min(ansMatrix[newX][newY],step+1)
                        queue.append((newX,newY,step+1))
                        matrix[newX][newY] = -1
                                    
        for i in range(length):
            for j in range(width):
                if mat[i][j] == 0:
                    bfs(i,j,deepcopy(mat))#直接丟list進去會中坑
        return ansMatrix

#後來參考別人的把step加進去才成功
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        length,width=len(mat),len(mat[0])
        movement = [(1,0),(0,1),(-1,0),(0,-1)]
        ans=[[-1]*width for i in range(length)]
        queue=deque()
        for i in range(length):
            for j in range(width):
                if mat[i][j] == 0:
                    queue.append((i,j))#把所有的0都掉到queue
                    ans [i][j] = 0
        while(queue):
            x,y=queue.popleft()
            for i in movement:
                newX,newY = x+i[0],y+i[1]
                if 0 <= newX < length and 0 <= newY < width and ans[newX][newY] == -1:
                    queue.append((newX,newY))
                    ans[newX][newY] = ans[x][y] + 1 #bfs的下一步一定是上一步+1
        return ans

994. Rotting Oranges
     https://leetcode.com/problems/rotting-oranges/
     Submission：https://leetcode.com/submissions/detail/853622092/
     You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
我把想法寫在程式碼裡的，那也是我的思考流程

from collections import deque
class Solution:
    #m x n的矩陣
    #0 為空
    #1 為好橘子
    #2 為爛橘子
    #爛橘子就是喪屍，他會把四周新鮮的橘子變成爛橘子，找出最小的花費時間
    #爛橘子的數量沒有說，也就是說這會是一個坑點
    #要怎麼算步數也要注意，看來還是必須多塞一個值
    #只有有一個1在場上，就是-1
    def orangesRotting(self, grid: List[List[int]]) -> int:
        length = len(grid)
        width = len(grid[0])
        movement = [(0,1),(1,0),(0,-1),(-1,0)]
        def bfs(rotten):
            queue = deque(rotten)
            ans = 0
            while queue:
                x,y,step = queue.popleft()
                # print(ans)
                ans = max(ans,step)
                for i in movement:
                    newX,newY = x+i[0],y+i[1]
                    if 0<=newX<length and 0<=newY<width and grid[newX][newY] == 1:
                        grid[newX][newY] = 2
                        queue.append((newX,newY,step+1))
            return ans
        #第一步應該是要找出所有的爛橘子
        rotten = [(i,j,0) for i in range(length) for j in range(width) if grid[i][j] == 2]
        #每個爛橘子都會是起點，若直接把所有東西丟到queue裡呢？
        ans = bfs(rotten)
        for i in grid:
            if 1 in i:
                return -1
        return ans
    
    #其他人的寫法
    #概念上差不多，不過他高明的點是用set，直接把重複的去掉
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row, col = len(grid), len(grid[0])
        dirs = [(-1,0),(0,1),(1,0),(0,-1)]
        fresh_set=set()
        rotten = collections.deque()
        step = 0
        for x in range(row):
            for y in range(col):
                if grid[x][y]==1:
                    fresh_set.add((x,y))
                elif grid[x][y]==2:
                    rotten.append([x,y,step])
        while rotten:
            x,y,step = rotten.popleft()
            for dx, dy in dirs:
                if 0<=x+dx<row and 0<=y+dy<col and grid[x+dx][y+dy] == 1:
                    grid[x+dx][y+dy]=2
                    fresh_set.remove((x+dx,y+dy))
                    rotten.append([x+dx,y+dy,step+1])
        return step if not fresh_set else -1