笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 128

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

Complement of Base 10 Integer

原题地址 https://leetcode.com/contest/weekly-contest-128/problems/complement-of-base-10-integer/

Every non-negative integer N has a binary representation. For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.

Example 1:

1
2
3
Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

1
2
3
Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

1
2
3
Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Note:

  1. 0 <= N < 10^9

虽然题目说的是complement但不是我们一般说的补码(也就是two’s complement),而是反码,不需要像补码那样填充前导0并把每一位翻转然后再加上1,只需要翻转当前所有位就可以了,所有不能直接用~,需要先计算出相应的掩码并做位异运算。

注意python文档提到过0的bit_length被规定为0,需要另外处理一下。

1
2
3
4
5
6
7
8
9
class Solution(object):
def bitwiseComplement(self, N):
"""
:type N: int
:rtype: int
"""
if N == 0:
return 1
return (1 << N.bit_length()) - 1 - N

Pairs of Songs With Total Durations Divisible by 60

原题地址 https://leetcode.com/contest/weekly-contest-128/problems/pairs-of-songs-with-total-durations-divisible-by-60/

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

1
2
3
4
5
6
Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

1
2
3
Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

  1. 1 <= time.length <= 60000
  2. 1 <= time[i] <= 500

统计模60后的余数在数组中出现的次数,然后找到每个(x,60-x)x<60-x的组合中每个x60-x分别出现的次数并相乘,注意当x=0x=30时,与它配对的数余数与它相等但不能是它自己,所以需要按照从n个元素中选出2个的组合数计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def numPairsDivisibleBy60(self, time):
"""
:type time: List[int]
:rtype: int
"""
cnt = collections.Counter([t % 60 for t in time])
res = cnt[0] * (cnt[0] - 1) / 2 + cnt[30] * (cnt[30] - 1) / 2

for i in cnt:
if 0 < i < 30:
res += cnt[i] * cnt[60 - i]

return res

Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation:
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

1
2
3
4
5
6
7
Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation:
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

1
2
3
4
5
6
7
Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

  1. 1 <= D <= weights.length <= 50000
  2. 1 <= weights[i] <= 500

它的母题非常经典,有兴趣可以自己搜一下painter’s partition problem,说的是一个长度为n的数组如何划分出K个连续的非空子数组并使得这些子数组的和的最大值最小,也就是说切割成尽可能均衡的K个分片。

比较直接的做法是动态规划,用dp[i][k]表示到i位置为止划分出k个分片时每个分片的和的最大值最少可以取到多少。

基础情况:

  • dp[i][1]=sum(weights[:i]) 把前i个元素分到同一个分片,一共只有一个和,就是目前为止所有元素的和

递推式:

  • dp[i][k]=min(max(dp[j][k-1]+sum(weights[j+1:i])) foreach j in [k-1:i-1]) 如果到j位置为止可以划分出k-1个分片,那么从j+1i可以构成一个分片,这些分片的最大值要么在前k-1个分片中已经出现,要么在最后一个新分片中,取最大即可。而j可以>=k-1<i的任意位置来确定最后一个分片的长度。

这里为了减少运行时间,我用了acc[i]预先计算了到i为止的数组和,方便直接用减法找到任意分片的和。

当然,请注意,这个算法的复杂度是O(DN^2),虽然思路简单粗暴,但肯定会TLE,不要模仿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def shipWithinDays(self, weights, D):
"""
:type weights: List[int]
:type D: int
:rtype: int
"""
n = len(weights)
acc = [weights[0]] + [0] * (n - 1)
for i in range(1, n):
acc[i] = acc[i - 1] + weights[i]

dp = list(acc)

for k in range(D - 1):
for i in range(n - 1, k, -1):
dp[i] = min([max(dp[j], acc[i] - acc[j]) for j in range(i)])

return dp[-1]

接下来用二分查找的方法来降低复杂度。

如果规定了分片和的最大值为某个x,那么可以按照顺序可以划分出最少k个分片,如果定义k=f(x),那么f是一种不严格的单调递减关系,x越大,限制越宽松,k就可以越小。而且这个f是可以很容易写出实现方法的(见代码中的min_days(max_load)),顺序遍历数组,一旦到目前为止累积的和超过了x就把当前元素之前的累积和重置为当前元素,并在k的计数上增加1个,这就是在不分片和超过x时划分出最少k的算法。

