Plus One Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 자본 하나 Facebook 구글 Microsoft
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 73

문제 설명

”Plus One”문제에서 배열의 각 요소가 숫자의 숫자를 나타내는 배열이 제공됩니다. 완전한 배열은 숫자를 나타냅니다. XNUMX 번째 인덱스는 MSB 번호의. 숫자에 선행 XNUMX이 없다고 가정 할 수 있습니다.

우리의 임무는 주어진 숫자에 XNUMX을 더한 다음 결과를 배열 형태로 반환하는 것입니다.

digits =[4,3,2,1]
[4,3,2,2]

설명 :

Plus One Leetcode 솔루션

주어진 예에서와 같이 배열은 4321을 나타내고 4321 + 1은 4322가됩니다. 따라서 4322를 반환했습니다.

Plus One Leetcode 솔루션에 대한 접근 방식

모든 사람의 마음에 떠오르는 첫 번째 아이디어는 주어진 배열을 숫자로 변환하고 더하기 연산을 수행 한 다음 결과를 배열 형식으로 반환하는 것입니다.

그러나이 아이디어는 어떤 데이터 유형에도 맞지 않기 때문에 큰 크기의 배열에서는 실패합니다.

그래서 우리는 각 숫자를 하나씩 처리해야합니다.

  1. LSB에서 시작한 다음 MSB까지 각 숫자를 처리합니다.
  2. 현재 숫자가 9보다 작 으면 현재 숫자에 XNUMX을 더하고 배열을 반환하고 그렇지 않으면 현재 숫자에 XNUMX을 할당합니다.
  3. 마지막 요소가 처리되고 9와 같으면 모든 숫자가 9임을 의미합니다. 따라서 배열의 크기를 1 씩 늘리고 MSB에 XNUMX을 할당합니다.
  4. 배열 반환

실시

Plus One 용 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        for(int i=n-1;i>=0;i--)
        {
            if(digits[i]<9)
            {digits[i]++ ; return digits;} 
            else
                digits[i]=0;
        }
        vector<int>newnumber(n+1,0);
        newnumber[0]=1;
        return newnumber;
    }
int main() 
{ 
 vector<int> arr = {4,3,2,1}; 
  vector<int>ans= plusOne(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[4,3,2,2]

Plus One 용 Java 코드

import java.util.Arrays; 
public class Tutorialcup {
public static int[] plusOne(int[] digits) {
        
    int n = digits.length;
    for(int i=n-1; i>=0; i--) {
        if(digits[i] < 9) {
            digits[i]++; return digits;
        }
        digits[i] = 0;
    }
    
    int[] newNumber = new int [n+1];
    newNumber[0] = 1;
    return newNumber;
}
  public static void main(String[] args) {
        int [] arr = {4,3,2,1}; 
        int[]ans=plusOne(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[4,3,2,2]

Plus One Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 숫자 배열을 한 번만 탐색하기 때문입니다. 여기서 n은 숫자 배열의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1)  배열에 9보다 작은 숫자가 하나 이상 포함 된 경우, 그렇지 않으면 O (N).

참조

코멘트를 남겨

Translate »