Bluefissure's Blog

A Place for Recording

0%

LeetCode Weekly Contest 153

Posted on Edited on In , Disqus:

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))。