leetcode
leetcode 1701 ~ 1750
求和游戏

求和游戏

难度:

标签:

题目描述

代码结果

运行时间: 84 ms, 内存: 16.9 MB


// 思路:
// 1. 将字符串的前后两部分分开。
// 2. 使用流处理前后两部分的和,统计问号的数量。
// 3. 使用流判断是否存在使和相等的情况。

import java.util.stream.IntStream;

public class GameSolutionStream {
    public boolean isAliceWinning(String num) {
        int n = num.length();
        int half = n / 2;

        int leftSum = IntStream.range(0, half)
                .filter(i -> num.charAt(i) != '?')
                .map(i -> num.charAt(i) - '0')
                .sum();

        int rightSum = IntStream.range(half, n)
                .filter(i -> num.charAt(i) != '?')
                .map(i -> num.charAt(i) - '0')
                .sum();

        long leftQuestionMarks = IntStream.range(0, half)
                .filter(i -> num.charAt(i) == '?')
                .count();

        long rightQuestionMarks = IntStream.range(half, n)
                .filter(i -> num.charAt(i) == '?')
                .count();

        int diff = leftSum - rightSum;
        int qDiff = (int) ((rightQuestionMarks - leftQuestionMarks) * 9);

        return diff != qDiff;
    }
}

解释

方法:

此题解采用的是贪心算法的思路。首先,通过遍历字符串的前半部分和后半部分,分别统计两部分中数字的总和以及'?'的数量。然后,根据这些统计结果,分析Alice和Bob的最优策略。如果'?'的总数为奇数,那么无论如何都不可能使得前后两部分的和相等,因此Alice获胜。如果'?'的总数为偶数,那么我们需要进一步分析。考虑到Alice和Bob都会尽可能地使自己获胜,我们可以假设每一对'?'中,一个会被替换为9,另一个会被替换为0,这样对总和的影响最大。因此,我们可以通过比较n0-n1与(q1-q0)*9/2的关系来判断胜负。如果二者相等,那么Bob可以获胜,否则Alice获胜。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在题解中你提到如果'?'的总数为奇数,Alice必胜。这个结论是怎样得出的?能否详细解释一下奇数个'?'如何影响游戏结果?
当'?'的总数为奇数时,Alice必胜的结论主要基于游戏的对称性和替换策略。在游戏中,每个'?'可以被替换成0至9中的任意一个数字。如果'?'的总数为奇数,由于Alice和Bob轮流替换'?',最终会剩下一个'?'由Alice替换。Alice有机会选择一个对自己最有利的数字来确保两侧的总和不相等,从而获胜。无论前面的替换如何进行,Alice都能通过调整这最后一个'?'的值来控制游戏结果,确保自己处于有利位置。
🦆
题解中提到,如果'?'的总数为偶数时,需要进一步分析。这里的分析依据是什么,为什么选择将一对'?'中一个替换为9,另一个替换为0?
如果'?'的总数为偶数,Alice和Bob将轮流替换所有的'?',最终不会剩下任何'?'。在这种情况下,为了最大化对总和的影响,我们假设每一对'?'中,一个被替换为9,另一个被替换为0。这种替换策略是因为9和0的差距最大,可以最大化或最小化两部分的和的差异。这种极端替换策略可以让我们计算在最不利情况下(即对手尝试平衡总分时)Alice和Bob各自能达到的最大和最小总和差异。这样的分析帮助判断在最极端情况下游戏的可能结果。
🦆
你在题解中使用了(n0 - n1) != (q1 - q0) * 9 // 2来判断Alice是否获胜,这个公式是如何推导出来的?能否详细说明其背后的逻辑和数学原理?
公式(n0 - n1) != (q1 - q0) * 9 // 2的逻辑基于假设Alice和Bob都以最优策略替换'?',即一方试图增加总和,另一方试图减少总和。这里n0和n1分别表示字符串前半部和后半部的数字总和,q0和q1分别表示前半部和后半部的'?'数量。当Alice和Bob替换'?'时,他们可以选择替换为0或9来最大化差异。如果所有的'?'均被替换为9和0,则总和的最大可能变化是(q1 - q0) * 9。然而,由于Alice和Bob交替替换,实际上每一对替换可以使总和差异改变18(一个+9,一个-9)。因此,总的可能变化是(q1 - q0) * 9 / 2。如果n0和n1之间的差与这个最大可能变化不匹配,则表示无法通过替换'?'达到平衡,因此Alice获胜。

相关问题