מערך בינארי לאחר פעולות החלפת טווח M  


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית Coursera גולדמן זאקס Google גריי אורנג ' Snapchat
מערך בעיית שאילתות

אתה מקבל מערך בינארי, שמורכב מ- 0 מספרים ראשוניים ומספר Q של שאילתות. הצהרת הבעיה מבקשת להחליף את הערכים (להמיר 0s ל- 1s ו- 1 ל- 0s). לאחר ביצוע שאילתות Q, הדפס את המערך שהתקבל.

דוגמה  

arr[] = {0, 0, 0, 0, 0}

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

הסבר

החלפה ראשונה   0,1,1,1,0

החלפה שנייה 1,0,1,1,0

החלפה שלישית 1,0,0,0,1

מערך בינארי לאחר פעולות החלפת טווח Mאורן

אַלגוֹרִיתְם  

  1. צור מערך בוליאני בגודל n + 2.
  2. אתחל את המערך הבוליאני כשקר עבור כל אינדקס.
  3. עכשיו עבור כל שאילתה הפוך את האלמנט באינדקס שמאלה וימינה + 1.
  4. עכשיו פשוט מלא את המערך כקידומת xor. אחסן את xor של כל האלמנטים מאינדקס 1 עד i באינדקס i.
  5. הדפיסו את המערך

הסבר למערך בינארי לאחר פעולות החלפת טווח M

ניתן בינארי מערך, המורכב מ- 0 ו- 1 וכפי שהשם מרמז. אך בתחילה, הוא מכיל רק את הערכים כ- 0s. בהתחשב במספר השאלות Q. כל שאילתה מכילה שני ערכים, הערכים הם נקודת ההתחלה של טווח ונקודת סיום של טווח, בתוך הטווחים הללו, עלינו להחליף את הערכים כאשר החלפה פירושה שעלינו להמיר 0 שניות ל -1 ושנייה למספר Q 1 ( מספר השאילתה) פעמים. לשם כך אנו הולכים ליצור בוליאני מערך, בגודל שניים יותר באורך המערך n + 2. ואז נעבור לערכים Q מספר פעמים, אם יש לנו מספר רב יותר של שאילתות, אנחנו לא צריכים לקרוא לזה בעצמינו, במקום זאת, נעשה לולאה ונקרא לזה עם מספר שאילתות ותשומות שונות.

ראה גם
סכום מקסימלי של נתיב במשולש מספר נכון

בהחלפה להמיר את הערכים במקומות המדויקים הניתנים כטווח באותו מערך, המירו את כל האפסים לאלה, ואחדם לאפס על ידי ביצוע פעולת XOR. פעולת XOR עושה את אותו הדבר עבורנו אם נמצא אותו מספרים או ערכים זה ייתן ל- 0 כתוצאה פירושו שקר אם הוא מוצא מספר שונה של ערכים. זה ייתן את 1, כתוצאה מכך, פירושו נכון. אז נעשה את אותו הדבר בפונקציית ההחלפה כדי להפוך ערכים.

חצו את המערך ובצעו את הפעולה במערך. בצע את פעולת ה- XOR על הערך הנוכחי והערך הקודם של המערך. הדבר שעשינו כאילו הוא מוצא את אותו ביט זה ייתן 0 אחרת 1. פעולה זו תהיה האחרונה שתחלף בין כל הערכים שיהפכו לטווח. לסיום, הדפיסו את המערך.

קופונים  

יישום ב- C ++ עבור מערך בינארי לאחר פעולות החלפת טווח M

#include<iostream>

using namespace std;

void Toggle(bool arr[], int start, int end)
{
    arr[start] ^= 1;
    arr[end+1] ^= 1;
}

void getToggling(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}

void printOutput(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}

int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};

    Toggle(arr, 1, 5);
    Toggle(arr, 2, 5);
    Toggle(arr, 3, 5);

    getToggling(arr, n);

    printOutput(arr, n);
    return 0;
}
1 0 1 1 1

יישום ב- Java עבור מערך בינארי לאחר פעולות החלפת טווח M

class ToggleArray
{
    static void Toggle(boolean arr[], int start, int end)
    {
        arr[start] ^= true;
        arr[end + 1] ^= true;
    }

    static void getToggling(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            arr[k] ^= arr[k - 1];
        }
    }

    static void printOutput(boolean arr[], int n)
    {
        for (int k = 1; k <= n; k++)
        {
            if(arr[k] == true)
                System.out.print("1" + " ");
            else
                System.out.print("0" + " ");
        }
    }

    public static void main(String args[])
    {
        int n = 5, m = 3;
        boolean arr[] = new boolean[n + 2];

        Toggle(arr, 1, 5);
        Toggle(arr, 2, 5);
        Toggle(arr, 3, 5);

        getToggling(arr, n);

        printOutput(arr, n);
    }
}
1 0 1 1 1

ניתוח מורכבות  

מורכבות זמן

O (n + q) איפה "N" הוא מספר האלמנטים במערך ו- "q”הוא מספר השאילתות. כל השאילתות מתבצעות בזמן O (1) ואז העדכון דורש זמן O (N).

ראה גם
אסוף נקודות מרביות ברשת באמצעות שני מעברים

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך.