Массиви дуӣ пас аз амалиётҳои диапазони диапазони M


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Coursera Голдман Sachs Google GreyOrange Snapchat
тартиботи ҳарбӣ Масъалаи пурсиш

Ба шумо массиви дуӣ дода мешавад, ки аз 0 ибтидо ва шумораи саволҳо иборат аст. Дар баёнияи масъала хоҳиш карда мешавад, ки арзишҳо иваз карда шаванд (табдил додани 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 иборат аст ва тавре ки аз номаш бармеояд. Аммо дар аввал, он танҳо арзишҳоро ҳамчун 0s дар бар мегирад. Бо назардошти миқдори Q саволҳо. Ҳар як дархост ду арзишро дар бар мегирад, арзишҳо нуқтаи ибтидоии диапазон ва нуқтаи хотимаи диапазон мебошанд, дар доираи ин диапазонҳо мо бояд қиматҳоро иваз намоем, ки гузариш маънои онро дорад, ки 0-ро ба 1 ва 1-ро ба 0-и 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) -ро талаб мекунад.

Мураккабии фазо

Эй (н) ки дар "Н" шумораи унсурҳои массив аст.