Traduisez ce qui suit en chinois : Requête C++ pour répondre au nombre de 1 et de 0 à gauche d'un index donné

Discutez d'une question pour répondre à une requête sur un tableau donné. Par exemple, pour chaque index de requête, nous devons trouver le nombre de 1 et de 0 à gauche de l'index.

Input: arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
Output:
query 1: zeros = 1,ones = 1
query 2: zeros = 1,ones = 3
query 3: zeros = 1,ones = 0
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

Input: arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
Output:
query 1: zeros = 2,ones = 1
query 2: zeros = 2,ones = 0
query 3: zeros = 3,ones = 3

Façon de trouver la solution

Manière naïve

Un moyen simple de résoudre ce problème est de parcourir le tableau jusqu'à l'index de la requête et de vérifier chaque élément s'il est 0, puis d'incrémenter le compteur zéro de 1 sinon ; incrémenter le compteur zéro 1.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] =  { 2, 4, 1, 0, 5 };
    int qsize = sizeof(queries) / sizeof(queries[0]);
    int zeros=0,ones=0;
    // loop for running each query.
    for(int i = 0;i<qsize;i++){
        //counting zeros and ones
        for(int j = 0;j<queries[i];j++){
            if(nums[j]==0)
            zeros++;
            else
            ones++;
        }
        cout << "\nquery " << i+1 << ": zeros = " << zeros << ",ones = " << ones;
        zeros=0;
        ones=0;
    }
    return 0;
}

Output

query 1: zeros = 1,ones = 1
query 2: zeros = 2,ones = 2
query 3: zeros = 0,ones = 1
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

Méthode efficace

Dans la méthode précédente, à chaque fois on part du 0ème index pour calculer le 1 et le 0 pour la nouvelle requête.

Une autre façon consiste à calculer d'abord 0 et 1. apparaît à gauche de chaque index, les stocke dans un tableau et renvoie la réponse basée sur l'index écrit dans la requête.

Exemple

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] =  { 2, 4, 1, 0, 5 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int arr[n][2];
    int zeros = 0, ones = 0;
    // traverse through the nums array.
    for (int i = 0; i < n; i++) {
        // store the number of zeros and ones in arr.
        arr[i][0] = zeros;
        arr[i][1] = ones;
        // increment variable according to condition
        if (nums[i]==0)
            zeros++;
        else
            ones++;
    }
    int qsize = sizeof(queries) / sizeof(queries[0]);
        for (int i = 0; i < qsize; i++)
        cout << "\nquery " << i+1 << ": zeros = " << arr[queries[i]][0] << ",ones ="    << arr[queries[i]][1];
    return 0;
}

Output

query 1: zeros = 1,ones =1
query 2: zeros = 2,ones =2
query 3: zeros = 0,ones =1
query 4: zeros = 0,ones =0
query 5: zeros = 2,ones =3

Conclusion

Dans ce tutoriel, nous avons discuté du retour du nombre de 1 et de 0 à gauche de l'index pour chaque requête dans un tableau donné. Nous avons discuté de moyens simples et efficaces pour résoudre ce problème. Nous avons également discuté des programmes C++ pour résoudre ce problème, que nous pouvons implémenter à l'aide de langages de programmation comme C, Java, Python, etc. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!