博弈游戏算法

Algorithm , 评论

leetcode486. 预测赢家

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：[1, 5, 2]
输出：False
解释：一开始，玩家1可以从1和2中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 False 。
示例 2：

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

提示：

1 <= 给定的数组长度 <= 20.
数组里所有分数都为非负数且不会大于 10000000 。
如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

解题思路

1
2
3
4
5
6
7
8
9
class Pairs{
    int first; // 先手
    int second; //  后手

    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

定义一个类first表示先手，second表示后手

1
Pairs[][] dp = new Pairs[n][n];

dp[i][j] 表示 面对nums[i … j] , 两个选手的所能得到的最高分数

则：

dp[i][j].first = max(nums[i] + dp[i+1][j].second, nums[j] + dp[i][j-1].second)

dp[i][j].first = max( 选择最左边的⽯头堆 , 选择最右边的⽯头堆 )

解释：

我作为先⼿， ⾯对 nums[i…j] 时， 有两种选择：

要么我选择最左边的那⼀堆⽯头， 然后⾯对 nums[i+1…j]

但是此时轮到对⽅， 相当于我变成了后⼿；

要么我选择最右边的那⼀堆⽯头， 然后⾯对 nums[i…j-1]

但是此时轮到对⽅， 相当于我变成了后⼿。

此时，如果 先⼿选择左边:

dp[i][j].second = dp[i+1][j].fir

if 先⼿选择右边:

dp[i][j].sec = dp[i][j-1].fir

解释： 我作为后⼿， 要等先⼿先选择， 有两种情况：

如果先⼿选择了最左边那堆， 给我剩下了 piles[i+1…j]

此时轮到我， 我变成了先⼿；

如果先⼿选择了最右边那堆， 给我剩下了 piles[i…j-1]

此时轮到我， 我变成了先⼿。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Pairs{
    int first;
    int second;

    public Pairs(int first, int second) {
        this.first = first;
        this.second = second;
    }
}
class Solution {

    public  boolean PredictTheWinner(int[] nums) {
       int n = nums.length;
       if(n == 1)   return true;

        Pairs[][] dp = new Pairs[n][n];
        for (int i = 0; i < n; i++){
            for(int j = 0; j <n; j++){
                dp[i][j] = new Pairs(0,0);
            }
        }


        // 初始化 base case
        for (int i = 0; i < n; i++) {
            // 只有一堆
            // 先手拿到的分数， 后手肯定为0，
            dp[i][i].first = nums[i];
            dp[i][i].second = 0;
        }
        /// 斜着遍历
        for (int r = 2; r <= n; r++) { //对角线
            for (int i = 0; i < n - r + 1; i++) { // 行控制
                int j = r + i - 1; // 列
                // 选择拿左边的还是右边的
                int left = dp[i+1][j].second + nums[i];
                int right = dp[i][j-1].second+ nums[j];
                if(left > right){
                    // 选择左边
                    dp[i][j].first = left;
                    dp[i][j].second = dp[i+1][j].first;
                }else{
                    dp[i][j].first = right;
                    dp[i][j].second = dp[i][j-1].first;
                }
            }

        }

        return dp[0][n-1].first >=  dp[0][n-1].second;
    }
}

leetcode 877. 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。

示例：

输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。

提示：

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles) 是奇数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一

和上面一样的题目。

解法二

1
2
3
4
5
class Solution {
    public boolean stoneGame(int[] nums) {
         return true;
    }
}

擦…总是会赢。

这是为什么呢， 因为题⽬有两个条件很重要： ⼀是⽯头总共有偶数堆， ⽯头的总数是奇数。 这两个看似增加游戏公平性的条件， 反⽽使该游戏成为了⼀个割⾲菜游戏。 我们以 piles=[2, 1, 9, 5] 讲解， 假设这四堆⽯头从左到右的索引分别是 1， 2， 3， 4。

如果我们把这四堆⽯头按索引的奇偶分为两组， 即第 1、 3 堆和第 2、 4 堆，那么这两组⽯头的数量⼀定不同， 也就是说⼀堆多⼀堆少。 因为⽯头的总数是奇数， 不能被平分。

⽽作为第⼀个拿⽯头的⼈， 你可以控制⾃⼰拿到所有偶数堆， 或者所有的奇数堆。你最开始可以选择第 1 堆或第 4 堆。 如果你想要偶数堆， 你就拿第 4 堆， 这样留给对⼿的选择只有第 1、 3 堆， 他不管怎么拿， 第 2 堆⼜会暴露出来，你就可以拿。

同理， 如果你想拿奇数堆， 你就拿第 1 堆， 留给对⼿的只有第2、 4 堆， 他不管怎么拿， 第 3 堆⼜给你暴露出来了。也就是说， 你可以在第⼀步就观察好， 奇数堆的⽯头总数多， 还是偶数堆的⽯头总数多， 然后步步为营， 就⼀切尽在掌控之中了。

leetcode292. Nim 游戏

这是一道简单题？？？？？？？？？？

你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

递归解法

当没有石子的话，也就意味着最后的石子被对方拿走了，也就是你输了。

当石子数剩下 1, 2, 3 个的时候，你可以一次性都拿走，也就是你赢了。

然后我们考虑所有的情况。

你拿走 1 个石子，然后不论对方从剩下的石子中拿走 1 个，2 个，还是 3 个，判断一下剩下的石子你是不是有稳赢的策略。

如果上边不行的话，你就拿走 2 个石子，然后再判断不论对方从剩下的石子拿走 1 个，2 个，还是3 个，剩下的石子你是不是都有稳赢的策略。

