ორობითი მასივის სუბსტრატების ათწილადი მნიშვნელობების მოთხოვნები  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon Google
Array შეკითხვის პრობლემა

მოცემული ორობითი მასივის ორობითი მასივის ქვეჯგუფების ათობითი მნიშვნელობებისთვის დაწერეთ მოთხოვნები. პრობლემის დებულება ითხოვს ორობითი მასივის დიაპაზონის დახმარებით ასე ჩამოყალიბებული ათობითი რიცხვის გარკვევას.

მაგალითი  

შეყვანის:

arr [] = {1, 0, 1, 1, 0, 0, 1, 1}

მოთხოვნა (1, 5)

მოთხოვნა (3, 6)

გამოყვანის:

12 9

განმარტება:

გამომუშავება, როგორც ორობითი რიცხვები, რომელიც წარმოადგენს 1-დან 5-ის ჩათვლით (01100), არის 12.

გამომავალი ისე ჩამოყალიბდა, როგორც ორობითი რიცხვები წარმოადგენს 3-დან 6-ის ჩათვლით (1001), არის 9.

ორობითი მასივის ქვეჯგუფების ათობითი მნიშვნელობების მოთხოვნებიPin

 

ორობითი მასივის ქვეჯგუფების ათობითი მნიშვნელობების მოთხოვნების ალგორითმი  

  1. შექმენით მასივი, როგორც prefixArray, ინიციალეთ იგი 0-ით.
  2. კოპირება ბოლო ელემენტ Arraray- ის ბოლო ელემენტზე მასივი მოცემულია.
  3. მასივის მასივიდან მასივიდან მარჯვნივ მარცხნივ, და შეინახეთ მოცემული მასივის ელემენტის პროდუქტი და 2-ის სიმძლავრე და დაამატეთ იგი Array მასივის პრეფიქსით.
  4. მიიღეთ მოთხოვნა, თუ მნიშვნელობის უფლება არ არის მოცემული მასივის ბოლო ინდექსის მნიშვნელობის ტოლი, დააბრუნეთ პრეფიქსი Array [მარცხნივ] და prefixArray [მარჯვნივ + 1] სხვაობის დაყოფა და 1 და მარჯვნივ ცვლა ოპერაცია მასივის ინდექსი
  5. სხვა დავაბრუნოთ პრეფიქსიArray [მარცხნივ] დაყოფა და მასივის 1 და მარჯვენა ინდექსი.
იხილეთ ასევე
სიმების დეკოდირება

ორობითი მასივის ქვეჯგუფების ათობითი მნიშვნელობების მოთხოვნების განმარტება  

რაც შეეხება ორობითი მასივის ქვეჯგუფების ათობითი მნიშვნელობების მოთხოვნებს, მოცემულია ა ორობითი მასივი და მთელი რიგი ინდექსები, როგორც მარცხენა და მარჯვენა ინდექსი. იპოვნეთ მოცემული ორობითი რიცხვის ათობითი ფორმა, რომელიც ასეა მოცემული მოცემული დიაპაზონით. ჩვენ მოგვცემენ მოთხოვნას, რომელშიც მოცემულია დიაპაზონი. ჩვენ უნდა ვიპოვოთ ათობითი რიცხვი, რომელიც ასე ჩამოყალიბებულია ორობითი რიცხვისგან, დიაპაზონით. ამისათვის ჩვენ ვაპირებთ შევქმნათ ზომის დამატებითი მასივი, იგივე მასივის სიგრძე. ჩვენ ვადგენთ მასივს, ან შეგვიძლია ვთქვათ, რომ შეგვიძლია ამ მასივის წინასწარი დამუშავება და შევავსოთ მასში გარკვეული მნიშვნელობები, რათა შევძლოთ მოთხოვნის გადაჭრა მუდმივ დროში.

მასივის გავლა, მაგრამ მასივის გადაკვეთამდე, მასივი შეავსეთ 0. Java- ში, როდესაც მასივი შეიქმნება, ის ავტომატურად ივსება 0-ით, მაგრამ C ++ - ში ეს ჩვენ თვითონ უნდა გავაკეთოთ. ამის შემდეგ მიიღეთ ბოლო მასივის ელემენტისა და 1 – ის პროდუქტი, შეინახეთ მნიშვნელობა პრეფიქსი – მასივის ბოლო ელემენტში. ახლა დაიწყეთ მარჯვნივ მარცხნიდან, ნიშნავს 2-დან დაწყებასnd მასივის ბოლო ელემენტი, ახლა მიიღეთ რიცხვების პროდუქტი 2-ის და მოცემული მასივის ელემენტის სიმძლავრით და დაამატეთ მას Array მასალის წინა მნიშვნელობით. გააგრძელეთ მისი დამატება prefixArray- ის მნიშვნელობებით და შეინახეთ მას prefixArray- ის შესაბამის ადგილას.

იხილეთ ასევე
მოცემული დიაპაზონის მნიშვნელობების მასივის ელემენტების თვლის მოთხოვნები

ჩვენთვის მოცემული თითოეული მოთხოვნისთვის შეამოწმეთ არის თუ არა მოცემული სწორი მნიშვნელობა მასივის ბოლო ინდექსის ტოლი. თუ აღმოჩნდა, რომ მართალია, მაშინ მიიღეთ განსხვავება prefixArray [მარცხნივ] და prefixArray [მარჯვნივ] და გავყოთ იმ მნიშვნელობით, რომელიც ასე ჩამოყალიბდა, როდესაც ცვლის ოპერაციას მივმართავთ 2-ის ხარისხში და დავაბრუნებთ ამ მნიშვნელობას, სხვა შემთხვევაში უბრალოდ დავაბრუნოთ სხვაობა prefixArray [მარცხნივ] და დაყავით იგი ცვლადი მოქმედებით მარჯვენა მნიშვნელობაზე და დააბრუნეთ იგი.

განხორციელება  

C ++ პროგრამა

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>

using namespace std;

void buildArray(int arr[], int n, int prefixArray[])
{
    memset(prefixArray, 0, n * sizeof(int));
    prefixArray[n - 1] = arr[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
}
int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
{
    if (right!= n - 1)
        return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));

    return prefixArray[left] / (1 << (n - 1 - right));
}
int main()
{
    int arr[] = {1, 0, 1, 1, 0, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefixArray[n];
    buildArray(arr, n, prefixArray);
    cout << getDeimalNum(arr, 1, 5, n, prefixArray) << endl;
    cout << getDeimalNum(arr, 3, 6, n, prefixArray) << endl;
    return 0;
}
12
9

ჯავა პროგრამა

import java.util.Arrays;

class DecimalfromSubArray
{
    static void buildArray(int arr[], int n, int prefixArray[])
    {
        Arrays.fill(prefixArray, 0);
        prefixArray[n - 1] = arr[n - 1] * (int)(Math.pow(2, 0));
        for (int i = n - 2; i >= 0; i--)
        {
            prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
        }
    }
    
    static int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
    {
        if (right != n - 1)
        {
            return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));
        }
        return prefixArray[left] / (1 << (n - 1 - right));
    }
    
    public static void main(String[] args)
    {
        int arr[] = {1, 0, 1, 1, 0, 0, 1, 1};
        int n = arr.length;

        int prefixArray[] = new int[n];
        buildArray(arr, n, prefixArray);

        System.out.println(getDeimalNum(arr,1, 5, n, prefixArray));

        System.out.println(getDeimalNum(arr,3, 6, n, prefixArray));
    }
}
12
9

ორობითი მასივის სუბსტრატების ათწილადი მნიშვნელობების მოთხოვნების სირთულის ანალიზი  

დროის სირთულე

O (q) სადაც "Q" არის მოთხოვნების რაოდენობა.

იხილეთ ასევე
ჩასმა დალაგება

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

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

Reference