Scribbling

class Solution: def canJump(self, nums): destination = len(nums) - 1 for i in range(len(nums)-2, -1, -1): if i + nums[i] >= destination: destination = i return destination == 0

class Solution: def totalNQueens(self, n: int) -> int: self.ret = 0 self.solver(n, [], [], []) return self.ret def solver(self, n, queens, sumyx, subyx): if len(queens) == n: self.ret += 1 return for i in range(n): y, x = len(queens), i if (i not in queens) and ((y+x) not in sumyx) and ((y-x) not in subyx): self.solver(n, queens+[i], sumyx+[(y+x)], subyx+[(y-x)])

오늘도 무지성 스텍 쌓아버린 나의 코드 from copy import deepcopy class Solution: def solveNQueens(self, n: int) -> List[List[str]]: ret = [] board = [['.'] * n for _ in range(n)] self.solver(n, board, 0, ret) return ret def solver(self, n, board, num_Q, ret): if num_Q == n: ret_board = [] for i in range(n): temp = list(board[i]) for j in range(len(temp)): if temp[j] != 'Q': temp[j] = '.' ret_board.append(''.join..

여러 경우의 수를 다 고려해봐야 한다. 어려운 문제이긴하나, dp를 써야한다는 점과 dp table의 크기를 정하는 것이 핵심. 여기서 matched[i][j]: p[i-1]까지의 패턴 문자열이 s[j-1] 문자열을 cover함을 의미. class Solution(object): def isMatch(self, s, p): matched = [[False] * (len(s)+1) for _ in range(len(p)+1)] matched[0][0] = True for i in range(2, len(p)+1): if p[i-1] == '*': matched[i][0] = matched[i-2][0] for i in range(1, len(p)+1): for j in range(1, len(s)+1): ..

class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == '0' or num2 == '0': return '0' ret = [0] * (len(num1) + len(num2)) for i in range(len(num1)-1, -1, -1): carry = 0 for j in range(len(num2)-1, -1, -1): temp = ret[i+j+1] + int(num1[i]) * int(num2[j]) + carry carry = temp // 10 ret[i+j+1] = temp % 10 ret[i] = carry ret = ''.join(map(str, ret)) return ret.lstrip('0')

욕심쟁이는 풀 수 있는 문제 class Solution: def jump(self, nums: List[int]) -> int: if len(nums) == 1: return 0 now, jump = 0, 0 while True: if now + nums[now] >= len(nums) - 1: return jump + 1 val, next_idx = -1, -1 for i in range(now+1, min(now+nums[now]+1, len(nums))): if i + nums[i] > val: val = i + nums[i] next_idx = i now = next_idx jump += 1

class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == '0' or num2 == '0': return '0' ret = [0] * (len(num1) + len(num2)) for i in range(len(num1)-1, -1, -1): carry = 0 for j in range(len(num2)-1, -1, -1): temp = ret[i+j+1] + int(num1[i]) * int(num2[j]) + carry carry = temp // 10 ret[i+j+1] = temp % 10 ret[i] = carry ret = ''.join(map(str, ret)) return ret.lstrip('0')

The key observations to solve this problems: - right >= left + 2, to contain water - if we have a max height either at left or right position, then we can calculate water in the opposite position. class Solution: def trap(self, height: List[int]) -> int: ret = 0 l, r = 0, len(height) - 1 leftmax, rightmax = height[l], height[r] while r - l >= 2: curmax = max(leftmax, rightmax) if curmax == right..

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: return self.binary_search(nums, 0, len(nums)-1, target) def binary_search(self, nums, left, right, target): if left > right: return [-1, -1] mid = (left + right) // 2 mid_val = nums[mid] if mid_val > target: return self.binary_search(nums, left, mid-1, target) elif mid_val < target: return self.binary_search(nums, ..

class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left = nums[left]: if nums[left]