leetcode contest 153 writeup

概要

leetcode第153周周赛

注:思路是理想思路,代码有可能是我比赛时写的,就不那么理想.

所以代码与思路不一定等价

第一题

思路

直接做

代码

from typing import List


class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
        if start > destination:
            start, destination = destination, start
        s = sum(distance)
        length = destination - start
        s_shun = 0
        for i in range(start, destination):
            s_shun += distance[i]
        s_re = s - s_shun
        if s_shun > s_re:
            return s_re
        else:
            return s_shun

第二题

思路

调库就行，吃的空的话可以试试直接推（考虑闰月就行

代码

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        import datetime
        return ["Monday", "Tuesday","Wednesday", "Thursday", "Friday", "Saturday", "Sunday"][datetime.datetime(year, month, day).weekday()]

第三题

思路

1. 思路类似于lcs，稍微改一下就可以
2. 写一个和lcs一样的dp关系式dp_no_delete[i] = max(arr[i], dp_no_delete[i - 1] + arr[i])
3. 在写一个代表了代表以i为结尾的和尽量大且有过删除的dp关系式dp_with_delete[i] = max(dp_no_delete[i - 1], dp_with_delete[i - 1] + arr[i])

代码

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        l = len(arr)
        dp_with_delete = [0] * l
        dp_no_delete = [arr[0]] * l
        for i in range(1, l):
            dp_no_delete[i] = max(arr[i], dp_no_delete[i - 1] + arr[i])
            dp_with_delete[i] = max(dp_no_delete[i - 1], dp_with_delete[i - 1] + arr[i])
        re = dp_no_delete[0]
        for i in range(1,l):
            m = dp_no_delete[i]
            n = dp_with_delete[i]
            if re < max(m, n):
                re = max(m, n)
        return re

第四题

思路

这题没写出来网上看了别人的代码写的。思路正确，但是需要优化下

代码

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        maxV = 1000000001
        dp = [[maxV for i in range(n + 1)] for _ in range(n + 1)]

        # initial
        arr2.sort()
        dp[0][0] = -1

        for i in range(1, n + 1):
            for j in range(0, i + 1):
                if arr1[i - 1] > dp[j][i - 1]:
                    dp[j][i] = arr1[i - 1]

                if j > 0:
                    loc = bisect.bisect_right(arr2, dp[j - 1][i - 1])
                    if loc < len(arr2):
                        dp[j][i] = min(dp[j][i], arr2[loc])

                if i == n and dp[j][i] != maxV:
                    return j

        return -1

后记

这次睡过头了忘记参见了，以上是后面写的。最后一题偏♂，反正我是做不出2333