笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 101

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

RLE Iterator

原题地址 https://leetcode.com/contest/weekly-contest-101/problems/rle-iterator/

Write an iterator that iterates through a run-length encoded sequence.

The iterator is initialized by RLEIterator(int[] A), where A is a run-length encoding of some sequence. More specifically, for all even i, A[i] tells us the number of times that the non-negative integer value A[i+1] is repeated in the sequence.

The iterator supports one function: next(int n), which exhausts the next n elements (n >= 1) and returns the last element exhausted in this way. If there is no element left to exhaust, next returns -1 instead.

For example, we start with A = [3,8,0,9,2,5], which is a run-length encoding of the sequence [8,8,8,5,5]. This is because the sequence can be read as “three eights, zero nines, two fives”.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: ["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
Output: [null,8,8,5,-1]
Explanation:
RLEIterator is initialized with RLEIterator([3,8,0,9,2,5]).
This maps to the sequence [8,8,8,5,5].
RLEIterator.next is then called 4 times:

.next(2) exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5].

.next(1) exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5].

.next(1) exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5].

.next(2) exhausts 2 terms, returning -1. This is because the first term exhausted was 5,
but the second term did not exist. Since the last term exhausted does not exist, we return -1.

Note:

  1. 0 <= A.length <= 1000
  2. A.length is an even integer.
  3. 0 <= A[i] <= 10^9
  4. There are at most 1000 calls to RLEIterator.next(int n) per test case.
  5. Each call to RLEIterator.next(int n) will have 1 <= n <= 10^9.

