leetcode486. Predict the Winner

题目要求

```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.```

思路和代码

```    public boolean PredictTheWinner(int[] nums) {
int[][] diff = new int[nums.length][nums.length];
for(int i = 0 ; i<nums.length ; i++){
diff[i][i] = nums[i];
}
for(int len = 1 ; len < nums.length ; len++) {
for(int i = 0; i+len < nums.length ; i++) {
diff[i][i+len] = Math.max(nums[i] - diff[i+1][i+len], nums[i+len] - diff[i][i+len-1]);
}
}
return diff[0][nums.length-1] >= 0;
}```

0 条评论

• leetcode480. Sliding Window Median

Median is the middle value in an ordered integer list. If the size of the list i...

• leetcode448. Find All Numbers Disappeared in an Array

假设一个长度为n的整数数组，数组中的元素的值位于[1,n]区间中。问，该数组中有哪些[1,n]区间中的整数没有出现？

• leetcode442. Find All Duplicates in an Array

存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。

• windows 7以上操作系统文件共享

windows 7以上操作系统文件共享后，通过其它计算机无法访问共享，需要对windows防火墙做相关设置才行，简单只需要如下三步：

• 吐槽版︱MRO-Microsoft R Open快捷键+界面识别+功能设置

因为用的是中文界面，发现翻译还是有点误差的。一般“交互执行”才能run出来。点击是可以的，但是快捷键在哪呢？

• 大型网站限流算法的实现和改造

计数器算法的意思呢就是当接口在一个时间单位中被访问时，我就记下来访问次数，直到它访问的次数到达上限。

• 业务逻辑漏洞探索之越权漏洞

越权，顾名思义，就是超出了权限或权力范围。多数WEB应用都具备权限划分和控制，但是如果权限控制功能设计存在缺陷，那么攻击者就可以通过这些缺陷来访问未经授权的功能...

• 信号与系统领域的英语单词

这是去年暑假帮老师给下一届学弟学妹们整理的一份英文单词表，因为在上数字信号处理这门课时，我们所有的讲义和教材都是英文的，老师希望整理出来给学生们记忆。而我 9 ...

• 分布式限流

在单机系统中，限流逻辑直接放在服务接口中即可，Guava RateLimiter 可以方便的实现。