如果上边还不行的话，你就拿走 3 个石子，然后再判断不论对方从剩下的石子拿走 1 个，2 个，还是3 个，剩下的石子你是不是都有稳赢的策略。

如果上边通通不行，那就是你输了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canWinNim(int n) {
        if(n == 0)  return false;

        if( n < 4){
            return true;
        }

        for(int i = 1; i <= 3; i++){
            if(canWinNim(n-1-i) && canWinNim(n-2-i) && canWinNim(n-3-i) ){
                return true;
            }
        }

        return false;
    }
}

超时时间限制

使用备忘录的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    Map<Integer, Boolean> map = new HashMap<>();
    public boolean canWinNim(int n) {
        if(map.containsKey(n)){
            return map.get(n);
        }
        if(n <= 0)  return false;

        if( n < 4){
            return true;
        }

        for(int i = 1; i <= 3; i++){
            if(canWinNim(n-1-i) && canWinNim(n-2-i) && canWinNim(n-3-i) ){
                map.put(n, true);
                return true;
            }
        }
        map.put(n, false);

        return false;
    }
}

Stack Overflow 。。。

数学推导

先说结论：

我们解决这种问题的思路⼀般都是反着思考：

如果我能赢， 那么最后轮到我取⽯⼦的时候必须要剩下 1~3 颗⽯⼦， 这样我才能⼀把拿完。如何营造这样的⼀个局⾯呢？

显然， 如果对⼿拿的时候只剩 4 颗⽯⼦， 那么⽆论他怎么拿， 总会剩下 13 颗⽯⼦， 我就能赢。如何逼迫对⼿⾯对 4 颗⽯⼦呢？ 要想办法， 让我选择的时候还有 57 颗⽯⼦， 这样的话我就有把握让对⽅不得不⾯对 4 颗⽯⼦。

如何营造 57 颗⽯⼦的局⾯呢？ 让对⼿⾯对 8 颗⽯⼦， ⽆论他怎么拿， 都会给我剩下 57 颗， 我就能赢。这样⼀直循环下去， 我们发现只要踩到 4 的倍数， 就落⼊了圈套， 永远逃不出 4 的倍数， ⽽且⼀定会输。 所以这道题的解法⾮常简单：

1
2
3
// 如果上来就踩到 4 的倍数， 那就认输吧
// 否则， 可以把对⽅控制在 4 的倍数， 必胜
return n % 4 != 0;

电灯开关问题

这个问题是这样描述的： 有 n 盏电灯， 最开始时都是关着的。 现在要进⾏ n
轮操作：

第 1 轮操作是把每⼀盏电灯的开关按⼀下（全部打开） 。

第 2 轮操作是把每两盏灯的开关按⼀下（就是按第 2， 4， 6… 盏灯的开关，它们被关闭） 。

第 3 轮操作是把每三盏灯的开关按⼀下（就是按第 3， 6， 9… 盏灯的开关，有的被关闭， ⽐如3， 有的被打开， ⽐如 6） …

如此往复， 直到第 n 轮， 即只按⼀下第 n 盏灯的开关。
现在给你输⼊⼀个正整数 n 代表电灯的个数， 问你经过 n 轮操作后， 这些电灯有多少盏是亮的？

布尔数组统计

使用一个布尔数组去模拟上述操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int isLight(int  n){
       boolean[] flag = new boolean[n+1];

       for(int i = 1; i <= n; i++){
           for(int j = i; j <= n; j+=i){
               flag[j] = !flag[j];
           }
       }

       // 统计
       int count = 0;
       for(int i = 1; i <= n; i++){
           if(flag[i]){
               count++;
           }
       }

       return count;

   }

妙解

1
2
3
public int isLight(int n) {
     return (int)Math.sqrt(n);
}

⾸先， 因为电灯⼀开始都是关闭的， 所以某⼀盏灯最后如果是点亮的， 必然要被按奇数次开关。

我们假设只有 6 盏灯， ⽽且我们只看第 6 盏灯。 需要进⾏ 6 轮操作对吧， 请问对于第 6 盏灯，会被按下⼏次开关呢？ 这不难得出， 第 1 轮会被按， 第 2轮， 第 3 轮， 第 6 轮都会被按。

为什么第 1、 2、 3、 6 轮会被按呢？ 因为 6=16=23 。 ⼀般情况下， 因⼦都是成对出现的， 也就是说开关被按的次数⼀般是偶数次。 但是有特殊情况，⽐如说总共有 16 盏灯， 那么第 16 盏灯会被按⼏次?

16=1*16=2*8=4*4

其中因⼦ 4 重复出现， 所以第 16 盏灯会被按 5 次， 奇数次。 现在你应该理解这个问题为什么和平⽅根有关了吧？不过， 我们不是要算最后有⼏盏灯亮着吗， 这样直接平⽅根⼀下是啥意思
呢？ 稍微思考⼀下就能理解了。

就假设现在总共有 16 盏灯， 我们求 16 的平⽅根， 等于 4， 这就说明最后会有 4 盏灯亮着， 它们分别是第 1*1=1 盏、 第 2*2=4 盏、 第 3*3=9 盏和第4*4=16 盏。

就算有的 n 平⽅根结果是⼩数， 强转成 int 型， 也相当于⼀个最⼤整数上界， ⽐这个上界⼩的所有整数， 平⽅后的索引都是最后亮着的灯的索引。 所以说我们直接把平⽅根转成整数， 就是这个问题的答案。

参考

  1. https://leetcode-cn.com/problems/nim-game/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-54/
  2. https://labuladong.gitbook.io/algo

朱宏梁Research & Develop

后端开发工程师