专栏首页眯眯眼猫头鹰的小树杈leetcode486. Predict the Winner

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.

假设有一个正整数数组,两名玩家轮流从里面取数组,玩家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<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是数组的长度。有的元素出现了一次,而有的元素出现了两次。找到数组中所有出现两次的数字。

    眯眯眼的猫头鹰
  • leetcode-167-Two Sum II-Input array is sorted

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

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

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

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

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

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

    Java学习录
  • 业务逻辑漏洞探索之越权漏洞

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

    漏斗社区
  • 信号与系统领域的英语单词

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

    caoqi95
  • 分布式限流

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

    dys

扫码关注云+社区

领取腾讯云代金券