[Mock] Amazon 3
4072 ワード
1176. Diet Plan Performance
A dieter consumes calories[i] calories on the i-th day.
Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):
Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.
My Answer 1: Time Limit Exceeded (26 / 27 test cases passed.)
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
points = 0
for i in range(len(calories)-k+1):
if sum(calories[i:i+k]) < lower:
points -= 1
if sum(calories[i:i+k]) > upper:
points += 1
return points
問題に沿ってやったけど...私もそう思います.time limit ~Solution 1: Accepted (Runtime: 180 ms - 100% / Memory Usage: 24.1 MB - 80.83%)
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
sum_t = sum(calories[:k])
j, ans = 0, 0
if sum_t < lower: ans = -1
if sum_t > upper: ans = 1
for i in range(k, len(calories)):
sum_t -= calories[j]
sum_t += calories[i]
j += 1
if sum_t < lower: ans -= 1
if sum_t > upper: ans += 1
return ans
k
長さの合計を保持最初の値を減算し、現在表示されている値を加算
前に解いたスライドウィンドウに似てるみたい~
572. Subtree of Another Tree
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
My Answer 1: Accepted (Runtime: 420 ms - 5.00% / Memory Usage: 14.7 MB - 95.88%)
# 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 isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
queue = [s]
subtree = s
# subtree 가 될만한 위치 찾기
while queue:
root = queue.pop(0)
if root:
queue.append(root.left)
queue.append(root.right)
if root.left and root.left.val == t.val:
subtree = root.left
if self.matchSubtree(subtree, t):
return True
if root.right and root.right.val == t.val:
subtree = root.right
if self.matchSubtree(subtree, t):
return True
if self.matchSubtree(subtree, t):
return True
return False
def matchSubtree(self, subtree, t):
# subtree 가 맞는지 확인
subq = [subtree]
tq = [t]
while subq:
subr = subq.pop(0)
tr = tq.pop(0)
if subr and tr:
if subr.val != tr.val:
return False
subq.append(subr.left)
subq.append(subr.right)
tq.append(tr.left)
tq.append(tr.right)
# 둘 중 하나라도 없으면 다른거니까 False
if subr and not tr or not subr and tr:
return False
return True
Reference
この問題について([Mock] Amazon 3), 我々は、より多くの情報をここで見つけました https://velog.io/@jsh5408/Mock-Amazon-3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol