Запыты па верагоднасці цотнага ці няцотнага ліку ў зададзеных дыяпазонах  


Узровень складанасці Жорсткі
Часта пытаюцца ў Google Honeywell Uber
масіў

Мы далі масіў цэлага ліку, q колькасць запытаў. Дзе кожны запыт утрымлівае тры цэлыя лікі, што вызначае тып запыту. Гэта азначае, што калі мы далі 0, гэта азначае, што мы павінны знайсці верагоднасць выбару няцотнага ліку ў дадзеным дыяпазоне. Дзе дыяпазон вызначаецца як пачатковая і канчатковая кропкі. У гэтым канкрэтным дыяпазоне любога тыпу канкрэтнага запыту. Вы павінны знайсці рашэнне для кожнага запыту. Кожны запыт будзе ў форме

TSE: калі вы далі T = 0, гэта азначае, што вам трэба знайсці верагоднасць выбару цотнага ліку ў дадзеным дыяпазоне (S: Кропка адліку, E: Канец канца) у дадзеным масіве А.

TSE: калі вы далі T = 1, то гэта азначае, што вам трэба знайсці верагоднасць выбару няцотнага ліку ў дадзеным дыяпазоне (S: Кропка адліку, E: Канец канца) у дадзеным масіве А.

Прыклад  

Уваход:

масіў [] = {2, 3, 4, 5, 6}

Запыт 1: 1 1 3

Запыт 1: 0 1 4

Вынахад:

1 / 3

1 / 2

Тлумачэнне:

мы далі T = 1 у запыце, значыць, мы павінны знайсці верагоднасць выбару няцотнага ліку ў дыяпазоне 1 і 3 уключна.

Глядзіце таксама
Перамяшаць масіў

мы далі T = 0 у запыце, гэта значыць, што мы павінны знайсці верагоднасць выбару цотнага ліку ў дыяпазоне 1 і 4 уключна.

Запыты па верагоднасці цотнага ці няцотнага ліку ў зададзеных дыяпазонахPin

Алгарытм  

  1. Стварыце два масівы для няцотных лікаў і цотных лікаў, памерам аднолькавых з дадзеным масівам. Ініцыялізуйце першы элемент абодвух масіваў 0.
  2. Абярыце масіў і праверце, ці няцотна лік, запоўніце значэнне масіва oddNumber, які мы стварылі, да ліку няцотных [i] + 1 і ў цотны масіў, які мы стварылі, да ліку цотных [i], і тое ж, калі знойдзена цотнае лік, захоўвае няцотны лік у бягучым няцотным масіве цотных нумароў, а масіў oddNumber - у масіве oddNumber.
  3. Прайдзіце да запыту колькі разоў і захавайце розніцу направа, налева і 1.
  4. Праверце, ці трэба нам выбіраць цотны лік ці няцотны лік, каб знайсці верагоднасць, калі няцотны лік, то захавайце значэнне ў probab як розніцу oddNumber [справа] і oddNumber [злева - 1].
  5. У іншым выпадку захоўваюць значэнне ў probab як рознасць evenNumber [справа] і evenNumber [злева - 1].
  6. Праверце, ці меншая за верагоднасць 0 роўная або роўная 0, а потым раздрукуйце 1. У адваротным выпадку, калі яна роўная temp, раздрукуйце XNUMX. У адваротным выпадку знайдзіце агульную колькасць ласкаў, якія можна падлічыць.
  7. Надрукуйце значэнне probab і гэту колькасць ласкаў.

Тлумачэнне  

Мы збіраемся стварыць два масівы - адзін для няцотнага ліку, а другі - для цотнага ліку. Зараз мы збіраемся прайсціся па масіве і даведацца, ці незвычайны элемент масіва ці нават няцотны. Мы будзем захоўваць цотны лік у масіве oddNumber. І папярэдняе значэнне evenNumber да бягучага значэння evenNumber, трэба прытрымлівацца таго ж, калі лік цотны. Затым захавайце няцотнае значэнне ў масіве evenNumber і папярэдняе значэнне масіва oddNumber у бягучым значэнні бягучага oddNumber. Усё гэта для стварэння і запаўнення масіва лічбамі ў створаных масівах адпаведна.

Глядзіце таксама
Зваротныя галосныя рашэння радка Leetcode

