פלוס פתרון Leetcode אחד


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ קפיטל אחד פייסבוק Google מיקרוסופט
מערך

הצהרת בעיה

בבעיה "פלוס אחד" אנו מקבלים מערך שבו כל אלמנט במערך מייצג ספרה של מספר. המערך השלם מייצג מספר. אינדקס האפסות מייצג את MSB של המספר. אנו יכולים להניח כי אין מספר אפס מוביל במספר.

המשימה שלנו היא להוסיף את המספר הנתון ואז להחזיר את התוצאה בצורה של מערך.

דוגמה

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

הסבר:

פלוס פתרון Leetcode אחד

כמו בדוגמה הנתונה, המערך מייצג 4321 ו 4321 + 1 הופך 4322. אז חזרנו 4322.

גישה לפיתרון Leetcode Plus One

הרעיון הראשון שעולה בראשם של כולם הוא להמיר את המערך הנתון למספר, לבצע פעולת חיבור ואז להחזיר את התוצאה בצורה של מערך.

אך רעיון זה ייכשל במערך גודל גדול מכיוון שהוא לא יתאים לשום סוג נתונים.

אז עלינו לעבד כל ספרה אחת אחת.

  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]

קוד 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]

ניתוח מורכבות של פתרון Leetcode פלוס אחד

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) כי אנחנו חוצים את מערך הספרות פעם אחת בלבד. כאן n הוא אורך מערך הספרות.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1)  במקרה שהמערך מכיל ספרה אחת לפחות קטנה מ- 9, אחרת O (n).

הפניות