IT_World

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) dx = [0, 1] dy = [1, 0] flag = [[False] * n for _ in range(m)] q = [] heapq.heappush(q, (grid[0][0], 0, 0)) flag[0][0] = True while True: cost, x, y = heapq.heappop(q) if x == m-1 and y == n-1: return cost for i in range(2): nx = x + dx[i] ny = y + dy[i] if nx >= m or ny >= n or flag[nx][ny]: conti..

Solution 1 :최단거리 경우의수 class Solution: def uniquePaths(self, m: int, n: int) -> int: paths = [[0]*m for _ in range(n)] paths[0][0] = 1 for i in range(n): for j in range(m): if i==0 and j ==0 : continue paths[i][j] += paths[i-1][j] if i>0 else 0 paths[i][j] += paths[i][j-1] if j>0 else 0 return paths[i][j] Solution 2: 순열을 이용한 방법 같은 것 p개 q개 r개 있는 n개의 것을 순서를 생각하며 나열하는 경우의 수는 n! /(p! * q! * n!) (이렇게는..

def inorderTraversal(self, root: TreeNode) -> List[int]: stack = [root] res = [] while stack: node = stack.pop() if node: stack.append(node.right) stack.append(node) stack.append(node.left) else: if stack: node = stack.pop() res.append(node.val)

class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: dta = ListNode(0) dta.next = head dataset = set() while head and head.next: dataset.add(head.val) while head.next and head.next.val in dataset : head.next = head.next.next head = head.next return dta.next

class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ del nums1[m:] nums1 += nums2[0:n] nums1.sort()

class Solution: def climbStairs(self, n: int) -> int: if n < 3: return n else : return self.climbStairs(n-1) + self._climbStairs(n-2) def _climStairs(self, n: int): if n not in self.cache.keys() : self.cache[n] = self.climbStairs(n) return self.cache[n]

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: result = [] def dfs(cansum,index,path): if cansum < 0 : return if cansum == 0 : result.append(path) return for i in range(index,len(candidates)): dfs(cansum - candidates[i],i, path + [candidates[i]]) dfs(target, 0, []) return result

class Solution: def combine(self, n: int, k: int) -> List[List[int]]: rnglst = list(range(1,n+1)) cmblst = list(combinations(rnglst, k)) return cmblst