LeetCode Weekly Contest 153

DP盛宴

(第二题真煞笔)

1184. Distance Between Bus Stops

min(sum(s, d), total_sum - sum(s, d))

1
2
3
4
5
6
7
class Solution:
def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
s = min(start, destination)
d = max(start, destination)
a = sum(distance[s:d])
t = sum(distance)
return min(a, t-a)

1185. Day of the Week

Zeller’s congruence

1
2
3
4
5
6
7
class Solution:
def dayOfTheWeek(self, d: int, m: int, y: int) -> str:
if m==1 or m==2:
m += 12
y -= 1
w = (d+2*m+3*(m+1)//5+y+y//4-y//100+y//400+1) % 7
return ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"][w]

1186. Maximum Subarray Sum with One Deletion

题意:要求在可以删除一个元素的情况下,求最大区间和

思路:最大区间和使用dp维护,另外使用一个dp来维护删除一个元素的情况下的最大区间和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maximumSum(self, arr: List[int]) -> int:
INF = 10**9+1000
dp1 = [-INF] * len(arr)
dp2 = [-INF] * len(arr)
ans = arr[0]
csum = 0
for i, a in enumerate(arr):
dp1[i] = a;
if i:
dp1[i] = max(a, dp1[i-1] + a); # same as max-sub-seq
dp2[i] = max(dp1[i-1], dp2[i-1] + a);
ans = max(ans, dp1[i])
ans = max(ans, dp2[i])
return ans

详解:

dp1和普通的求最大区间和的方法相同,dp1[i]维护的是以位置i结尾的最大连续区间和。

dp2则维护删除了一个元素的以位置i结尾的最大连续区间和,转移规则如下:

  1. 如果删除i号元素,则之前i-1是没有删除元素情况下的以位置i-1结尾的最大连续区间和,即dp1[i-1]
  2. 如果没删除i号元素,则之前i-1是删除了一个元素情况下的以位置i-1结尾的最大连续区间和,由于没有删除,需要加上这个元素,即dp2[i-1]+arr[i]
  3. 求1. 2.的最大值即为dp2[i]

所以dp2[i] = max(dp1[i-1], dp2[i-1] + arr[i]);

转移过程中维护ans即为答案

1187. Make Array Strictly Increasing

题意:一次操作可以将arr1中的某个元素用arr2的元素替代(次数不限),问最少需要几次操作才能保证arr1严格递增。

思路:针对每个位置通过dp维护当前元素为k时所需要的操作次数v,交替更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
dp = {-1:0}
arr2.sort()
for a in arr1:
n_dp = collections.defaultdict(lambda: float('inf'))
for key in dp:
if a > key:
n_dp[a] = min(n_dp[a],dp[key])
loc = bisect.bisect_right(arr2,key)
if loc < len(arr2):
n_dp[arr2[loc]] = min(n_dp[arr2[loc]],dp[key]+1)
dp = n_dp
if dp:
return min(dp.values())
return -1

详解:

首先,dp[k] = v表示在当前位置的元素为k时,保证arr1严格递增所需的操作次数为v,我们循环arr1中的元素arr1[i]和dp中的k,在更新时有两种情况:

  1. arr1[i] > k,则说明arr1当前位置的元素比k大,不替换arr2中的元素也可以满足递增,转移方程为:dp'[arr1[i]] = min(dp'[arr1[i]], dp[k])。(注意,由于位置i需要用到前一个位置的dp,所以此处用了dp'来表示,代码中则是使用了n_dp

  2. arr1[i] <= k,此时需要通过arr2进行替代操作。

    但是仔细一想,由于即便是arr1[i] > k的情况下我们也需要维护通过arr2进行替换操作的状态,否则在下一个位置dp时可能会丢掉状态,所以不要写成if(arr1[i]<=k)或者写在1. 的else分支内。

    通过arr2进行转移的方法听起来十分简单。我们需要在arr2中选出比k大的最小的数并将步骤数+1(为什么只需要最小的一个?),因此只需要将arr2排序后,进行二分即可。转移方程:dp'[arr2[loc]] = min(dp'[arr2[loc]], dp[k] + 1)

复杂度分析也很简单:“循环arr1,循环dp,二分arr2”,即O(n^2log(n))