חידת LeetCode Solution - Minimum Reverse Operations, פתרון ליטקוד, LeetCode Solution, איך לפתור שאלות ב LeetCode? איך לפתור חידת LeetCode? מדעי המחשב, תכנות מחשבים, איך להתקבל לעבוד בהייטק? איך ללמוד תכנות מחשבים? איך להיות מתכנת? איך לעבור ראיון טכני? איך להתכונן לראיון עבודה בהייטק? תרגול שאלות ליטקוד כהכנה לראיון, איך להיות מתכנת מחשבים? איך לעבוד בפיתוח תוכנה? איך להתכונן לראיונות כתיבת קוד? איך לפתור חידת היגיון? חידות היגיון... P, שמייצג מיקום בתוך המערך ARR. כל המערך ARR מאותחל ל 0, למעט המיקום P שמאותחל ל 1. כאשר בוודאות P לא יכול להיות אף אחד מהערכים שנמצאים במערך Banned. You can perform multiple operations on arr. אתה יכול ... מערך באורך 10, כאשר המיקום ההתחלתי הוא 5 והמקדם היפוך הוא 1 ונקבל את זה: בשורה התחתונה, אנחנו מבינים בוודאות שמקדם היפוך 1, לא יכול להזיז את הערך 1 מהמקום ההתחלתי שלו P לשום מקום אחר. ולכן כל הערכים ... כלשהם. אז מה בטוח נכון? אז כבר יש כמה דברים שהם בטוח נכונים, לדוגמה, שאם K=מספר אי זוגי, הרי שבוודאות נוכל לדעת שאם P=מספר זוגי, אז ANS בכל המקומות האי זוגיים, יהיה - 1. וכך גם אם K=מספר אי זוגי, הרי שבוודאות נוכל לדעת שאם P=מספר אי זוגי, אז ANS בכל המקומות הזוגיים, יהיה - 1. אז הנה כבר גילינו משהו ... P=0, ו K=4. דהיינו, המקרה הזה: אם נסתכל עליו היטב, וננסה לחשוב מה בטוח נכון בו? מה אנחנו יודעים בוודאות של 100 אחוז? הרי שנגלה את הדבר הבא: נגלה, שקודם כל עלינו לסמן את הנקודות הרחוקות ביותר שאליהן בטוח ... זאת אומרת, שאם מציגים לנו את מקרה ש: N=20, P=0, ו K=4. ומבקשים מאיתנו לסמן את מה שבטוח נכון בוודאות, בהנחה שאין לנו רשימת מקומות חסומים, הרי שאנחנו נסמן את המקומות הנל. דהיינו, נסמן את המקום הרחוק ביותר שניתן להגיע אליו בהיפוך 1. דהיינו, נדע בוודאות, שאין שום אפשרות להגיע יותר רחוק בהיפוך 1. ואת המיקום שהגענו אליו, גם אותו נהפוך בעוד היפוך 1, למיקום הרחוק ביותר שאפשרי להגיע ב 2 היפוכים וכך הלאה. כי אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 6 ... נקודה. אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה, אפשרי להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר שאפשרי להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי. דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ ... של K-1, ולסמן בסדר עולה 1-2-3 וכולי. דהיינו, קודם כל לנסות לסמן בתוך ANS את המקומות שבטוח נכונים שאליהם בוודאות לא ניתן להגיע בפחות מ X דילוגים ימינה או שמאלה. ואם תוך כדי שאנחנו עושים דילוג ימינה, אנחנו מגיעים ... נמשיך לדלג ימינה. ואם גם בו יש Banned אז נחזור עוד צעד אחד אחורה וכולי, עד שנגיע למצב שנדע בוודאות שלא ניתן לדלג יותר ימינה. דהיינו, אם יש רצף של מקומות חסומים, שהם באורך (K-1), הרי שברגע שנגיע אליהם, ... הקודמות, הרי שכרגע יש לנו פרישה ימינה ושמאלה, מנקודת ה P על עבר 2 הקצוות, של עוגנים ונקודות של וודאות, שבכל נקודה אנחנו יודעים בוודאות שלא ניתן להגיע אליה, בפחות היפוכים מהערך שכתוב בה. כי כמו שאמרנו בדוגמה הקודמת, אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 6 ... וכולי, ואין שום אפשרות להגיע למיקום 18 בפחות מ 6 היפוכים כנל. ואחרי שפתרנו את כל העוגנים הראשונים של הוודאות, הרי שבעצם עכשיו השאלה הפכה להיות הרבה יותר קלה. ונסתכל רגע על המקרה הקודם: אם נסתכל לצורך העניין על ... אנחנו צריכים לנסות להבין בכמה היפוכים ניתן להגיע ממיקום 18 למיקום 19 או 20. ולמיקום 18, אנחנו כבר יודעים שבוודאות צריך 6 היפוכים. או אם נסתכל על מיקום 10 או 11, אנחנו לא צריכים לנסות להבין בכמה היפוכים אפשרי ... להבין תוך כמה היפוכים אפשרי להגיע ממיקום 1 למיקום 2-3-4-5. כי אלו בעצם הטווחים שאליהם אנחנו רוצים להגיע בתוך הוודאות שמצאנו קודם. בקיצור... את ההמשך, נסו לגלות לבד. סיכום: לקחנו שאלה שנחשבת לדי מסובכת, שגם להבין אותה די קשה, ... את החוקיות של התהליך וגילינו שיש כאן חוקיות. מפה לשם הפתרון במהותו הוא, לסמן קודם כל את כל נקודות הוודאות לגבי הנקודות הרחוקות ביותר שאליהן צריך לפחות X היפוכים. והכל בהתאם למיקומים חסומים. ומכאן ואילך עלינו רק לסמן את המיקומים שבין המיקומים הוודאיים שאנחנו כבר יודעים אותם. בהצלחה.