資訊專欄INFORMATION COLUMN
摘要：但是，往往會(huì)有可以優(yōu)化的空間。假設(shè)我們用來記錄子數(shù)組之間，第一個(gè)取數(shù)字的玩家和第二個(gè)取數(shù)字的玩家之間最大的差距。再考慮初始情況，即當(dāng)數(shù)組長(zhǎng)度為時(shí)，可以得知此時(shí)玩家一和玩家二之間的差距即為該數(shù)組元素的值。
題目要求
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.
假設(shè)有一個(gè)正整數(shù)數(shù)組，兩名玩家輪流從里面取數(shù)組，玩家1先取，玩家2后取，要求判斷出玩家1是否一定能夠取勝？
思路和代碼看到這種題目的時(shí)候，會(huì)直觀的想到，如果我能夠暴力的遍歷出玩家1和玩家2之間所有的取數(shù)字的方式，就一定可以算出玩家1是否能夠取勝。但是，往往會(huì)有可以優(yōu)化的空間。假設(shè)我們用diffi來記錄子數(shù)組i~j之間，第一個(gè)取數(shù)字的玩家和第二個(gè)取數(shù)字的玩家之間最大的差距。則 diffi = Math.max(nums[i]-diffi+1, nums[j+1]-diffi), 即從左取第一個(gè)數(shù)字或是從右取第一個(gè)數(shù)字能夠獲得的最大差距。再考慮初始情況，即當(dāng)數(shù)組長(zhǎng)度為1時(shí)，可以得知此時(shí)玩家一和玩家二之間的差距即為該數(shù)組元素的值。代碼如下：
public boolean PredictTheWinner(int[] nums) {
int[][] diff = new int[nums.length][nums.length];
for(int i = 0 ; i= 0;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75989.html
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...
找出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...
摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時(shí)間空間思路這題往小說可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...
閱讀 2498·2021-08-11 11:16
閱讀 2938·2019-08-30 15:55
閱讀 3337·2019-08-30 12:53
閱讀 1578·2019-08-29 13:28
閱讀 3271·2019-08-28 18:17
閱讀 944·2019-08-26 12:19
閱讀 2475·2019-08-23 18:27
閱讀 712·2019-08-23 18:17
