LeetCode - 292 Nim Game
文章目录
问题
思路
提交
TLE
public class Solution {
public boolean canWinNim(int n) {
if (n <= 3) {
return true;
}
boolean canWin1 = true;
boolean canWin2 = true;
boolean canWin3 = true;
for (int i = 4; i <= n; i++) {
boolean t = canWin3;
if (canWin1 && canWin2 && canWin3) {
canWin3 = false;
} else {
canWin3 = true;
}
canWin1 = canWin2;
canWin2 = t;
}
return canWin3;
}
}
O(n) 时间复杂度,直接 TLE 了!好吧,稍微归纳一下实际上很简单 O(1)
public class Solution {
public boolean canWinNim(int n) {
if (n <= 3) {
return true;
}
return n % 4 != 0;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论