חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... פעם. וכאן העלילה מסתבכת. מביאים לנו 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, cost2 = 1 Output: 6 Explanation: The following operations can be performed ... 76, 25, 69, 9, 94, 48, 21, 97, 50, 23, 89, 37, 62, 4, 79, 18, 93, 58, 14, 81, 28, 85) ובהינתן מחיר1 + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו נצעד אל התשובה כך: אז איך בעצם ניגשים לזה? אז לשם כך ... פעמים, עד שהיינו מיישרים קו של כל המספרים. עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט סופרים את כל פעולות ההוספה של הערך 1. היינו מכפילים את כמות פעולות ההוספה בערך של מחיר1, והיינו מגיעים לעלות שלנו ליישר את כל המספרים כלפי מעלה. ונעצור כאן לרגע וננתח את הנל. בעצם יש לנו כאן כמה שלבים. שלב 1 - איתור המספר הגדול ביותר ברשימה. שלצורך העניין ... ולסכום את הכמות של כל פעולות ההוספה. שלב 4 - עלינו להכפיל את כמות פעולות ההוספה, בעלות של מחיר1 וכך יש לנו את התוצאה, של מה העלות שלנו ליישר את כל הרשימה כלפי מעלה. או שיכולנו גם בשלב 3 - לחשב את העלות של ליישר את המספר הנוכחי כלפי מעלה. ובשלב 4 - לעבור על כל ... עד כה, לקחנו את השאלה המקורית וחילקנו אותה לחלקים. התחלנו במקרה שהוא יחסית קל, שבו יש לנו רק מחיר1 ועלינו לחשב את מחיר1 בלבד. וראינו שבעצם ניתן לעשות זאת בזמן ריצה שהוא O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ובהינתן אפשרות אחת ... ביניים של מה שהבנו עד כה. ועכשיו נעבור לחלק נוסף של השאלה, שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם היינו יודעים מראש, איך הכי יעיל למלא את הרשימה, אז היה יותר קל ... דהיינו, אם ננתח את כל האפשרויות, נראה שבסופו של דבר, יש רק 3 אפשרויות אפשריות. שהן: מבחינת המחיר שנשלם: 1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה. 2 - זה כן משנה ולכן עלינו לבצע כמה שיותר, הגדלות כפולות ורק לאחר מכן הגדלות בודדות. 3 - זה כן משנה ולכן עלינו ... לזה? אז אם נעשה קצת סימולציות באופן ידני וננסה למצוא את החוקיות, נראה שהחישוב הוא כך: אם מחיר1 2 הוא קטן ממחיר2, אז בכל מקרה עדיף תמיד לעשות הגדלות בודדות. אם מחיר1 2 הוא זהה למחיר2, אז זה לא משנה איך נבצע את ההגדלות בצורה בודדת או כפולה. אם מחיר1 2 הוא גדול ממחיר2, אז בכל מקרה עדיף תמיד קודם כל לעשות כמה שיותר הגדלות כפולות ורק אחר כך בלית ברירה, לעשות הגדלות בודדות. לדוגמה: אם נניח מחיר1 של הגדלה בודדת אחת, הוא 100 והמחיר2 של הגדלה כפולה הוא 1, אז ברור שנעדיף לשלם כמה שפחות ולבצע כמה שיותר הגדלות כפולות. אבל אם