생성 된 어레이 Leetcode 솔루션에서 최대 값 얻기

난이도 쉽게
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 75

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

생성 된 배열 Leetcode 솔루션에서 최대 값 얻기 문제는 단일 정수를 제공했습니다. 주어진 싱글로 정수, 생성 된 배열에서 최대 정수를 찾아야합니다. 어레이 생성에는 몇 가지 규칙이 있습니다. 부과 된 제약 조건 하에서 생성 될 수있는 최대 정수를 찾아야합니다. 규칙은 다음과 같습니다.

  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 솔루션에서 최대 값을 얻기위한 접근 방식

생성 된 배열 Leetcode 솔루션에서 최대 값 얻기 문제에는 충족해야하는 몇 가지 제약이 있습니다. 주어진 제약 조건 하에서 최대 정수를 찾아야합니다. 어레이 생성 규칙은 문제 설명에 이미 설명되어 있습니다. 가장 먼저 떠오르는 방법은 배열을 생성하고 최대 요소를 찾는 것입니다. 하지만 그렇게하면 문제가 해결 될까요?

우리가 단순히 세대를 따라 가면 올바른 결과를 찾을 수 없습니다. 배열을 생성하는 방법에 따라 다릅니다. 우리가 i 번째 인덱스에있을 때 2ith와 (2i + 1) 인덱스에서 요소를 생성하면. 그 순간 우리는 (i + 1) 번째 인덱스에 대해 생성 된 값을 가지지 못할 것입니다. 이 경우 결과가 정확하지 않습니다.

문제를 해결하기 위해 요소 생성 공식을 조작합니다. 세 번째 규칙에서 i를 i-1로 바꾸면 arr [3 * i-2] = arr [i] + arr [i-1]을 찾습니다. 이제 우리는 배열 생성을위한 규칙을 사용할 수 있습니다. 이 규칙은 이미 생성 된 값의 값을 사용하기 때문입니다. 따라서 여기에서는 미래의 알려지지 않은 값을 사용하는 대신 미리 계산 된 값을 사용합니다. 이제 for 루프를 사용하여 전체 프로세스를 시뮬레이션하고 1 * i 및 2 * i-2이 배열의 경계에 있는지 확인합니다. 이것이 확인되면 수식을 사용하여 배열을 채 웁니다.

암호

생성 된 배열 Leetcode 솔루션에서 최대 값 얻기를위한 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

생성 된 배열 Leetcode 솔루션에서 최대 값 얻기를위한 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

복잡성 분석

시간 복잡성

의 위에), n 개의 요소를 모두 생성하기 때문입니다.

공간 복잡성

의 위에), 배열 값을 저장할 임시 배열을 만들었 기 때문입니다.

균열 시스템 설계 인터뷰
Translate »
1