【每日一题Day88】LC2293极大极小游戏|模拟递归-创新互联
You are given a 0-indexed integer array
10年积累的成都做网站、成都网站制作经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站制作后付款的网站建设流程,更有云霄免费网站建设让你可以放心的选择与我们合作。nums
whose length is a power of2
.Apply the following algorithm on
nums
:
- Let
n
be the length ofnums
. Ifn == 1
, end the process. Otherwise, create a new 0-indexed integer arraynewNums
of lengthn / 2
.- For every even index
i
where0<= i< n / 2
, assign the value ofnewNums[i]
asmin(nums[2 * i], nums[2 * i + 1])
.- For every odd index
i
where0<= i< n / 2
, assign the value ofnewNums[i]
asmax(nums[2 * i], nums[2 * i + 1])
.- Replace the array
nums
withnewNums
.- Repeat the entire process starting from step 1.
Returnthe last number that remains in
nums
after applying the algorithm.
小年快乐~ 周赛在周六周日永远搞不清 周赛在周日周赛在周日周赛在周日
队列思路:使用队列存放需要迭代的数组元素,并记录下标序号 i i i,根据下标奇偶性取大值最小值,每处理一组元素,序号加1,直至队列中只存在一个元素,返回即可。
- 由于数组长度均为 2 n 2^n 2n,迭代过程中长度一直为偶数直至长度为1,因此下标序号可以累计
实现
class Solution {public int minMaxGame(int[] nums) {Deque
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) 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://ybzwz.com/article/dgcohs.html