笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 38

https://leetcode.com/contest/leetcode-weekly-contest-38/

本周刷题,周日睡晚了所以没参加。这周的题我看了下,根据前几名的时间来推算,比上周麻烦多了。但实际上主要问题出在第二题的贪心策略和第三题的动态规划上,虽然很明显能想到是通过贪心和动规解决的,但具体策略上容易想不到。标注为hard难度的第四题反而是硬码就能过去的。

Maximum Product of Three Numbers

原题地址:https://leetcode.com/contest/leetcode-weekly-contest-38/problems/maximum-product-of-three-numbers/

Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]

Output: 6

Example 2:

Input: [1,2,3,4]

Output: 24

Note:

  1. The length of the given array will be in range $[3,10^4]$ and all elements are in the range $[-1000, 1000]$.
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

我思路比较简单,取整个数组里面最大的正数,最大的由三个数产生的乘积中一定有一个是来自这个数的,剩下的要比较的就是最小的两个负数的乘积,以及两个次大的正数的乘积,哪个更大?

当然如果根本不存在最大的正数,也就是说整个数组的数都小于等于0,那么就把最大的三个数(也就是绝对值最小的三个负数)相乘。说到底,本质上就是把数组按升序排序后记为a,比较a[-1]*a[-2]*a[-3]a[-1]*a[0]*a[1]哪个大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def maximumProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
m1=max(nums)
nums.pop(nums.index(m1))
m2=max(nums)
nums.pop(nums.index(m2))
m3=max(nums)
nums.pop(nums.index(m3))
nums.append(m2)
nums.append(m3)
if m1<=0:
return m1*m2*m3
l1=min(nums)
nums.pop(nums.index(l1))
l2=min(nums)
if l1*l2>m2*m3:
return l1*l2*m1
else:
return m1*m2*m3

我为了运行的快一点,没做排序但做了不少分支,结果提交的时候也是所有py代码里面最快的。如果不追求运行速度的话完全可以写的简单一些,直接排序后比较上面两个乘积的大小就行了。

Course Schedule III

原题地址:https://leetcode.com/contest/leetcode-weekly-contest-38/problems/course-schedule-iii/

Course Schedule III

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Example:
Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

Output: 3

Explanation:

There’re totally 4 courses, but you can take 3 courses at most:

First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.

Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.

Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.

The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

  1. The integer 1 <= d, t, n <= 10,000.
  2. You can’t take two courses simultaneously.

这类任务调度问题在CS161的习题中已经讨论了不少,不过一般讨论的优化目标是$\mathop {\max }\limits_i \left[ \max (f_i - d_i,0) \right]$或者$\sum\nolimits_i {\max (f_i - d_i,0)}$,其中$f_i$表示任务$i$的实际完成时间,这类问题通常遵循死线最近优先完成原则1,这题的优化目标是$\sum\nolimits_i {[d_i - f_i \ge 0]}$,策略上也没有太大不同,先按照d的升序给课程们排序,依次开始完成课程,当当前完成时间晚于课程的d时,从之前完成的课程中去除用时最多(t最大)的课再放入当前的课,这样以一课换一课如果失败则确实不存在更优的课程安排。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
class Solution(object):
def scheduleCourse(self, courses):
"""
:type courses: List[List[int]]
:rtype: int
"""
c= sorted(courses, key = lambda x : x[1] )
roll=[]
time = 0
for i in c:
time += i[0]
heapq.heappush(roll,-i[0])
while time > i[1]:
time += heapq.heappop(roll)
return len(roll)

需要注意的是我一开始从roll中选择t最大的课时直接用了maxpop函数出现了TLE,所以这里维护了一个最小堆来快速寻找最大的t

K Inverse Pairs Array

原题地址 https://leetcode.com/contest/leetcode-weekly-contest-38/problems/k-inverse-pairs-array/

K Inverse Pairs Array

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For ith and jth element in the array, if i < jand a[i] > a[j] then it’s an inverse pair; Otherwise, it’s not.

Since the answer may very large, the answer should be modulo 10^9 + 7.

Example 1:
Input: n = 3, k = 0
Output: 1
Explanation:
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:
Input: n = 3, k = 1
Output: 2
Explanation:
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Note:
The integer n is in the range [1, 1000] and k is in the range [0, 1000].

这个一开始我想的是递归,假设这个函数为$f(n,k)$,比较容易看出$f(n+1,k)$和$f(n,k),f(n,k-1),\ldots f(n,k-n)$之间的关系:

现在把$n+1$在数组的位置固定在第$n+1$位,那么$k$对逆就要在$[1,\ldots,n]$中产生,即这种条件下可以有$f(n,k)$中数组。

把$n+1$在数组的位置固定在第$n$位,那至少和第$n+1$已经形成一对逆,剩下的$k-1$对也要在$[1,\ldots,n]$中产生,即有$f(n,k-1)$

……

如果把$n+1$放在第一位,那就已经和后面$n$位形成了$n$对逆了,后面这些数再排出$k-n$对即可,即有$f(n,n-k)$

