חידת LeetCode Solution - Candy, פתרון ליטקוד, LeetCode Solution, איך לפתור שאלות ב LeetCode? איך לפתור חידת LeetCode? מדעי המחשב, תכנות מחשבים, איך להתקבל לעבוד בהייטק? איך ללמוד תכנות מחשבים? איך להיות מתכנת? איך לעבור ראיון טכני? איך להתכונן לראיון עבודה בהייטק? תרגול שאלות ליטקוד כהכנה לראיון, איך להיות מתכנת מחשבים? איך לעבוד בפיתוח תוכנה? איך להתכונן לראיונות כתיבת קוד? איך לפתור חידת היגיון? חידות היגיון, איך לעבור ראיון עבודה טכני?... הציון שלו הוא 1. ילד 2 הציון שלו הוא 0. ילד 3 הציון שלו הוא 2. עכשיו, עלינו לחלק סוכריות לילדים האלו, עפ החוקים הבאים: חוק 1 - כל ילד צריך לקבל לפחות סוכריה 1. חוק 2 - כל ילד עם ציון יותר גבוה, צריך לקבל יותר סוכריות מאשר כל ילד שצמוד אליו. והחידה היא, מהו מספר הסוכריות המינימלי והקטן ביותר שצריך לתת לילדים האלו? כדי ליישם את 2 החוקים הקודמים. וכמובן שעלינו למצוא נוסחה כללית שתתאים ... ננסה להבין אותה יותר טוב. בעצם נותנים לנו רשימה של ילדים ולכל ילד נותנים ציון כלשהו. ואנחנו צריכים לחלק סוכריות לילדים לפי הציון שלהם ולפי 2 חוקים כלשהם. כאשר אנחנו אמורים לנסות לתת כמה שפחות סוכריות לילדים. עכשיו, אם נתבונן בשאלה נבין, שכמות הסוכריות שאנחנו צריכים לחלק לילדים, תלויה אך ורק בציון שלהם ולא בשום דבר אחר. שזה בעצם אומר, שאת הסוכריות אנחנו כאילו מחלקים לציונים ולא לילדים. שזה בעצם אומר, שאנחנו יכולים להתעלם מכך שיש בכלל ילדים ואנחנו יכולים לנסח ... אותה בצורה יותר פשוטה ושונה, כדלקמן: יש לנו רשימת מספרים כלשהי ועלינו לשים על כל מספר X כלשהו של סוכריות, בהתאם ל 2 חוקים. מהו המספר המינימלי של סוכריות שצריך לשים על רשימת המספרים. ובעצם ככה אנחנו יכולים לנסח ולהבין את השאלה בצורה יותר פשוטה. עכשיו ננסה להבין את 2 החוקים של חלוקת הסוכריות. חוק 1 אומר, שלכל מספר, צריך לתת לפחות סוכריה 1. חוק 2 אומר, שכל מי שהמספר שלו יותר גבוה, מקבל יותר סוכריות ממי שנמצא לידו. וצריך לשים לב, שאם מישהו עומד ליד מישהו שיש לו ערך זהה, לגביו אין את האילוץ שהוא יקבל יותר סוכריות ממי שעומד לידו (כמו שניתן לראות בדוגמה ה 2 שהם הביאו באתר שלהם, במקרה של [1,2,2] ). דהיינו, יכול להיות שכמה ילדים עם אותו הציון, יקבלו מספר שונה של סוכריות, בהתאם למי שהם עומדים לידו. אז איך בעצם ניגשים לפתור את השאלה הזאת? אז בעצם יש לנו כאן 2 תהליכים. תהליך 1 הוא לחשב מה מינימום הסוכריות שצריך לקבל כל ילד. תהליך 2 הוא לחשב כמה סהכ סוכריות קיבלו כל הילדים. וכמובן שניתן להבין שתהליך החישוב של מה מינימום הסוכריות שצריך לקבל כל ילד שנמצא ברשימה, הוא התהליך הראשון ובמקרה הוא גם התהליך הקשה יותר בחישובים, ולכן נתחיל ממנו. אז איך נדע כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה? אז ננסה לחלק את זה לחלקים. במקום לשאול את השאלה של כמה מינימום סוכריות צריך לקבל כל ילד שנמצא ברשימה? במקום זה ננסה לשאול בצורה יותר פשוטה, כמה מינימום סוכריות צריך לקבל ילד 1 מסוים שעומד ברשימה? ולכאורה זה אולי נראה אותה השאלה, ואפילו אפשרי לומר שזאת כמעט אותה השאלה. אבל באמת אלו 2 צורות שונות לפקס את המוח. ובמקום לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל כל ילד, צריך לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל הילד ה X ברשימה. דהיינו, לנסות לחשוב רק על ילד 1 בלבד. עכשיו ננסה להפוך את השאלה ... שעומד בשורה. אז נניח שיש לנו את השורה הבאה [0,1,2,3,4,5,6,7] דהיינו, שהילד הראשון הערך שלו הוא 0. אז כמה סוכריות הוא צריך לקבל הכי פחות? תשובה: 1. כי הוא יכול לקבל את המינימום ההכרחי של סוכריות. ואין לו ציון יותר גבוה משום ילד אחר ברשימה. האם זאת האמת? כן. האם זאת תמיד האמת? כן. האם ... 56, 84, 93, 78, 49, 30, 12, 76, 98, 13, 61] דהיינו, שהציון של הילד הראשון הוא 73. כמה סוכריות צריך לקבל הילד הראשון? איך מחשבים את זה? איך ניגשים לזה? אז כאשר אנחנו מנתחים את הדרך לפתור את ... הקושי לגשת לתשובה, זה בגלל שכל מספר הציון שלו, הוא מושפע מהציון של מי שלידו. ולכן קשה להבין כמה סוכריות מקבל כל ילד. אבל האם זאת כל האמת? האם באמת אין בכל הבלאגן הזה משהו שהוא בטוח נכון? והתשובה היא שיש. והמקרה הפשוט ביותר, הוא המקרה שבו כמות הסוכריות שנותנים לילד, לא תלויה בדירוג של הילד שלידו. שזהו בעצם המקרה הפשוט ביותר. אבל האם באמת יש מקרה כזה? ... היא שכן. דהיינו, כל ילד שהדירוג שלו לא יותר גדול מאשר של הילד שלידו, הרי שאותו הילד אמור לקבל סוכריה 1 ולא יותר. כי עליו חל חוק 1 ולא חוק 2. כי חוק 2 אומר שכל ילד שהדירוג שלו גדול משל הילד שלידו, הוא צריך לקבל יותר סוכריות מאשר הילד שלידו, אבל אם הדירוג של הילד, הוא קטן או זהה לכל הילדים שלידו, הרי שהוא צריך לקבל סוכריה 1 בלבד. וזה בעצם אומר, שבשלב הראשון, אנחנו נעבור על הרשימה וכל ילד שנמצא ברשימה שהדירוג שלו לא יותר גדול (דהיינו קטן או זהה) לדירוג של הילד שלידו, אנחנו ניתן לו סוכריה 1. כי זה בטוח נכון ואין שום אפשרות אחרת. לדוגמה ברשימה [5,4,3,2,3,4,5] הילד שיש לו את הערך 2, הוא בטוח צריך לקבל סוכריה 1 בלבד. כי הוא לא יותר גדול מ 2 הילדים שלידו. וכל ילד צריך לקבל לפחות סוכריה 1. ולכן הוא צריך לקבל סוכריה 1. או לדוגמה ברשימה הזאת: [7,6,6,5,4,0,1,2,3,2] שמעכשיו נייצג אותה כך: מקום 01 [דירוג 7 = כמות? ] מקום 02 ... לו דירוג 0 וגם הילד במקום העשירי שיש לו את הדירוג 2 גם שניהם בטוח צריכים לקבל כמות של סוכריה 1, כי הם לא יותר גדולים משום דירוג אחר שעומד לידם. ועכשיו הרשימה שלנו תיראה כך: מקום 01 [דירוג ... 1] אז בעצם בשיטה הזאת, מצאנו משהו שהוא בטוח נכון, דהיינו, את כל הילדים שצריכים לקבל כמות וודאיות של סוכריה 1 בלבד. ועכשיו בשיטה דומה לזאת, נחפש משהו שהוא בטוח נכון, ונגלה שהחוק הוא, שכל מי שנמצא ליד מקום שיש לו כמות וודאית של סוכריות דהיינו, של 1 ושהוא לא יותר גדול ממישהו אחר שעומד לידו ושעדיין לא קיבל סוכריות, הרי שהוא צריך לקבל כמות וודאית של 2 סוכריות, דהיינו, כמות גדולה ב 1 יותר מהכמות שלידו. וכך נקבל את התוצאה הבאה: מקום 01 [דירוג 7 = כמות ... [דירוג 3 = כמות? ] מקום 10 [דירוג 2 = כמות 1] בגלל ש: מקום 1 - מקבל 2 סוכריות, כי הוא ליד כמות וודאית של 1 סוכריות (ולכן הוא מקבל כמות גדולה ב 1) + הוא לא יותר ...