【每日一题Day88】LC2293极大极小游戏 | 模拟 递归

简介: 思路:数组中的元素被使用过就不再被使用,因此可以将第i ii对计算得到的结果,存储至nums[i]

极大极小游戏【LC2293】


You are given a 0-indexed integer array nums whose length is a power of 2.


Apply the following algorithm on nums:


1.Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.


2.For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).


3.For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).


4.Replace the array nums with newNums.


5.Repeat the entire process starting from step 1.


Return the last number that remains in nums after applying the algorithm.


小年快乐~ 周赛在周六周日永远搞不清 周赛在周日周赛在周日周赛在周日


队列


  • 思路:使用队列存放需要迭代的数组元素,并记录下标序号i,根据下标奇偶性取最大值最小值,每处理一组元素,序号加1,直至队列中只存在一个元素,返回即可。


。由于数组长度均为2 n  ,迭代过程中长度一直为偶数直至长度为1,因此下标序号可以累计


  • 实现


class Solution {
    public int minMaxGame(int[] nums) {
        Deque<Integer> deque = new LinkedList<>();
        for (int num : nums){
            deque.addLast(num);
        }
        int i = 0;
        while (deque.size() > 1){
            if ((i & 1) == 0){
                deque.addLast(Math.min(deque.pollFirst(),deque.pollFirst()));
            }else{
                deque.addLast(Math.max(deque.pollFirst(),deque.pollFirst()));
            }
            i++;
        }
        return deque.pollFirst();
    }
}


。复杂度


  • 时间复杂度:O ( n )
  • 空间复杂度:O ( n )


构建数组


  • 思路:构建新数组


  • 实现


class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        while (n != 1) {
            int[] newNums = new int[n / 2];
            for (int i = 0; i < newNums.length; i++) {
                if (i % 2 == 0) {
                    newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            nums = newNums;
            n /= 2;
        }
        return nums[0];
    }
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/min-max-game/solutions/2061544/ji-da-ji-xiao-you-xi-by-leetcode-solutio-ucpt/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


。复杂度


  • 时间复杂度:O ( n )
  • 空间复杂度:O ( n )


递归


  • 思路:若数组长度为1,那么返回nums[0],否则,按照题意求出新数组,递归求解新数组的答案


  • 实现


class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] newNums = new int[n / 2];
        for (int i = 0; i < newNums.length; i++) {
            if (i % 2 == 0) {
                newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        return minMaxGame(newNums);
    }
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/min-max-game/solutions/2061544/ji-da-ji-xiao-you-xi-by-leetcode-solutio-ucpt/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


。复杂度


  • 时间复杂度:O ( n )
  • 空间复杂度:O ( n )


原地修改


  • 思路:数组中的元素被使用过就不再被使用,因此可以将第i ii对计算得到的结果,存储至nums[i]


  • 实现


class Solution {
    public int minMaxGame(int[] nums) {
       int n = nums.length;
       while (n > 1){
           for (int i = 0; i < n / 2; i++){
               if (i % 2 == 0){
                   nums[i] = Math.min(nums[i * 2], nums[i * 2 + 1]);
               }else{
                   nums[i] = Math.max(nums[i * 2], nums[i * 2 + 1]);
               }
           }
           n /= 2;
       }
       return nums[0];
    }
}


。复杂度


  • 时间复杂度:O ( n )
  • 空间复杂度:O ( 1 )
目录
相关文章
|
8月前
|
算法
【每日一题Day297】LC2682找出转圈游戏输家 | 模拟+哈希表
【每日一题Day297】LC2682找出转圈游戏输家 | 模拟+哈希表
74 0
|
8月前
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列
47 0
|
8月前
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
【每日一题Day290】LC1281整数的各位积和之差 | 模拟
48 0
|
8月前
|
算法
【动态规划专栏】专题二:路径问题--------6.地下城游戏
【动态规划专栏】专题二:路径问题--------6.地下城游戏
59 0
|
8月前
|
定位技术
【每日一题Day200】LC1263推箱子 | 01-BFS
【每日一题Day200】LC1263推箱子 | 01-BFS
47 1
|
8月前
|
机器人
【每日一题Day174】LC1041困于环中的机器人 | 模拟 位运算
【每日一题Day174】LC1041困于环中的机器人 | 模拟 位运算
51 0
|
8月前
|
前端开发
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
【每日一题Day228】LC2460对数组执行操作 | 模拟+双指针
45 0
|
算法 测试技术 C#
C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例
C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例
刚学完二叉树,来试试这些oj题练练手吧!
刚学完二叉树,来试试这些oj题练练手吧!
81 0
刘金玉的零基础VB教程072期:贪吃蛇游戏开发第八节 总结 补充从尾部开始变长
刘金玉的零基础VB教程072期:贪吃蛇游戏开发第八节 总结 补充从尾部开始变长

热门文章

最新文章