算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 预测赢家，我们先来看题面：https:///problems/predict-the-winner/You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。示例 示例 1：
输入：nums = [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：
输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。 解题用DP[I][J]表示，作为先手，数组的起止坐标为I和J，自己获得的积分和对手获取积分差值的最大值。有状态转移方程：DP[I][J] = MAX{NUMS[I]-DP[I+1][J], NUMS[J]-DP[I][J-1]}，用动态规划的方式来解决这道题目。/**
* @Date: 2022/01/01/8:15
* @Description:
*/
// [1,5,233,7] 并不是拿最大的就好。比如我先拿1，你不管拿哪个，我都会拿到233，否则我拿到7，你就会拿到233.
// 预测1号玩家 能不能赢。
// 两人每次都从一端 取一个数。
// 你可以假设每个玩家的玩法都会使他的分数最大化。
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.PredictTheWinner(new int[]{1, 5, 2}));
}
public boolean PredictTheWinner(int[] nums) {
if (nums == null || nums.length == 0) return true;
// 至少有一个元素。用动态规划的方法。
// dp[i][j] = max{nums[i]-dp[i+1][j], nums[j]-dp[i][j-1]}
int[] arr = new int[nums.length];
for (int i = 1; i <= nums.length; i++) {
arr[arr.length-i] = nums[nums.length-i]; // 赋值，对角线上的。
for (int j = arr.length-i+1; j < nums.length ; j++) {
arr[j] = Math.max(nums[nums.length-i]-arr[j],nums[j]-arr[j-1]);
}
}
return arr[nums.length-1]>=0;
}
}好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
|
