- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/divisor-game/
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there is a number N
on the chalkboard. On each player's turn, that player makes a move consisting of:
1、 Choosinganyx
with0<x<N
andN%x==0
.;
2、 ReplacingthenumberNonthechalkboardwithN-x
.;
Also, if a player cannot make a move, they lose the game.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example 1:
Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Example 2:
Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
Note:
对于数字N,做两个操作:1. 找出一个因数x,2. 把N换成N - x。两个人轮流做这个操作,问第一个人是否能赢。
首先说结论:当N是偶数时第一个人一定赢,当N是奇数时第一个一定输。
1、 奇数的因子只有奇数,偶数的因子至少一个偶数2;
2、 奇数-奇数=偶数;
3、 当Alice的值是N时必输,则当Alice的值是N+1时必赢(拿1即可);
那么,当N为下列数字时,先发的状态如下。 当N=1,输; 当N=2,赢(性质3); 当N=3,输(性质1和2,对方一定是偶数,上面的偶数情况都赢); 当N=4,赢(性质3); 当N=5,输(性质1和2,对方一定是偶数,上面的偶数情况都赢); ... 所以,N为偶数都赢,N为奇数都输。
C++代码如下:
class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};
1 2 3 4 5 6
动态规划就是很朴素的做法了,对每个位置i,遍历其因数x,判断N-x的状态,当N-x为输的时候自己赢。
C++代码如下:
class Solution {
public:
bool divisorGame(int N) {
if (N == 1) return false;
if (N == 2) return true;
vector<bool> dp(N, false);
dp[1] = true;
for (int i = 3; i <= N; ++i) {
for (int j = 1; j < i; ++j) {
if (i % j == 0 && !dp[i - j - 1]) {
dp[i - 1] = true;
break;
}
}
}
return dp[N - 1];
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
参考资料:https://leetcode.com/problems/divisor-game/discuss/368269/C%2B%2B-100-and-96-and
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
题目地址:https://leetcode.com/problems/divisor-game/ 题目描述 Alice and Bob take turns playing a game, wit
以下关系仅适用于两个 (3, 12) 数字,当用于三个数字 (3,12,10) 时无法产生正确答案。只是想知道这是我的理解还是仅适用于两个数字,对我来说欧几里得算法也是如此。 LCM(a, b) =
我想知道,如何在运行代码后将显示的除数相加? #include #include int main() { int n, i; scanf("%d", &n); for(i
我的问题是: Print all numbers from low to high. If any number being printed is divisible by any divisor n
我正在 MathBlog 上阅读 Project Euler Problem 12 的解决方案,但在理解代码背后的逻辑时遇到了一些困难。该程序使用素因数分解来查找三角形数的因数数。 private i
当给定一个整数 n 时,打印出 n 以内的所有正数和 4 个正约数。 示例: 10 --> 6 8 10 16 --> 6 8 10 14 15 我的代码 public class ass5_q1
所以我尝试找出这个问题的解决方案,但我的程序表现得很奇怪。 #include using namespace std; int triangle_numbers(int n, int meh = 0
由于减法中的浮点错误,在以下情况下是否可以被零除? float x, y, z; ... if (y != 1.0) z = x / (y - 1.0); 换句话说,下面是不是更安全一些? f
我正在oracle 10g下创建一个SQL查询,结果应该给我类似的东西: ---------------------------------------------------------------
当涉及非常大的数字时,我的代码非常慢。 def divisors(num): divs = 1 if num == 1: return 1 for i in r
我是一名优秀的程序员,十分优秀!