חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... 1 בכל פעם. וכאן העלילה מסתבכת. מביאים לנו 2 מספרים נוספים COST1 + COST2. דהיינו, לכל פעולת הוספה יש מחיר. אם נוסיף רק 1 בודד בכל פעם, תהיה לזה עלות של COST1. ואם נוסיף 1 בשני מקומות בו זמנית, תהיה לזה עלות של COST2. לדוגמה, נניח שמחיר1 (COST1) הוא 2 אז אם נבצע 9 פעולות של הוספת 1, הרי שעלות ההוספות תהיה 18. ואם נניח שמחיר2 (COST2) הוא 1, אז בדוגמה הנל נבצע 4 הוספות של מחיר2, דהיינו, עלות 4, כי לכל פעולת הוספה יש עלות של 1. ובנוסף נוסיף עוד עלות של מחיר1 שהיא 2. והרי שיש לנו עלות של 6. כי בדוגמה הנל עשינו 4 הוספות כפולות בעלות של מחיר2 שהוא 1. 41=4. ועשינו גם פעולה אחת של הוספה 1 שהיא בעלות של מחיר1 שהוא 2. ואז 4+2 = 6. כמו בדוגמה שהם הביאו Example 2: Input: nums = [2,3,3,3,5], cost1 = 2, ... 94, 48, 21, 97, 50, 23, 89, 37, 62, 4, 79, 18, 93, 58, 14, 81, 28, 85] ובהינתן מחיר1 + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו ... זאת X פעמים, עד שהיינו מיישרים קו של כל המספרים. עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט סופרים את כל פעולות ההוספה של הערך 1. היינו מכפילים את כמות פעולות ההוספה בערך של מחיר1, והיינו מגיעים לעלות שלנו ליישר את כל המספרים כלפי מעלה. ונעצור כאן לרגע וננתח את הנל. בעצם יש לנו ... הרשימה ולסכום את הכמות של כל פעולות ההוספה. שלב 4 - עלינו להכפיל את כמות פעולות ההוספה, בעלות של מחיר1 וכך יש לנו את התוצאה, של מה העלות שלנו ליישר את כל הרשימה כלפי מעלה. או שיכולנו גם בשלב ... ובעצם עד כה, לקחנו את השאלה המקורית וחילקנו אותה לחלקים. התחלנו במקרה שהוא יחסית קל, שבו יש לנו רק מחיר1 ועלינו לחשב את מחיר1 בלבד. וראינו שבעצם ניתן לעשות זאת בזמן ריצה שהוא O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה ... סיכום ביניים של מה שהבנו עד כה. ועכשיו נעבור לחלק נוסף של השאלה, שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך ... האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם ... את העלות. דהיינו, אם ננתח את כל האפשרויות, נראה שבסופו של דבר, יש רק 3 אפשרויות אפשריות. שהן: מבחינת המחיר שנשלם: 1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה. 2 - זה כן משנה ולכן ... בעצם ניגשים לזה? אז אם נעשה קצת סימולציות באופן ידני וננסה למצוא את החוקיות, נראה שהחישוב הוא כך: אם מחיר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 הגדלות כפולות (סהכ 200) ונצטרך לבצע עוד 300 הגדלות בודדות. ומכך נוכל לחשב את העלות המינימלית, בהכפלה של מחיר1 + מחיר2 בהתאם. במילים אחרות, כרגע ניתן להבין שבעצם כדי לפצח את השאלה המקורית, בסך הכל עלינו לגלות איך יודעים כמה ...