Երկուական զանգված `M միջակայքի փոփոխման գործողություններից հետո  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Coursera Goldman Sachs-ը Google GreyOrange Snapchat
Դասավորություն Հարցման խնդիր

Ձեզ տրվում է երկուական զանգված, որը բաղկացած է 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-րդ toggling 1,0,1,1,0

3-րդ toggling 1,0,0,0,1

Երկուական զանգված `M միջակայքի փոփոխման գործողություններից հետոPin

Ալգորիթմ  

  1. Ստեղծեք n + 2 չափի բուլյան զանգված:
  2. Սկզբից նախանշեք բուլյան զանգվածը որպես կեղծ յուրաքանչյուր ցուցանիշի համար:
  3. Այժմ յուրաքանչյուր հարցման համար տարրը մատով խփեք ձախ և աջ ինդեքսում + 1:
  4. Այժմ պարզապես լրացրեք զանգվածը որպես xor զանգված նախածանց: Պահպանեք 1-ից ինդեքսից բոլոր տարրերի xor ինդեքսում:
  5. Տպիր զանգվածը

Երկուական զանգվածի բացատրությունը M տիրույթի անջատման գործողություններից հետո

Հաշվի առնելով երկուական դասավորություն, որը բաղկացած է 0-ից և 1-ից, և ինչպես հուշում է անունը: Ի սկզբանե, այն պարունակում է միայն արժեքները որպես 0s: Հաշվի առնելով հարցումների Q քանակը: Յուրաքանչյուր հարցում պարունակում է երկու արժեք, արժեքները տիրույթի մեկնարկային կետն ու տիրույթի վերջնակետն են, այս միջակայքերում մենք պետք է փոխենք այն արժեքները, երբ փոխելը նշանակում է, որ 0-ը պետք է վերածենք 1-ի և 1-ը 0-ի հարցման համարը) անգամ: Դրա համար մենք պատրաստվում ենք ստեղծել Boolean զանգված, ևս երկու անգամ չափի n + 2 զանգվածի երկարությունը: Այնուհետև մենք մի քանի անգամ փոխելու ենք Q արժեքները, եթե ավելի շատ հարցում ունենք, ապա ստիպված չենք լինի դա զանգահարել մեր կողմից, փոխարենը կկազմենք օղակ և կկանչենք այն տարբեր հարցման համարներով և մուտքերով:

Տես նաեւ,
Ուղու առավելագույն գումարը Numberիշտ համարի եռանկյունում

Տեղափոխման ընթացքում նույն զանգվածում որպես տիրույթ տրված ճշգրիտ տեղերում արժեքները փոխարկեք, բոլոր զրոները վերածեք մեկի, և դրանք այն զրո դարձնելով ՝ կատարելով XOR գործողությունը: XOR գործողությունը նույնն է անում մեզ համար, եթե գտնվի նույն թվերը կամ արժեքները, այն կտա 0-ը, ինչը նշանակում է, որ կեղծ է, եթե գտնում է տարբեր քանակի արժեքներ: Դա կտա 1-ը, որպես արդյունք, նշանակում է ճշմարիտ: Այսպիսով, մենք նույնը կանենք փոփոխման գործառույթում `արժեքները շրջելու համար:

Անցեք զանգվածը և կատարեք զանգվածի գործողությունը: Կատարեք XOR գործողությունը զանգվածի ընթացիկ և նախորդ արժեքի վրա: Այն, ինչ մենք արեցինք, կարծես թե գտնում է նույն բիթը, հակառակ դեպքում կտա 0: Այս գործողությունը վերջինը կլինի բոլոր այն արժեքները, որոնք կդառնան միջակայքում: Վերջապես, տպեք զանգվածը:

Կոդ  

Իրականացում 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n + q) որտեղ «Ն» զանգվածում տարրերի քանակն է և «q”Հարցումների քանակն է: Բոլոր հարցումներն իրականացվում են O (1) ժամանակում, ապա թարմացումը պահանջում է O (N) ժամանակ:

Տես նաեւ,
Հավաքեք առավելագույն միավորները ցանցում `օգտագործելով երկու անցում

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: