前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它

2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它

作者头像
福大大架构师每日一题
发布2022-06-04 10:44:34
4250
发布2022-06-04 10:44:34
举报

2022-05-03:Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。

如果玩家移除石子后,导致 所有已移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏 。

如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false 。

输入:stones = [2,1]。

输出:true。

解释:游戏进行如下:

- 回合 1:Alice 可以移除任意一个石子。

- 回合 2:Bob 移除剩下的石子。

已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此,Bob 输,Alice 获胜。

力扣2029. 石子游戏 IX。

答案2022-05-03:

这道题很难想到,直接记住结论。

偶0只有1:b赢。偶0只有2:b赢。

偶0有1有2:a赢。

奇0:1和2差的绝对值大于2,a赢;否则b赢。

代码用rust编写。代码如下:

代码语言:javascript
复制
fn main() {
    let mut arr: Vec<isize> = vec![1, 2, 3, 3, 3, 10, 10, 10, 100, 100, 100];
    let ans = stone_game_ix(&mut arr);
    println!("ans = {}", ans);
}

fn stone_game_ix(stones: &mut Vec<isize>) -> bool {
    let mut counts: Vec<isize> = vec![0, 0, 0];
    for i in 0..stones.len() {
        counts[(stones[i as usize] % 3) as usize] += 1;
    }
    if counts[0] % 2 == 0 {
        counts[1] != 0 && counts[2] != 0
    } else {
        counts[1] - counts[2] > 2 || counts[2] - counts[1] > 2
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_3_week/Code05_StoneGameIX.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档