รับสูงสุดในโซลูชัน Leetcode อาร์เรย์ที่สร้างขึ้น


ระดับความยาก สะดวกสบาย
แถว

ปัญหา Get Maximum ใน Generated 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

คำอธิบาย: ตามกฎที่กำหนด:
จำนวน [0] = 0, จำนวน [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 อาร์เรย์ที่สร้างขึ้น

ปัญหา Get Maximum in Generated Array Leetcode Solution มีข้อ จำกัด บางประการที่ต้องปฏิบัติตาม ภายใต้ข้อ จำกัด ที่กำหนดเราจำเป็นต้องค้นหาจำนวนเต็มสูงสุด กฎสำหรับการสร้างอาร์เรย์ได้อธิบายไว้แล้วในคำอธิบายของปัญหา วิธีแรกที่ควรคำนึงถึงคือการสร้างอาร์เรย์และการค้นหาองค์ประกอบสูงสุด แต่จะแก้ปัญหาได้หรือไม่

ถ้าเราเดินหน้าคนรุ่นใหม่ไปเราจะไม่พบผลลัพธ์ที่ถูกต้อง เพราะมันขึ้นอยู่กับว่าเราสร้างอาร์เรย์อย่างไร หากเราสร้างองค์ประกอบที่ดัชนี 2ith และ (2i + 1) เมื่อเราอยู่ที่ดัชนี ith ในขณะนั้นเราจะไม่มีค่าที่สร้างขึ้นสำหรับดัชนี (i + 1) th ในกรณีนั้นผลลัพธ์จะไม่ถูกต้อง

ในการแก้ปัญหาเราจะจัดการสูตรสำหรับการสร้างองค์ประกอบ ถ้าเราแทนที่ i ด้วย i-1 ในกฎข้อที่ 3 เราพบว่า arr [2 * i-1] = arr [i] + arr [i-1] ดังนั้นตอนนี้เราสามารถใช้กฎสำหรับการสร้างอาร์เรย์ได้ เนื่องจากกฎนี้ใช้ค่าของมูลค่าที่สร้างขึ้นแล้ว ดังนั้นที่นี่แทนที่จะใช้ค่าที่ไม่รู้จักในอนาคตเรากำลังใช้ค่าที่คำนวณไว้ล่วงหน้า ตอนนี้เราเพียงแค่จำลองกระบวนการทั้งหมดโดยใช้ for loop และตรวจสอบว่า 2 * i และ 2 * i-1 อยู่ในขอบเขตของอาร์เรย์หรือไม่ เมื่อได้รับการยืนยันแล้วเราจะใช้สูตรเพื่อเติมอาร์เรย์

รหัส

รหัส C ++ สำหรับ Get Maximum in Generated Array Leetcode Solution

#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 สำหรับ Get Maximum ใน Generated Array Leetcode Solution

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 องค์ประกอบทั้งหมด

ความซับซ้อนของอวกาศ

บน), เพราะเราสร้างอาร์เรย์ชั่วคราวเพื่อเก็บค่าอาร์เรย์