189 8069 5689

【每日一题Day88】LC2293极大极小游戏|模拟递归-创新互联

极大极小游戏【LC2293】

You are given a 0-indexed integer arraynumswhose length is a power of2.

10年积累的成都做网站、成都网站制作经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有云霄免费网站建设让你可以放心的选择与我们合作。

Apply the following algorithm onnums:

  1. Letnbe the length ofnums. Ifn == 1, end the process. Otherwise, create a new 0-indexed integer arraynewNumsof lengthn / 2.
  2. For every even indexiwhere0<= i< n / 2, assign the value ofnewNums[i]asmin(nums[2 * i], nums[2 * i + 1]).
  3. For every odd indexiwhere0<= i< n / 2, assign the value ofnewNums[i]asmax(nums[2 * i], nums[2 * i + 1]).
  4. Replace the arraynumswithnewNums.
  5. Repeat the entire process starting from step 1.

Returnthe last number that remains innumsafter applying the algorithm.

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

队列

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

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

  • 实现

    class Solution {public int minMaxGame(int[] nums) {Dequedeque = 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) O(n)
      • 空间复杂度： O ( n ) 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) O(n)
      • 空间复杂度： O ( n ) 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) O(n)
      • 空间复杂度： O ( n ) O(n) O(n)
原地修改

  • 思路：数组中的元素被使用过就不再被使用，因此可以将第 i i i对计算得到的结果，存储至 n u m s [ i ] nums[i] 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(n) O(n)
      • 空间复杂度： O ( 1 ) O(1) O(1)

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章名称：【每日一题Day88】LC2293极大极小游戏|模拟递归-创新互联
网址分享：http://jkwzsj.com/article/dgcohs.html

其他资讯