笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 129

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

Partition Array Into Three Parts With Equal Sum

原题地址 https://leetcode.com/contest/weekly-contest-129/problems/partition-array-into-three-parts-with-equal-sum/

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i+1 < j with (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])

Example 1:

1
2
3
Input: [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2:

1
2
Input: [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3:

1
2
3
Input: [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Note:

  1. 3 <= A.length <= 50000
  2. -10000 <= A[i] <= 10000

按顺序凑出第一个和为sum(A)/3,然后找第二个,如果都存在则返回true

注意可能存在负数,所以不能在第一次超过sum(A)/3时过早判定false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def canThreePartsEqualSum(self, A):
"""
:type A: List[int]
:rtype: bool
"""
s = sum(A)
if s % 3 != 0:
return False
print s
cur, part = 0, 0

for i in A:
if cur + i == s / 3:
part += 1
if part == 2:
return True
cur = 0
else:
cur += i

return False

Smallest Integer Divisible by K

原题地址 https://leetcode.com/contest/weekly-contest-129/problems/smallest-integer-divisible-by-k/

Given a positive integer K, you need find the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.

Return the length of N. If there is no such N, return -1.

Example 1:

1
2
3
Input: 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.

Example 2:

1
2
3
Input: 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.

Example 3:

1
2
3
Input: 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.

Note:

  1. 1 <= K <= 10^5

只包含1的$n$位数可以表示为$(10^n-1)/9$,要求找到最小的$n$满足$$(10^n-1)/9=xK$$其中$x$为正整数。众所周知根据Euler’s Totient Theorem如果$a$和$p$互质一定有$${a^{\varphi (n)}} \equiv 1 \quad (\bmod n)$$所以只要9K和10互质,即K不能被2或5整除,就可以保证一定存在这个$n$,但可惜的是Euler函数$\varphi (n)$并不保证是使得等式成立的最小值,所以还需要长度为K的遍历来找到最小值,至于为什么长度K可以保证找到结果,证明参加Fermat小定理。

这里用类似除法竖式的方法,把上一位的余数r添上后面一位1再与K求余数,直到可以整除为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def smallestRepunitDivByK(self, K):
"""
:type K: int
:rtype: int
"""
if K % 2 == 0 or K % 5 == 0:
return -1

r = 1

for i in range(1, K + 1):
if r % K == 0:
return i
r = (r * 10 + 1) % K

Best Sightseeing Pair

原题地址 https://leetcode.com/contest/weekly-contest-129/problems/best-sightseeing-pair/

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

1
2
3
Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

  1. 2 <= A.length <= 50000
  2. 1 <= A[i] <= 1000

线性扫描一次:到目前(j)为止最佳的起始点i满足使得A[i]+i最大,如果上式加上A[j]-j大于目前为止最好的sightseeing,那就再把sightseeing记录也更新,完成后计算A[j]+jj是否比最佳起始点更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def maxScoreSightseeingPair(self, A):
"""
:type A: List[int]
:rtype: int
"""
start = max_val = 0

for i, v in enumerate(A):
temp = start + v - i
max_val = max(max_val, temp)
start = max(start, v + i)

return max_val

Binary String With Substrings Representing 1 To N

原题地址 https://leetcode.com/contest/weekly-contest-129/problems/binary-string-with-substrings-representing-1-to-n/

Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

1
2
Input: S = "0110", N = 3
Output: true

Example 2:

1
2
Input: S = "0110", N = 4
Output: false

Note:

  1. 1 <= S.length <= 1000
  2. 1 <= N <= 10^9

本来可能需要KMP算法,不过暴力做也没什么。

只需要检查N/2+1N是否在S中就可以了,更小的数也是前面这些数的子串。越大的数越可能难以在S中找到匹配,因此倒序检查可以提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def queryString(self, S, N):
"""
:type S: str
:type N: int
:rtype: bool
"""
for i in range(N, N / 2, -1):
if bin(i)[2:] not in S:
return False

return True