Выбярыце тып запыту, левую і правую кропкі як дыяпазон, атрымайце розніцу ў іх. Мы знойдзем дадзены запыт, якога тыпу. Калі ён большы за 1, мы павінны выбраць няцотны лік, каб даведацца пра верагоднасць выбару цотнага ліку. Інакш мы знойдзем верагоднасць цотнага ліку ў дыяпазоне. Калі яно няцотнае, то мы атрымаем розніцу створанага намі масіва oddNumber і аднолькавую з верагоднасцю цотных лікаў - розніцу цотных. Мы захаваем розніцу ў probab, і калі probab менш або роўны 0, мы надрукуем 0, у адваротным выпадку, калі probab роўны k, друкуем 1. У адваротным выпадку нам трэба знайсці агульную колькасць ласкаў. І, нарэшце, надрукуйце значэнне probab і favors.

Рэалізацыя  

Праграма C ++ для запытаў на верагоднасць цотнага ці няцотнага ліку ў зададзеных дыяпазонах

#include<iostream>

using namespace std;

#define C 3

int getDivisor(int a, int b)
{
    if (a == 0 || b == 0)
        return 0;

    if (a == b)
        return a;

    if (a > b)
        return getDivisor(a - b, b);

    return getDivisor(a, b - a);
}

void solveQuery(int arr[], int n, int Q,int query[][C])
{
    int evenNumber[n + 1];
    int oddNumber[n + 1];
    evenNumber[0] = oddNumber[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] & 1)
        {
            oddNumber[i + 1] = oddNumber[i] + 1;
            evenNumber[i + 1] = evenNumber[i];
        }
        else
        {
            evenNumber[i + 1] = evenNumber[i] + 1;
            oddNumber[i + 1] = oddNumber[i];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int right = query[i][2];
        int left = query[i][1];
        int T = query[i][0];

        int dif = right - left + 1;
        int probab;

        if (T)
            probab = oddNumber[right] - oddNumber[left - 1];
        else
            probab = evenNumber[right] - evenNumber[left - 1];

        if (!probab)
            cout << "0" << endl;

        else if (probab == dif)
            cout << "1" << endl;

        else
        {
            int div = getDivisor(probab, dif);
            cout << probab / div << "/" << dif / div << endl;
        }
    }
}

int main()
{
    int arr[] = { 2,3,4,5,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2;
    int query[Q][C] = { { 1, 1, 3 },
        { 0, 1, 4 }
    };

    solveQuery(arr, n, Q, query);
    return 0;
}
1/3
1/2

Праграма Java для запытаў на верагоднасць цотнага ці няцотнага ліку ў зададзеных дыяпазонах

public class QueryProbability
{
    static int getDivisor(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return getDivisor(a - b, b);

        return getDivisor(a, b - a);
    }
    
    static void solveQuery(int []arr, int n, int Q, int [][]query)
    {
        int []evenNumber = new int[n + 1];
        int []oddNumber = new int[n + 1];
        evenNumber[0] = oddNumber[0] = 0;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) > 0)
            {
                oddNumber[i + 1] = oddNumber[i] + 1;
                evenNumber[i + 1] = evenNumber[i];
            }
            else
            {
                evenNumber[i + 1] = evenNumber[i] + 1;
                oddNumber[i + 1] = oddNumber[i];
            }
        }
        
        for (int i = 0; i < Q; i++)
        {
            int right = query[i][2];
            int left = query[i][1];
            int T = query[i][0];

            int dif = right - left + 1;
            int probab;
            if (T > 0)
                probab = oddNumber[right] - oddNumber[left - 1];
            else
                probab = evenNumber[right] - evenNumber[left - 1];

            if (probab <= 0)
                System.out.println("0");
            else if (probab == dif)
                System.out.println("1");

            else
            {
                int div = getDivisor(probab, dif);
                System.out.println(probab / div + "/" +dif / div);
            }
        }
    }
    
    static public void main (String[] args)
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        int Q = 2;
        int [][]query = { { 1, 1, 3 },
            { 0, 1, 4 }
        };

        solveQuery(arr, n, Q, query);
    }
}
1/3
1/2

Аналіз складанасці для запытаў на верагоднасць цотнага ці няцотнага ліку ў зададзеных дыяпазонах  

Складанасць часу

O (q * n) дзе "Q" - колькасць запытаў і "П" - колькасць элементаў у масіве

Глядзіце таксама
Падлічыце розныя элементы ў кожным акне памерам K

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.

Спасылка