อาร์เรย์ไบนารีหลังจากการดำเนินการสลับช่วง M  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน Coursera แซคส์โกลด์แมน Google สีเทาOrange Snapchat
แถว ปัญหาการสืบค้น

คุณจะได้รับอาร์เรย์ไบนารีซึ่งประกอบด้วย 0 เริ่มต้นและจำนวนคิวรี Q คำสั่งปัญหาขอให้สลับค่า (การแปลง 0s เป็น 1s และ 1s เป็น 0s) หลังจากดำเนินการคิวรี Q แล้วให้พิมพ์อาร์เรย์ผลลัพธ์

ตัวอย่าง  

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

Toggle(2,4)

Toggle(1,2)

Toggle(3,5)
1 0 0 0 1

คำอธิบาย

การสลับครั้งที่ 1   0,1,1,1,0

การสลับครั้งที่ 2 1,0,1,1,0

การสลับครั้งที่ 3 1,0,0,0,1

อาร์เรย์ไบนารีหลังจากการดำเนินการสลับช่วง Mหมุด

ขั้นตอนวิธี  

  1. สร้างอาร์เรย์บูลีนขนาด n + 2
  2. เริ่มต้นอาร์เรย์บูลีนเป็นเท็จสำหรับแต่ละดัชนี
  3. ตอนนี้สำหรับแต่ละแบบสอบถามให้พลิกองค์ประกอบที่ดัชนีซ้ายและขวา + 1
  4. ตอนนี้เพียงแค่เติมอาร์เรย์เป็นอาร์เรย์ xor นำหน้า จัดเก็บ xor ขององค์ประกอบทั้งหมดจากดัชนี 1 ถึง i ที่ดัชนี i
  5. พิมพ์อาร์เรย์

คำอธิบายสำหรับอาร์เรย์ไบนารีหลังจากการดำเนินการสลับช่วง M

รับไบนารี แถวซึ่งประกอบด้วย 0 และ 1 และตามชื่อที่แนะนำ แต่ในขั้นต้นจะมีค่าเป็น 0 เท่านั้น ระบุจำนวนคิวรี Q แต่ละแบบสอบถามมีค่าสองค่าค่าคือจุดเริ่มต้นของช่วงและจุดสิ้นสุดของช่วงภายในช่วงเหล่านี้เราต้องสลับค่าโดยที่การสลับหมายความว่าเราต้องแปลง 0s เป็น 1s และ 1s เป็น 0s Q number ( จำนวนการสืบค้น) จำนวนครั้ง สำหรับสิ่งนี้เราจะสร้างไฟล์ บูลีน อาร์เรย์ที่มีขนาดเพิ่มขึ้นอีกสองความยาวของอาร์เรย์ 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” คือจำนวนองค์ประกอบในอาร์เรย์