[Leetcode/python3]第203场周赛题解

时间:2020-8-27 作者:admin


P1 圆形赛道上经过次数最多的扇区

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成,扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛,该马拉松全程由 m 个阶段组成。其中,第 i 个阶段将会从扇区 rounds[i – 1] 开始,到扇区 rounds[i] 结束。举例来说,第 1 阶段从 rounds[0] 开始,到 rounds[1] 结束。

请你以数组形式返回经过次数最多的那几个扇区,按扇区编号 升序 排列。

注意,赛道按扇区编号升序逆时针形成一个圆(请参见第一个示例)。

[Leetcode/python3]第203场周赛题解
解:只需考虑起点和终点。 中间过程相当于没跑。

class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        a, b = rounds[0], rounds[-1]
        if a == b: return [a]
        if a < b: return [x for x in range(a, b+1)]
        return  [x for x in range(1, b + 1)] + [x for x in range(a, n+1)]   

P2 你可以获得的最大硬币数目

有 3n 堆数目不一的硬币,你和你的朋友们打算按以下方式分硬币:

  • 每一轮中,你将会选出 任意 3 堆硬币(不一定连续)。
  • Alice 将会取走硬币数量最多的那一堆。
  • 你将会取走硬币数量第二多的那一堆。
  • Bob 将会取走最后一堆。
  • 重复这个过程,直到没有更多硬币。
    给你一个整数数组 piles ,其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

解:贪心。
Code 1:

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles = sorted(piles)[::-1]
        return sum(piles[2*i + 1] for i in range(len(piles) // 3))

Code 2:

class Solution:
    def maxCoins(self, A):
        return sum(sorted(A)[len(A)//3::2])

P3 查找大小为 M 的最新分组

给你一个数组 arr ,该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串,该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中(假设二进制字符串和 arr 都是从 1 开始索引的情况下),二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ,请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串,且左右两边不再有可以延伸的 1 。

返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤,请返回 -1 。

解一: 倒序 + 二分

  1. 最终状态为 n 个 1 , 用区间 [ 1, n ] 表示 。

    [6,3,5,1,2,4],m=1[6, 3,5,1,2,4], m=1

    为例,

    4=>[1,3],[5,6]4 => [ 1, 3], [ 5, 6]


    2=>[1,1],[3,3],[5,6]2 => [1, 1], [3,3], [5,6]

    ReturnReturn


    维护的区间时递增的, 每次可以用二分。 对

    n=105n =10^5

    的复杂度为

    105log(105)=166096410^5*\log(10^5) = 1660964


    PS: 比赛时,觉得一定是这样的。 因为第三题一般都是

    nlog(n)n\log(n)

    , 没想到这次模拟一下就可以了。

class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        if n == m: return n
        A = [[1, n]]
        def bs(A, x):
            if x < A[0][0]:
                return -1
            if x >= A[-1][0]:
                return len(A) -1
            L, R = 0, len(A) -1
            while L < R:
                mid = (L + R) >> 1
                if A[mid][0] <= x:
                    if A[mid + 1][0] <= x:
                        L = mid + 1
                    else:    
                        return mid
                else:    
                    R = mid - 1
            return L         
        cnt = n
        for x in arr[::-1]:
            cnt -= 1
            idx = bs(A, x)
            if idx == -1: 
                return -1
            a, b = A[idx]
            if x - a == m or b - x == m: 
                return cnt
            del A[idx]
            if x+1 <= b:
                A.insert(idx, [x + 1, b])
            if a <= x-1:    
                A.insert(idx, [a, x - 1])
        return -1        
                

解二: 模拟

O(n)O(n)

class Solution:
    def findLatestStep(self, A, m):
        Counter = collections.defaultdict(int)
        n = len(A)
        cnt = [0] * n
        res = -1
        for i, a in enumerate(A):
            a -= 1
            L = cnt[a-1] if a else 0
            R = cnt[a+1] if a + 1 < n else 0
            cnt[a - L] = cnt[a + R] = cnt[a] = L + R + 1
            Counter[L] -= 1
            Counter[R] -= 1
            Counter[cnt[a]] += 1
            if Counter[m]:
                res = i + 1
        return res

P4 石子游戏 V

几块石子 排成一行 ,每块石子都有一个关联值,关联值为整数,由数组 stoneValue 给出。

游戏中的每一轮:Alice 会将这行石子分成两个 非空行(即,左侧行和右侧行);Bob 负责计算每一行的值,即此行中所有石子的值的总和。Bob 会丢弃值最大的行,Alice 的得分为剩下那行的值(每轮累加)。如果两行的值相等,Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时,游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

解一:记忆化搜索。
PS: 用记忆化搜索能过。 但是,直接求是TLE。

O(n3)O(n^3)

的复杂度, 对

n=500n=500

, 应该是过不了的。

class Solution:
    def stoneGameV(self, A: List[int]) -> int:
        C = []
        for x in A:
            if not C:
                C.append(x)
            else:    
                C.append(x + C[-1])
                
        def get(i):
            return 0 if i < 0 else C[i]
        
        n = len(A)
        from functools import lru_cache
        @lru_cache(None)
        def dp(i,j):
            if j ==i: return 0
            ret = 0
            for k in range(i, j):
                left, right = get(k) - get(i-1), get(j) - get(k)
                if right < left:
                    ret = max(ret, right + dp(k + 1, j))
                elif left < right:    
                    ret = max(ret, left + dp(i, k))
                else:    
                    ret = max(ret, right + dp(k+1, j), left + dp(i, k))
            return ret
        
        return dp(0, n-1)

解二:DP + 优化

class Solution:
    def stoneGameV(self, A: List[int]) -> int:
        n = len(A)
        C = self.getRangeCum(A)
        M = self.getmid(A)
        dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]

        for k in range(1, n+1):
            for i in range(n):
                j = i + k - 1
                if j >= n: continue
                mid_L = M[i][j][0]
                mid_R = M[i][j][1]
                if mid_L != -1: dp[i][j][2] = max(dp[i][j][2], dp[i][mid_L][0])
                if mid_R != -1: dp[i][j][2] = max(dp[i][j][2], dp[mid_R][j][1])
                    
                tmp = dp[i][j][2] + C[i][j]
                if i == j:
                    dp[i][j][0] = dp[i][j][1] = tmp
                else:
                    dp[i][j][0] = max(tmp, dp[i][j-1][0])
                    dp[i][j][1] = max(tmp, dp[i+1][j][1])
                
        return dp[0][-1][-1]
    
    def getRangeCum(self, A):
        n = len(A)
        C = [[0]*n for _ in range(n)]
        for L in range(n):
            for R in range(L, n):
                C[L][R] = A[L] if L == R else C[L][R-1] + A[R]
        return C
    
    def getmid(self, A):
        n = len(A)
        C = self.getRangeCum(A)
        M = [[[-1] * 2 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            L = i
            p, R = L, L + 1
            while R < n:
                while C[L][p] <= C[L][R] / 2:
                    p += 1
                if p - 1 >= L:
                    M[L][R][0] = p -1
                    if C[L][p-1] == C[L][R] / 2:
                        M[L][R][1] = p

                if M[L][R][1] == -1 and p+1 <= R:
                    M[L][R][1] = p + 1
                R += 1
        return M
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。