[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]):
  • If T < lower, they performed poorly on their diet and lose 1 point;
  • If T > upper, they performed well on their diet and gain 1 point;
  • Otherwise, they performed normally and there is no change in points.
    Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.
  • Note that the total points can be negative.

    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