Массивын Leetcode шийдлийг хамгийн дээд хэмжээнд аваарай


Хэцүү байдлын түвшин Easy
Array

Array 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
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 байна. Тиймээс хариулт нь 3 байна.

Массивын Leetcode уусмалаар хамгийн дээд хэмжээг авах арга

Array Leetcode Solution-т хамгийн их хэмжээг авах асуудал нь зарим хязгаарлалтыг хангасан байх ёстой. Өгөгдсөн хязгаарлалтын дагуу бид хамгийн их бүхэл тоог олох шаардлагатай. Массив үүсгэх дүрмийг асуудлын тайлбарт аль хэдийн тайлбарласан болно. Санаанд орж буй хамгийн эхний арга бол массивыг үүсгэх, хамгийн их элемент олох явдал юм. Гэхдээ энэ нь асуудлыг шийдэж чадах уу?

Хэрэв бид зүгээр л үеийнхэнтэйгээ хамт явж байвал зөв үр дүнг олж чадахгүй. Энэ нь бид массивыг хэрхэн үүсгэхээс хамаарна. Хэрэв бид ith индекст байхдаа 2ith ба (2i + 1) индекс дээр элементүүдийг үүсгэдэг бол. Тухайн үед бид (i + 1) индексийг үүсгэх утга байхгүй болно. Энэ тохиолдолд үр дүн нь үнэн зөв биш байх болно.

Асуудлыг шийдэхийн тулд бид элемент үүсгэх томъёогоор ажиллах болно. Хэрэв бид i-ийг i-1-ээр сольсон бол 3-р дүрмээр. arr [2 * i-1] = arr [i] + arr [i-1] болохыг бид олж мэдэв. Тиймээс одоо массив үүсгэх дүрмийг ашиглаж болно. Учир нь энэ дүрэм нь аль хэдийн үүсгэсэн утгын утгыг ашигладаг. Тиймээс энд ирээдүйн үл мэдэгдэх утгыг ашиглахын оронд урьдчилан тооцоолсон утгыг ашиглаж байна. Тэгэхээр одоо for цикл ашиглан бүх үйл явцыг дуурайлган массивын хязгаарт 2 * i ба 2 * i-1 байгаа эсэхийг шалгана уу. Үүнийг баталгаажуулсны дараа бид массивыг дүүргэхийн тулд томъёог ашигладаг.

код

Array Leetcode Solution дээр хамгийн ихийг авахын тулд C ++ код

#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

Array Leetcode Solution дээр хамгийн их хэмжээг авахад зориулсан Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид бүх n элементүүдийг үүсгэдэг.

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид массивын утгыг хадгалах түр массивыг үүсгэсэн.