88. Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/
My Answer 1: Accepted (Runtime: 40 ms - 40.38% / Memory Usage: 14.2 MB - 86.19%)
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.
"""
nums1 += nums2
nums1.sort()
while n:
nums1.remove(0)
n -= 1둘이 합해서 sort 후 n 만큼의 0 없애주기
양심 없이 풀었읍니다..^^
Solution 1: Accepted (Runtime: 36 ms - 72.41% / Memory Usage: 14.4 MB - 32.23%)
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.
"""
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]큰 값부터 역순으로 비교해서 nums1 의 맨 뒷자리부터 채워주기
nums1 과 nums2 중에 큰 값이 뒷자리를 차지하게 됨
nums2 가 남으면 nums1 앞쪽에 그대로 copy
94. Binary Tree Inorder Traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/
My Answer 1: Accepted (Runtime: 28 ms - 84.39% / Memory Usage: 14.3 MB - 46.97%)
# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
def func(root):
if root is None:
return
func(root.left)
ans.append(root.val)
func(root.right)
ans = []
func(root)
return ans왼 - 루트 - 오 순으로 보는 inorder 재귀 쓰기
My Answer 2: Accepted (Runtime: 28 ms - 84.39% / Memory Usage: 14.2 MB - 76.10%)
from collections import deque
# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
queue = deque([root])
while queue:
r = queue.popleft()
if r:
if r.right and r.right not in queue:
queue.appendleft(r.right)
if r.left:
tmp = r.left
r.left = None
queue.appendleft(r)
queue.appendleft(tmp)
else:
ans.append(r.val)
return ansFollow up: Recursive solution is trivial, could you do it iteratively?
을 보고... 반복문으로도 풀어봄
appendleft 하려고 deque 사용
right 부터 담아주기
left 가 있으면 지금 root 값은 left 다음으로 ans 에 들어가야하니까
다시 보자는 의미로 left 를 자른 root 만 담아주기
최종적으로 left 는 젤 왼쪽에 append 돼서 left 를 최우선으로 보게 됨
left 가 없을 때만 ans 에 root.val 넣어주기
Solution 1: Accepted (Runtime: 32 ms - 61.17% / Memory Usage: 14.3 MB - 46.97%)
# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right더 깔끔한 루션이
stack 이 빌 때까지 계속 반복문 돌리고 (while True:)
가장 깊숙한 left 까지 이동하면서 stack 에 root 들 넣어줌
그 담부턴 pop 해가면서 value 값 res 에 넣고 right 확인
36. Valid Sudoku
https://leetcode.com/problems/valid-sudoku/
My Answer 1: Accepted (Runtime: 96 ms - 74.11% / Memory Usage: 14.2 MB - 70.70%)
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# width
for i in range(9):
cnt = collections.Counter(board[i])
cnt.pop(".")
for v in cnt.values():
if v > 1:
return False
# height
for i in range(9):
tmp = ""
for j in range(9):
tmp += board[j][i]
cnt = collections.Counter(tmp)
cnt.pop(".")
for v in cnt.values():
if v > 1:
return False
# box
for i in range(0, 9, 3):
for j in range(0, 9, 3):
tmp = board[i][j:j+3] + board[i+1][j:j+3] + board[i+2][j:j+3]
cnt = collections.Counter(tmp)
cnt.pop(".")
for v in cnt.values():
if v > 1:
return False
return True9*9 면 작은 숫자인 편이라 생각해서.. 걍 세가지 구역별로 Counter 써서 확인해줌
가로, 세로, 3*3 박스 순으로 숫자의 개수 확인해서 return False
다 통과하면 return True
Solution 1: Accepted (Runtime: 92 ms - 88.94% / Memory Usage: 14.3 MB - 43.44%)
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
N = 9
# Use hash set to record the status
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
boxes = [set() for _ in range(N)]
for r in range(N):
for c in range(N):
val = board[r][c]
# Check if the position is filled with number
if val == ".":
continue
# Check the row
if val in rows[r]:
return False
rows[r].add(val)
# Check the column
if val in cols[c]:
return False
cols[c].add(val)
# Check the box
idx = (r // 3) * 3 + c // 3
if val in boxes[idx]:
return False
boxes[idx].add(val)
return True가로, 세로, 박스의 set 를 만들어서
board 값이 숫자일 때만 각각의 set 에 add
가로, 세로에 이미 존재하면 return False
박스는 (r // 3) * 3 + c // 3 로 인덱스 계산해서
지금 숫자가 속하는 박스에 이미 존재하는지 확인
38. Count and Say
https://leetcode.com/problems/count-and-say/
My Answer 1: Accepted (Runtime: 40 ms - 88.79% / Memory Usage: 14.5 MB - 24.13%)
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
s = self.countAndSay(n-1)
ans = ""
prev = s[0]
cnt = 1
for i in range(1, len(s)):
if prev != s[i]:
ans += str(cnt) + prev
cnt = 1
prev = s[i]
else:
cnt += 1
ans += str(cnt) + prev
return ans주어진 countAndSay 를 재귀 함수로 사용
base) n 이 1 이면 return "1"
나머지는 countAndSay(n-1) 돌려서 이전 숫자의 string 을 받아옴
prev 값과 달라지면 say 하기
say 한 값은 ans 에 저장해서 return
