除数博弈 + 数组拆分+山脉峰值

    科技2022-08-19  107

    除数博弈

    题目:

    爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。 最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:

    选出任一 x,满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作,就会输掉游戏。

    只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏。

    示例

    示例 1: 输入:2 输出:true 解释:爱丽丝选择 1,鲍勃无法进行操作。

    示例 2: 输入:3 输出:false 解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

    分析:

    这道题其实就是一道找规律题,特别简单,当N为2是爱胜,当为3时爱败,当为4时爱胜,当为5时爱败。因此当N为偶数爱胜,当N为奇数爱败。

    代码如下:

    public boolean divisorGame(int N) { return N%2==0; }

    数组拆分

    题目:

    给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

    示例:

    示例 1: 输入: [1,4,3,2] 输出: 4 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

    分析:

    看了好几遍题才明白,min函数就像Math.max(4,5);返回两个值中的最大数一样。首先将数组排序,取偶数位的数字和就是最终答案。

    代码如下:

    public int arrayPairSum(int[] nums) { //排序 Arrays.sort(nums); int max=0; for(int i=0;i<nums.length;i+=2){ max = max + nums[i]; } return max; }

    山脉峰值

    题目

    我们把符合下列属性的数组 A 称作山脉:

    A.length >= 3 存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 给定一个确定为山脉的数组,返回任何满足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

    示例

    示例 1: 输入:[0,1,0] 输出:1

    示例 2: 输入:[0,2,1,0] 输出:1

    分析:

    这道题看了好几遍题都不明白,不理解题的意思,看了题解非常简单。就像我们学的单调函数一样,单调递增和单调递减交界处就是峰值。从左向右搜索只要满足后一项小于前一项都返回。

    代码如下:

    public int peakIndexInMountainArray(int[] A) { int index = 0; while(A[index] < A[index+1]){ index++; } return index; }

    ps:这几道题都非常简单,今天打卡结束!!!!!!!!!!

    Processed: 0.009, SQL: 10