直接展开成序列可能会占用很大的空间,因此可以给RLEIterator分配一个光标cur表示现在遍历到的位置,考虑到初始化以后就不再进行数据的添加操作,那么可以改变偶数iA[i]计数以表示还有多少A[i+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
26
27
class RLEIterator(object):

def __init__(self, A):
"""
:type A: List[int]
"""
self.A = A
self.cur = 0
self.len = len(A)

def next(self, n):
"""
:type n: int
:rtype: int
"""
while self.cur < self.len:
if self.A[self.cur] >= n:
self.A[self.cur] -= n
return self.A[self.cur + 1]
else:
n -= self.A[self.cur]
self.cur += 2
return -1

# Your RLEIterator object will be instantiated and called as such:
# obj = RLEIterator(A)
# param_1 = obj.next(n)

Online Stock Span

原题地址 https://leetcode.com/contest/weekly-contest-101/problems/online-stock-span/

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation:
First, S = StockSpanner() is initialized. Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Note:

  1. Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
  2. There will be at most 10000 calls to StockSpanner.next per test case.
  3. There will be at most 150000 calls to StockSpanner.next across all test cases.
  4. The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

对于每个A[i],span即最近的大于A[i]的值到A[i]的距离。当然对于A[0],这个最近的较大值可以看成在-1位置的一个虚拟的元素。如果是一次性给出一个序列,可以按照类似于LC891的变体:求所有连续子集的极差之和提到的做法维护一个单调栈,但这里的元素却是实时添加的,如果每次都为新添加的price遍历整个序列,会导致很大的时间开销。所以可以这样改进:维护一个pre列表,pre[i]在下标i之前超过A[i]的最近元素的坐标,当添加新的price前,先与A[-1]比较大小,如果A[-1]<=price再把坐标从len(A)-1迭代为pre[len(A)-1]进行比较,直至第一次找到使得A[i]>pricei,再把price放进列表,并把它的对应前驱pre设置为i放入pre列表。

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
class StockSpanner(object):

def __init__(self):
self.A = []
self.pre = []

def next(self, price):
"""
:type price: int
:rtype: int
"""
i = len(self.A) - 1
while i >= 0:
if self.A[i] > price:
break
i = self.pre[i]

self.A.append(price)
self.pre.append(i)

return len(self.A) - i - 1


# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

Numbers At Most N Given Digit Set

原题地址 https://leetcode.com/contest/weekly-contest-101/problems/numbers-at-most-n-given-digit-set/

We have a sorted set of digits D, a non-empty subset of {'1','2','3','4','5','6','7','8','9'}. (Note that '0' is not included.)

Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {'1','3','5'}, we may write numbers such as '13', '551', '1351315'.

Return the number of positive integers that can be written (using the digits of D) that are less than or equal to N.

Example 1:

1
2
3
4
5
Input: D = ["1","3","5","7"], N = 100
Output: 20
Explanation:
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2:

1
2
3
4
5
6
7
Input: D = ["1","4","9"], N = 1000000000
Output: 29523
Explanation:
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits of D.

Note:

  1. D is a subset of digits '1'-'9' in sorted order.
  2. 1 <= N <= 10^9

假设N是一个n位数,毫无疑问任意构造1n-1位数一定满足<=N,从d个数组合出的有d^i个。

接下来只需要考虑从D构造满足<=Nn位数。首先找到有D有多数个数字是小于N的首位的,假设为k,都可以安排在首位,剩下的n-1位就可以随意组合,这里就可以找到k*d^(n-1)个数。如果N的首位也在D中,那么就可以递归的考虑可以由D组合出多少个小于去掉首位的Nn-1为数,这里特别注意一下,如果去掉首位后这个数字以0开头,那么不能从D构造出小于新数字的n-1位数,就可以直接跳到递归出口了,当然,另一个递归出口是N只有一位时,这个数字还存在于D,可以直接算作一个取到=的结果。

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 atMostNGivenDigitSet(self, D, N):
"""
:type D: List[str]
:type N: int
:rtype: int
"""
d = len(D)

def Ndigits(x): #return amount of the nums < x, where nums have equal digits with x
res = 0
n = len(str(x))
i = bisect.bisect_left(D, str(x)[0])
res += i * d**(n - 1)
if i < d and D[i] == str(x)[0]:
if n > 1:
if str(x)[1] != '0':
res += Ndigits(int(str(x)[1:]))
else:
res += 1
return res

return sum(d**i for i in range(1, len(str(N)))) + Ndigits(N)

Valid Permutations for DI Sequence

原题地址 https://leetcode.com/contest/weekly-contest-101/problems/valid-permutations-for-di-sequence/

We are given S, a length n string of characters from the set {'D', 'I'}. (These letters stand for “decreasing” and “increasing”.)

A valid permutation is a permutation P[0], P[1], ..., P[n] of integers {0, 1, ..., n}, such that for all i:

  • If S[i] == 'D', then P[i] > P[i+1], and;
  • If S[i] == 'I', then P[i] < P[i+1].

How many valid permutations are there? Since the answer may be large, return your answer modulo 10^9 + 7.

Example 1:

1
2
3
4
5
6
7
8
9
Input: "DID"
Output: 5
Explanation:
The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

Note:

  1. 1 <= S.length <= 200
  2. S consists only of characters from the set {'D', 'I'}.

还是试着用动态规划去解决。dp[i][j]表示当P前排到第i位时,如果第i位元素的数值在剩下的所有元素中排到第j位,共有多少种排法。那么当你排到第i+1位时,如果S[i]=='D',第i+1位必须小于第i位,如果第i+1位大小在之后的元素能排到第j位,那么第i位的值的大小在剩下的元素中必须至少排在第j+1位,因此dp[i+1][j]dp[i][j+1:]的和;同理,当S[i]=='I'时,为了保证第i+1位大于第i为,第i位在之后的元素中也至多只能排到第j大,dp[i+1][j]dp[i][:j+1]的和。排到最后一位时,这一位在剩下的元素中必然只能插入到第0位,因此最后结果就是dp[-1][0]的值。

以example 1的输入"DID"为例

j\i 0 1 2 3
0 1:(0) 3:(30),(20),(10) 3:(301),(201),(102) 5: (3021),(2031),(1032),(3120),(2130)
1 1:(1) 2:(31),(21) 5:(302),(203),(103),(312),(213)
2 1:(2) 1:(32)
3 1:(3)

直球编程得到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def numPermsDISequence(self, S):
"""
:type S: str
:rtype: int
"""
n = len(S) + 1
dp = [[1] * n] + [[0] * n for _ in range(n - 1)]

for i in range(n - 1):
if S[i] == 'D':
for j in range(n - i - 1):
dp[i + 1][j] = (sum(dp[i][j + 1:])) % (10**9 + 7)
else:
for j in range(n - i - 1):
dp[i + 1][j] = (sum(dp[i][:j + 1])) % (10**9 + 7)
return dp[-1][0]

这样写虽然能通过,但众所周知这里存在着大量的重复计算和存储导致了$o(n^3)$的时间复杂度和$o(n^2)$的空间复杂度,我们可以稍作调整写成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def numPermsDISequence(self, S):
"""
:type S: str
:rtype: int
"""
n = len(S)
dp = [1] * (n + 1)

for c in S:
if c == 'D':
dp = dp[1:]
for i in range(len(dp) - 1, 0, -1):
dp[i - 1] = (dp[i - 1] + dp[i]) % (10**9 + 7)
else:
dp = dp[:-1]
for i in range(len(dp) - 1):
dp[i + 1] = (dp[i + 1] + dp[i]) % (10**9 + 7)
return dp[0]

使得时间复杂度降低到$o(n^2)$同时空间复杂度降低到$o(n)$