class Solution {
public:
bool winnerSquareGame(int n) {
}
};
1510. 石子游戏 IV
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原站题解
php 解法, 执行用时: 168 ms, 内存消耗: 22.6 MB, 提交时间: 2023-08-18 14:32:29
class Solution {
/**
* @param Integer $n
* @return Boolean
*/
function winnerSquareGame($n) {
$f = array_fill(0, $n+1, false);
for ( $i = 1; $i <= $n; $i++ ) {
for ( $k = 1; $k * $k <= $i; $k++ ) {
if ( !$f[$i - $k*$k] ) {
$f[$i] = true;
break;
}
}
}
return $f[$n];
}
}
cpp 解法, 执行用时: 60 ms, 内存消耗: 7.6 MB, 提交时间: 2023-08-18 14:30:49
class Solution {
public:
bool winnerSquareGame(int n) {
vector<int> f(n + 1);
for (int i = 1; i <= n; ++i) {
for (int k = 1; k * k <= i; ++k) {
if (!f[i - k * k]) {
f[i] = true;
break;
}
}
}
return f[n];
}
};
java 解法, 执行用时: 13 ms, 内存消耗: 38.6 MB, 提交时间: 2023-08-18 14:30:17
class Solution {
public boolean winnerSquareGame(int n) {
boolean[] f = new boolean[n + 1];
for (int i = 1; i <= n; ++i) {
for (int k = 1; k * k <= i; ++k) {
if (!f[i - k * k]) {
f[i] = true;
break;
}
}
}
return f[n];
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 2.2 MB, 提交时间: 2023-08-18 14:29:44
func winnerSquareGame(n int) bool {
f := make([]bool, n+1)
for i := 1; i < n+1; i++ {
k := 1
for k * k <= i {
if !f[i - k*k] {
f[i] = true
break
}
k++
}
}
return f[n]
}
python3 解法, 执行用时: 988 ms, 内存消耗: 16.9 MB, 提交时间: 2023-08-18 14:27:49
'''
我们用 f[i] 表示先手在面对 i 颗石子时是否处于必胜态（会赢得比赛）。
由于先手和后手都采取最优策略，那么 f[i] 为必胜态，当且仅当存在某个 f[i - k^2] 为必败态。
也就是说，当先手在面对 i 颗石子时，可以选择取走 k^2 颗，
剩余的 i-k^2 颗对于后手来说是必败态，因此先手会获胜。
f[0] = false, 没有石子，先手必败。
'''
class Solution:
def winnerSquareGame(self, n: int) -> bool:
f = [False] * (n+1)
for i in range(1, n+1):
k = 1
while k * k <= i:
if f[i - k * k] == False:
f[i] = True
break
k += 1
return f[n]