leetcode486. Predict the Winner

王軍發布于2019-08-19 10:25 / 493人閱讀

摘要：但是，往往會有可以優化的空間。假設我們用來記錄子數組之間，第一個取數字的玩家和第二個取數字的玩家之間最大的差距。再考慮初始情況，即當數組長度為時，可以得知此時玩家一和玩家二之間的差距即為該數組元素的值。

題目要求

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1. 1 <= length of the array <= 20.
2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
3. If the scores of both players are equal, then player 1 is still the winner.

假設有一個正整數數組，兩名玩家輪流從里面取數組，玩家1先取，玩家2后取，要求判斷出玩家1是否一定能夠取勝？

思路和代碼

看到這種題目的時候，會直觀的想到，如果我能夠暴力的遍歷出玩家1和玩家2之間所有的取數字的方式，就一定可以算出玩家1是否能夠取勝。但是，往往會有可以優化的空間。假設我們用diffi來記錄子數組i~j之間，第一個取數字的玩家和第二個取數字的玩家之間最大的差距。則 diffi = Math.max(nums[i]-diffi+1, nums[j+1]-diffi), 即從左取第一個數字或是從右取第一個數字能夠獲得的最大差距。再考慮初始情況，即當數組長度為1時，可以得知此時玩家一和玩家二之間的差距即為該數組元素的值。代碼如下：

    public boolean PredictTheWinner(int[] nums) {
        int[][] diff = new int[nums.length][nums.length];
        for(int i = 0 ; i= 0;
    }

GPU云服務器云服務器 Winner Predict the Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75989.html

486. Predict the Winner

486. Predict the Winner 題目鏈接：https://leetcode.com/problems... 看了discussion里面參考的mit算法視頻：https://www.youtube.com/watch... recursion + memo 或者 iteration用dp table public class Solution { public boolea...

jubincn 2019-08-14 17:26 評論0 收藏0
Leetcode 相似題只有題號不含代碼。

找出string里的單詞。 186. Reverse Words in a String II, 434. Number of Segments in a String combination類型題 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 評論0 收藏0
[Leetcode] Nim Game 尼姆游戲

摘要：腦筋急轉彎復雜度時間空間思路這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數，你就輸了，因為對方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 評論0 收藏0