leetcode contest 153 writeup

 

概要

leetcode第153周周赛

题目 难度 知识点
公交站间的距离 简单
一周中的第几天 简单
删除一次得到子数组最大和 中等 dp
使数组严格递增 困难 dp

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

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

第一题

思路

直接做

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

第二题

思路

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

代码

1
2
3
4
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])

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

第四题

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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