חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... מסתבכת. מביאים לנו 2 מספרים נוספים COST1 + COST2. דהיינו, לכל פעולת הוספה יש מחיר. אם נוסיף רק 1 בודד בכל פעם, תהיה לזה עלות של COST1. ואם נוסיף 1 בשני מקומות בו זמנית, תהיה לזה עלות של COST2. ... הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר הגדלות כפולות, ורק לאחר מכן הגדלות בודדות, כמה פעמים נוכל לבצע הגדלות כפולות, לפני שנהיה חייבים לבצע הגדלות בודדות. ואחרי שנדע את כל זה, עכשיו נוכל לחשב את העלות של כל ההגדלות. עד כאן זה בעצם סיכום ביניים ... עד כה. ועכשיו נעבור לחלק נוסף של השאלה, שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל ... לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה. אבל זהו כמובן ... של דבר, יש רק 3 אפשרויות אפשריות. שהן: מבחינת המחיר שנשלם: 1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה. 2 - זה כן משנה ולכן עלינו לבצע כמה שיותר, הגדלות כפולות ורק לאחר מכן הגדלות בודדות. 3 - זה כן משנה ולכן עלינו לבצע אך ורק הגדלות בודדות. ומאחר שבסופו של דבר, יש רק 3 אפשרויות בלבד, לכן איך בעצם ניגשים לזה? אז אם נעשה קצת סימולציות ... את החוקיות, נראה שהחישוב הוא כך: אם מחיר1 2 הוא קטן ממחיר2, אז בכל מקרה עדיף תמיד לעשות הגדלות בודדות. אם מחיר1 2 הוא זהה למחיר2, אז זה לא משנה איך נבצע את ההגדלות בצורה בודדת או כפולה. אם מחיר1 2 הוא גדול ממחיר2, אז בכל מקרה עדיף תמיד קודם כל לעשות כמה שיותר הגדלות כפולות ורק אחר כך בלית ברירה, לעשות הגדלות בודדות. לדוגמה: אם נניח מחיר1 של הגדלה בודדת אחת, הוא 100 והמחיר2 של הגדלה כפולה הוא 1, אז ברור שנעדיף לשלם כמה שפחות ולבצע כמה שיותר הגדלות כפולות. אבל אם מחיר2 הוא 100 ומחיר1 הוא 1, אז ברור שנעדיף לבצע כמה שיותר הגדלות בודדות. ואם מחיר1 הוא 1 ומחיר2 הוא 2, אז זה לא משנה איך נבצע את ההגדלות. או במילים אחרות, מכך ... 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו להבין האם כדאי לנו לבצע כמה שיותר הגדלות בודדות או כפולות, באמצעות חישוב המחיר כנל. ואז, אם עלינו לבצע כמה שיותר הגדלות בודדות, או במידה וזה לא משנה איך נבצע את ההגדלות, אז נוכל לפתור את התרגיל כנל, כי בעצם מבחינתנו נוכל לומר שיש רק אפשרות אחת, של הגדלה בודדת, של מחיר1. שאת המצב הזה אנחנו יודעים לפתור כנל. אבל אם ורק אם נגלה, שמחיר2 של הגדלה כפולה, הוא קטן ממחיר1 כפול 2, דהיינו, שאז אנחנו נרצה לבצע כמה שיותר הגדלות כפולות ורק אחר כך בודדות, אז בעצם אנחנו נצטרך לדעת, איך יודעים כמה הגדלות כפולות ניתן לבצע. ואז, ניקח את סך כל ההגדלות שצריך ... מתוך זה 100 הגדלות כפולות. אז נוכל להסיק, שנעשה 100 הגדלות כפולות (סהכ 200) ונצטרך לבצע עוד 300 הגדלות בודדות. ומכך נוכל לחשב את העלות המינימלית, בהכפלה של מחיר1 + מחיר2 בהתאם. במילים אחרות, כרגע ניתן להבין שבעצם כדי ... צריכים להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד. ואם יש לנו את הרשימה [1, 100] דהיינו, שאנחנו צריכים להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות. או במילים אחרות, בטוח נכון שכאשר צריכים להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה. ומה אם יש לנו להגדיל 2 עמודות, לדוגמה [1, 1, 2], שעלינו להגדיל ... לדוגמה [1,1,1,2], הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, שתביא אותנו ל [2,2,1,2] ואז נצטרך לבצע עוד הגדלה בודדת כדי ליישר את כל הרשימה ל [2,2,2,2]. ומה יקרה אם תהיה לנו רשימה כזאת [1,1,1,100] כמה הגדלות כפולות נוכל ... שאנחנו צריכים לבצע 993 הגדלות. דהיינו, 297 הגדלות. ואת זה ניתן לבצע באמצעות, 148 הגדלות כפולות + הגדלה אחת בודדת. אז לכאורה מצאנו לנו חוקיות מסוימת, שאומרת, ניקח את כמות ההגדלות שצריך לבצע בסך הכל ונחלק אותה ל 2. וזאת תהיה כמות ההגדלות הכפולות שניתן לבצע. את השארית, נגדיל בצורה של הגדלה בודדת. ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך להגדיל את כולן באותה כמות הגדלות, אז: אם יש לנו מספר ... נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך בוודאות שנצטרך לבצע עוד הגדלה אחת בודדת של השארית. אבל כל מה שאמרנו עד כאן, נכון, אבל באופן חלקי. ניקח לדוגמה מבני עמודות כאלו: את כל ... בהגדלות כפולות. אבל מה לגבי מבנה כזה: מבנה כזה, נוכל לפתור אותו ב 2 הגדלות כפולות + הגדלה 1 בודדת. ומה לגבי מבנים כאלו? גם אותם לא נוכל לפתור בהגדלות כפולות, אלא נצטרך כמות של הגדלות בודדות. אז מה החוקיות כאן? אז נסתכל לדוגמה על המקרים הבאים: נראה שבכולם, כן ניתן למלא את הכל בהגדלות כפולות. ... על המקרים הבאים: נראה שגם בהם ניתן למלא את כל העמודות עם הגדלה כפולה + בחלק מהמקרים עם הגדלה בודדת כלשהי. אז אם נשחק שוב בצורה ידנית עם המון מקרים, נראה שיש כאן את החוקיות הבאה: אז החוקיות אומרת ... כל המספרים. נאתר גם עמודה אחת בלבד של הערך MIN שעליו אנחנו צריכים לבצע הכי הרבה הגדלות, בין אם בודדות או כפולות כנל. את כל שאר העמודות נתייחס אליהן כאל כל שאר המספרים שבטווח, כולל עמודות נוספות של MIN ... לערך 10. עכשיו נצטרך לספור את כמות פעולות ההגדלה שעלינו לבצע, על כל שאר הערכים שאינם MAX ושאינם העמודה הבודדת של MIN שהגדרנו קודם. לדוגמה במקרה של [1,2,3,4,5,6,7,8,9,10] יש לנו MAX שהוא 10 יש לנו MIN שהוא 1 שצריכים ... זהה ל 5, הרי שבסהכ נוכל לעשות 5 הגדלות כפולות. כי בסך הכל הכללי, אנחנו צריכים לעשות 10 הגדלות בודדות. ו 10 לחלק ל 2, יוצא 5. דהיינו, נוכל לעשות 5 הגדלות כפולות, כדי להגדיל את כל המספרים כולם, ... ערכי הביניים בלבד (ללא כמות ההגדלות של MIN אל MAX), לחלק ל 2. כאשר בנוסף נצטרך לבצע עוד הגדלות בודדות כדלקמן. לדוגמה: אם MAX = 5 ו MIN = 0. אז אנחנו צריכים לבצע 5 הגדלות כדי להגיע מ ... 4. הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 4. ובנוסף נצטרך לבצע עוד הגדלה בודדת אחת (5 פחות 4 שווה 1), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות ... הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 11. ובנוסף נצטרך לבצע עוד 13 הגדלות בודדות (24 פחות 11 שווה 13), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות כמות ... הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 11. ובנוסף נצטרך לבצע עוד 2 הגדלות בודדות (10 פחות 8 שווה 2), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות כמות ... ל 2. ואם הכמות היא אי זוגית, אז סהכ ההגדלות הכפולות תהיה כנל, כאשר בנוסף תהיה גם עוד הגדלה בודדת אחת. לדוגמה: אם MAX = 16 ו MIN = 6. אז אנחנו צריכים לבצע 10 הגדלות כדי להגיע מ ... כל ההגדלות כולן, דהיינו, 6 + 9 שווה 15 לחלק ל 2 שווה 7 פלוס שארית 1 של הגדלה בודדת אחת. וזאת בעצם החוקיות של כמה הגדלות כפולות אנחנו צריכים לבצע, כדי להביא את כל המספרים ל MAX. ואחרי ... הכללית, הוא די פשוט שלב 1 - ננסה להבין האם עלינו לנסות להשתמש בהגדלות כפולות במחיר2 או רק בהגדלות בודדות במחיר 1. איך נדע? כנל, אם מחיר2 יותר זול ממחיר1 כפול 2, אז נעדיף להשתמש במחיר2. אחרת, נשתמש בהגדלות בודדות ובמחיר1. ואם אנחנו לא צריכים להשתמש בהגדלות כפולות, אלא רק בבודדות, אז יש לנו כבר את הפתרון כנל. אבל נניח שעלינו כן להשתמש כמה שיותר בהגדלות כפולות. אז נצטרך: 1 ...