LeetCode第101场周赛题解

900. RLE 迭代器

题目难度Medium

编写一个遍历游程编码序列的迭代器。

迭代器由 RLEIterator(int[] A) 初始化，其中 A 是某个序列的游程编码。更具体地，对于所有偶数 i，A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。

迭代器支持一个函数：next(int n)，它耗尽接下来的 n 个元素（n >= 1）并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽，则 next 返回 -1 。

例如，我们以 A = [3,8,0,9,2,5] 开始，这是序列 [8,8,8,5,5] 的游程编码。这是因为该序列可以读作 “三个八，零个九，两个五”。

示例：

输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
输出：[null,8,8,5,-1]
解释：
RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
这映射到序列 [8,8,8,5,5]。
然后调用 RLEIterator.next 4次。

.next(2) 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。

.next(1) 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。

.next(1) 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。

.next(2) 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5，
但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。

提示：

  1. 0 <= A.length <= 1000
  2. A.length 是偶数。
  3. 0 <= A[i] <= 10^9
  4. 每个测试用例最多调用 1000 次 RLEIterator.next(int n)。
  5. 每次调用 RLEIterator.next(int n) 都有 1 <= n <= 10^9 。

思路：

直接模拟，因为A[i]值较大，所以将[3,8,0,9,2,5]映射成[8,8,8,5,5]存储的方式不可取，会导致内存溢出。所以应该将A直接存储，每次调用next时候，从数组头部开始检查，如果A[0]小于n，则将A[0]和A[1]移除队列，并将n自身减去A[0]，直到检查到A[0]大于等于n，记最后被耗去的项是A[1]，并将A[0]减去n。

时间复杂度O(N)

空间复杂度O(N)

代码：

class RLEIterator:

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

    def next(self, n):
        """
        :type n: int
        :rtype: int
        """
        last = -1
        while self.RLE and self.RLE[0] < n:
            n -= self.RLE[0]
            self.RLE = self.RLE[2:]

        if self.RLE:
            last = self.RLE[1]
            self.RLE[0] -= n
            while self.RLE[0] == 0:
                self.RLE = self.RLE[2:]

        return last


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

901. 股票价格跨度

  • 题目难度Medium

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

提示：

  1. 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
  2. 每个测试用例最多可以调用 10000 次 StockSpanner.next。
  3. 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
  4. 此问题的总时间限制减少了 50%。

思路：

动态规划。我们用数组stock代表每天股票的价格，直接遍历不是最好的方法，在第i次调用函数next的时候，我们考虑第i-1天的股票价格：若第i-1天股票价格大于第i天，我们应该返回答案1；若第i-1天的股票价格小于等于第i天，那么第i-1天左边连续小于等于i-1天的股票价格显然也小于等于第i天的股票价格，如果我们用spanner数组表示每次next函数输出的结果，那么我们只需要从第i-1天开始，跳过spanner[i-1]天，再继续检查第i-spanner[i-1]天的股票价格即可。

这个过程也可以用单调栈实现，这道题的本质是寻找每个数左边第一个比它严格大的数字，故可以采用单调栈的思想，维护一个单调递减的栈，栈中存放数字的下标，每次新加入一个数字时，若栈顶小于等于当前数字，则出栈直到栈空或者栈顶严格大于当前数字，最终栈顶距离新插入数字的下标的距离就是答案，然后将新数字压栈。

代码还可以进一步优化，当第i次调用next函数的时候，前i-1天小于第i天的股票价格就没必要保存了，我们直接在单调栈中，既保存股票价格又保存股票价格的时间跨度即可。

时间复杂度O(N)

空间复杂度O(N)

代码：

class StockSpanner:
    
    def __init__(self):
        self.stock = []
        self.spanner = []
        self.length = 0

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        ans = 1
        i = self.length - 1
        while i >= 0 and self.stock[i] <= price:
            ans += self.spanner[i]
            i -= self.spanner[i]
            
        self.length += 1
        self.stock.append(price)
        self.spanner.append(ans)
        
        return ans


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

