הבעיה: הוספת אחד למספר המיוצג כמערך של ספרות
בהינתן מספר אי שלילי המיוצג כמערך של ספרות, המשימה שלנו היא להוסיף 1 למספר המקורי (להגדיל את המספר המיוצג על ידי הספרות).
הערות ודגשים
- קלט יכול להכיל אפסים (0) בהתחלה ויחשב כקלט חוקי.
- אסור להחזיר אפסים (0) בהתחלה זאת אומרת שאם הקלט שלנו נראה כך: [0,1,2,3,4] נצטרך להחזיר [1,2,3,5]
תחילה, נפענח את הכתוב, הרמזים ואת הנחות העזר (במידה וקיימות) שיש לנו:
קלט: מספר, אשר מיוצג על ידי מערך שבנוי מספרות אי שליליות. הערכים בתוך המערך מסודרים לפי סדר הכתיבה של המספר. כלומר, קלט [1,2,3] מייצג את המספר 123.
פלט: עלינו להוסיף “1” (לספרת היחידות) ולהחזיר את הרשימה המעודכנת. כלומר, אילו קיבלנו [1,2,3] , הפלט שהיינו נדרשים להחזיר היה [1,2,4].
הפתרון
חשוב לציין שישנן כמה דרכים לפתור את הבעיה, לפני שאתם צוללים לפתרון שאנו מציעים לכם כאן תעצרו רגע ותנסו בעצמכם, גם אם לא תצליחו וגם אם תטעו בדרך זה תהליך חשוב שצריך לעבור וזה יעזור לכם בהבנת התרגיל ובתרגילים ההבאים בכלל.
מה שמשותף לכל דרכי הפתרון הם מקרי הקצה (edge cases) וחשוב מאוד לחשוב עליהם
מקרה קצה ראשון: ספרות האחדות היא 9, כלומר יש צורך לאפס אותה ולהעביר נשא (carry) אל ספרת העשרות. במידה וגם היא 9, יש להמשיך באותה שיטה.
מקרה קצה שני: הוספת תא נוסף (לכל היותר) במערך. בהינתן קלט שבו כל הספרות אמורות להתאפס ולהעביר “נשא” כולל הספרה הגבוהה ביותר, נצטרך להוסיף “1” לראש הרשימה.
מקרה קצה שלישי: מערך עם ספרה בודדת שהיא 0.
מקרה קצה רביעי: קלט שבו יש “0” בהתחלה (חוקי לפי תנאי השאלה) וצריך להוריד אותו לפני החזרת התשובה (דרישה בשאלה). לדוגמא הקלט [0,1] צריך לחזור בתור [2].
ראשית, נציג פתרון נאיבי ב2 שורות (הודות לפייתון זה מתאפשר):
# @param A : list of integers
# @return a list of integers
def plusOne(self, A):
A = [str(num) for num in A]
return [int(digit) for digit in (str(1+int(''.join(A))))]
הסבר: בשורה הראשונה הופכים את המערך A ממערך של ספרות למערך של ספרות מטיפוס string.
בשורה השנייה תחילה הופכים את כל המערך(רשימה) מרשימה של מחרוזות למחרוזת אחת שהיא המספר, ממירים חזרה לטיפוס int, מוסיפים לתוצאה 1, ממירים חזרה לstring והופכים את התוצאה הסופית אשר מיוצגת ע”י מחרוזת לרשימה של ספרות.
*נסו בעצמכם להבין מה זמן הריצה וסיבוכיות המקום של הפתרון
פתרון נוסף, קצת פחות בזבזני ויותר “בשרני” הוא הפתרון הבא: עוברים על הרשימה מהסוף להתחלה וכל עוד שנתקלים בספרה 9 מאפסים אותה. אם הגענו לספרה שאינה 9, מוסיפים לה 1(אשר מתפקד גם בתור נשא). אם הגענו לסוף המערך (מפני שכל הספרות שנתקלנו בהן עד כה הן 9), נוסיף ספרה חדשה למערך של “1”.
לבסוף, נוריד אפסים מובילים במידה וקיימים, ונחזיר את התשובה.
גרסת Python:
# @param A : list of integers
# @return a list of integers
def plusOne(self, A):
A=A[::-1]
for index, digit in enumerate(A):
if digit == 9:
A[index] = 0
else:
A[index] +=1
break
else:
A.append(1)
return self.trimLeadingZeros(A[::-1])
def trimLeadingZeros(self, A):
for index, digit in enumerate(A):
if digit != 0:
return A[index:]
גרסת #C:
List<int> plusOne(List<int> digits)
{
for (var i = (digits.Count - 1); i >= 0; i--)
{
if (digits[i] == 9)
{
digits[i] = 0;
if (i == 0)
{
digits.Insert(0, 1);
}
}
else
{
digits[i]++;
break;
}
}
return trimLeadingZeros(digits);
}
List<int> trimLeadingZeros(List<int> digits)
{
var zeroCounter = digits.TakeWhile(digit => digit == 0).Count();
digits.RemoveRange(0, zeroCounter);
return digits;
}
סיבוכיות ושאר ירקות
נסו לענות בעצמכם לפני שאתם קופצים לפתרון 🙂
זמן הריצה של הקוד: O(n)
סיבוכיות מקום: O(n)
בוודאי – במקרה קצה שבו כל הספרות הן 9 יש לעבור על כל הרשימה.
1 – לכל היותר נוסיף “1” לראש המערך