... LeetCode Solution - Block Placement Queries, פתרון ליטקוד, LeetCode Solution, לפתור
שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק,
שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד ... 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2. אז קודם כל נסביר את
השאלה שהולכת כך: נתון לפנינו: ציר קו באורך אין ... לנו רשימה של שאילתות, שמורכבת מ 2 סוגים של שאילתות: סוג 1 של שאילתה, אומר לנו לשים מחסום בנקודה X בקו שלנו. סוג 2 של שאילתה,
שואל אותנו, האם ניתן לשים על הציר שלנו, בלוק ... עצמו לא תופס מקום. שאילתה מסוג 2 מוצגת כך: queries(i) = (2, x, sz) כאשר הספרה הראשונה היא 2, זה אומר שמדובר על שאילתה מסוג 2,
ששואלת אותנו, האם ניתן להציב בלוק ברוחב SZ עד למיקום X לדוגמה: queries(i) = (2, 5, 6) השאילתה
שואלת אותנו, האם ניתן להציב בלוק ברוחב 6, החל ... 5. והתשובה היא, שלא. כי עד למיקום 5, ניתן להציב אך ורק בלוק עד רוחב 5 אך לא יותר מכך. או לדוגמה: queries(i) = (2, 5, 3) השאילתה
שואלת אותנו, האם ניתן להציב בלוק ברוחב 3, החל ... תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו. ובהינתן לדוגמה הגדרת המכשולים האלו: אז אם
נשאל, האם ניתן ממקום 0 ועד מקום 17, לשים מכשול ברוחב 5? התשובה תהיה שכן, כי ניתן לשים את המכשול, בטווח שבין 3 לבין 9 כך: אז מה בעצם
שואלים אותנו? אז
השאלה הולכת כך: נותנים לנו רשימה של שאילתות, חלקן מסוג 1, דהיינו, שאילתות שמגדירות לנו היכן למקם מחסומים. כמו כן חלק מהשאילתות, הן מסוג 2, דהיינו, הן
שואלות אותנו, האם בהתאם למחסומים שהצבנו עד כה על ... יתכן שאותה שאילתה מסוג 2, פעם אחת תהיה אפשרית ולאחר מכן היא לא תהיה יותר אפשרית, מאחר שהוגבלנו על ידי הצבת מחסום כלשהו. ובעצם
השאלה היא, בהינתן לנו רשימת שאילתות, עלינו להחזיר ... 2 כנל. ולכאורה, זאת התשובה לשאלת הליטקוד הזאת, היא מאוד מאוד מאוד פשוטה. כי בתכלס, אפשרי לקחת נייר ולרשום את כל המחסומים. וכאשר
שואלים אותנו, האם ניתן להציב בלוק ברוחב כלשהו, עד ... נצטרך לבדוק מ 1 ועד X, האם יש את הרוחב הרצוי להצבת הבלוק. כך שמצד האמת, התשובה לשאלת ליטקוד הזאת היא מאוד פשוטה. אז מהי בעצם
השאלה? ולמה
השאלה הזאת, נחשבת לשאלת ליטקוד מאוד מאוד קשה? והתשובה היא, שעיקר
השאלה היא, איך לעשות את החישובים הנל בצורה יעילה. ... 100,000,000 מקומות, כדי לדעת אם אפשרי או לא אפשרי להציב את המכשול ברוחב SIZE עד למיקום X? זה כנראה מתיש ולא יעיל... ולכן מהות
השאלה היא, מהי הדרך היעילה ביותר כדי לתת תשובה לשאילתה מסוג 2. זאת מהות
השאלה. אז חלק גדול מהפתרונות שהוצעו
לשאלה הזאת, עובדים עם לוגיקה של segment tree. ... ניכנס כאן כרגע לכיוון הזה של הפתרון. אבל אני כן אציג בדרך של מחויב ואפשרי, מה בטוח נכון, לחלק לחלקים וכולי, כיצד ניתן לפתור את
השאלה הזאת... אז איך ניגשים
לשאלה הזאת? איך מנסים למצוא פתרון יותר יעיל
לשאלה הזאת. אז נתחיל בפתרון הכי לא יעיל שיש וממנו ... הפתרון הכי לא יעיל, יהיה לעבור מיקום מיקום אחד אחד מההתחלה ועד X כנל. ואיך ניתן לשפר את הפתרון הזה בדרך יחסית יעילה? נוכל
לשאול את עצמנו, מה בטוח נכון. דהיינו, בכל פעם ... המספרים שלנו, מהו הטווח הגדול ביותר שניתן להציב בתוכו בלוק ברוחב כלשהו. ואיך ניתן לעשות זאת בכמה שפחות פעולות. לדוגמה: נניח
ששואלים אותנו האם עד מיקום 1M ניתן להציב מכשול ב ... עדכון. ונחדד, נניח שנבחר באפשרות של לשמור בכל מיקום כולל כל מיקום, את הרוחב המקסימאלי האפשרי עד לאותו מיקום, הרי שעדיין נצטרך
לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים בכל פעם מחדש. וזאת גם
שאלה בפני עצמה. אז אולי אפשרי שנקצר את פעולות ... המכשול. ונחדד, נניח שנבחר באפשרות של לשמור רק בכל מיקום של מכשול, את הרוחב המקסימאלי האפשרי עד לאותו מכשול, הרי שעדיין נצטרך
לשאול את עצמנו, מה תהיה הדרך היעילה ביותר לעדכן את כל המיקומים של המכשולים בכל פעם מחדש. וזאת גם
שאלה שאנחנו צריכים להתבונן בה. אז איך בעצם ניגש ... שנמצא במיקום 9, והתשובה תהיה כן, כנל. וגם תהליך 4 עצמו, מורכב מכמה חלקים. חלק 1 - לאתר את המכשול הקרוב ביותר לנקודה שעליה אנחנו
נשאלים. חלק 2 - לבצע את החישוב כדי למצוא תשובה ... גם עניין של אפשרות להסיק מהשאילתות מסוג 2 הקודמות לשאילתה הנוכחית, במידה ולא היו שאילתות מסוג 1 ביניהן. לדוגמה, אם שאלו אותנו
שאלה על מיקום 1000, ומיד אחר כך שאלו אותנו שוב ...