x取值最小为max(weights),对应k=n,最大为sum(weights),对应k=1,那么对于1<=D<=nD对应的某个分片和的最大值k一定在max(weights)sum(weights),可以利用二分查找对x的范围逐步缩减,测试每个范围的中点mid所对应的k是否为目标D

写到这里,我也很羞耻的分享一件事:我之前阅读过很多实现二分查找的源代码,可以看到大多数情况不会去检查mid是否正好符合需要的目标,而是用不等号合并到>=或者<=的情况,我当时没特别注意,只是觉得写的人太偷懒了,明明找到==的情况就可以直接return了也不愿意多写一个case。直到我遇到这个问题的时候,才发现了这样杜绝early return的意义所在,比如在这题中,我前面强调过单调关系是不严格的,也就是有多个x可以对应同一个f(x)=k,用二分查找遇到的第一个能满足f(x)=k并不能保证这个x就是使等式成立的最小的那个x,所以需要合并到<=D的情况,更新下一次查找的上界为当前的x(即mid),直至找到满足要求的最小的x就是需要返回的结果。这也是二分查找在很多情况下的基本需求,不是仅仅让你找元素是否在给定范围中,而是还需要返回一些该元素的其他信息,甚至对这个元素的其他信息还有一些要求,比如常见的返回元素在数组中的位置,Python有一个库bisect就是实现这个功能的,可以去看文档,bisect返回的是最左的位置,而bisect_right返回的是最右的位置,都是需要在处理==时合并到对应的不等式情形的。

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
class Solution(object):
def shipWithinDays(self, weights, D):
"""
:type weights: List[int]
:type D: int
:rtype: int
"""
n = len(weights)
acc = [0] * (n + 1)
for i in range(n):
acc[i + 1] = acc[i] + weights[i]

def min_days(max_load):
start = 0
d = 1
for i in range(n):
if acc[i + 1] - acc[start] > max_load:
d += 1
start = i
return d

l, r = max(weights), acc[-1]

while l < r:
mid = l + (r - l) / 2
k = min_days(mid)
if k <= D:
r = mid
else:
l = mid + 1

return l

Numbers With Repeated Digits

原题地址 https://leetcode.com/contest/weekly-contest-128/problems/numbers-with-repeated-digits/

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

1
2
3
Input: 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

1
2
3
Input: 100
Output: 10
Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3:

1
2
Input: 1000
Output: 262

Note:

  1. 1 <= N <= 10^9

先找<N+1的所有无重复位的整数。假设N+1一共有n位。A(m,k)表示从m个数中取出k个数的排列数,即m!/(m-k)!

1-n-1位数没有大小限制,只需要考虑无重复即可

  • 如果不包含0,那么i位数可以在1-9中任选排列,共有A(9,i)个数
  • 如果包含0,那么i位数有i-1位非0,在i-1位无0数中可以选择i-1位后面的位置插入一个0形成包含0i位数,共有(i-1)*A(9,i-1)个数

n位数考虑逐步扩大前缀长度,从首位开始,如果N+1在这一位上的数字是d1,那么每个小于d1的数字都可以作为前缀,后面n-1位可以取任何与d1不同的值,共有A(9,n-1)*(d1-1)个数,接下来考虑固定首位与d1一致,第二位可以比与N+1的第二位d2小的任意值,当也要求与d1不一致,然后像上面那样考虑剩下的n-2位……

如果已经固定的前缀中出现了重复的数字,那么后面的位置也不需要再考虑了,所以当需要固定某一位作为前缀的最后一位时,如果前缀中已经出现了,那么就可以直接跳出扩大前缀的循环了。

最后得到共有res个没有重复数字的<N+1的数,那么就有N-res个带有重复数字的数。

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
class Solution(object):
def numDupDigitsAtMostN(self, N):
"""
:type N: int
:rtype: int
"""
L = [int(i) for i in str(N + 1)]
n = len(L)
f = [1] * 10
for i in range(9):
f[i + 1] = f[i] * (i + 1)

def A(m, k):
return f[m] / f[m - k]

res = 0

for i in range(1, n): # not contain 0
res += A(9, i)

for i in range(1, n - 1): # contain 0
res += A(9, i) * i

prefix = set()

for i, d in enumerate(L):
for j in range(0 if i else 1, d):
if j not in prefix:
res += A(9 - i, n - i - 1)
if d in prefix:
break
prefix.add(d)

return N - res