חידת LeetCode Solution - Minimum Reverse Operations, פתרון ליטקוד, LeetCode Solution, איך לפתור שאלות ב LeetCode? איך לפתור חידת LeetCode? מדעי המחשב, תכנות מחשבים, איך להתקבל לעבוד בהייטק? איך ללמוד תכנות מחשבים? איך להיות מתכנת? איך לעבור ראיון טכני? איך להתכונן לראיון עבודה בהייטק? תרגול שאלות ליטקוד כהכנה לראיון, איך להיות מתכנת מחשבים? איך לעבוד בפיתוח תוכנה? איך להתכונן לראיונות כתיבת קוד? איך לפתור חידת היגיון? חידות היגיון... אף אחד מהערכים שנמצאים במערך Banned. You can perform multiple operations on arr. אתה יכול לבצע פעולת הכפלה / היפוך על המערך ARR. צריך לשים לב, שלמילה multiple יש כל מיני פירושים אפשריים. אחד מהקשיים להבין את השאלה, נובע מכך שלמילה הזאת יש כל מיני פירושים אפשריים. הפירוש הנכון כאן, הוא שאתה יכול לבצע פעולת הכפלה / היפוך על המערך ARR כדלקמן. In an operation, you can choose a subarray with size k and reverse the subarray. בכל פעולת היפוך, אתה יכול לבחור תת מערך, באורך K ולהפוך אותו בתוך המערך ARR. דהיינו, נתון לנו גם משתנה K, שמייצג את האורך האפשרי של תת המערך שאפשרי לבצע עליו היפוך. ואנחנו יכולים לקחת מקטע / תת מערך מתוך המערך ARR, שתת המקטע יהיה באורך K. ואנחנו יכולים לעשות איתו פעולת היפוך בתוך המערך ARR. דהיינו, אנחנו יכולים לקחת מקטעים באורך K מתוך המערך ARR ולעשות להם פעולת היפוך. לדוגמה, בהינתן ש K = 4. אז תתי מקטעים באורך 4 יכולים להיות אלו: כאשר פעולת היפוך תיראה כך: נניח שלקחנו את המיקום, מ 3 ועד 6, אז פעולת ההיפוך תיראה כך: ואם נניח שלקחנו את ... ההיפוך הבא: וגם את ההיפוך הבא: וכן על זה הדרך, ניתן להמשיך ולמלא את כל שאר האפשרויות של כל ההיפוכים האפשריים וכולי. A subarray is a contiguous non-empty sequence of elements within an array. The values of ans[i] are ... הזאת. אז לכאורה הדרך לפתרון היא פשוטה ביותר. עלינו לקחת את המערך ARR ואת הערך K ולסמן את כל ההיפוכים האפשריים שאפשרי לעשות על המערך ARR, היפוכים באורך K. ולסמן אחרי כל היפוך, היכן יהיה הערך 1. ועלינו לבדוק את כל האפשרויות האפשריות של לעשות כל היפוך באורך K על המערך ARR. ואחרי הכל עלינו לראות היכן נמצא הערך 1. ועלינו לבדוק, מה היה מינימום ההיפוכים האפשריים, כדי להביא לשם את הערך 1. דהיינו, בדוק את כל האפשרויות האפשריות להעביר את 1 ממקום למקום. ואז ... העניין N = 10, K = 2 אבל P = נניח 5, אז נקבל את התוצאה הבאה, אם נעשה היפוכים ימינה: וגם את התוצאה הבאה, אם נעשה היפוכים שמאלה: בקיצור, עד כה הבנו, שמקדם K=1, לא מצליח להעביר את המיקום של ה P ממקום למקום ומקדם K=2, ... הערך של P, אז הוא יראה תופעה מעניינת שקורית כאשר K=3. כי נראה שכאשר K = 3, הרי שיש היפוכים של 3, שלא מזיזים את הערך 1 ממקום למקום. וכאשר K=3, הרי שהערך 1 יכול לזוז רק בדילוגים של ... ימין או שמאל, שמגבילה את ההיפוך האפשרי. ובעצם עד כאן, הבנו קצת או אולי אפילו המון, את החוקיות של ההיפוכים האפשריים. ואחרי שהבנו את כל זה, עכשיו ננסה להבין, לגבי המקרה הכללי, מה בטוח נכון? האם יש משהו שהוא ... בהיפוך 1. ואת המיקום שהגענו אליו, גם אותו נהפוך בעוד היפוך 1, למיקום הרחוק ביותר שאפשרי להגיע ב 2 היפוכים וכך הלאה. כי אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 6 בפחות מ 2 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 9 בפחות מ 3 היפוכים וכולי, ואין שום אפשרות להגיע למיקום 18 בפחות מ 6 היפוכים. ובדוגמה שהבאתי, אנחנו עושים את כל ההיפוכים ימינה. אבל כמובן שצריכים לעשות את זה גם שמאלה, במידה ויש להיכן להפוך שמאלה בהתאם למקרה שמביאים לנו. או במילים אחרות, יש מיקומים מסויימים, שאנחנו יכולים להגיע אליהם בהיפוך 1 או ב 2 היפוכים או 10 היפוכים. והמשימה שלנו היא לדעת מהו המינימום היפוכים האפשרי, להגיע לכל נקודה. אבל אם מראש נסמן את המיקום הרחוק ביותר ימינה, שניתן להגיע בהיפוך 1 ימינה, אז משם נוכל לדעת בוודאות, שמכאן ואילך ימינה, אפשרי להגיע רק ב 2 היפוכים ומעלה. ואחר כך נסמן שוב ימינה את הנקודה הרחוקה ביותר שאפשרי להגיע אליה עם 2 היפוכים ימינה. ונדע בוודאות, שאין שום אפשרות להגיע ימינה ממנה, בפחות מ 3 היפוכים וכולי. דהיינו, השלב הראשון בלפתור את התרגיל, הוא לרוץ על המערך ANS החל מנקודת ההתחלה של P לכיוון ימינה ... על עבר 2 הקצוות, של עוגנים ונקודות של וודאות, שבכל נקודה אנחנו יודעים בוודאות שלא ניתן להגיע אליה, בפחות היפוכים מהערך שכתוב בה. כי כמו שאמרנו בדוגמה הקודמת, אנחנו יודעים בוודאות, שאין שום אפשרות בעולם להגיע למיקום 3 בפחות מ 1 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 6 בפחות מ 2 היפוכים. ומכך נובע שאין שום אפשרות להגיע למיקום 9 בפחות מ 3 היפוכים וכולי, ואין שום אפשרות להגיע למיקום 18 בפחות מ 6 היפוכים כנל. ואחרי שפתרנו את כל העוגנים הראשונים של הוודאות, הרי שבעצם עכשיו השאלה הפכה להיות הרבה יותר קלה. ונסתכל רגע על המקרה הקודם: אם נסתכל לצורך העניין על מיקום 19 או 20, אנחנו לא צריכים לנסות להבין בכמה היפוכים ניתן להגיע אליהם ממיקום P=0. אלא אנחנו צריכים לנסות להבין בכמה היפוכים ניתן להגיע ממיקום 18 למיקום 19 או 20. ולמיקום 18, אנחנו כבר יודעים שבוודאות צריך 6 היפוכים. או אם נסתכל על מיקום 10 או 11, אנחנו לא צריכים לנסות להבין בכמה היפוכים אפשרי להגיע לשם ממיקום P=0. אלא אנחנו ננסה להבין מהי הדרך הקצרה ביותר להגיע אליהם ממקום 9 שאליו צריך 3 היפוכים, או אולי ממקום 12 שאליו צריך 4 היפוכים. ואם K הוא אי זוגי, אז יהיה עוד יותר קל לפתור את זה. ואם K הוא זוגי, גם קל ... בתוך K עצמו בלבד. בלי קשר לנקודת ההתחלה של P. דהיינו, אנחנו צריכים להבין, במידה ולדוגמה K=11. תוך כמה היפוכים ניתן להגיע ממיקום 1 למיקום 3-5-7-9. ואם K = 6, אנחנו צריכים להבין תוך כמה היפוכים אפשרי להגיע ממיקום 1 למיקום 2-3-4-5. כי אלו בעצם הטווחים שאליהם אנחנו רוצים להגיע בתוך הוודאות שמצאנו קודם. בקיצור... לשם הפתרון במהותו הוא, לסמן קודם כל את כל נקודות הוודאות לגבי הנקודות הרחוקות ביותר שאליהן צריך לפחות X היפוכים. והכל בהתאם למיקומים חסומים. ומכאן ואילך עלינו רק לסמן את המיקומים שבין המיקומים הוודאיים שאנחנו כבר יודעים אותם. בהצלחה.
050-3331-331