LeetCode-预测赢家(每日一题)

题目描述

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

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

示例 1：

1 2	输入：[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 2	输入：[1, 5, 233, 7] 输出：True

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

解法

1. 递归法

思路：我们可以选择左边或者右边的元素，这样选择完之后就相当于是一个同样的子问题了。重点是递归的终止条件和应该返回什么。

当数组大小为1时，没有选择了，此时递归终止。

返回的应该是a与b相差的金额，即选择两个结果中的最大值进行返回(让a拿的多)。

最终判断得到的值是否大于0.

递归需要关系的是当前函数应该返回什么以及终止条件，而不是重复的思考整个拿取的过程🚗

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        if (nums == null) return false;
        int left = 0, right = nums.length - 1;
        int ans = isWin(nums, left, right);
        return ans >= 0;
    }

    private int isWin(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        // 选择左边
        int leftAns = nums[left] - isWin(nums, left + 1, right);
        // 选择右边
        int rightAns = nums[right] - isWin(nums, left, right - 1);

        return Math.max(leftAns, rightAns);
    }
}

时间复杂度为$O(2^n)$ 每个值的选择有两种情况
空间复杂度为$O(n)$ 递归栈空间为数组大小

2. 记忆化递归

思路：例如a拿7 b拿1和a拿1 b拿7剩下的都是5和233，可以用一个数组或者哈希表来存储结果，如果遇到相同的就不需要进行重复运算了。

class Solution {
    // flag[i][j]表示左端为i, 右端为j时，a赢得分数
    int[][] flag;

    public boolean PredictTheWinner(int[] nums) {
        if (nums == null) return false;
        int len = nums.length;
        flag = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                flag[i][j] = -1;
            }
        }
        int left = 0, right = len - 1;
        int ans = isWin(nums, left, right);
        return ans >= 0;
    }

    private int isWin(int[] nums, int left, int right) {
        if (flag[left][right] != -1) return flag[left][right];
        if (left == right) {
            flag[left][right] = nums[left];
            return flag[left][right];
        }
        int leftAns = nums[left] - isWin(nums, left + 1, right);
        int rightAns = nums[right] - isWin(nums, left, right - 1);
        flag[left][right] = Math.max(leftAns, rightAns);
        return flag[left][right];
    }
}

时间复杂度为$O(2^n)$ 每个值的选择有两种情况
空间复杂度为$O(n^2)$ 使用额外的二维数组保存数据

3. 动态规划

思路：又迎来了老生常谈的动态规划😂，还是要多去体会动态规划的思想才能更好的掌握啊。其实想明白了递归的思路就大概清楚动态规划应该怎么写了。

状态划分：a在n大小的数组赢得的分数可以由子问题n-1大小数组结果得来。
状态确定：$dp[i][j]$表示在左端为i，右端为j时的数组中a与b相差的分数。
状态转移：$dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])$
确定边界：$i == j$ $dp[i][j] = nums[i]$

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        if (nums == null) return false;
        int len = nums.length;
        int[][] dp = new int[len][len];
        // 边界条件
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == j) dp[i][j] = nums[i];
            }
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][len - 1] >= 0;
    }
}