Predict the Winner LT486
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 <= length of the array <= 20.
- Any scores in the given array are non-negative integers and will not exceed 10,000,000.
- If the scores of both players are equal, then player 1 is still the winner.
Idea 1.a backtracking with memory. For the first player to win, the score score1 >= score2 for the second player, while score1 + score2 = sum of all scores in the array, it mean score1 * 2 >= sum. Let dp(a, b) represent the maxmum score of player1 when choosing in the range nums[a, b], based on the observation and -max(-a, -b) = min(a, b), we can get the followig equation:
dp(a, b) = max(sum(a, b) - dp(a+1, b), sum(a, b) - dp(a, b-1))
= max(nums[a] - max(-dp(a+2, b), -dp(a+1, b-1),
nums[b] - max(-dp(a+1, b-1), -dp(a, b-2)))
= max(nums[a] + min(dp(a+2, b), dp(a+1, b-1)),
nums[b] + min(dp(a+1, b-1), dp(a, b-2)))
Time complexity: O(n2)
Space complexity: O(n2)
class Solution {
private int maxScoreForRange(int[] nums, int a, int b, int[][] maxScores) {
if(a > b) {
return 0;
}
if(maxScores[a][b] == 0) {
int scoreA = nums[a] + Math.min(maxScoreForRange(nums, a+2, b, maxScores), maxScoreForRange(nums, a+1, b-1, maxScores));
int scoreB = nums[b] + Math.min(maxScoreForRange(nums, a+1, b-1, maxScores), maxScoreForRange(nums, a, b-2, maxScores));
maxScores[a][b] = Math.max(scoreA, scoreB);
}
return maxScores[a][b];
}
public boolean PredictTheWinner(int[] nums) {
int sum = 0;
for(int num: nums) {
sum += num;
}
int[][] maxScores = new int[nums.length][nums.length];
if(maxScoreForRange(nums, 0, nums.length-1, maxScores) * 2 >= sum) {
return true;
}
return false;
}
}
Idea 1.b, recursion, based on the idea that score1 >= score2, score1 - score2 >= 0, avoid the computation to calculate the sum. We use turn to represent player1 (turn =1 ) and player2(turn = -1), and switch turn based on the player.
Note: the returned value is given by turn * max(turn*b, turn *b), equivalently max(a, b) for player1's turn and min(a, b) for player2's turn.
Time complexity: O(2^n), size of recursion tree is 2^n
Space complexity: O(n) the depth of the recursion tree
class Solution {
private int differenceForRange(int[] nums, int a, int b, int turn) {
if(a > b) {
return 0;
}
int scoreA = turn * nums[a] + differenceForRange(nums, a+1, b, -turn);
int scoreB = turn * nums[b] + differenceForRange(nums, a, b-1, -turn);
return turn * Math.max(turn * scoreA, turn * scoreB);
}
public boolean PredictTheWinner(int[] nums) {
if(differenceForRange(nums, 0, nums.length-1, 1) >= 0) {
return true;
}
return false;
}
}
with variable turn, add the choice when it's player1's turn, subtract the choice when it's player2's turn.
Time complexity: O(2^n)
Space complexity: O(n)
class Solution {
private int differenceForRange(int[] nums, int a, int b) {
if(a > b) {
return 0;
}
int scoreA = nums[a] - differenceForRange(nums, a+1, b);
int scoreB = nums[b] - differenceForRange(nums, a, b-1);
return Math.max(scoreA, scoreB);
}
public boolean PredictTheWinner(int[] nums) {
return differenceForRange(nums, 0, nums.length-1) >= 0;
}
}
Idea 1.c recusion + memory
Time complexity: O(n2)
Space complexity: O(n2)
class Solution {
private int differenceForRange(int[] nums, int a, int b, Integer[][] diffScores) {
if(a > b) {
return 0;
}
if(diffScores[a][b] == null) {
int scoreA = nums[a] - differenceForRange(nums, a+1, b, diffScores);
int scoreB = nums[b] - differenceForRange(nums, a, b-1, diffScores);
diffScores[a][b] = Math.max(scoreA, scoreB);
}
return diffScores[a][b];
}
public boolean PredictTheWinner(int[] nums, Integer[][] diffScores) {
Integer[][] diffScores = new Integer[nums.length][nums.length];
return differenceForRange(nums, 0, nums.length-1, diffScores) >= 0;
}
}
Idea 2. Dynamic programming based on the equation about diffence on score:
dp(a, b) = Math.max(nums[a] - dp(a+1, b), nums[b] - dp(a, b-1))
class Solution {
public boolean PredictTheWinner(int[] nums) {
int[][] scores = new int[nums.length][nums.length];
for(int i = nums.length-1; i >= 0; --i) {
scores[i][i] = nums[i];
for(int len = 2; i + len - 1 < nums.length; ++len) {
int j = i + len - 1;
scores[i][j] = Math.max(nums[i] - scores[i+1][j],
nums[j] - scores[i][j-1]);
}
}
return scores[0][nums.length-1] >= 0;
}
}
Time complexity: O(n2)
Space complexity: O(n2)
Idea 3. Based on the above equation, we can use row instead of matrix by updating from left to right as previous value on the same row is needed and down to up as traversing the hidden matrix via a row.
row(b) = max(nums[a] - row(b_old), nums[b] - row[b-1])
Time complexity: O(n2)
Space complexity: O(n)
class Solution {
public boolean PredictTheWinner(int[] nums) {
int[] row = new int[nums.length];
for(int i = nums.length-1; i >= 0; --i) {
row[i] = nums[i];
for(int len = 2; i + len - 1 < nums.length; ++len) {
int j = i + len - 1;
row[j] = Math.max(nums[i] - row[j],
nums[j] - row[j-1]);
}
}
return row[nums.length-1] >= 0;
}
}
python:
class Solution:
def DiffScoresForRange(self, nums: List[int], a: int, b: int, diffScores) -> int:
if a > b:
return 0 if diffScores[a][b] == None :
scoreA = nums[a] - self.DiffScoresForRange(nums, a+1, b, diffScores)
scoreB = nums[b] - self.DiffScoresForRange(nums, a, b-1, diffScores)
diffScores[a][b] = max(scoreA, scoreB) return diffScores[a][b] def PredictTheWinner(self, nums: List[int]) -> bool:
diffScores = [[None for j in range(len(nums))] for i in range(len(nums))]
return self.DiffScoresForRange(nums, 0, len(nums)-1, diffScores) >= 0
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
diffScores = [[0 for j in range(len(nums))] for i in range(len(nums))] for i in range(len(nums)-1, -1, -1):
diffScores[i][i] = nums[i]
for length in range(2, len(nums)+1-i, 1):
j = i + length - 1
diffScores[i][j] = max(nums[i] - diffScores[i+1][j],
nums[j] - diffScores[i][j-1]) return diffScores[0][len(nums)-1] >= 0
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
row = [0 for i in range(len(nums))] for i in range(len(nums)-1, -1, -1):
row[i] = nums[i]
for length in range(2, len(nums)+1-i, 1):
j = i + length - 1
row[j] = max(nums[i] - row[j],
nums[j] - row[j-1]) return row[len(nums)-1] >= 0
最新文章
- ubuntu下怎么解决python "Non-ASCII character"错误
- window环境下杀死tomcat
- 转： Red Hat/Fedora Linux 上使用 yum 安装 python pip 模块
- 統計分析dbms_stats包与analyze 的区别
- Mesh Baker的基本操作与功能演示
- Pentaho Data Integration笔记 (四)：Kitchen
- EF-CodeFirst-表关系-延迟/贪婪加载
- Linux 常用命令汇总
- 分布式测试工具Beetle.DT的部署并进行HTTP,SQL,TCP压测
- 手把手教你实现boost::bind
- PyMysql的LIKE查询%问题
- day 24 二十四、组合、继承、方法重写和重用、super（）
- 以编程方式使用 Microsoft Office Visio 2003 ActiveX 控件
- 定时自动从FTP服务器取数据脚本
- Install zeal on ubuntu16.04
- 通过echarts的demo
- 20165309 2017-2018-2《Java程序设计》课程总结
- [剑指Offer]39-数组中出现次数超过一半的数字（快排延申，找第k大数同理）
- ssh访问服务器端visdom
- centos 修改时区及NTP时间同步