חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... אנחנו מבצעים בכל פעם פעולה אחת של הגדלה 1 בלבד, נעשה זאת לדוגמה בדרך הבאה: בנוסף אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, ... בערך 1. כאשר בדוגמה הנל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל ... 58, 14, 81, 28, 85) ובהינתן מחיר1 + מחיר2 כלשהם, לדוגמה מחיר1 הוא 10 ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימאלי ההכרחי שנהיה חייבים לשלם, כדי להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו ... אז איך בעצם ניגשים לזה? אז לשם כך נחזור שוב על השאלה מההתחלה וננסה לחלק את כל התהליך לחלקים הכי קטנים, לדוגמה כך: שואלים אותנו: נותנים לנו רשימת מספרים. עלינו להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת ... היינו עושים זאת X פעמים, עד שהיינו מיישרים קו של כל המספרים. עכשיו, נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט ... את פעולות ההגדלה, הסכימה, ההכפלה וכולי? אז לכאורה, אכן צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל ... ניתן לעשות זאת בזמן ריצה שהוא O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ובהינתן אפשרות אחת ויחידה להגדיל את המספרים כנל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את ... אחת. ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה ... שעומד בפני עצמו, והוא, בהינתן לנו מחיר1 שהוא עלות של הגדלה בודדת ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימאלי שנוכל לשלם, כדי להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימאלי שעלינו לשלם כדי להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם ... מחיר1 הוא 1 ומחיר2 הוא 2, אז זה לא משנה איך נבצע את ההגדלות. או במילים אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא: בהינתן רשימת מספרים, שעלינו להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון ... כמה מקסימום הגדלות כפולות ניתן לבצע. אז איך ניגשים לזה? אז איך ניגשים לזה? אז נתחיל מהמקרה הקל ביותר, נניח שיש לנו את הרשימה הבאה (1,2) דהיינו, שאנחנו צריכים להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד. ואם יש לנו את הרשימה (1, 100) דהיינו, שאנחנו צריכים להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות. או במילים אחרות, בטוח נכון שכאשר צריכים להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה. ומה אם יש לנו להגדיל 2 עמודות, לדוגמה (1, 1, 2), שעלינו להגדיל את 2 העמודות של ה 1 אל הערך 2. הרי שניתן לבצע כאן הגדלה אחת כפולה ... את כל הרשימה ל (2, 2, 2). ואם יש לנו רשימה של (1, 1, 100). במקרה כזה נוכל לבצע 99 הגדלות כפולות, שיביאו את הרשימה ל (100,100,100). ואם לצורך העניין נצטרך להגדיל 3 עמודות, לדוגמה (1,1,1,2), הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, ... לבצע בסך הכל ונחלק אותה ל 2. וזאת תהיה כמות ההגדלות הכפולות שניתן לבצע. את השארית, נגדיל בצורה של הגדלה בודדת. ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך להגדיל את כולן באותה כמות הגדלות, אז: אם יש לנו מספר זוגי של עמודות שצריכים להגדיל, לדוגמה: (1,1,100) (1,1,1,1,100) (1,1,1,1,1,1,100) (1,1,1,1,1,1,1,1,100) אז ניקח את סהכ ההגדלות שצריכים לבצע, נחלק ל 2 ונקבל את כמות ההגדלות הכפולות שצריכים לבצע. ואם יש לנו מספר אי זוגי של עמודות שצריכים להגדיל, לדוגמה: (1,100) (1,1,1,100) (1,1,1,1,1,100) (1,1,1,1,1,1,1,100) אז ... לבצע את החישוב הבא: אם כמות ההגדלות שצריך לבצע, היא עצמה זוגית, דהיינו, לדוגמה במקרים הבאים: (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) שיש לנו כמות אי זוגית של עמודות שצריכים להגדיל + צריכים להגדיל כל עמודה ב 99, שזה מספר אי זוגי, אז במקרה כזה, ניקח את סהכ הסכום שצריך להגדיל, נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך ... הבאה: אז החוקיות אומרת כך: כאשר אנחנו באים לנתח את כמות ההגדלות הכפולות שאנחנו יכולים לבצע, עלינו לאתר את העמודה עם הערך הקטן ביותר, שאותה אנחנו הכי צריכים להגדיל. דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו ...
050-3331-331