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)
第四题题目都不看 直接放囉
吃完早餐了 爽爽爽