Summary Ranges
ניתן לך מערך ממוין nums של מספרים שלמים שונים. חלק אותו למספר הקטן ביותר של טווחים של מספרים שלמים עוקבים, כך שכל ערך שייך לטווח אחד בדיוק. כתוב טווח a..b כטקסט "a->b", או כ-"a" כשהוא מכיל ערך אחד. החזר את הטווחים בסדר עולה.
פונקציה
- numsinteger-array
- המערך הממויין של מספרים שלמים שונים
- מחזירהstring-array
- את הטווחים כטקסט, מהערכים הקטנים ביותר לגדולים ביותר
אילוצים
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsממוינת בסדר עולה ואין בה כפילויות.
דוגמאות
- קלט
- nums = [0, 1, 2, 5, 6, 9]
- פלט
- ["0->2", "5->6", "9"]
- הסבר
0, 1, 2מופיעים זה אחר זה, ולכן הם יוצרים את"0->2". הקפיצה מ־2 ל־5 מתחילה טווח חדש,"5->6", ו־9 עומד לבדו בתור"9".
- קלט
- nums = [-3, -1, 0, 1, 4, 7, 8]
- פלט
- ["-3", "-1->1", "4", "7->8"]
- הסבר
- ל־-3 אין שכן (-2 חסר),
-1, 0, 1יוצרים רצף, 4 עומד לבדו, ו־7, 8סוגרים את הרשימה. ערכים שליליים פועלים באותו אופן: אחרי -1 מגיע -1 + 1 = 0.
+16 בדיקות נסתרות בשליחה
שאלת המשך
נניח ש-nums עשוי להכיל כפילויות, כמו [1, 2, 2, 3]. מה היית משנה כדי שהוא עדיין ידפיס "1->3"?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
המערך ממוין. מתי שני ערכים סמוכים שייכים לאותו טווח?
הם שייכים יחד בדיוק כאשר
nums[i+1] == nums[i] + 1. כל זוג שכנים אחר מסמן את סוף הטווח האחד ואת תחילת הטווח הבא.זכור היכן התחיל הטווח הנוכחי. התקדם כל עוד הערך הבא גדול באחד מהערך הנוכחי; כשהרצף נקטע או שהמערך מסתיים, כתוב את הטווח מתחילתו ועד לערך הנוכחי, והתחל את הטווח הבא בערך שאחריו.
פתרון
מכיוון שהערכים ממוינים וייחודיים, טווח של מספרים שלמים עוקבים הוא תמיד רצף של איברים שכנים במערך, וטווח מסתיים בדיוק במקום שבו ההפרש בין שני איברים שכנים גדול מ־1. חלוקת המערך בכל פער כזה נותנת את מספר הטווחים הקטן ביותר, מכיוון שאף טווח לא יכול לחצות פער. כל מה שנותר הוא מעקב קפדני: תחילת כל רצף, האיבר האחרון ופורמט הטקסט.
בדוק את שני השכנים של כל ערך
האינטואיציה
בחן ערך אחד בכל פעם ושאל שתי שאלות. האם טווח מתחיל כאן? כן, אם זהו הערך הראשון או שהערך שלפניו אינו קטן ממנו באחד. האם טווח מסתיים כאן? כן, אם זהו הערך האחרון או שהערך שאחריו אינו גדול ממנו באחד.
ב-[0, 1, 2, 5, 6, 9], טווח מתחיל ב-0, ב-5 וב-9, ומסתיים ב-2, ב-6 וב-9. זכור את הערך שבו הטווח הנוכחי התחיל. כאשר טווח מסתיים ב-nums[i], כתוב "start->nums[i]", או רק "start" כשהטווח התחיל והסתיים באותו ערך, כמו שקורה ב-9.
מבקרים בכל ערך פעם אחת ובודקים שני שכנים, ולכן זמן הריצה הוא O(n). מלבד הפלט, נשמר רק ערך התחלה אחד בזיכרון, ולכן המקום הנוסף הוא O(1).
אלגוריתם
- הגדר
start = nums[0]. - עבור כל אינדקס
i: אםi > 0וגםnums[i] != nums[i-1] + 1, הגדרstart = nums[i]. - אם
iהוא האינדקס האחרון אוnums[i+1] != nums[i] + 1, הטווח מסתיים כאן. - הוסף
"start"כאשרstart == nums[i], אחרת"start->nums[i]". - החזר את הרשימה לאחר האינדקס האחרון.
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return rangesשני מצביעים בכל רצף
האינטואיציה
התייחסו לכל טווח כאל מקטע של המערך ומצאו את שני קצותיו. המצביע i עומד על הערך הראשון בטווח. המצביע j מתחיל ב-i ונע ימינה כל עוד הערך הבא גדול בדיוק באחד, ולכן הוא נעצר על הערך האחרון בטווח.
עבור [-3, -1, 0, 1, 4, 7, 8]: i ב- -3 לא יכול להמשיך, כי -1 אינו -2, ולכן הטווח הוא "-3". לאחר מכן i קופץ ל- -1, ו-j מתקדם מעל 0 ו-1 ונעצר לפני 4: "-1->1". לאחר מכן "4" ו-"7->8". אחרי כל טווח, i עובר ל-j+1, הערך הראשון בטווח הבא.
מספר הטווחים הוא הקטן ביותר האפשרי: שני ערכים שמפריד ביניהם פער לעולם לא יכולים להשתייך לאותו טווח, והשיטה מפצלת רק בפערים. שני המצביעים נעים רק קדימה, ולכן הלולאה הפנימית רצה בסך הכול n פעמים לאורך כל הטווחים, מה ששומר על זמן ריצה של O(n) ועל זיכרון נוסף של O(1).
אלגוריתם
- הגדר את
i = 0. - הגדר את
j = i, והזז אתjימינה כל עודj+1 < nוגםnums[j+1] == nums[j] + 1. - הוסף את
"nums[i]"כאשרi == j, אחרת הוסף את"nums[i]->nums[j]". - הגדר את
i = j + 1וחזור על הפעולה עד ש־iיעבור את הסוף. - החזר את הרשימה.
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
מלכודות ומקרי קצה
הלוגיקה נכנסת בכמה שורות; הטעויות נמצאות בקצוות.
- שוכחים את הטווח האחרון. לולאה שכותבת טווח רק כשהיא נתקלת בפער אף פעם לא כותבת את הטווח האחרון, ולכן
[0, 1, 2, 5, 6, 9]מאבד את"9"שלו. סגרו טווח גם באינדקס האחרון. - כותבים
"a->a"עבור ערך יחיד. טווח שמכיל ערך אחד נכתב כך:"a". - מדפיסים ערכים גדולים בסימון מדעי. R ממיר מספר double כמו
1000000000ל-1e+09; המירו את הערכים למספרים שלמים לפני שאתם מחברים אותם.
שאלות נפוצות4
מהי סיבוכיות הזמן של Summary Ranges?
O(n). כל ערך נבדק פעם אחת, וכל טווח נכתב פעם אחת. מלבד רשימת הפלט, המקום הנוסף הוא O(1): תחילת הטווח הנוכחי ואינדקס אחד או שניים.
למה חיתוך בכל פער נותן את מספר הטווחים הקטן ביותר?
טווח מכיל מספרים שלמים עוקבים, ולכן הוא לא יכול להכיל שני ערכים שביניהם חסר מספר. לכן, כל פער במערך הממוין חייב להפריד בין שני טווחים, ועם g פערים צריך לפחות g+1 טווחים. חיתוך רק במקומות שבהם יש פערים נותן בדיוק g+1.
איך מטפלים בטווח שיש בו רק מספר אחד?
בדקו אם הטווח מתחיל ומסתיים באותו ערך. אם כן, כתבו את הערך הזה לבדו, כמו "9". אם לא, כתבו את ערך ההתחלה, את החץ ואת ערך הסיום, כמו "5->6". עם שני מצביעים, הבדיקה היא i == j.
האם טווחי סיכום דורשים שהקלט יהיה ממוין?
כן. השיטה משווה רק בין איברים שכנים, ולכן היא מסתמכת על כך שמספרים שלמים עוקבים נמצאים זה לצד זה. אם הקלט אינו ממוין, מיין אותו תחילה, וכך המשימה כולה תהיה O(n log n), או הכנס את הערכים לקבוצת גיבוב והרחב כל טווח מהערך הקטן ביותר שלו, כמו בבעיית הרצף העוקב הארוך ביותר.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def summaryRanges(nums):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
nums = [0, 1, 2, 5, 6, 9]
צפוי
["0->2", "5->6", "9"]