数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律C++ 中二进制数组子数组十进制值的查询
在这个问题中，我们给定一个二进制数组 bin[] 和 Q 个查询，每个查询包含两个值 L 和 R。我们的任务是**创建一个程序，用 C++ 解决二进制数组子数组的十进制值查询**。
**问题描述** - 在这里，为了解决每个查询，我们将不得不找到并打印由从 L 到 R 开始的子数组创建的十进制数，即子数组[L...R]。
让我们举个例子来理解这个问题，
输入
bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6输出
2 101
解释
对于查询 1，形成的子数组为 { 0, 0, 1, 0}。它将创建二进制数 0010，其十进制转换结果为 2。
对于查询 2，形成的子数组为 { 1, 1, 0, 0, 1, 0, 1}。它将创建二进制数 1100101，其十进制转换结果为 101。
解决方案方法
**一个简单的解决方案**是遍历从索引 L 到索引 R 的二进制字符串，找到形成的二进制数，然后将给定的二进制数转换为其十进制等价物。
程序演示我们方法的实现
示例
#include <iostream>
#include <math.h>
using namespace std;
int CalcDecimalValue(int bin[], int L, int R) {
int decimal = 0;
int j = 0;
for(int i = R; i >= L; i--){
decimal += bin[i] * pow(2, j);
j++;
}
return decimal;
}
int main() {
int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
int n = sizeof(bin) / sizeof(bin[0]);
int Q = 2;
int query[Q][2] = {{2, 5},{0, 6}};
for(int i = 0; i < Q; i++){
cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i] [0], query[i][1])<<"\n";
}
return 0;
}输出
For query 1: The decimal value of subarray is 2 For query 2: The decimal value of subarray is 101
**另一种解决问题的方法**是使用预计算数组。我们将创建一个预计算数组，该数组将存储直到第 (n-i) 个索引值的十进制数。为了解决查询，我们将找到 l 和 r 处的值之间的差值。
数组的第 i 个值将使用二进制到十进制转换公式找到。从右边应用它，即从 n-1 开始，
decimalArray[i] = bin[i]*2^(n-1-i) + bin[i+1]*2^(n-1-i+1) + … bin[n- 1]*2^(0)。
程序说明我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];
void createDecimalArray(int bin[], int n){
memset(decimalArray, 0, n*sizeof(int));
decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
for (int i = n - 2; i >= 0; i--)
decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}
int CalcDecimalValue(int L, int R, int n){
if (R != n - 1)
return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
return decimalArray[L] / (1 << (n - 1 - R));
}
int main(){
int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
int n = sizeof(bin) / sizeof(bin[0]);
createDecimalArray(bin, n);
int Q = 2;
int query[Q][2] = {{2, 5},{0, 6}};
for(int i = 0; i < Q; i++){
cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0], query[i][1], n)<<"\n";
}
return 0;
}输出
For query 1: The decimal value of subarray is 2 For query 2: The decimal value of subarray is 101
更新于: 2020-09-09
79 次浏览
广告