Plus One حل Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل عاصمة واحدة Facebook جوجل Microsoft
مجموعة

بيان المشكلة

في المسألة "Plus One" لدينا مصفوفة حيث يمثل كل عنصر في المصفوفة رقمًا من رقم. المصفوفة الكاملة تمثل رقمًا. يمثل الفهرس الصفري MSB من العدد. يمكننا أن نفترض أنه لا يوجد صفر بادئ في العدد.

مهمتنا هي إضافة رقم واحد ثم إرجاع النتيجة في شكل مصفوفة.

مثال

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 ، فقم بإضافة واحد إلى الرقم الحالي وأعد المصفوفة الأخرى ، وقم بتعيين صفر إلى الرقم الحالي.
  3. إذا تمت معالجة العنصر الأخير وكان أيضًا يساوي 9 ، فهذا يعني أن جميع الأرقام كانت 9. لذلك ، سنزيد حجم المصفوفة بمقدار واحد ونخصص 1 لـ MSB.
  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]

كود جافا لـ 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]

تحليل التعقيد لحل Plus One Leetcode

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نجتاز مصفوفة الأرقام مرة واحدة فقط. هنا n هو طول مجموعة الأرقام.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1)  في حالة احتواء المصفوفة على رقم واحد على الأقل أصغر من 9 ، وإلا O (ن).

المراجع