X

LEETCODE 1510. Stone Game IV 解题思路分析

题目大意:

石子游戏 IV

Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。

一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了,则无法操作的玩家输掉游戏。

给你正整数 n ,且已知两个人都采取最优策略。如果 Alice 会赢得比赛,那么返回 True ,否则返回 False 。

示例 1:

输入:n = 1
输出:true
解释:Alice 拿走 1 个石子并赢得胜利,因为 Bob 无法进行任何操作。

示例 2:

输入:n = 2
输出:false
解释:Alice 只能拿走 1 个石子,然后 Bob 拿走最后一个石子并赢得胜利(2 -> 1 -> 0)。

示例 3:

输入:n = 4
输出:true
解释:n 已经是一个平方数,Alice 可以一次全拿掉 4 个石子并赢得胜利(4 -> 0)。

示例 4:

输入:n = 7
输出:false
解释:当 Bob 采取最优策略时,Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子, Bob 会拿走 1 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 3 -> 2 -> 1 -> 0)。
如果 Alice 一开始拿走 1 个石子, Bob 会拿走 4 个石子,然后 Alice 只能拿走 1 个石子,Bob 拿走最后一个石子并赢得胜利(7 -> 6 -> 2 -> 1 -> 0)。

示例 5:

输入:n = 17
输出:false
解释:如果 Bob 采取最优策略,Alice 无法赢得胜利。

提示:

  • 1 <= n <= 10^5

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1510

解题思路分析:

这道题难度并不大,本题是典型的动态规划DP题目(递归加记忆数组方式)。

这种游戏类的题目切记不要真的建立2个角色去模拟比赛过程。而是要站在一个全局的角度,使用一个方法来模拟任意一个人的操作。当前函数的返回值即是当前用户(不论张三还是李四)的结果,函数中做递归调用时,子递归的返回值即是对方结果。

解题时,首先举出所有选择的可能,即小于等于n的所有非零平方数,并将这些数字存入List集合。

接下来的步骤就是基本的递归操作。首先建立递归函数,参数为当前剩余的石子堆数n。函数返回值为当前用户在还剩下n堆石头时是否可以赢得比赛。递归函数中,如果n等于0,代表已没有石子,当前用户输掉比赛,返回false。当n为非0时,我们无法立刻得知拿走几堆石头最好,因此我们需要循环每一种可能来找到最优解,循环List中所有方案,分别尝试拿1堆,4堆,9堆。。。。。如果当前堆数正好等于n,代表当前用户可以直接赢得比赛,返回true。如果当前堆数大于n,由于List中的元素是升序排列,之后的元素也都大于n,因此当前用户已没有选择,在当前情况下一定会输掉比赛,返回false。剩下的为普通情况,即我们还无法一眼看出结果,此时,拿掉当前堆数,剩下n-当前堆数的石子,并将其递归至子问题(递归至对手),如果返回结果是true,代表做出当前选择会使得对方有获胜的机会,我们还需要循环到下一个方案继续尝试。如果返回false,代表当前选择让对方无法获胜,此时直接返回true即可。

另外关于记忆数组,由于本题的递归函数中只有一个变量n,因此我们建立一个一维数组来保存已经计算过的递归结果即可。

实现代码:

    Boolean[] memo; // 记忆数组
    public boolean winnerSquareGame(int n) {
        memo=new Boolean[n+1]; // 初始化记忆数组
        // 保存所有小于等于n的非零数平方
        List<Integer> list = new ArrayList<>();
        int index=1;
        while(index*index<=n){
            list.add(index*index);
            index++;
        }
        // 递归求解,
        // 因为求的是先手用户的结果,因此递归函数的返回值即是结果
        // 如果求后手选手的结果的话,将递归函数返回值取非即可。
        return canWin(n,list);
    }
    // n:当前剩下的石子堆数
    // list:所有选择
    // 返回值:还剩n堆石头时,当前用户是否可以赢得比赛
    boolean canWin(int n, List<Integer> list){
        if(n==0) return false;  // 已没有石头,输
        if(memo[n]!=null) return memo[n]; // 记忆数组中存在当前解,直接返回
        boolean canWin=false; // 当前用户是否可赢得比赛
        for(int i=0;i<list.size();i++){ // 循环每一种选择
            int count=list.get(i); // 当前选择,即选择的石头堆数
            if(count==n){ // 如果堆数等于n,代表可正好拿完所有石头
                canWin=true; // 当前用户获胜
                break;
            }
            if(count>n){ // 如果堆数大于n,那么我们无法拿取石头,当前用户输
                canWin=false; // 当前用户输
                break;
            } 
            // 拿了当前堆数的石头,递归至对手
            // 如果对手无法获胜
            if(!canWin(n-count,list)){
                canWin=true; // 则当前用户获胜
                break;
            }
        }
        memo[n]=canWin; // 将结果记录到记忆数组
        return canWin; // 返回当前用户是否获胜
    }

本题解法执行时间为89ms。

Runtime: 89 ms, faster than 100.00% of Java online submissions for Stone Game IV.

Memory Usage: 47.1 MB, less than 100.00% of Java online submissions for Stone Game IV.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1510-stone-game-iv-解题思路分析/
Categories: leetcode
kwantong: