חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... [5,5,5,5,5]. ולשם כך עלינו לעשות 9 פעולות של הוספת הערך 1, לכל אחד מהמספרים, כדי שבסופו של תהליך, כל הערכים יהיו זהים לערך של המספר הגדול ביותר. את זה נעשה באמצעות פעולות ההוספה הבאות: [2+1+1+1, 3+1+1, 3+1+1, 3+1+1, 5]. דהיינו, באמצעות 9 פעולות הוספה של הערך 1, נוכל להפוך את כל הערכים שברשימה לערך הגדול ביותר, שהוא הערך 5. דהיינו, אם אנחנו מבצעים בכל פעם פעולה אחת של הגדלה 1 בלבד, ... ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנל. אבל כמו כן, באפשרותך בפעולה אחת, הגדלה של שני ערכים שונים ב 1. דהיינו, בבת אחת להוסיף בשני מקומות שונים, את הערך 1, כדי ליישר קו שהכל יהיה בערך ... 9 פעולות של הוספת הערך 1, במקום זה נוכל לבצע 5 פעולות של הוספת 1, כדי ליישר את כל הערכים לערך 5. במהות, בכל פעולה, אנחנו מגדילים 2 ערכים שונים, כל אחד מהם מגדילים אותו בערך 1. כאשר בדוגמה הנל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל הערכים יהיו זהים ערך הגדול ביותר. ואנחנו יכולים לבצע את זה, או באמצעות פעולת הוספה של 1 בכל פעם, או ... יש לנו כאן במהות 2 תהליכים. 1 - איתור המספר הגדול ביותר. 2 - הגדלת כל המספרים וסכימה של הערכים וכולי. האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך בשלב 1 לעבור ... צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות: 1 - לנסות לאתר כל המספר הגדול ביותר. 2 - באותה ריצה, לסכום את כל הערכים שיש לנו ברשימה. דהיינו, הערך במיקום 1 + הערך במיקום 2 + הערך במיקום 3 וכולי, כמו שהם, בלי ... חישוב של: הערך הגדול ביותר, כפול כמות המספרים ברשימה. ואז נוכל להסיק מכך את הערך המקסימאלי שהיה, אם כל הערכים ברשימה היו בגודל של הערך הגדול ביותר. לדוגמה במקרה הנל, 50 ערכים 100 שהוא הערך הגדול ביותר, = 5000. עכשיו, אם נסכום את כל המספרים, אז נראה שהערך שלהם הוא X. ואז 5000 פחות X, זה בעצם ההפרש שבין הערכים הנוכחיים לבין מקרה שבו כל הערכים היו באותו הגודל המקסימאלי. ו ה X הזה, מייצג את כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים ... 9 פעולות אבל מצד האמת, אפשרי לחשב זאת גם כך: (5 5 = 25) דהיינו, המקסימאלי שהיה אם כל הערכים היו זהים לערך הגדול ביותר, שהוא 5 כנל. (2+3+3+3+5 = 16) דהיינו, סכום נוכחי של כל הערכים. ואז: 25-16=9. דהיינו, עלינו לבצע 9 הגדלות, כדי ליישר את כל הערכים כלפי מעלה. במילים אחרות, על ידי ניסוי ידני כמה פעמים של פתירת התרגיל הנל, ניתן לראות שבזמן ריצה O(N) ... לא נוכל לפתור את השאלה הגדולה. אז איך בעצם יודעים כמה פעמים ניתן לבצע הגדלה כפולה, דהיינו, שמגדילים שני ערכים בבת אחת? תשובה: נגיע לזה בהמשך. אבל כרגע נחזור לנתח את השאלה המקורית. אז בעצם עד כה, היה לנו ... מספר אחד, עד למקסימום. יש לנו גם תהליך של לחשב, כמה מקסימום פעמים נוכל לבצע הגדלה כפולה של שני ערכים בבת אחת. ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X ... לנו את כל שאר העמודות שבאמצע. לדוגמה [1,2,3,4,5,6,7,8,9,10] הערך MAX הוא 10. הערך MIN הוא 1. וכל השאר הם ערכים שנמצאים בין ה MAX לבין הערך MIN. אז לצורך העניין ניקח את המטריצה שלנו ונסתכל עליה בצורה הבאה. נאתר ... על 1 כדי להביא אותו לערך 10. עכשיו נצטרך לספור את כמות פעולות ההגדלה שעלינו לבצע, על כל שאר הערכים שאינם MAX ושאינם העמודה הבודדת של MIN שהגדרנו קודם. לדוגמה במקרה של [1,2,3,4,5,6,7,8,9,10] יש לנו MAX שהוא 10 יש לנו MIN שהוא 1 שצריכים לבצע עליו 9 הגדלות ויש לנו את שאר הערכים [2,3,4,5,6,7,8] דהיינו, 7 ערכים שצריכים לגדול ל 10. דהיינו, הם צריכים להיות 710=70. ומאחר ש 2+3+4+5+6+7+8 = 35. אז 70-35 = 35. דהיינו, ... אחת של הערך MIN, שהיא צריכה לגדול ב MAX -MIN פעמים כדי להיות בערך MAX. ויש את כל שאר הערכים, שהכמות שלהם כפול MAX פחות הסכום שלהם, שווה לכמות ההגדלות שאנחנו צריכים לבצע עליהם. בדוגמה הנל, כמות הערכים היא 7, כפול MAX שהוא 10, פחות הסכום שלהם שהוא 35, יוצא 35 שזאת כמות ההגדלות שצריכים לבצע. ועכשיו נראה ... לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת זהה לכמות ההגדלות שאנחנו צריכים לבצע על כל שאר ערכי הביניים, כדי להביא אותם לערך MAX. לדוגמה: אפשרות 2 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת גדולה מכמות ההגדלות שאנחנו צריכים לבצע על כל שאר ערכי הביניים, כדי להביא אותם לערך MAX, שעליהם צריכים לבצע כמות הגדלות קטנה יותר. אפשרות 3 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת קטנה מכמות ההגדלות שאנחנו צריכים לבצע על כל שאר ערכי הביניים, כדי להביא אותם לערך MAX, שעליהם צריכים לבצע כמות הגדלות גדולה יותר. לדוגמה: ואם נחקור את החוקיות של 3 ... אם כמות ההגדלות שאנחנו צריכים לבצע, כדי להביא את MIN ל MAX, היא זהה לכמות ההגדלות האחרות של כל ערכי הביניים, הרי שכמות ההגדלות הכפולות שניתן יהיה לבצע, תהיה הכמות הכללית של ההגדלות שצריכים לבצע, לחלק ל 2. או במילים אחרות, כמות ההגדלות הכפולות שנבצע, תהיה זהה ל MAX פחות MIN וזהה גם לסהכ ההגדלות שצריכים לבצע על כל ערכי הביניים כדי שיגיעו ל MAX. לדוגמה: אם MAX = 5 ו MIN = 0. אז אנחנו צריכים לבצע 5 הגדלות ... אם כמות ההגדלות שאנחנו צריכים לבצע, כדי להביא את MIN ל MAX, היא גדולה מכמות ההגדלות האחרות של כל ערכי הביניים, הרי שכמות ההגדלות הכפולות שניתן יהיה לבצע, תהיה כמות ההגדלות של כל ערכי הביניים בלבד (ללא כמות ההגדלות של MIN אל MAX), לחלק ל 2. כאשר בנוסף נצטרך לבצע עוד הגדלות בודדות כדלקמן. ... חוץ מההגדלה הזאת, היא קטנה מ 5, לדוגמה היא 4. הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 4. ובנוסף נצטרך לבצע עוד הגדלה בודדת אחת (5 פחות 4 שווה 1), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות כמות ההגדלות שצריכים לבצע על כל שאר ערכי הביניים. או לדוגמה: אם MAX = 27 ו MIN = 3. אז אנחנו צריכים לבצע 24 הגדלות כדי להגיע מ ... חוץ מההגדלה הזאת, היא קטנה מ 24, לדוגמה היא 11. הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 11. ובנוסף נצטרך לבצע עוד 13 הגדלות בודדות (24 פחות 11 שווה 13), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות כמות ההגדלות שצריכים לבצע על כל שאר ערכי הביניים. או לדוגמה: אם MAX = 16 ו MIN = 6. אז אנחנו צריכים לבצע 10 הגדלות כדי להגיע מ ... חוץ מההגדלה הזאת, היא קטנה מ 10, לדוגמה היא 8. הרי שכמות ההגדלות הכפולות, תהיה זהה לכמות ההגדלות של ערכי הביניים, דהיינו, 11. ובנוסף נצטרך לבצע עוד 2 הגדלות בודדות (10 פחות 8 שווה 2), עפ נוסחה של, כמות ההגדלות שצריך כדי להגיע מ MIN אל MAX פחות כמות ההגדלות שצריכים לבצע על כל שאר ערכי הביניים. אפשרות 3 - אם כמות ההגדלות שאנחנו צריכים לבצע, כדי להביא את MIN ל MAX, היא קטנה מכמות ההגדלות האחרות של כל ערכי הביניים, הרי שכמות ההגדלות הכפולות שניתן יהיה לבצע, תהיה כמות סך כל ההגדלות של כל העמודות, כולל MIN אל MAX וכולל של כל שאר ערכי הביניים אל MAX, לחלק ל 2. כאשר אם הכמות של סהכ ההגדלות היא זוגית, אז כמות ההגדלות הכפולה, תהיה סהכ ...