Запитвания относно вероятността за четно или нечетно число в дадени диапазони  


Ниво на трудност Трудно
Често задавани в Google Honeywell Uber
Array

Дадохме масив на цяло число, 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 включително.

Запитвания относно вероятността за четно или нечетно число в дадени диапазонищифт

алгоритъм  

  1. Създайте два масива за нечетни числа и четни числа с размер, същият като даден масив. Инициализирайте първия елемент от двата масива на 0.
  2. Прекосете масива и проверете дали числото е нечетно, след това попълнете стойността на масива oddNumber, който създадохме, до броя на четните [i] + 1 и в четния масив, който създадохме, до числото четно [i] и същото, ако беше намерено четно число, съхранява нечетното число в текущия нечетен масив evenNumber и масива oddNumber в масива oddNumber.
  3. Преминете до заявката брой пъти и запазете разликата отдясно, отляво и 1.
  4. Проверете дали трябва да изберем четно число или нечетно число, за да намерим вероятността, ако нечетно число, след това съхраняваме стойността в probab като разликата между oddNumber [дясно] и oddNumber [ляво - 1]
  5. В противен случай съхранява стойността в probab като разликата на evenNumber [вдясно] и evenNumber [вляво - 1].
  6. Проверете дали вероятността е по-малка или равна на 0, след това отпечатайте 0. В противен случай, ако е равна на temp, след това отпечатайте 1. В противен случай намерете общия брой услуги, които могат да бъдат отчетени.
  7. Отпечатайте стойността probab и този брой услуги.

Обяснение  

Ще създадем два масива, един за нечетно число и един за четно число, който да се съхранява. Сега ще преминем през масива и ще открием дали елементът на масива е нечетен или дори нечетен. Ще съхраняваме четното число в масива oddNumber. И предишната стойност на evenNumber към текущата стойност на evenNumber, следва да се следва същото, ако числото е четно. След това съхранявайте нечетната стойност в масива evenNumber и предишната стойност на масива oddNumber в текущата стойност на текущата oddNumber. Всичко това е да се създаде и запълни масив съответно с числа в създадените масиви.

Вижте също
Обратни гласни на низово решение с Leetcode

Вземете типа на заявката, лявата и дясната точки като диапазон, вземете разликата от тях. Ще открием, че дадената заявка е от кой тип. Ако е по-голямо от 1, тогава трябва да изберем нечетно число, за да разберем вероятността за избор на четно число. В противен случай ще намерим вероятността за четно число в диапазон. Ако е нечетно, тогава ще получим разликата в масива oddNumber, който създадохме, и същото с вероятността за четното число, разликата на evenNumber. Ще съхраним разликата в 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

Сложност на пространството

О (п) където "н" е броят на елементите в масива.

препратка