单调栈实现

class StockSpanner:

    def __init__(self):
        self.stock = []
        self.stack = []
        self.length = 0

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        ans = 0
        while self.stack and self.stock[self.stack[-1]] <= price:
            self.stack.pop()
        
        if not self.stack:
            ans = self.length + 1
        else:
            ans = self.length - self.stack[-1]
        self.stock.append(price)
        self.stack.append(self.length)
        
        self.length += 1
        
        return ans


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

进一步优化

class StockSpanner(object):

    def __init__(self):
        self.stack = []

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        ans = 1
        while self.stack and self.stack[-1][0] <= price:
            ans += self.stack.pop()[1]
        self.stack.append((price, ans))
        return ans

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

902. 最大为 N 的数字组合

题目难度Hard

我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）

现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。

返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。

示例 1：

输入：D = ["1","3","5","7"], N = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

输入：D = ["1","4","9"], N = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

提示：

  1. D 是按排序顺序的数字 '1'-'9' 的子集。
  2. 1 <= N <= 10^9

思路：

比N低位的直接枚举相加\sum_{i=1}^{len(N)-1}len(D)^i，与N位数相同的，就从高位到低位依次比较，当前位D中有k个小于等于N[i]：若k位全小于，则结束比较；若有一位等于N[i]，则递归地继续比较。若N中数字全部都在集合D中，则答案加1。

代码：

循环实现

class Solution:
    def atMostNGivenDigitSet(self, D, N):
        """
        :type D: List[str]
        :type N: int
        :rtype: int
        """
        nums_D = [int(i) for i in D]
        nums_N = []
        while N > 0:
            nums_N.insert(0, N % 10)
            N //= 10
        len_D = len(nums_D)
        len_N = len(nums_N)
        ans = 0
        dig = [1] * len_N
        for i in range(1, len(nums_N)):
            dig[i] = len_D * dig[i - 1]
            ans += dig[i]
        all_satisfied = True
        for i in range(len_N):
            for j in nums_D:
                if j < nums_N[i]:
                    ans += dig[len_N-i-1]
            if nums_N[i] not in nums_D:
                all_satisfied = False
                break
        if all_satisfied:
            ans += 1
        return ans

递归实现

class Solution:
    def atMostNGivenDigitSet(self, D, N):
        """
        :type D: List[str]
        :type N: int
        :rtype: int
        """
        D = [int(d) for d in D]
        N = self.split(N)
        r = self.count(D,N)
        for i in range(1,len(N)):
            r += len(D)**i
        return r
    def count(self, D, N):
        if len(N) == 0:
            return 0
        if len(N) == 1:
            return len([d for d in D if d <= N[0]])
        r=(len([d for d in D if d < N[0]]))*(len(D) ** (len(N) - 1))
        if N[0] in D:
            r+=self.count(D, N[1:])
        return r
    def split(self, N):
        result = []
        while(N > 0):
            result.append(N % 10)
            N //= 10
        result.reverse()
        return result

903. DI 序列的有效排列

  • 题目难度Hard

我们给出 S，一个源于 {'D', 'I'} 的长度为 n 的字符串 。（这些字母代表 “减少” 和 “增加”。）
有效排列 是对整数 {0, 1, ..., n} 的一个排列 P[0], P[1], ..., P[n]，使得对所有的 i：

  • 如果 S[i] == 'D'，那么 P[i] > P[i+1]，以及；
  • 如果 S[i] == 'I'，那么 P[i] < P[i+1]。

有多少个有效排列？因为答案可能很大，所以请返回你的答案模 10^9 + 7.

示例：

输入："DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

提示：

  1. 1 <= S.length <= 200
  2. S 仅由集合 {'D', 'I'} 中的字符组成。

