同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
一开始,有 n
个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了,则无法操作的玩家输掉游戏。
给你正整数 n
,且已知两个人都采取最优策略。如果 Alice 会赢得比赛,那么返回 True
,否则返回 False
。
示例 1:
输入:n = 1 输出:true 解释:Alice 拿走 1 个石子并赢得胜利,因为 Bob 无法进行任何操作。
示例 2:
输入:n = 2 输出:false 解释:Alice 只能拿走 1 个石子,然后 Bob 拿走最后一个石子并赢得胜利(2 -> 1 -> 0)。
示例 3:
输入:n = 4 输出:true 解释:n 已经是一个平方数,Alice 可以一次全拿掉 4 个石子并赢得胜利(4 -> 0)。
示例 4:
输入:n = 7 输出:false 解释:当 Bob 采取最优策略时,Alice 无法赢得比赛。 如果 Alice 一开始拿走 4 个石子, Bob 会拿走 1 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 3 -> 2 -> 1 -> 0)。 如果 Alice 一开始拿走 1 个石子, Bob 会拿走 4 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 6 -> 2 -> 1 -> 0)。
示例 5:
输入:n = 17 输出:false 解释:如果 Bob 采取最优策略,Alice 无法赢得胜利。
提示:
1 <= n <= 10^5
我们设计一个函数 $dfs(i)$,表示当前石子堆中有 $i$ 个石子时,当前玩家是否能赢得比赛。如果当前玩家能赢得比赛,则返回 $true$,否则返回 $false$。那么答案即为 $dfs(n)$。
函数 $dfs(i)$ 的计算过程如下:
为了避免重复计算,我们可以使用记忆化搜索,即使用数组 $f$ 记录函数 $dfs(i)$ 的计算结果。
时间复杂度 $O(n \times \sqrt{n})$,空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。
class Solution:
def winnerSquareGame(self, n: int) -> bool:
@cache
def dfs(i: int) -> bool:
if i == 0:
return False
j = 1
while j * j <= i:
if not dfs(i - j * j):
return True
j += 1
return False
return dfs(n)
class Solution {
private Boolean[] f;
public boolean winnerSquareGame(int n) {
f = new Boolean[n + 1];
return dfs(n);
}
private boolean dfs(int i) {
if (i <= 0) {
return false;
}
if (f[i] != null) {
return f[i];
}
for (int j = 1; j <= i / j; ++j) {
if (!dfs(i - j * j)) {
return f[i] = true;
}
}
return f[i] = false;
}
}
class Solution {
public:
bool winnerSquareGame(int n) {
int f[n + 1];
memset(f, 0, sizeof(f));
function<bool(int)> dfs = [&](int i) -> bool {
if (i <= 0) {
return false;
}
if (f[i] != 0) {
return f[i] == 1;
}
for (int j = 1; j <= i / j; ++j) {
if (!dfs(i - j * j)) {
f[i] = 1;
return true;
}
}
f[i] = -1;
return false;
};
return dfs(n);
}
};
func winnerSquareGame(n int) bool {
f := make([]int, n+1)
var dfs func(int) bool
dfs = func(i int) bool {
if i <= 0 {
return false
}
if f[i] != 0 {
return f[i] == 1
}
for j := 1; j <= i/j; j++ {
if !dfs(i - j*j) {
f[i] = 1
return true
}
}
f[i] = -1
return false
}
return dfs(n)
}
function winnerSquareGame(n: number): boolean {
const f: number[] = new Array(n + 1).fill(0);
const dfs = (i: number): boolean => {
if (i <= 0) {
return false;
}
if (f[i] !== 0) {
return f[i] === 1;
}
for (let j = 1; j * j <= i; ++j) {
if (!dfs(i - j * j)) {
f[i] = 1;
return true;
}
}
f[i] = -1;
return false;
};
return dfs(n);
}
我们也可以使用动态规划求解本题。
定义数组 $f$,其中 $f[i]$ 表示当前石子堆中有 $i$ 个石子时,当前玩家是否能赢得比赛。如果当前玩家能赢得比赛,则 $f[i]$ 为 $true$,否则为 $false$。那么答案即为 $f[n]$。
我们在 $[1,..n]$ 的范围内枚举 $i$,并在 $[1,..i]$ 的范围内枚举 $j$,其中 $j$ 为平方数,如果当前玩家拿走 $j$ 个石子后,另一个玩家无法赢得比赛,则当前玩家赢得比赛,即 $f[i] = true$。如果枚举完所有的 $j$,都无法满足上述条件,则当前玩家输掉比赛,即 $f[i] = false$。因此我们可以得到状态转移方程:
$$ f[i]= \begin{cases} true, & \text{if } \exists j \in [1,..i], j^2 \leq i \text{ and } f[i-j^2] = false\\ false, & \text{otherwise} \end{cases} $$
最后,我们返回 $f[n]$ 即可。
时间复杂度 $O(n \times \sqrt{n})$,空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。
class Solution:
def winnerSquareGame(self, n: int) -> bool:
f = [False] * (n + 1)
for i in range(1, n + 1):
j = 1
while j <= i // j:
if not f[i - j * j]:
f[i] = True
break
j += 1
return f[n]
class Solution {
public boolean winnerSquareGame(int n) {
boolean[] f = new boolean[n + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i / j; ++j) {
if (!f[i - j * j]) {
f[i] = true;
break;
}
}
}
return f[n];
}
}
class Solution {
public:
bool winnerSquareGame(int n) {
bool f[n + 1];
memset(f, false, sizeof(f));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i / j; ++j) {
if (!f[i - j * j]) {
f[i] = true;
break;
}
}
}
return f[n];
}
};
func winnerSquareGame(n int) bool {
f := make([]bool, n+1)
for i := 1; i <= n; i++ {
for j := 1; j <= i/j; j++ {
if !f[i-j*j] {
f[i] = true
break
}
}
}
return f[n]
}
function winnerSquareGame(n: number): boolean {
const f: boolean[] = new Array(n + 1).fill(false);
for (let i = 1; i <= n; ++i) {
for (let j = 1; j * j <= i; ++j) {
if (!f[i - j * j]) {
f[i] = true;
break;
}
}
}
return f[n];
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。