285. Inorder Successor in BST
https://leetcode.com/problems/inorder-successor-in-bst/
https://www.lintcode.com/problem/448/
My Answer 1: Accepted (Runtime: 973 ms / Memory Usage: 5.99 MB) - 27.80 %
"""
Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Solution:
"""
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
"""
def inorderSuccessor(self, root, p):
def func(root, parent):
if root is None:
return
if root.val < p.val:
func(root.right, parent)
if root == p:
if root.right:
func(root.right, parent)
if root.val > p.val:
self.ans = root
func(root.left, root)
self.ans = None
func(root, root)
return self.ansif root.val < p.val:
=> 왼쪽은 볼 필요가 없으니까 root.right 보기
if root.val > p.val:
=> p 보다 큰 값은 successor 의 가능성이 있으니까 일단 ans update
root.left 를 보면서 더 작은 successor 가 있는지 확인
if root == p:
=> root.right 가 있으면 그 중에 제일 작은 값을 찾고
없으면 자동으로 지정된 ans 가 successor 가 됨
Solution 1: Accepted (Runtime: 963 ms / Memory Usage: 6.06 MB) - 31.40 %
class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
if root is None:
return
if root.val > p.val:
return self.inorderSuccessor(root.left, p) or root
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)더 간단한 루션이
이렇게도 되는구나..
287. Find the Duplicate Number
https://leetcode.com/problems/find-the-duplicate-number/
My Answer 1: Accepted (Runtime: 612 ms - 71.27% / Memory Usage: 35.9 MB - 7.12%)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
count = collections.Counter(nums)
for k, v in count.items():
if v > 1:
return k가장 먼저 든 생각은 역시 Counter 로 개수 세기
You must solve the problem without modifying the array nums and uses only constant extra space.
그게 뭔데..
그거 어떻게 하는건데..
Solution 1: Accepted (Runtime: 797 ms - 17.94% / Memory Usage: 28.1 MB - 51.11%)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
while nums[0] != nums[nums[0]]:
nums[nums[0]], nums[0] = nums[0], nums[nums[0]]
return nums[0]1 ~ n 의 범위라서 인덱스를 이용하면 된다고 한다
value 와 index 를 맞춰주다보면 중복이 적발됨
ex)
3, 3, 5, 4, 1, 3 => 3 & nums[3] = 4
4, 3, 5, 3, 1, 3
1, 3, 5, 3, 4, 3
3, 1, 5, 3, 4, 3
289. Game of Life
https://leetcode.com/problems/game-of-life/
My Answer 1: Accepted (Runtime: 28 ms - 91.16% / Memory Usage: 14.3 MB - 71.68%)
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def func(i, j):
count = 0
# 가로
if i-1 >= 0 and (board[i-1][j] == 1 or board[i-1][j] == 3):
count += 1
if i+1 < len(board) and (board[i+1][j] == 1 or board[i+1][j] == 3):
count += 1
# 세로
if j-1 >= 0 and (board[i][j-1] == 1 or board[i][j-1] == 3):
count += 1
if j+1 < len(board[0]) and (board[i][j+1] == 1 or board[i][j+1] == 3):
count += 1
# 대각선
if i-1 >= 0 and j-1 >= 0 and (board[i-1][j-1] == 1 or board[i-1][j-1] == 3):
count += 1
if i+1 < len(board) and j+1 < len(board[0]) and (board[i+1][j+1] == 1 or board[i+1][j+1] == 3):
count += 1
if i-1 >= 0 and j+1 < len(board[0]) and (board[i-1][j+1] == 1 or board[i-1][j+1] == 3):
count += 1
if i+1 < len(board) and j-1 >= 0 and (board[i+1][j-1] == 1 or board[i+1][j-1] == 3):
count += 1
if count == 3 and board[i][j] == 0:
board[i][j] = 2
if board[i][j] == 1:
if count > 3 or count < 2:
board[i][j] = 3
for i in range(len(board)):
for j in range(len(board[i])):
func(i, j)
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] == 2:
board[i][j] = 1
if board[i][j] == 3:
board[i][j] = 0주변의 1 의 개수를 모두 세서
board[i][j] 가 0 일 때,
주변의 1 이 3 개면 산다는 의미로 임시 값 2 로 바꿔줌
board[i][j] 가 1 일 때,
주변의 1 이 3 보다 크거나 2 보다 작으면 죽게된다는 의미로 임시 값 3 으로 바꿔줌
다시 보면서 2 는 1 로 살려주고 3 은 0 으로 죽여주면 된다..^^
그냥 이렇게 노가다할래요...