思路：

  1. 分治算法+区间动态规划

    区间动态规划，令 f(i,j) 表示 j−i+1 个数的排列，满足区间 S(i,j−1) 的方案数；

    我们每次枚举最大数字的位置，其中可以放在区间开头，放在区间末尾，或者放在区间中某个位置；

    放在区间开头时，若 S(i) == 'D'，则我们转移 f(i,j) += f(i+1,j)；

    放在区间末尾时，若 S(j - 1) == 'I'，则我们转移 f(i,j) += f(i,j−1)；

    否则，枚举位置 k in [i+1,j−1]，将区间分为两部分，若S(k - 1) == 'I' 并且 S(k) == 'D'，则 根据乘法原理和组合数计算，转移 f(i,j) += C(len−1,k−i) ∗ f(i,k−1) ∗ f(k+1,j)，其中 C(len−1,k−i) 为组合数，这里代表从 len−1 个数中选择 k−i 个数的方案数。

  2. 顺序动态规划+状态压缩

    dp[i][j]代表符合DI规则的前i个位置的由j结尾的数组的数目，那么可以求得递推公式：

    DI字符串在i位置是'D'：dp[i][j] += dp[i-1][k] for k >= j

    DI字符串在i位置是'I'：dp[i][j] += dp[i-1][k] for k < j

    由递推公式可以看出我们需要的是dp[i][0],dp[i][1],...,dp[i][j]的和，因此我们改变dp[i][j]的意义，dp[i][j]此时代表前述的和，做到这一点只需要在代码中添加dp[i][j]+=dp[i][j-1]

时间复杂度O(N^2)

空间复杂度O(N^2)

代码：

区间动态规划

class Solution:
    def __init__(self):
        self.memo = {'':1, 'D':1, 'I':1} # 记忆化
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        # 分治 + 动态规划
        # time complexity: O(n^2)
        n = len(S)
        if S in self.memo:
            return self.memo[S]
        CONST = 10**9 + 7
        ans = 0
        if S[0] == "D": # 最大数出现在最左端
            ans += self.numPermsDISequence(S[1:])
        if S[-1] == "I": # 最大数出现在最右端
            ans += self.numPermsDISequence(S[:-1])
        comb = 1 # 组合数
        for i in range(n-1):
            comb = comb*(n-i)//(i+1)
            if S[i:i+2] == "ID": # 最大数出现在中间
                temp1, temp2 = S[:i], S[i+2:]
                ans += self.numPermsDISequence(temp1)*self.numPermsDISequence(temp2)*comb
                ans %= CONST
        self.memo[S] = ans
        return ans

顺序动态规划

class Solution:
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        mod = 10 ** 9 + 7
        n = len(S)
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(i + 1):
                if S[i - 1] == 'D':
                    for k in range(j, i + 1):
                        # here start from j, regard as swap value j with i, then shift all values no larger than j
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= mod
                else:
                    for k in range(0, j):
                        dp[i][j] += dp[i - 1][k]
                        dp[i][j] %= mod
        #print(dp)
        return sum(dp[n]) % mod

状态压缩写法

class Solution:
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        dp = [1] * (len(S) + 1)
        for c in S:
            if c == "I":
                dp = dp[:-1]
                for i in range(1, len(dp)):
                    dp[i] += dp[i - 1]
            else:
                dp = dp[1:]
                for i in range(len(dp) - 1)[::-1]:
                    dp[i] += dp[i + 1]
        return dp[0] % (10**9 + 7)

一种更简洁的写法

class Solution:
    def numPermsDISequence(self, S):
        """
        :type S: str
        :rtype: int
        """
        r = [1]
        for si in S:
            if si=='D':
                nr = [0]
                for ri in r[::-1]:
                    nr.append((nr[-1]+ri)%1000000007)
                nr = nr[::-1]
            else:
                nr = [0]
                for ri in r:
                    nr.append((nr[-1]+ri)%1000000007)
            r = nr
        return sum(r)%1000000007
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,558评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,002评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,036评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,024评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,144评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,255评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,295评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,068评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,478评论 1赞 305
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,789评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,965评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,649评论 4赞 336
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,267评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,982评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,800评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,847评论 2赞 351