综上所述$$f(n+1,k)=\sum\limits_{j = n -k}^{k} {f(n,j)}$$显然可能出现$f$的第二个参数为负数的情况,也就是$n<k-1$,对应的意义就是把$n$放的太前不用再排其他数就已经凑够了$k$对逆,那么很显然这些位置代表的情况就不用算了直接置为0就行。不过这个递归关系写出来调用的函数次数真是有点多了,再加上$k$这个维度,其实考虑动态规划更加现实。接下来我们用$k+1$替换掉上式的$k$得到$$f(n+1,k+1)=\sum\limits_{j = n - (k+1) }^{k+1} {f(n,j)}$$
再用这个等式减去上面的等式有:
$$f(n+1,k+1)=f(n,k+1)+f(n+1,k)-f(n,n-k)$$
我想我的意思已经很明确了,不过这里比较需要费心的地方是边界条件,更功利的说是一开始作为基石的那几个需要自己规定的函数值。比如对于

  • $n=0$ 时函数值都要置为0
  • $k=0$ 时函数值规定为1
  • $k>n(n-1)/2$时函数值为0 取等号时为1
  • 刚刚说到的函数参数为负的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def kInversePairs(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
if k > n*(n-1)/2 or k<0:
return 0
if k==n*(n-1)/2 or k==0:
return 1
d=[[0 for i in range(k+1)] for j in range(n+1)]
mod=10**9+7
for i in range(1,n+1):
for j in range(min(n*(n-1)/2,k)+1):
if j==0 or j==i*(i-1)/2:
d[i][j]=1
elif j>i*(i-1)/2:
d[i][j]=0
elif j>=i:
d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-i]
else:
d[i][j]=d[i][j-1]+d[i-1][j]
d[i][j]=d[i][j]%mod
return d[n][k]

我写这个的时候遇到了比较少见的MLE错误,起初我也在想这种规模的二维数组也能MLE吗,后来加了那句d[i][j]=d[i][j]%mod就过了,原因是数据值本身太大了,仔细看题目说过要返回取模以后的数,其实学过密码学就会觉得对于只涉及加减乘的运算来说取模是每步运算都取还是只有最后返回取对于结果没什么影响,所以没必要担心,大胆地在每次计算后都取一下模吧。

Design Excel Sum Formula

原题地址 https://leetcode.com/contest/leetcode-weekly-contest-38/problems/design-excel-sum-formula/
因为题实在太长了我就不重新贴了,我之前说过其实这题不怎么需要动脑,暴力码就行。比较容易出错的是int Sum(int row, char column, List of Strings : numbers)要求被设置成存放求和结果的那个单元(r,c)是动态的,调用过一次Sum后,如果求和函数的范围内的单元的值发生了变化,(r,c)也要随之变化。而(r,c)再被调用Sum或者Set函数改变值时,原来的公式定义才会被覆盖。

我们没文化的人就是这个样子,不会用什么精巧的方法,在Excel类内定义了一个成员字典formula维护被赋予的函数定义,每次有任何单元的值发生变化时先检查字典里面这个函数有没有被作为其他那个求和函数的成员,如果有,就顺便重新在哪个被定义的单元上更改求和结果。至于怎样区别是直接命令更改的单元值,还是因为定义范围内的单元变化导致的这个单元的变化,我是通过修改了Set函数原型,增加了一个默认参数区分是直接调用还是其他函数的调用引起的调用,当然我不建议好孩子学这种做法,如果不修改函数原型,可以添加一个成员来标识这次的调用是不是由于其他函数的调用引发的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Excel(object):

def __init__(self, H,W):
"""
:type H: int
:type W: str
"""
self.H=H
self.W=ord(W)-ord('A')+1
self.c=[[0 for j in range(self.W)] for i in range(self.H)]
self.formula=dict()
def set(self, r, c, v,user=True):
"""
:type r: int
:type c: str
:type v: int
:rtype: void
"""
temp=0
if user and (r,c) in self.formula:
self.formula[r,c]=[]
if 0<r<=self.H and ord('A')<=ord(c)<ord('A')+self.W:
temp=self.c[r-1][ord(c)-ord('A')]
self.c[r-1][ord(c)-ord('A')]=v
for (r0,c0) in self.formula:
if (r,c) in self.formula[(r0,c0)]:
val=self.get(r0,c0)
self.set(r0,c0,val+(v-temp)*self.formula[(r0,c0)].count((r,c)),False)
def get(self, r, c):
"""
:type r: int
:type c: str
:rtype: int
"""
if 0<r<=self.H and ord('A')<=ord(c)<ord('A')+self.W:
return self.c[r-1][ord(c)-ord('A')]
def sum(self, r, c, strs):
"""
:type r: int
:type c: str
:type strs: List[str]
:rtype: int
"""
self.formula[r,c]=[]
s=0
for cal in strs:
points=cal.split(':')
if len(points)<2:
s+=self.get(int(points[0][1:]),points[0][0])
self.formula[(r,c)].append((int(points[0][1:]),points[0][0]))
else:
start=points[0]
end=points[1]
for i in range(int(start[1:]),int(end[1:])+1):
for j in range(ord(start[0]),ord(end[0])+1):
s+=self.get(i,chr(j))
self.formula[(r,c)].append((i,chr(j)))
self.set(r,c,s,False)
return self.get(r,c)