חידת LeetCode Solution - Minimum Cost to Equalize Array, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... ביותר. 2 - הגדלת כל המספרים וסכימה של הערכים וכולי. האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך בשלב 1 לעבור על כל הרשימה, כדי לאתר את המספר הגדול ביותר. ורק אחר ... הערכים להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות: 1 - לנסות לאתר כל המספר הגדול ביותר. 2 - באותה ריצה, לסכום את כל הערכים שיש לנו ברשימה. דהיינו, הערך במיקום 1 + הערך במיקום 2 + הערך במיקום 3 וכולי, כמו שהם, בלי לבצע שום חישוב נוסף. בסוף ריצה אחת על כל הרשימה, נוכל לדעת מהו המספר הגדול ביותר. ואז מכך נוכל לבצע חישוב של: הערך הגדול ביותר, ... כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים לערך המקסימאלי שלהם. ולתובנה הזאת, שניתן לחשב את הכל בריצה אחת, ניתן להגיע באמצעות ניסוי ידני, שבו פותרים את התרגיל שוב ושוב בצורה ידנית כמה פעמים. נניח שהרשימה היא ... כל הערכים כלפי מעלה. במילים אחרות, על ידי ניסוי ידני כמה פעמים של פתירת התרגיל הנל, ניתן לראות שבזמן ריצה O(N) ניתן לפתור את התרגיל הנל, כנל. שניתן בריצה אחת, לאתר את המספר הגדול ביותר ולפתור את הכל. ובעצם עד כה, לקחנו את השאלה המקורית וחילקנו אותה לחלקים. ... שהוא יחסית קל, שבו יש לנו רק מחיר1 ועלינו לחשב את מחיר1 בלבד. וראינו שבעצם ניתן לעשות זאת בזמן ריצה שהוא O(N). ועכשיו נמשיך לחלק לחלקים ונעבור לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ... לדעת, מהו המחיר המינימלי שעלינו לשלם כדי להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם היינו יודעים מראש, איך הכי יעיל למלא את הרשימה, אז היה יותר קל לחשב את העלות. דהיינו, ... MIN הוא 1. וכל השאר הם ערכים שנמצאים בין ה MAX לבין הערך MIN. אז לצורך העניין ניקח את המטריצה שלנו ונסתכל עליה בצורה הבאה. נאתר את הערך MAX שאליו אנחנו צריכים להגדיל את כל המספרים. נאתר גם עמודה ... אותם אל MAX, בהתאם לחישובים לעיל. ואחרי שהבנו את כל זה, עכשיו נראה שאפשרי לעשות את כל זה, בזמן ריצה של O(N). דהיינו, בריצה אחת בלבד. ואיך? נרוץ פעם אחת על כל הרשימה. תוך כדי ריצה אחת, נאתר את MAX ונאתר את MIN ונסכום את סהכ כל המספרים באופן כללי. לאחר מכן, נכפיל את MAX ...