求和游戏
难度:
标签:
题目描述
代码结果
运行时间: 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必胜。这个结论是怎样得出的?能否详细解释一下奇数个'?'如何影响游戏结果?
▷🦆
题解中提到,如果'?'的总数为偶数时,需要进一步分析。这里的分析依据是什么,为什么选择将一对'?'中一个替换为9,另一个替换为0?
▷🦆
你在题解中使用了(n0 - n1) != (q1 - q0) * 9 // 2来判断Alice是否获胜,这个公式是如何推导出来的?能否详细说明其背后的逻辑和数学原理?
▷