LCP 49-环形闯关游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

「力扣挑战赛」中有一个由 N 个关卡组成的环形闯关游戏，关卡编号为 0~`N-1，编号 0的关卡和编号N-1 的关卡相邻。每个关卡均有积分要求，challenge[i]表示挑战编号i的关卡最少需要拥有的积分。 ![图片.png](https://pic.leetcode- cn.com/1630392170-ucncVS-%E5%9B%BE%E7%89%87.png){:width="240px"} 小扣想要挑战关卡，闯关具体规则如下： \- 初始小扣可以指定其中一个关卡为「开启」状态，其余关卡将处于「未开启」状态。 \- 小扣可以挑战处于「开启」状态且**满足最少积分要求**的关卡，若小扣挑战该关卡前积分为score，挑战结束后，积分将增长为 score|challenge[i]（即位运算中的 “OR” 运算） \- 在挑战某个关卡后，该关卡两侧相邻的关卡将会开启（若之前未开启） 请帮助小扣进行计算，初始最少需要多少积分，可以挑战 **环形闯关游戏** 的所有关卡。 **示例1：** > 输入：challenge =
[5,4,6,2,7] > > 输出：4 > > 解释： 初始选择编号 3 的关卡开启，积分为 4 >挑战编号 3 的关卡，积分变为 4 | 2 = 6，开启 2、4 处的关卡 >挑战编号 2 的关卡，积分变为 6 | 6 = 6，开启 1 处的关卡 >挑战编号 1 的关卡，积分变为 6 | 4 = 6，开启 0 处的关卡 >挑战编号 0 的关卡，积分变为 6 | 5 = 7 >挑战编号 4 的关卡，顺利完成全部的关卡 **示例2：** > 输入：challenge = [12,7,11,3,9] > > 输出：8` > > 解释： 初始选择编号 3 的关卡开启，积分为 8 >挑战编号 3
的关卡，积分变为 8 | 3 = 11，开启 2、4 处的关卡 >挑战编号 2 的关卡，积分变为 11 | 11 = 11，开启 1 处的关卡

挑战编号 4 的关卡，积分变为 11 | 9 = 11，开启 0 处的关卡 >挑战编号 1 的关卡，积分变为 11 | 7 = 15 >挑战编号
0 的关卡，顺利完成全部的关卡 示例3： > 输入：challenge = [1,1,1] > > 输出：1 提示： - 1 <= challenge.length <= 5*10^4 - 1 <= challenge[i] <= 10^14

看完这道题目的描述，我注意到这几个关键点：
1、如果拿关卡挑战积分的最大值作为初始积分a，一定能完成所有挑战。
2、在关卡的挑战过程中，积分变化是二进制位或操作，在挑战过程中，初始积分的某些为0的二进制位会被补成1。
3、题目的目的是要找最小初始积分，那么我们可以尝试改变m的某些二进制位，最小化成b。

为了实现思路3，我发现：
1、a、b，在二进制表示时，从高到低位，第一位不同必然是a为1，b为0
2、而a表示为二进制1xxxxx中最高位的1是必须的，因为挑战过程中，积分在没有这个1的时候，无法挑战（小于）含有这个1的关卡，永远得不到这个1；
3、继续找下一个1，判断这个1是否可以不要？正好 x..x1y..y > x..x01..1（且这是前面部分x..x确定时，剩下最高二进制位为0，最大可能能完成所有挑战的初始积分），如果x..x01..1不能完成完成所有关卡，那么这个位需要为1，否则可以为0
4、不断进行3的操作，就能最终找到答案。

有了算法，当然需求考虑一下时间复杂度:
算法步骤3，直接暴力判断（用x..x01..1作为初始积分，分别试用每一个关卡作为起点，向两边扩展），复杂度是O(n^2)
算法步骤4，最多就是60次（2^(6*10) > 10^18)

所以步骤3需要优化，想到两个突破口：
1、从一个关卡作为起点，扩展经过的点都可以不必再尝试作为起点；
2、从不同起点向左向右扩展时，很多时候的计算是重复的，可以提前预处理，在尝试答案前，计算出以某个关卡为起点（也以它的挑战分为初始分），单纯向左或向右能扩展多远。这一步预处理时间是O(n)，能节约步骤3、4里大量计算。
（其它题解有最坏情况算法复杂度更低的思路，我这里不赘述了。不过有意思的是，跑实际数据，仅用优化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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
    def ringGame(self, challenge: List[int]) -> int:
        def check(m) :
            i = n
            while i < n+n :
                # 尝试以关卡i为起点
                if challenge[i] > m :
                    i += 1
                    continue

                s, l, r = m|score_left[i]|score_right[i], idx_left[i], idx_right[i]
                while True :
                    if r-l > n : return True # 已挑战完所以关卡
                    # 向两边挑战关卡，并更新积分
                    if challenge[l] <= s :
                        s |= score_left[l]
                        l = idx_left[l]
                    if challenge[r] <= s :
                        s |= score_right[r]
                        r = idx_right[r]
                    else : break
                i = r # 扩展经过的点都可以不必再尝试作为起点；

            return False

        n = len(challenge)
        challenge = challenge * 3 # 模拟成环
        n3 = n*3

        # 预计算出以某个关卡为起点（也以它的挑战分为初始分），单纯向左或向右能扩展多远和扩展后的积分
        score_left, idx_left = [0]*n3, [0]*n3
        for i in range(n3) :
            score_left[i] = challenge[i]
            j = i-1
            while j >= 0 and challenge[j] <= score_left[i] :
                score_left[i] |= score_left[j]
                j = idx_left[j]
            idx_left[i] = j

        score_right, idx_right = [0]*n3, [0]*n3
        for i in range(n3-1, -1, -1) :
            score_right[i] = challenge[i]
            j = i+1
            while j < n3 and challenge[j] <= score_left[i] :
                score_right[i] |= score_right[j]
                j = idx_right[j]
            idx_right[i] = j

        # 从高到低确定答案的二进制位
        bit = 1 << (max(challenge).bit_length()-1)
        res = bit
        while bit :
            bit >>= 1
            if not check(res | (bit-1)) : res |= bit

        return res
 Comments
On this page
LCP 49-环形闯关游戏