LeetCode 1025. Divisor Game
2024-09-03 08:29:17
题目链接：https://leetcode.com/problems/divisor-game/
题意：Alice和Bob玩一个游戏，Alice先开始。最初，黑板上有一个数字N。每一轮，选手首先需要选择一个数x（0<x<N且N%x==0），并将黑板上的数字N替换成N-x。如果哪个选手无法继续操作，则意味着输掉了游戏。如果Alice赢了返回true。
分析：
（1）先从最简单的case入手。N=1，Alice必败；N=2，Alice只能选择1，则Bob必败，Alice必胜；N=3，Alice只能选择1，则Bob必胜，Alice必败；N=4，Alice可以选择1，也可以选择2，Alice选择1，则Bob必败Alice必胜，Alice选择2，则Bob必胜Alice必败，因此，Alice一定会选择1，因此Alice胜。
（2）由此可推出结论，当Alice面对数字N时，她所需要选择的数字x必须使得Bob在处理N-x时必败，她才可能获胜。因此，如果Alice所有可以选择的x都使得Bob在处理N-x时必胜，那么Alice必败；只要Alice所有可以选择的x中有一种情况能使Bob在处理N-x时必败，那Alice都是必胜的。
class Solution {
public:
bool divisorGame(int N) {
int dp[1010];
dp[1] = 0;
for(int i = 2; i <= N; ++i){
dp[i] = 0;
for(int j = 1; j < i; ++j){
if(i % j == 0){
if(dp[i - j] == 0){
dp[i] = 1;
break;
}
}
}
}
if(dp[N]) return true;
return false;
}
};
最新文章
- softwareTesting_work2_question2
- SDK截图（四）：压缩位图实例
- 【代码笔记】iOS-将图片处理成圆的
- SQL Server 2014里的IO资源调控器
- Warning: Permanently added '...' (RSA) to the list of known hosts --Windows下git bash 警告处理
- hadoop拾遗（一）---- 避免切分map文件
- 高可用开源方案 Keepalived VS Heartbeat对比
- Java对象嵌套
- Beta版本冲刺计划安排
- 201521123013 《Java程序设计》第8周学习总结
- MySQL Connector 卸载
- kernel笔记——进程调度
- apt-get软件包管理命令 和 apt-key命令
- 小甲鱼Python第二十一讲课后习题
- 运用Python计算Π的多少（大致计算）
- python系统编程（五）
- 【转】WPF Template模版之DataTemplate与ControlTemplate（一）
- js控制css时注意
- python两个字典合并，两个list合并
- 页面显示This is the initial start page for the WebDriver server.的解决办法