חידת LeetCode Solution - Block Placement Queries, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... כנל. הבהרה: המכשול עצמו תופס 0 מקום. לדוגמה: queries[i] = [1, 10] פירושו, תציב מכשול בנקודה 10 על ציר המספרים. כאשר המכשול עצמו לא תופס מקום. שאילתה מסוג 2 מוצגת כך: queries[i] = [2, x, sz] כאשר הספרה הראשונה ... כן חלק מהשאילתות, הן מסוג 2, דהיינו, הן שואלות אותנו, האם בהתאם למחסומים שהצבנו עד כה על גבי ציר המספרים, האם עד כה ניתן למקום את הבלוק ברוחב מוגדר כלשהו, עד למיקום X כלשהו. כאשר כל שאילתה מסוג 2, ... אז אם נתבונן נראה, שבעצם אנחנו מחפשים למצוא דרך, איך נוכל בדרך הקצרה ביותר, לדעת, על מיקום כלשהו בציר המספרים שלנו, מהו הטווח הגדול ביותר שניתן להציב בתוכו בלוק ברוחב כלשהו. ואיך ניתן לעשות זאת בכמה שפחות פעולות. לדוגמה: ... שונים. אז, בדרך הארוכה ביותר, היינו יכולים לעשות במקרה הגרוע ביותר 1M פעולות, כדי לעבור על כל המקומות ברשימת המספרים. בפתרון הקודם שהצענו, הרי שאם יש לנו 5000 מכשולים, הרי שיש לנו 5000 טווחים של גדלים שבהם ניתן להכניס ... יכולים להכניס מכשול ברוחב 10, בין 6 לבין 15. אז מהי בעצם החוקיות כאן לגבי מכשול שני, שממוקם בציר המספרים אחרי המכשול הראשון? תשובה: החוקיות היא כזאת, כאשר מציבים מכשול שני, עלינו לבדוק את המרחק בינו לבין המכשול שלפניו (בציר המספרים). אם המרחק שבין המכשול השני לבין המכשול הראשון שלפניו (בציר המספרים), הוא קטן מהטווח המקסימאלי שהגדרנו עבור המכשול הראשון, אז הטווח המקסימאלי של המכשול השני, יהיה כמו של המכשול שלפניו (בציר המספרים). (הערה: לפניו / אחריו, פירושו ביחס לציר המספרים ולא ביחס לסדר הצבת המכשולים) לדוגמה: אם הצבנו מכשול ראשון ב 5 והטווח המקסימאלי שלו הוא 5, והצבנו אחריו ... את הדבר הבא: בכל פעם שנציב מכשול במיקום כלשהו, תמיד נבדוק את הטווח המקסימאלי שמוגדר עבור המכשול שלפניו בציר המספרים. ונבדוק אם הטווח הזה, גדול מהמרחק שבין המכשול הנוכחי החדש, לבין המכשול שלפניו בציר המספרים. ואז נוכל לחשב, האם יש לנו טווח חדש גדול יותר, בין המכשול החדש למכשול שלפניו, או שגם המכשול הנוכחי, מוגבל לטווח המקסימאלי שמוגדר עבור המכשול שלפניו. ובמלים אחרות אנחנו עוד מבינים מכך, שככל שהמכשולים מתרחקים ימינה בציר המספרים, הרי שהטווח האפשרי, יכול רק לגדול. כי הטווח המקסימאלי, יכול רק לגדול. אבל לעולם הוא לא יהיה יותר קטן. ... במיקום 5 כנל. ומה יקרה אם לדוגמה המכשול הראשון יהיה במיקום 5 כנל ואז המכשול הבא יהיה לפניו בציר המספרים, נניח במיקום 2? לדוגמה כך: במקרה כזה, ניתן להבין שעד 2 יהיה מקום למכשול בגודל 2. ובין 3 לבין ... שבמיקום 4 כנל. ומה החוקיות כאן? אז אם נתבונן נראה, שזה בעצם אומר, שברגע שהמכשול השני, הוא נמצא בציר המספרים לפני המכשול הראשון, אז, עלינו קודם כל לבדוק את המרחק שבין המכשול הקטן יותר, לבין המכשול שלפניו, שבמקרה שלנו, ... נשאל את עצמו 2 שאלות: 1 - מה המרחק בין המכשול החדש הגדול יותר, לבין המכשול שקטן ממנו בציר המספרים? 2 - מה הטווח המקסימאלי שמוגדר עבור המכשול שקטן ביותר בציר המספרים. ואז, אם המרחק ביניהם יהיה גדול מהטווח המקסימאלי של המכשול הקטן יותר, הרי שיש לנו טווח מקסימאלי חדש גדול ... 25. במילים אחרות, בעת הצבת מכשול חדש: 1 - בדוק את הטווח המקסימאלי של המכשול שלפניו / מתחתיו בציר המספרים. 2 - בדוק את המרחק בין המכשול החדש לבין המכשול שלפניו. 3 - בהתאם לכך, הגדר את הטווח המקסימאלי ...