Scribbling

가장 먼저 떠오르는 방법은 완전 탐색 --> Time Limit Exceeded class Solution: def minPathSum(self, grid: List[List[int]]) -> int: n, m = len(grid), len(grid[0]) dp = [[int(1e9)] * m for _ in range(n)] self.explorer(dp, grid, 0, 0, 0) return dp[n-1][m-1] def explorer(self, dp, grid, i, j, nowSum): nowSum += grid[i][j] if i == len(grid) - 1 and j == len(grid[0]) - 1: dp[i][j] = min(dp[i][j], nowSum) return if nowS..

class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: n, m = len(obstacleGrid[0]), len(obstacleGrid) board = [[0] * n for _ in range(m)] board[0][0] = 1 obstacles = [] for i in range(m): for j in range(n): if obstacleGrid[i][j] == 1: board[i][j] = 0 obstacles.append((i, j)) for j in range(1, n): if (0, j) in obstacles: continue board[0][j] = board[0][j-1] for ..

한국 고등학교 수학 공부했으면 다 푸는 문제 class Solution: def uniquePaths(self, m: int, n: int) -> int: board = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): board[i][j] = board[i-1][j] + board[i][j-1] return board[m-1][n-1]

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head: return count, cur, prv = 0, head, None while cur != None: prv = cur count += 1 cur = cur.next tail = prv k %= count if k == 0: return head cur = head for i in ..

class Solution: def getPermutation(self, n: int, k: int) -> str: def factorial(n): if n == 1: return 1 return n * factorial(n-1) nums = [str(i) for i in range(1, n+1)] if k == 1: return ''.join(nums) k -= 1 ret = '' while k > 0: x = factorial(n-1) if k >= x: quotient = k // x k -= quotient * x ret += nums.pop(quotient) else: ret += nums.pop(0) n -= 1 ret += ''.join(nums) return ret

class Solution: def generateMatrix(self, n: int) -> List[List[int]]: ret = [[0] * n for _ in range(n)] num = 1 count = 0 y, x = count, count while y < n: y, x = count, count i, j = y, x for j in range(x, n): ret[i][j] = num num += 1 for i in range(y+1, n): ret[i][j] = num num += 1 for j in range(n-2, x-1, -1): ret[i][j] = num num += 1 for i in range(n-2, y, -1): ret[i][j] = num num += 1 count +=..

class Solution: def maxSubArray(self, nums: List[int]) -> int: ret = -int(1e9) now = 0 for num in nums: now += num ret = max(ret, now) if now

class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: ret = [] i = 0 for i, interval in enumerate(intervals): if interval[0] = newInterval[0]: ret[-1][1] = max(ret[-1][1], newInterval[1]) else: ret.append(newInterval) for j in range(i, len(intervals)): interval = intervals[j] if ret and ret[-1][1] >= interval[0]: ret[-1][1] = max(ret[-1][1], int..

Sorting ahead is the key here. class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: (x[0], x[1])) ret = [] for interval in intervals: if ret and ret[-1][0]

Recursion solution: class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: self.ret = [] self.helper(matrix, 0, 0, len(matrix), len(matrix[0])) return self.ret def helper(self, matrix, y, x, m, n): if m > 0: for i in range(n): self.ret.append(matrix[y][x]) x += 1 x -= 1 m -= 1 if n > 0 : for i in range(m): y += 1 self.ret.append(matrix[y][x]) n -= 1 if m > 0: for i in range..