博客

# 281
class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.v1 = v1
        self.v2 = v2
        self.length1 = len(v1)
        self.length2 = len(v2)
        self.index1 = 0
        self.index2 = 0
        self.row_pointer = 1

    def move_row_pointer(self):
        """move pointer to right row"""
        if self.row_pointer == 1:
            if self.index1 > self.length1 - 1:
                self.row_pointer = 2
        else:
            if self.index2 > self.length2 - 1:
                self.row_pointer = 1

    def next(self) -> int:
        self.move_row_pointer()
        if self.row_pointer == 1:
            ans = self.v1[self.index1]
            self.index1 += 1
            self.row_pointer = 2
        else:
            ans = self.v2[self.index2]
            self.index2 += 1
            self.row_pointer = 1
        return ans

    def hasNext(self) -> bool:
        return self.index1 <= self.length1 - 1 or self.index2 <= self.length2 - 1

# 282
class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        res = []
        def helper(index, preOutStr, preSum, preValue):
            if index == len(num):
                if preSum == target:
                    res.append(preOutStr)
                return
            if max(1, abs(preValue)) * (int(num[index:])) < abs(target - preSum):
                return
            for i in range(index, index + 1 if num[index] == '0' else len(num)):
                cur = num[index:i + 1]
                curValue = int(cur)
                if not preOutStr:
                    helper(i + 1, cur, curValue, curValue)
                else:
                    helper(i + 1, preOutStr + '+' + cur, preSum + curValue, curValue)
                    helper(i + 1, preOutStr + '-' + cur, preSum - curValue, -curValue)
                    helper(i + 1, preOutStr + '*' + cur, preSum - preValue + curValue * preValue, curValue * preValue)
        helper(0, '', 0, 0)
        return res

# 283
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tmp = 0 
        for i in nums:
            if i != 0:
                nums[tmp] = i
                tmp += 1
        while tmp < len(nums):
            nums[tmp] = 0
            tmp += 1

# 286
class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if not rooms or not rooms[0]:
            return rooms
        m , n = len(rooms) , len(rooms[0])
        INF = 2147483647
        res = []
        d0 = [1 , -1 , 0 , 0]
        d1 = [0 , 0 , -1 , 1]
        def dfs(res):
            while res:
                x0 , y0 = res.pop(0)
                for i in range(4):
                    x = x0 + d0[i]
                    y = y0 + d1[i]
                    if 0 <= x < m and 0 <= y < n and rooms[x][y] == INF:
                        rooms[x][y] = rooms[x0][y0] + 1
                        res.append([x , y])
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    res.append([i , j])
        dfs(res)

# 287
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        tmp = Counter(nums)
        for idx , res in tmp.items():
            if res >= 2:
                return idx

# 289
class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]
        rows = len(board)
        cols = len(board[0])
        copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]
        for row in range(rows):
            for col in range(cols):
                live_neighbors = 0
                for neighbor in neighbors:

                    r = (row + neighbor[0])
                    c = (col + neighbor[1])
                    if 0 <= r < rows and 0 <= c < cols and copy_board[r][c] == 1:
                        live_neighbors += 1     
                if live_neighbors < 2 or live_neighbors > 3:
                    board[row][col] = 0

                if live_neighbors == 3:
                    board[row][col] = 1

# 290
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        word = s.split()
        if len(pattern) != len(word):
            return False
        dict1 = dict()
        dict2 = dict()
        for i in range(len(pattern)):
            if (pattern[i] in dict1 and dict1[pattern[i]] != word[i]) or (word[i] in dict2 and dict2[word[i]] != pattern[i]):
                return False
            dict1[pattern[i]] = word[i]
            dict2[word[i]] = pattern[i]

        return True