笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 102

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

Sort Array By Parity

原题地址 https://leetcode.com/contest/weekly-contest-102/problems/sort-array-by-parity/

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

1
2
3
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

  1. 1 <= A.length <= 5000
  2. 0 <= A[i] <= 5000

提供一个没动脑子的写法,肯定有比我的方法高效的多的方法,然而懒得写了,因为这题真没什么思考的价值。

1
2
3
4
5
6
7
class Solution(object):
def sortArrayByParity(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
return [i for i in A if i % 2 == 0] + [i for i in A if i % 2 == 1]

Fruit Into Baskets

原题地址 https://leetcode.com/contest/weekly-contest-102/problems/fruit-into-baskets/

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

1
2
3
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

1
2
3
4
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

1
2
3
4
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

1
2
3
4
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect fruits.

Note:

  1. 1 <= tree.length <= 40000
  2. 0 <= tree[i] < tree.length

题目说的有点绕,简单来说就是给你一个数组tree,让你找至多包含两个不同元素的连续子数组的最大长度。

tree的元素不超过两种时,显然返回tree的长度即可。

tree的元素数量大于2时,使用一个next向量把向右第一个与tree[i]不同的元素坐标j记录到next[i]=j,遍历时迭代找next[j]下标的元素是否还在两种元素内,如果不在则从j开始继续遍历,之前的长度next[j]-i作为候选的结果。如果在则从j=next[j]开始找到第三种元素出现的地方。当然,当next[j]已经到达数组末尾len(tree)时,也没必要再从j开始遍历了。

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 totalFruit(self, tree):
"""
:type tree: List[int]
:rtype: int
"""
res = 0
next = [0] * len(tree)
cur = 0

if len(set(tree)) < 3:
return len(tree)

for i in range(1, len(tree)):
if tree[i] != tree[cur]:
next[cur] = i
cur = i

next[cur] = len(tree)
i = 0
a, b = tree[i], tree[next[i]]
while i < len(tree):
a, b = tree[i], tree[next[i]]
j = next[i]
while next[j] < len(tree) and tree[next[j]] in (a, b):
j = next[j]
res = max(res, next[j] - i)
if next[j] == len(tree):
break
i = j

return res

Sum of Subarray Minimums

原题地址 https://leetcode.com/contest/weekly-contest-102/problems/sum-of-subarray-minimums/

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

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

Example 1:

1
2
3
4
Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.

Note:

  1. 1 <= A.length <= 30000
  2. 1 <= A[i] <= 30000

这个问题实际上已经在LC891的变体中讨论过了,而且这里只要求最小值之和,正反两个反向用两次单调栈遍历一下即可。

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(object):
def sumSubarrayMins(self, A):
"""
:type A: List[int]
:rtype: int
"""
n = len(A)
s_x, e_x = [-1] * n, [n] * n

mono_stack = []

for i in range(n):
while mono_stack and A[mono_stack[-1]] >= A[i]:
e_x[mono_stack.pop()] = i
mono_stack.append(i)

mono_stack = []

for i in range(n - 1, -1, -1):
while mono_stack and A[mono_stack[-1]] > A[i]:
s_x[mono_stack.pop()] = i
mono_stack.append(i)

return sum(A[i] * (e_x[i] - i) * (i - s_x[i]) % (10**9 + 7) for i in range(n)) % (10**9 + 7)

Super Palindromes

原题地址 https://leetcode.com/contest/weekly-contest-102/problems/super-palindromes/

Let’s say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

1
2
3
4
Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Note:

  1. 1 <= len(L) <= 18
  2. 1 <= len(R) <= 18
  3. L and R are strings representing integers in the range [1, 10^18).
  4. int(L) <= int(R)

这题有点Prime Palindrome的味道,在如何找比一个大于等于n的最小palindrome上可以直接用palind(n),然后验证其平方是否也为palindrome,当然这么做肯定会超时。我当时是观察了所有平方数也为palindrome的palindrome,发现除了中间位,它的每一位都不能超过2,我当时也不知道该如何证明这个结论,就直接用了,在palind(n)加上了各位不能超过2的限制。

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
class Solution(object):
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
def palind(n):
x = str(n)
l = len(x)
for i in range(int(l / 2) - 1, -1, -1):
if int(x[i]) > 2:
return palind(n + 10**(l - i) - int(x[i:]))
for i in range(int(l / 2)):
if int(x[-1 - i]) > int(x[i]):
return palind(n + (10 - int(x[-1 - i])) * (10**i))
x = list(x)
for i in range(int(l / 2)):
x[-1 - i] = x[i]
return int(''.join(x))

def is_palind(x):
x = str(x)
for i in range(int(len(x) / 2)):
if int(x[-1 - i]) != int(x[i]):
return False
return True

res = 0
i = int(palind(int(math.sqrt(int(L)))))
print i
while i <= int(math.sqrt(int(R))):
if is_palind(i**2):
res += 1
i = palind(i + 1)
return res

接下来试图简单证明这个结论。假设palindrome数$x$的各位分别为$d_{i-1}$,即
$$x=10^{n-1} d_{n-1}+10^{n-2} d_{n-2}+\cdots+10 d_1 +d_0$$且有$$d_i=d_{n-1-i}$$那么$x^2$天然可以被表达为某种palindrome结构
$$\begin{align} x^2 & = 10^{2n - 2}d_{n - 1}^2 + 10^{2n - 3}({d_{n - 1}}d_{n - 2} + d_{n - 2}d_{n - 1}) + 10^{2n - 4}(d_{n - 1}d_{n - 3} + d_{n - 2}^2 + d_{n - 3}d_{n - 1}) + \cdots \\ & + 10^{n - 1}(d_{n - 1}d_0 + \cdots + d_0d_{n - 1}) + \cdots \\ & + 10^2(d_2d_0 + d_1^2 + d_0d_2) + 10(d_1d_0 + d_0d_1) + d_0^2 \end{align}$$

当且仅当$10^i$的系数都为个位数(<10)时,不存在进位的干扰,各项系数关于中间对称。系数中一定存在每个$d_i$的平方项,而且除了一位数以外,中间项系数$10^{n-1}$还能写成平方和$\sum\nolimits_{i = 0}^{n - 1} {d_i^2}$,显然除了一位数3,其他任何数的各位都不能超过2,且各位平方和不能超过10,那么至多可以存在2个2和1个1,或者9个1。

具体来说可以分奇数偶讨论,取palindrome的前半部分长度为n(不包含中间元素),如果palindrome为偶数:

  • 1xxxxxxxx1,前n位可以放1-4个1,其中第一位必然为1,那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
  • 2xxxxxxxx2,其他位必须全为0,共有1种情况

如果palindrome为奇数

  • 1xxxx1xxxx1,前n位可以放1-4个1,其中第一位必然为1,那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
  • 1xxxx0xxxx1,前n位可以放1-4个1,其中第一位必然为1,那么共有${n-1 \choose 1}+{n-1 \choose 2}+{n-1 \choose 3}+1$种情况
  • 2xxxx0xxxx2,其他位必须全为0,共有1种情况
  • 2xxxx1xxxx2,其他位必须全为0,共有1种情况
  • 1xxxx2xxxx1,前n位可以放1-2个1,其中第一位必然为1,共有$n-1+1$种情况

sqrt(L)d1位数,sqrt(R)d2位数时,d1+1d2-1位的superpalindrome平方根有多少个可以直接按照上面给的计数方法计算。接下来需要从大到小遍历找到大于等于sqrt(L)的palindrome,从小到大找到小于等于sqrt(R)的palindrome,并进行验证这些边界情况。另外,d1==d2可能需要另外讨论。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution(object):
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""

l, r = int(math.sqrt(int(L))), int(math.sqrt(int(R)))
res = 1 if l <= 3 <= r else 0

d1, d2 = len(str(l)), len(str(r))

def des_palind_part(x):
for i in range(len(x) - 1, -1, -1):
if int(x[i]) > 2:
return des_palind_part(x[:i] + '2' * (len(x) - i))
return x

def asc_palind_part(x):
for i in range(len(x)):
if int(x[-1 - i]) > 2:
return asc_palind_part(str(int(x) + 10**(i + 1) - int(x[-1 - i:])))
return x

def construct_palind(x, d):
if d % 2 == 0:
return x + x[::-1]
else:
return x[:-1] + x[::-1]

for i in range(d1 + 1, d2):
n = i / 2
if i % 2 == 0:
res += 2
for k in range(1, 4):
if k > n - 1:
break
res += int(scipy.misc.comb(n - 1, k))
else:
res += 5
for k in range(1, 4):
if k > n:
break
res += 2 * int(scipy.misc.comb(n - 1, k))
res += n - 1

if d1 == d2:
x = '1' + '0' * \
max((d1 / 2 - 1), 0) if d1 % 2 == 0 else '1' + '0' * max(d1 / 2, 0)
guess = construct_palind(x, d1)
while int(guess) < l:
x = asc_palind_part(str(int(x) + 1))
guess = construct_palind(x, d1)
while int(guess) <= r:
if sum(int(i)**2 for i in guess) < 10:
res += 1
x = asc_palind_part(str(int(x) + 1))
guess = construct_palind(x, d2)
return res

x = '2' * (d1 / 2) if d1 % 2 == 0 else '2' * (d1 / 2 + 1)
guess = construct_palind(x, d1)
while int(guess) >= l:
if sum(int(i)**2 for i in guess) < 10:
res += 1
x = des_palind_part(str(int(x) - 1))
guess = construct_palind(x, d1)

x = '1' + '0' * max((d2 / 2 - 1), 0) if d2 % 2 == 0 else '1' + '0' * max(d2 / 2, 0)
guess = construct_palind(x, d2)
while int(guess) <= r:
if sum(int(i)**2 for i in guess) < 10:
res += 1
x = asc_palind_part(str(int(x) + 1))
guess = construct_palind(x, d2)

return res