Получите максимум в решении Leetcode сгенерированного массива  


Сложный уровень Легко
алгоритмы массив кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions

Задача «Получить максимум в сгенерированном массиве» Leetcode Solution предоставила нам одно целое число. С данным синглом целое, нам нужно найти максимальное целое число в сгенерированном массиве. Для генерации массива есть несколько правил. При наложенных ограничениях нам нужно найти максимальное целое число, которое могло быть сгенерировано. Правила следующие:

  1. arr [0] = 0, arr [1] = 1
  2. arr [2 * i] = arr [i], где 2 <= 2 * i <= n
  3. и arr [2 * i + 1] = arr [i] + arr [i + 1], где 2 <= 2 * i + 1 <= n

Но прежде чем углубляться в решение проблемы. Мы должны взглянуть на несколько примеров.

Получите максимум в решении Leetcode сгенерированного массивашпилька

n = 7
3

Пояснение: Согласно данным правилам:
nums [0] = 0, nums [1] = 1
число [(1 * 2) = 2] = число [1] = 1
число [(1 * 2) + 1 = 3] = число [1] + число [2] = 1 + 1 = 2
число [(2 * 2) = 4] = число [2] = 1
число [(2 * 2) + 1 = 5] = число [2] + число [3] = 1 + 2 = 3
число [(3 * 2) = 6] = число [3] = 2
число [(3 * 2) + 1 = 7] = число [3] + число [4] = 2 + 1 = 3

Итак, мы можем увидеть nums = [0,1,1,2,1,3,2,3], и максимальное число из них - 3. Таким образом, ответ - 3.

Подход для получения максимума в решении Leetcode сгенерированного массива  

Задача «Получить максимум в сгенерированном массиве Leetcode Solution» имеет некоторые ограничения, которые должны быть удовлетворены. При заданных ограничениях от нас требуется найти максимальное целое число. Правила генерации массива уже объяснялись в описании задачи. Первый метод, который приходит на ум, - это генерация массива и поиск максимального элемента. Но решит ли это проблему?

Смотрите также
Объединить два отсортированных списка Решения Leetcode

Если мы просто продолжим работу с поколением, мы не сможем найти правильных результатов. Потому что это зависит от того, как мы генерируем массив. Если мы генерируем элементы с индексом 2-го и (2i + 1), когда мы находимся в индексе i. В тот момент у нас не было бы сгенерированного значения для (i + 1) -го индекса. В этом случае результат будет неточным.

Для решения проблемы будем манипулировать формулами генерации элементов. Если мы заменим i на i-1 в третьем правиле. мы находим, что arr [3 * i-2] = arr [i] + arr [i-1]. Итак, теперь мы можем использовать правила для генерации массивов. Потому что это правило использует значение уже сгенерированного значения. Итак, здесь вместо использования любых будущих неизвестных значений мы используем предварительно рассчитанные значения. Итак, теперь мы просто моделируем весь процесс с помощью цикла for и проверяем, находятся ли 1 * i и 2 * i-2 в границах массива. После подтверждения мы используем формулы для заполнения массива.

Код:  

Код C ++ для получения максимума в решении Leetcode сгенерированного массива

#include <bits/stdc++.h>
using namespace std;

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

Код Java для получения максимума в решении Leetcode сгенерированного массива

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

Анализ сложности  

Сложность времени

НА), потому что мы генерируем все n элементов.

Смотрите также
Сумма решений Leetcode с левыми листьями

Космическая сложность

НА), потому что мы создали временный массив для хранения значений массива.

1