Плус едно решение за Leetcode


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко капитал Еден Facebook Google Мајкрософт
Низа

Проблем изјава

Во проблемот „Плус еден“ ни е дадена низа каде што секој елемент во низата претставува цифра од број. Комплетната низа претставува број. Индексот на нулта претставува MSB на бројот. Можеме да претпоставиме дека нема водечка нула во бројот.

Нашата задача е да плус еден даден број и потоа да го вратиме резултатот во форма на низа.

пример

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

објаснување:

Плус едно решение за Leetcode

Како и во дадениот пример, низата претставува 4321 и 4321 + 1 станува 4322. Значи, вративме 4322.

Пристап за решение плус еден Leetcode

Првата идеја што им паѓа на ум на сите е да ја конвертирате дадената низа во број, да извршите операција за собирање и потоа да го вратите резултатот во форма на низа.

Но, оваа идеја нема да успее за низа со големи димензии, бидејќи не би се вклопила во кој било тип на податоци.

Значи, секоја цифра треба да ја обработиме една по една.

  1. Започнете од LSB и потоа обработете ја секоја цифра до MSB.
  2. Ако тековната цифра е помала од 9, тогаш додадете една на тековната цифра и вратете ја низата друго доделете нула на тековната цифра.
  3. Ако последниот елемент е обработен и тој исто така беше еднаков на 9, тоа значи дека сите цифри беа 9. Значи, ќе ја зголемиме големината на низата за една и ќе му доделиме 1 на MSB.
  4. Вратете ја низата

Имплементација

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]

Јава код за Плус Еден

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]

Анализа на комплексноста на решението за плус еден лек-код

Временска сложеност

Временската сложеност на горенаведениот код е Тој) затоа што ја разгледуваме низата цифри само еднаш. Тука n е должината на низата со цифри.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е О (1)  во случај ако низата содржи најмалку една цифра помала од 9, инаку Тој).

Референци