ორობითი მასივი M დიაპაზონის გადართვის ოპერაციების შემდეგ


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Coursera Goldman Sachs Google რუხი ნარინჯისფერი Snapchat
Array შეკითხვის პრობლემა

თქვენ გეძლევათ ორობითი მასივი, რომელიც თავდაპირველად 0 და Q მოთხოვნებისგან შედგება. პრობლემის დებულება ითხოვს მნიშვნელობების გადართვას (0 – ების გადაქცევას 1 – ებად და 1 – ების გადაკეთებას 0 – ებად). 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 to 0s Q ნომერი ( შეკითხვის ნომერი) ჯერ. ამისათვის ჩვენ ვაპირებთ შევქმნათ ა ლოგიკური მასივი, მასალის კიდევ ორი ​​ზომით სიგრძე 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა და ”q”არის მოთხოვნების რაოდენობა. ყველა მოთხოვნა ხორციელდება O (1) დროში და შემდეგ განახლებას მოითხოვს O (N) დრო.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.