Плюс адно рашэнне Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык Capital One facebook Google Microsoft
масіў

Пастаноўка праблемы

У задачы "Плюс адзін" нам даецца масіў, дзе кожны элемент масіва ўяўляе лічбу ліку. Поўны масіў уяўляе лік. Нулявы індэкс ўяўляе МСБ ліку. Мы можам выказаць здагадку, што ў ліку няма нуля.

Наша задача скласці плюс адзін зададзены лік, а потым вярнуць вынік у выглядзе масіва.

Прыклад

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

Тлумачэнне:

Плюс адно рашэнне Leetcode

Як і ў дадзеным прыкладзе, масіў уяўляе 4321, а 4321 + 1 становіцца 4322. Такім чынам, мы вярнулі 4322.

Падыход да рашэння Plus One Leetcode

Першая ідэя, якая прыходзіць у галаву ўсім, - пераўтварыць дадзены масіў у лік, выканаць аперацыю складання і вярнуць вынік у выглядзе масіва.

Але гэтая ідэя не атрымаецца для масіва вялікага памеру, бо не ўпісваецца ў любы тып дадзеных.

Такім чынам, нам трэба апрацоўваць кожную лічбу па адной.

  1. Пачніце з LSB, а затым апрацуйце кожную лічбу да MSB.
  2. Калі бягучая лічба меншая за 9, дадайце да бягучай лічбы і вярніце масіў, інакш прысвоіце бягучай лічбе нуль.
  3. Калі апрацоўваецца апошні элемент, і ён таксама быў роўны 9, гэта азначае, што ўсіх лічбаў было 9. Такім чынам, мы павялічым памер масіва на адзін і прысвоім MSB 1.
  4. Вярнуць масіў

Рэалізацыя

Код C ++ для Plus One

#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]

Код Java для Plus One

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 - даўжыня лічбавага масіва.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1)  у выпадку, калі масіў змяшчае хаця б адну лічбу, меншую за 9, у адваротным выпадку Аб (п).

Спасылкі