שאלה

[i1991]

qu

[שניצל]

מה הבעיה בפתרון שלך? שים לב ש-part_flip צריך לרוץ ב-(O(k ולא (O(1.

[Ghosthunter]

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

[Lee Jun Fan]

רשימה דו כיוונית זה טוב, אבל ה-FLIP שאתה מציע לא באמת יהפוך (כי המצביע של כל תא עדיין יצביע על מי שהוכנס אחריו, ואתה צריך לשנות אותו שיצביע על מי שהוכנס לפניו). תחשוב איך אתה שומר את ה-next וה-prev בצורה כזאת שתוכל ב-(O(1 להפוך את כל ההצבעות ברשימה.

[i1991]

אוקיי.. אולי בנוסף לרשימה דו כיוונית נוסיף מערך בו כל תא מסמן את הסדר של התא(ישר או הפוך). כל רצף חדש יסומן במערך עם סימון 1 וכאשר נבצע flip נשנה ל(-1)

וגם כאשר נרצה לעשות הפיכה חלקית (למרות שאני לא בטוח אם הכוונה היא להפיכת כל רצף בפני עצמו או להפיכת כל איחוד הרצפים) נעבור בדיוק על k ערכי המערך ונשה את ערכם ממינוס לפלוס או ההפך

[שניצל]

אני לא מבין למה להסתבך.

עושים רשימה דו כיוונית, עם ביט אחד שמציין אם הרשימה "ישרה" או "הפוכה". ב-pop/push בודקים אם הרשימה ישרה/הפוכה ואז מוציאים/מכניסים את האיבר מהקצה המתאים, וב-flip רק הופכים את הביט הזה.

כיוון ש-part_flip צריך לרוץ ב-(O(k, אין בעיה פשוט להוציא את k האיברים הראשונים מהרשימה לתוך מערך ואז להכניס אותם בחזרה.

[i1991]

אני לא מבין למה להסתבך.

עושים רשימה דו כיוונית, עם ביט אחד שמציין אם הרשימה "ישרה" או "הפוכה". ב-pop/push בודקים אם הרשימה ישרה/הפוכה ואז מוציאים/מכניסים את האיבר מהקצה המתאים, וב-flip רק הופכים את הביט הזה.

יש כמה דברים שלא ברורים לי בפתרון שלך: לעשות כמה רשימות דו כיווניות (אחת לכל רצף) או רק אחת ? אם רק אחת-איפה בדיוק נציין אם הרשימה ישרה או הפוכה לגבי כל אחד מן הרצפים ?

כיוון ש-part_flip צריך לרוץ ב-(O(k, אין בעיה פשוט להוציא את k האיברים הראשונים מהרשימה לתוך מערך ואז להכניס אותם בחזרה.

הבעיה היא שלא מדובר בk איברים אלא בk רצפים וזה קצת מסבך לי את העניינים אלא אם כן לא הבנתי כ"כ טוב את הפתרון שהצעת

[שניצל]

צודק, לא הבנתי נכון את ההגדרה.

בכל מקרה, אפשר שכל רצף ייוצג ע"י רשימה, ואז כל המחסנית מיוצגת ע"י רשימה של רצפים (ככה שסה"כ יש לך רשימה של רשימות). לרשימה יש ביט שמציין אם היא הפוכה או ישרה, ולכל רצף יש ביט שאומר האם הוא "ישר" או "הפוך" ביחס לרשימה כולה (ככה שבשביל לבדוק האם הרצף הנתון ישר או הפוך, צריך לעשות xor לביט שלו ולביט של הרשימה).

בשביל להכניס/להוציא איבר מהרשימה, קודם כל מחליטים על איזה רצף צריך לפעול (הראשון או האחרון, לפי ביט ההיפוך של הרשימה) ואז מחליטים על איזה צד שלו צריך לעבוד (לפי ביט ההיפוך של הרצף).

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

[i1991]

חוזר שוב לשאלה הזו. נניח אני מממש בעזרת הרשימה של רשימות. איך נבצע את פעולת ההכנסה וההוצאה בo(1)?

זה דורש לשמור מצביע לתחילת כל רשימה ולסוף כל רשימה-וזה יכול להגיע למספר אינסבופי של מצביעיםדבר שלא ניתן למימוש...

[שניצל]

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

סה"כ מספר המצביעים לא עולה על מספר האיברים שיש בכלל ברשימה (עד כדי כפל בקבוע).

[i1991]

רק התחלתי ללמוד תכנות אז אולי אני טועה..אבל בכל זאת:

אם אני רוצה לכתוב פסדו-קוד או קוד ממש של התוכנית אז כל פעם שאבנה רשימה חדשה אצטרך לשים מצביע לתחילת הרשימה ומצביע נוסף לסוף הרשימה וכל פעם שיבצעו push למחסנית אצטרך ליצור מצביעים חדשים-זה לא קצת בעיה שכמות המצביעים תלויה באורך הקלט? איך כותבים את זה בקטע קוד??

[שניצל]

אה.... מה?

כל פעם שעושים push אתה צריך ליצור רק מספר סופי של מצביעים.

[i1991]

אוקיי ..ואם אנחנו מכניסים n איברים נצטרך ליצור n מצביעים לכל רשימה-מצביע לסוף הרשימה כך שאם נרצה להוציא את האיבר הראשון/האחרון לא יהיה צורך לרוץ על כל הרשימה

[שניצל]

אוקי, אבל כל פעם אתה יוצר רק מצביע אחד. לא הבנתי מה הבעיה כאן.

[Ghosthunter]

רק התחלתי ללמוד תכנות אז אולי אני טועה..אבל בכל זאת:

אם אני רוצה לכתוב פסדו-קוד או קוד ממש של התוכנית אז כל פעם שאבנה רשימה חדשה אצטרך לשים מצביע לתחילת הרשימה ומצביע נוסף לסוף הרשימה וכל פעם שיבצעו push למחסנית אצטרך ליצור מצביעים חדשים-זה לא קצת בעיה שכמות המצביעים תלויה באורך הקלט? איך כותבים את זה בקטע קוד??

גם ברשימה מקושרת מספר המצביעים גדל כמספר האיברים ברשימה (יש מצביע בכל איבר לאיבר הבא).