LeetCode Weekly Contest 427

[DJYOMIYAHINA (通通打死)]

1. 直接硬幹 python的%很好用 直接用 小孩都愛用

def constructTransformedArray(self, nums: List[int]) -> List[int]:
    n = len(nums)
    results = [0 for _ in range(n)]
    for i in range(n):
        new_idx = (i+nums[i])%n
        results[i] = nums[new_idx]
    return results


2. 也是硬幹 只有十點還可以 寫起來很麻煩==

def maxRectangleArea(self, points: List[List[int]]) -> int:
    mp_x = defaultdict(list)
    mp_y = defaultdict(list)
    pt_set = set()

    for pt in points:
        mp_x[pt[0]].append(pt[1])
        mp_y[pt[1]].append(pt[0])
        pt_set.add((pt[0],pt[1]))

    ans = -1
    for pt in points:
        lt_x, lt_y = pt[0], pt[1]
        for rt_x in mp_y[lt_y]:
            for lb_y in mp_x[lt_x]:
                if rt_x>lt_x and lb_y<lt_y and (rt_x,lb_y) in pt_set:
                    # could be a rectangle
                    check = True
                    for pt in points:
                        check_x, check_y = pt[0], pt[1]
                        if lt_x<check_x<rt_x and (check_y==lt_y or
check_y==lb_y):
                            check=False # on edge
                            break
                        if lb_y<check_y<lt_y and (check_x==lt_x or
check_x==rt_x):
                            check=False # on edge
                            break
                        if lb_y<check_y<lt_y and lt_x<check_x<rt_x:
                            check=False # inside
                            break
                    if check is True:
                        ans = max(ans, (rt_x-lt_x)*(lt_y-lb_y))
    return ans


3. prefix sum + dp
想了好久 被我擠出來了
還以為要掛在這了

def maxSubarraySum(self, nums: List[int], k: int) -> int:
    n = len(nums)
    dp = [-10**20 for _ in range(n)]
    prefix = [0 for _ in range(n)]

    # build prefix-sum arr
    cur_sum = 0
    for i,num in enumerate(nums):
        cur_sum += num
        prefix[i] = cur_sum
    prefix.append(0) # prefix[-1]=0

    # dp
    for i in range(k-1,n):
        if (i-k)>=0:
            dp[i] = max(dp[i-k], 0)+(prefix[i]-prefix[i-k])
        else:
            dp[i] = prefix[i]-prefix[i-k]
    return max(dp)

第四題題目都不看 直接放囉
吃完早餐了 爽爽爽

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733629554.A.9B3.html
※ 編輯: DJYOMIYAHINA (125.228.146.144 臺灣), 12/08/2024 11:46:11
推 sustainer123: 大師
→ Furina: 大師