חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... <= 106 1 <= cost2 <= 106 אז קודם כל נסביר את השאלה שהולכת כך: נותנים לנו רשימת של מספרים. לדוגמה [2,3,3,3,5]. עלינו לגרום לכל המספרים, להפוך להיות בערך של המספר הגדול ביותר שנמצא ברשימת המספרים. את זה ניתן לעשות באמצעות פעולה של הוספת הערך 1 לכל המספרים, עד שהם יגיעו לערך הרצוי. לדוגמה, נניח שאנחנו רוצים להפוך את המספר 2 למספר 5, אז אנחנו צריכים לעשות ... המספר 2 למספר 5. ובדוגמה הנל [2,3,3,3,5], המספר הגדול ביותר ברשימה, הוא 5 ולכן אנחנו נרצה להפוך את כל המספרים לערך 5, דהיינו, שבסוף התהליך הרשימה תיראה כך: [5,5,5,5,5]. ולשם כך עלינו לעשות 9 פעולות של הוספת הערך 1, לכל אחד מהמספרים, כדי שבסופו של תהליך, כל הערכים יהיו זהים לערך של המספר הגדול ביותר. את זה נעשה באמצעות פעולות ההוספה ... אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנל. אבל כמו כן, באפשרותך בפעולה אחת, הגדלה ... ערכים שונים, כל אחד מהם מגדילים אותו בערך 1. כאשר בדוגמה הנל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל ... של 1 בכל פעם, או של 2 פעולות הוספה של 1 בכל פעם. וכאן העלילה מסתבכת. מביאים לנו 2 מספרים נוספים COST1 + COST2. דהיינו, לכל פעולת הוספה יש מחיר. אם נוסיף רק 1 בודד בכל פעם, תהיה לזה ... a cost of 2. nums becomes [5,5,5,5,5]. The total cost is 6. ועכשיו השאלה הנשאלת היא כדלקמן: בהינתן רשימת מספרים כלשהי באורך כלשהו, לדוגמה המספרים הבאים (ובכוונה אני מביא כאן רשימה ארוכה, כדי להמחיש את הקושי של השאלה) [1, 42, 73, 18, 90, 55, ... ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו נצעד אל התשובה כך: אז איך בעצם ניגשים לזה? אז ... שוב על השאלה מההתחלה וננסה לחלק את כל התהליך לחלקים הכי קטנים, לדוגמה כך: שואלים אותנו: נותנים לנו רשימת מספרים. עלינו להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת באמצעות פעולת הוספה של הערך 1, לכל אחד מהמספרים, עד שניישר קו של כל המספרים. נעצור כאן לרגע אחד. האם עד כאן היינו יודעים איך לנתח את המצב הזה? תשובה: כנראה שכן. בתור התחלה, היינו מאתרים את המספר הגדול ביותר ברשימה. ואחר כך היינו מוספים את הערך 1 לכל אחד מהמספרים. היינו עושים זאת X פעמים, עד שהיינו מיישרים קו של כל המספרים. עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט סופרים את כל פעולות ההוספה של הערך 1. היינו מכפילים את כמות פעולות ההוספה בערך של מחיר1, והיינו מגיעים לעלות שלנו ליישר את כל המספרים כלפי מעלה. ונעצור כאן לרגע וננתח את הנל. בעצם יש לנו כאן כמה שלבים. שלב 1 - איתור המספר הגדול ביותר ברשימה. שלצורך העניין ברשימה הנל המספר הגדול ביותר הוא 100. שלב 2 - לעבור על כל המספרים, ולבצע פעולה של 100 פחות הערך בכל מיקום. וכך נקבל את כמות ההוספות שעלינו לבצע כדי להביא את המספר ... אציין ואומר, שבעצם יש לנו כאן במהות 2 תהליכים. 1 - איתור המספר הגדול ביותר. 2 - הגדלת כל המספרים וסכימה של הערכים וכולי. האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך ... כל הרשימה, נוכל לדעת מהו המספר הגדול ביותר. ואז מכך נוכל לבצע חישוב של: הערך הגדול ביותר, כפול כמות המספרים ברשימה. ואז נוכל להסיק מכך את הערך המקסימאלי שהיה, אם כל הערכים ברשימה היו בגודל של הערך הגדול ביותר. לדוגמה במקרה הנל, 50 ערכים 100 שהוא הערך הגדול ביותר, = 5000. עכשיו, אם נסכום את כל המספרים, אז נראה שהערך שלהם הוא X. ואז 5000 פחות X, זה בעצם ההפרש שבין הערכים הנוכחיים לבין מקרה שבו ... היו באותו הגודל המקסימאלי. ו ה X הזה, מייצג את כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים לערך המקסימאלי שלהם. ולתובנה הזאת, שניתן לחשב את הכל בריצה אחת, ניתן להגיע באמצעות ניסוי ידני, שבו פותרים את ... בזמן ריצה שהוא O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ובהינתן אפשרות אחת ויחידה להגדיל את המספרים כנל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את כמות הפעמים שניתן לבצע את פעולת ההגדלה הזאת? ואסביר: נשים רגע ... ננסה לחשוב אך ורק על החלק של כמה פעמים ניתן לבצע פעולת הגדלה כפולה, שבה בבת אחת מגדילים שני מספרים בערך 1, עד שכל המספרים מגיעים לערך הגבוה ביותר. האם נדע איך לחשב את זה? כי אם לא, אז ממילא לא נוכל לפתור את ... של למצוא את המספר הגדול ביותר. יש לנו גם תהליך של לחשב כמה פעמים נצטרך לבצע הגדלה של כל המספרים בכל פעם מספר אחד, עד למקסימום. יש לנו גם תהליך של לחשב, כמה מקסימום פעמים נוכל לבצע הגדלה כפולה ... לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר הגדלות כפולות, ורק לאחר מכן הגדלות בודדות, כמה ... ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימלי שנוכל לשלם, כדי להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל ... איך נבצע את ההגדלות. או במילים אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא: בהינתן רשימת מספרים, שעלינו להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו להבין האם כדאי ... כמות ההגדלות שצריך לבצע, היא עצמה זוגית, דהיינו, לדוגמה במקרים הבאים: [2,100] [2,2,2,100] [2,2,2,2,2,100] [2,2,2,2,2,2,2,100] שצריכים להגדיל את כל המספרים ב 98 שזה מספר זוגי, אז שוב כנל, ניקח את סהכ ההגדלות שצריכים לבצע, לחלק ל 2. וזו תהיה כמות ההגדלות הכפולות שניתן לבצע. אבל אם נצטרך להגדיל את המספרים בערך אי זוגי וכמות המספרים עצמם שנצטרך להגדיל תהיה אי זוגית, לדוגמה: [1,100] [1,1,1,100] [1,1,1,1,1,100] [1,1,1,1,1,1,1,100] שיש לנו כמות אי זוגית של עמודות שצריכים ... אנחנו הכי צריכים להגדיל. דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו צריכים להגדיל את כל המספרים, כך עלינו לחפש את הערך MIN, שהיא העמודה עם המספר הקטן ביותר, שבה אנחנו צריכים לבצע את כמות ההגדלות ... פעולות הגדלה כדי להביא אותו לערך MAX. עכשיו, אם ננתח בצורה ידנית המון מקרים, נראה כי בעצם בהינתן רשימת מספרים כלשהי, הרי שיש לנו עמודה אחת או יותר של הערך MAX. ויש לנו עמודה אחת או יותר של הערך ...