חידת LeetCode Solution - Block Placement Queries, פתרון ליטקוד, LeetCode Solution, לפתור שאלות ב LeetCode, מדעי המחשב, תכנות מחשבים, לעבוד בהייטק, ללמוד תכנות מחשבים, להיות מתכנת, ללמוד לתכנת, הכנה לראיון טכני, ראיון עבודה בהייטק, שאלות ליטקוד, פיתוח תוכנה, איך לכתוב קוד? ללמוד לכתוב קוד, חידות היגיון, ללמוד לחשוב, ללמוד לנתח דברים, ללמוד לפרק לגורמים, ללמוד לחלק לחלקים, ללמוד למצוא חוקיות, איך לחלק לחלקים? איך למצוא חוקיות? לנתח תהליכים... כך: queries[i] = [1, x] כאשר הספרה הראשונה היא 1, זה אומר שמדובר על שאילתה מסוג 1, שאומרת לנו להציב מכשול במקום X כנל. הבהרה: המכשול עצמו תופס 0 מקום. לדוגמה: queries[i] = [1, 10] פירושו, תציב מכשול בנקודה ... [2, x, sz] כאשר הספרה הראשונה היא 2, זה אומר שמדובר על שאילתה מסוג 2, ששואלת אותנו, האם ניתן להציב בלוק ברוחב SZ עד למיקום X לדוגמה: queries[i] = [2, 5, 6] השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 6, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שלא. כי עד למיקום 5, ניתן להציב אך ורק בלוק עד רוחב 5 אך לא יותר מכך. או לדוגמה: queries[i] = [2, 5, 3] השאילתה שואלת אותנו, האם ניתן להציב בלוק ברוחב 3, החל ממיקום 0 ועד למיקום 5. והתשובה היא, שכן. כי עד למיקום 5, ניתן להציב כל בלוק עד רוחב 5. ואם לדוגמה אמרנו לנו את זה queries[0] = [1, 10] queries[1] = [2, 15, ... היא מאוד מאוד מאוד פשוטה. כי בתכלס, אפשרי לקחת נייר ולרשום את כל המחסומים. וכאשר שואלים אותנו, האם ניתן להציב בלוק ברוחב כלשהו, עד למיקום X, בסך הכל נצטרך לבדוק מ 1 ועד X, האם יש את הרוחב הרצוי ... אבל ממש לא יעיל. למה הוא לא יעיל? ממגוון רחב מאוד של סיבות. כי נניח שישאלו אותנו, האם ניתן להציב עד מיקום 100,000,000 בלוק ברוחב 13,522. ונניח שעד מיקום 100,000,000 יש לנו 9,999 מכשולים במקומות שונים. האם באמת הגיוני שאנחנו נצטרך עכשיו לספור 100,000,000 מקומות, כדי לדעת אם אפשרי או לא אפשרי להציב את המכשול ברוחב SIZE עד למיקום X? זה כנראה מתיש ולא יעיל... ולכן מהות השאלה היא, מהי הדרך היעילה ... למצוא דרך, איך נוכל בדרך הקצרה ביותר, לדעת, על מיקום כלשהו בציר המספרים שלנו, מהו הטווח הגדול ביותר שניתן להציב בתוכו בלוק ברוחב כלשהו. ואיך ניתן לעשות זאת בכמה שפחות פעולות. לדוגמה: נניח ששואלים אותנו האם עד מיקום 1M ניתן להציב מכשול ב SIZE של 2000 כאשר יש לנו 5000 מכשולים שונים. אז, בדרך הארוכה ביותר, היינו יכולים לעשות במקרה ... לפי סדר המכשולים על גבי הציר. ונניח שאנחנו רוצים בכל פעם לעדכן אותה, במידע של מהו הטווח המקסימאלי, שאפשרי להציב בלוק, החל מהתחלת הציר ועד לנקודת מכשול כלשהי, אז כיצד יהיה הכי יעיל לעשות את זה? אז לשם כך ... המקרה הפשוט ביותר. כך: אז לצורך העניין נתבונן על ציר ריק ללא מכשולים, ונשאל: מהו גודל הבלוק המקסימאלי שניתן להציב עד נקודה מספר 1? תשובה: בלוק ברוחב של 1. ועד נניח למיקום 7, איזה גודל מקסימאלי של בלוק, ניתן להציב? תשובה: 7. כי עד מיקום 7, לא ניתן להכניס בלוק יותר רחב מהרוחב של המיקום הנוכחי. במילים אחרות, לצורך ... הראשון ניתן לומר שהוא נמצא במיקום 0. דהיינו, ניתן להתייחס למיקום 0, כאילו יש בו מכשול. שעד אליו ניתן להציב בלוקים ברוחב 0. ואז אם לדוגמה יש לנו מכשול ראשון במיקום 5. ואז אנחנו שמים מכשול שני, נניח לפניו ...