23/04/07

carFleet.py

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    '''
    Leetcode 853. Car Fleet
    stack을 사용 p는 절편, (x, s*x)의 선분을 좌표평면에 그리고 절편 큰 순서로 add, 절편이 더 크면서 기울기가 작으면 target 전에 만나기 때문에 pop
    stack의 남은 길이는 아직 만나지 못한 차량의 개수
    '''
    pair = [[p, s] for p, s in zip(position, speed)]
    stack = []

    for p, s in sorted(pair)[::-1]: # 타겟과 가까운 것부터
        stack.append((target-p)/s) # 기울기
        if len(stack) >= 2 and stack[-1] <= stack[-2]:
            stack.pop()
    return len(stack) # 도착지에 도착할 차량 수

invertTree.py

'''
Leetcode 226. Invert Binary Tree
이진 트리 좌우 반전
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        temp = root.left
        root.left = root.right
        root.right = temp
        
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

largestRectangleArea.py

def largestRectangleArea(self, h: List[int]) -> int:
    '''
    Leetcode 84. Largest Rectangle in Histogram
    stack을 활용한 histogram 문제 높이가 오름차순일 때 push 내림차순일 때 pop
    '''
    N = len(h)
    stack = []
    m = []
    for i in range(N):
        # pop
        if stack and stack[-1][1] >= h[i]:
            j = i
            while stack and stack[-1][1] >= h[i]:
                index, height = stack.pop()
                m.append((i - index) * height)
                j = index
            stack.append((j, h[i]))
        # push
        else:
            stack.append((i, h[i]))
    # 남은 스택
    while stack:
        index, height = stack.pop()
        m.append((N - index) * height)

    return max(m)

maxDepth.py

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
def maxDepth(self, root: Optional[TreeNode]) -> int:
    '''
    Leetcode 104. Maximum Depth of Binary Tree
    dfs로 트리의 깊이 구하기
    '''
    if not root:
        return 0
    stack = [[root, 1]]
    res = 1
    while stack:
        node, depth = stack.pop()
        if node:
            res = max(res, depth)
            stack.append([node.left, depth+1])
            stack.append([node.right, depth+1])
    return res

numIslands.py

def numIslands(self, grid: List[List[str]]) -> int:
    '''
    Leetcode 200. Number of Islands
    graph문제
    '''
    rows, cols = len(grid), len(grid[0])
    visit = set()
    iSize = []
    iCnt = 0
    def bfs(r, c):
        s = 1
        q = [(r, c)]
        visit.add((r, c))
        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        while q:
            r1, c1 = q.pop(0)
            for x, y in direction:
                r2, c2 = r1 + x, c1 + y
                if r2 in range(rows) and c2 in range(cols) and grid[r2][c2] == '1' and (r2, c2) not in visit:
                    q.append((r2, c2))
                    visit.add((r2, c2))
                    s += 1
        iSize.append(s)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visit:
                bfs(r, c)
                iCnt += 1
    print(len(visit)) # 1 개수
    print(iSize) # 섬의 사이즈
    print(iCnt) # 섬 개수
    return iCnt
    
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]    

numIslands(grid)

orangesRotting.py

def orangesRotting(self, grid: List[List[int]]) -> int:
    '''
    Leetcode 994. Rotting Oranges
    
    '''
    ROWS, COLS = len(grid), len(grid[0])
    time, fresh = 0, 0
    q = []
    # 감염될 노드 개수 세줌 감염할 부모노드 큐에 넣어줌
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                fresh += 1
            if grid[r][c] == 2:
                q.append([r, c])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]    

    # 감염시킬 노드 있는 동안 루프 돌기
    while q and fresh > 0:

        # 큐 길이만큼 pop
        l = len(q)
        for i in range(l):
            r1, c1 = q.pop(0)
            # bfs로 push
            for x, y in directions:
                r2, c2 = r1 + x, c1 + y
                if r2 in range(ROWS) and c2 in range(COLS) and grid[r2][c2] == 1:
                    grid[r2][c2] = 2
                    q.append([r2, c2])
                    fresh -= 1
        time += 1

    return time if fresh == 0 else -1
    
print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]])

pacificAtlantic.py

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    '''
    Leetcode 417. Pacific Atlantic Water Flow
    r = 0, rows -1, c = 0, cols - 1 의 각 동서남북 끝부분에서 깊이우선탐색으로 끝부분의 바다와 이어지는 지 여부를 visit에 각각 저장하고 둘 다 해당하면 결과값에 추가
    '''
    ROWS, COLS = len(heights), len(heights[0])
    pac, atl = set(), set() # 태평양, 대서양
    # dfs
    def dfs(r, c, visit, prevHeight):
        if r not in range(ROWS) or c not in range(COLS) or (r, c) in visit or heights[r][c] < prevHeight:
            return
        visit.add((r, c))
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for x, y in directions:
            dfs(r + x, c + y, visit, heights[r][c])
    # 동서남북에서 시작해서 깊이 우선탐색으로 pac, atl 방문 노드 저장      
    for c in range(COLS):
        dfs(0, c, pac, heights[0][c])
        dfs(ROWS - 1, c, atl, heights[ROWS-1][c])

    for r in range(ROWS):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, COLS - 1, atl, heights[r][COLS-1])

    res = []
    for r in range(ROWS):
        for c in range(COLS):
            if (r, c) in pac and (r, c) in atl:
                res.append([r, c])
    return res

solve.py

def solve(self, board: List[List[str]]) -> None:
    '''
    Leetcode 130. Surrounded Regions
    T: 캡쳐할 수 없는 섬
    바깥 동서남북 테두리를 먼저 탐색하고 O를 발견하면 이어지는 섬을 탐색해서 T로 변환
    T를 제외한 O를 X로 변환하고 다시 T를 O로 변환
    '''
    ROWS, COLS = len(board), len(board[0])

    def capture(r, c):
        if r not in range(ROWS) or c not in range(COLS) or board[r][c] != "O":
            return
        board[r][c] = "T"
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for x, y in directions:
            capture(r+x, c+y)

    # O -> T
    for r in range(ROWS):
        for c in range(COLS):
            if (r in [0, ROWS-1] or c in [0, COLS-1]) and board[r][c] == "O":
                capture(r, c)
    # O -> X
    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] == "O":
                board[r][c] = "X"
    # T -> O
    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] == "T":
                board[r][c] = "O"
    print(board)

twoSum.py

def twoSum(self, nums: List[int], target: int) -> List[int]:
    '''
    Leetcode 1. Two Sum
    루프문을 돌면서 값을 저장, 이전에 저장한 값 중 지금 값과 차이 값이 있으면 반환
    '''
    prevMap = {}

    for i, n in enumerate(nums):
        diff = target - n
        if diff in prevMap:
            return [prevMap[diff], i]
        prevMap[n] = i
    return