LeetCode 5561. 获取生成数组中的最大值

Stella981
• 阅读 885

文章目录

    • 1. 题目
    • 2. 解题

1. 题目

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums :

  • nums[0] = 0
  • nums[1] = 1
  • 当 2 <= 2 * i <= n 时,nums[2 * i] = nums[i]
  • 当 2 <= 2 * i + 1 <= n 时,nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

示例 1:
输入:n = 7
输出:3
解释:根据规则:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此,nums = [0,1,1,2,1,3,2,3],最大值 3

示例 2:
输入:n = 2
输出:1
解释:根据规则,nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

示例 3:
输入:n = 3
输出:2
解释:根据规则,nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2
 
提示:
0 <= n <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/get-maximum-in-generated-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
   
   
public:
    int getMaximumGenerated(int n) {
   
   
        if(n <= 1) return n;
        vector<int> arr(n+1);
        arr[0] = 0;
        arr[1] = 1;
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
   
   
            if(2*i >= 2 && 2*i <= n)
            {
   
   
                arr[2*i] = arr[i];
                ans = max(ans, max(arr[i], arr[2*i]));
            }
            if(2*i+1 >= 2 && 2*i+1 <= n)
            {
   
   
                arr[2*i+1] = arr[i]+arr[i+1];
                ans = max(ans, max(arr[i], arr[2*i+1]));
            }
            else
                break;
        }
        return ans;
    }
};

0 ms 6.7 MB


我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
LeetCode 5561. 获取生成数组中的最大值

点赞
收藏
评论区
推荐文章
胡哥有话说 胡哥有话说
4年前
面试官在“逗”你系列:连续子数组的最大和或最小和
前言本文题目是“连续子数组的最大和或最小和”。话不多说,开始“打怪”修炼...一、理解题目以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组3,2,1,2,4,6,5中连续子数组的最大和为:3(2)1248输入:3,2,1,2,4,6,
待兔 待兔
11个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
java 冒泡排序
思路1.将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;(第一轮结束后,序列最后一个元素一定是当前序列的最大值;)2.对序列当中剩下的n1个元素再次执行步骤1。3.对于长度为n的序列,一共需要执行n1轮比较时间复杂度最佳情况:T(n)O(n)最差情况:T(n)O(n2)平均情
先知 先知
4年前
C 语言代码大全
1两个数组的合并题目描述已知数组a中有m个按升序排列的元素,数组b中有n个按降序排列的元素,编程将a与b中的所有元素按降序存入数组c中。输入输入有两行,第一行首先是一个正整数m,然后是m个整数;第二行首先是一个正整数n,然后是n个整数,m,n均小于等于1000000。输出输出合并后的mn个整数,数据之间用空格隔开。输出占一行。样例输入4
执键写春秋 执键写春秋
4年前
Java练习(四)——数组元素顺序移位
题目:一个数组有n个整数,使其前面各数顺序向后移m个位置,最后m个数变成最前面的m个数。要求从控制台定义数组长度,并从控制台输入数据及顺序后移的位数。【位数不超过数组长度】packagetest;importjava.util.Scanner;publicclassPratice4publicstaticvoidmain(String
Stella981 Stella981
3年前
LeetCode
一目录不折腾的前端,和咸鱼有什么区别目录一目录二题目三解题思路四统计分析五解题套路二题目在一个nm的二维数组中:每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。示例
Stella981 Stella981
3年前
Python_每日习题_0003_完全平方数
题目一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?程序分析因为168对于指数爆炸来说实在太小了,所以可以直接省略数学分析,用最朴素的方法来获取上限:n0while(n1)2nn<168:n1
贾蔷 贾蔷
2星期前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们
贾蔷 贾蔷
1星期前
NOIP 2000 提高组 洛谷1004题(方格取数)解题思路与C++代码解析
一、题目描述简要描述题目:例如,在一个n×n的方格图中,每个格子包含一个正整数。需要选择两条从左上角到右下角的路径,路径可重复经过格子,但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。二、解题思路与算法分析1.问题分析1.问题核心是求解两条不交
贾蔷 贾蔷
3天前
洛谷P1255题 解题思路和步骤 C++实现带注释,c++入门基础题
一、问题描述与递推关系建立洛谷P1255数楼梯问题要求计算n级台阶的不同走法数,每次可以跨1级或2级。这本质上是斐波那契数列的变种问题,递推公式为f(n)f(n1)f(n2)。当n≤50时可用普通整型存储,但题目中n可能达到5000,这就必须使用高精度运