讨论/题目交流/🏆 第 183 场力扣周赛/
🏆 第 183 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 非递增顺序的最小子序列
4 分 - 将二进制表示减到 1 的步骤数
6 分 - 最长快乐字符串
7 分 - 石子游戏 III

T1. Array + Sort
    返回子序列而不是子串(子数组), 因此对nums递减排序, 然后自左向右累加nums[i]并存nums[i]至结果数组, 直到累加元素和 > 未累加元素和时, 跳出循环直接返回结果数组. 此时结果数组必然是最短且元素和最大的子序列。
    时间复杂度O(nlogn), 空间复杂度O(n)。
class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        curSum, total = 0, sum(nums)
        res = []
        nums = sorted(nums, reverse=True)
        for i in range(len(nums)):
            curSum += nums[i]
            res.append(nums[i])
            if curSum > total - curSum:
                break
        return res
T2. String + Math
更正题解:
法一 - 字符串转10进制数, 然后模拟即可。时间复杂度O(n), 空间复杂度O(1)。
不过需要注意给定串s最大长度可达500, 直接操作并不可取, 语言不通用!
class Solution:
    def numSteps(self, s: str) -> int:
        num, val, res = 0, 1, 0
        for i in range(len(s) - 1, -1, -1):
            num += (ord(s[i]) - 48) * val
            val *= 2
        while num != 1:
            if num % 2 == 0:
                num //= 2
            else:
                num += 1
            res += 1
        return res

法二: 模拟
字符串->字符数组, 然后自右向左遍历, 若当前位为0则继续考察前一位, 当前位为1则模拟从低位向高位的进位, 直到发现某个数位为'0', 将其进1置'1'.
时间复杂度O(n), 空间复杂度O(n).
class Solution:
    def numSteps(self, s: str) -> int:
        s = list(s)
        curIdx, res = len(s) - 1, 0
        while curIdx > 0:
            if s[curIdx] == '0':
                curIdx -= 1; res += 1
            else:
                res += 1
                while curIdx >= 0 and s[curIdx] == '1':
                    curIdx -= 1; res += 1
                if curIdx > 0:
                    s[curIdx] = '1'
        return res
T3. Greedy
    贪心策略: 每次追加'a', 'b', 'c'中剩余数量最多的字符, 并记录上次添加的字符是哪种, 从而使得不会有连续的3'a', 'b''c'出现, 同时保证串最长.
    时间复杂度O(n), 空间复杂度O(1)。
class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        lastCh, isAdd = "x", 1
        res = ""
        while isAdd:
            isAdd = 0
            if a >= b >= c or a >= c >= b:
                if lastCh != "a":
                    if a >= 2:
                        res += "aa"; a -= 2
                    elif a == 1:
                        res += "a"; a -= 1
                    lastCh = "a"; isAdd = 1
                else:
                    if b >= c and b >= 1:
                        res += "b"; lastCh = "b"; b -= 1; isAdd = 1
                    elif c >= b and c >= 1:
                        res += "c"; lastCh = "c"; c -= 1; isAdd = 1
            elif b >= a >= c or b >= c >= a:
                if lastCh != "b":
                    if b >= 2:
                        res += "bb"; b -= 2
                    elif b == 1:
                        res += "b"; b -= 1
                    lastCh = "b"; isAdd = 1
                else:
                    if a >= c and a >= 1:
                        res += "a"; lastCh = "a"; a -= 1; isAdd = 1
                    elif c >= a and c >= 1:
                        res += "c"; lastCh = "c"; c -= 1; isAdd = 1
            elif c >= a >= b or c >= b >= a:
                if lastCh != "c":
                    if c >= 2:
                        res += "cc"; c -= 2
                    elif c == 1:
                        res += "c"; c -= 1
                    lastCh = "c"; isAdd = 1
                else:
                    if a >= b and a >= 1:
                        res += "a"; lastCh = "a"; a -= 1; isAdd = 1
                    elif b >= a and b >= 1:
                        res += "b"; lastCh = "b"; b -= 1; isAdd = 1
        return res
T4. DFS + Memo
    dfs(i, M) - 从第i堆石子开始取, 最多能取M(M = 3)堆时可取到的最大石子数, 然后记忆化搜索Alice取得的最大石子数之和, 石子数总和-Alice取得的最大石子数之和即为Bob取得的石子数, 取得更多石子数量的即为胜者。
    时间复杂度O(n), 空间复杂度O(n).
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n, total = len(stoneValue), sum(stoneValue)
        
        sufSum = [0] * (n + 1)
        memo = {}
        
        for i in range(n - 1, -1, -1):
            sufSum[i] = sufSum[i + 1] + stoneValue[i]
        
        # dfs(i, M) - 从第i堆石子开始取, 最多能取M(M = 3)堆时可取到的最大石子数
        def dfs(i, M):
            # 记忆化: 若组合(i, M)已经搜索过, 则直接返回
            if (i, M) in memo:
                return memo[(i, M)]
            # 边界: 石子已全部取完
            if i >= n:
                return 0
            # 搜索过程: 枚举拿x∈[1, 3]堆时的最优解(注意values[i]可能为负数, 故应初始化为一个"无穷小"的负数)
            best = float("-inf")
            for x in range(1, M + 1):
                # 剩余石子减去对方最优策略
                best = max(best, sufSum[i] - dfs(i + x, M))
            # 记忆化最优解, 并返回之
            memo[(i, M)] = best
            return best
        
        Alice = dfs(0, 3)
        Bob = total - Alice
        if Alice > Bob: return "Alice"
        elif Bob > Alice: return "Bob"
        else: return "Tie"
14
展开全部 22 讨论