1351. Count Negative Numbers in a Sorted Matrix
Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.
My Answer 1: Accepted (Runtime: 124 ms - 39.49% / Memory Usage: 15.2 MB - 45.52%)
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
ans = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] < 0:
ans += 1
return ans문제 고대로 음수 찾아서 ans + 1
1382. Balance a Binary Search Tree
Given a binary search tree, return a balanced binary search tree with the same node values.
A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.
If there is more than one answer, return any of them.
My Answer 1: Wrong Answer (4 / 16 test cases passed.)
# 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 balanceBST(self, root: TreeNode) -> TreeNode:
def func(root):
if root is None:
return 0
a = func(root.left)
b = func(root.right)
return a + b + 1
root2 = root
l = func(root.left)
r = func(root.right)
while abs(l-r) > 1:
if l < r:
R = root.right
root2 = root.right
tmp = root
tmp.right = None
while R.left:
R = R.left
R.left = tmp
root = root2
else:
R = root.left
root2 = root.left
tmp = root
tmp.left = None
while R.right:
R = R.right
R.right = tmp
root = root2
l = func(root.left)
r = func(root.right)
return root처음엔 루트마다 left, right 의 depth 를 계산
abs(left 깊이 - right 깊이) 가 1 이하가 될 때까지
left 가 더 깊으면 root 를 left.right 중에 젤 오른쪽 값에 붙이고
right 가 더 깊으면 root 를 right.left 중에 젤 왼쪽 값에 붙이는 방식으로 함
근데 depth 를 계산한게 아니라 개수를 계산한거라.. 망함
그래서 depth 로 하자니 그건 또 복잡해져서 포기
My Answer 2: Wrong Answer (6 / 16 test cases passed.)
# 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 balanceBST(self, root: TreeNode) -> TreeNode:
def func(root):
if root is None:
return 0
self.nums.append(root.val)
func(root.left)
func(root.right)
self.nums = []
func(root)
self.nums.sort()
def func2(root, val):
if root is None:
root = TreeNode(val)
else:
if val <= root.val:
root.left = func2(root.left, val)
else:
root.right = func2(root.right, val)
return root
self.ans = TreeNode(self.nums[len(self.nums)//2-1])
left = self.nums[:len(self.nums)//2-1]
right = self.nums[len(self.nums)//2:]
i = len(left)//2
while len(left):
func2(self.ans, left[i])
left = left[:len(left)//2] + left[len(left)//2+1:]
i = len(left)//2
i = len(right)//2
while len(right):
func2(self.ans, right[i])
right = right[:len(right)//2] + right[len(right)//2+1:]
i = len(right)//2
return self.ans이건 정말 무식하게 푼 건데..
트리의 모든 값들을 self.nums 에 저장하고 정렬한 다음
계속 중간값을 루트로 잡아서 Binary Tree 를 직접 만들어주기
left, right 나눠서 했지만 그냥 붙여서 해도 됐을라나
근데 다 통과 안된다는 점..^^
Solution 1: Accepted (Runtime: 364 ms - 42.81% / Memory Usage: 21.3 MB - 6.46%)
# 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 balanceBST(self, root: TreeNode) -> TreeNode:
v = []
def dfs(node):
if node:
dfs(node.left)
v.append(node.val)
dfs(node.right)
dfs(root)
def bst(v):
if not v:
return None
mid = len(v) // 2
root = TreeNode(v[mid])
root.left = bst(v[:mid])
root.right = bst(v[mid + 1:])
return root
return bst(v)dfs 로 모든 값들을 v 에 넣기 => inorder 라 정렬된 상태로 저장됨
bst 로 중간값 잡아서 Tree 생성
방식은 같은데 이렇게 풀었어야 하는구나~
냅다 외우기~~
1478. Allocate Mailboxes
Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.
Return the minimum total distance between each house and its nearest mailbox.
The answer is guaranteed to fit in a 32-bit signed integer.
My Idea
시간이 없어서 문제만 훑어봤지만..
house 끼리의 거리 조합들을 전부 구해서
거리 간격이 최솟값인 경우에 mailbox 놓기를 하면...
어케 되지 않을까 싶은데 구현은 못할듯..
Solution 1: Accepted (Runtime: 540 ms - 55.37% / Memory Usage: 16.4 MB - 48.59%)
class Solution:
def minDistance(self, houses: List[int], k: int) -> int:
n = len(houses)
houses = sorted(houses)
costs = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
median = houses[(i + j) // 2]
for t in range(i, j + 1):
costs[i][j] += abs(median - houses[t])
@lru_cache(None)
def dp(k, i):
if k == 0 and i == n: return 0
if k == 0 or i == n: return math.inf
ans = math.inf
for j in range(i, n):
cost = costs[i][j] # Try to put a mailbox among house[i:j]
ans = min(ans, cost + dp(k - 1, j + 1))
return ans
return dp(k, 0)DP 이용
우선 houses 를 정렬해주고
houses 의 중앙값 을 이용해서 어케 하는거 같은데...
3 중 for 문이를 돌고 나면 costs 에 houses[i] 부터 ~ 누적 거리값이 저장됨
그 다음부터는 모르겠읍니다...^^
0개의 댓글
