数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究范围查询以查找具有最大数字和的元素
简介
在本教程中，我们讨论了在 C++ 中进行范围查询以查找具有最大数字和的元素的问题。为了解决这个问题，需要一个元素数组和一些查询。查询表示数组的索引，并使用这些查询查找具有最大数字和的数组元素。最大数字和是两个数字（个位和十位数字的加法）或一位数字的最高和。例如：12，其和为 3（1 + 2）。在本教程中，通过使用查询找到具有最大数字和的数字。
为了实现这种方法，我们使用两种方法
朴素方法
构建线段树
演示 1
a[] = {1, 44, 16, 11, 18}
Query = [1, 4]
输出
The maximum digit sum element is 18
解释
在上面的示例中，使用查询的子数组为 {44, 16, 11, 18}。输入数组的起始索引为 0。为了找到最大数字和的元素，以以下方式添加两位数字
44 = 4+4 = 8
16 = 1+6 = 7
11 = 1+1 = 2
18 = 1+8 = 9
最大和为 9，并且具有最大数字和的元素为 18。
演示 2
a[] = {12, 44, 55, 45, 63}
Query = [2, 4]
输出
The maximum digit sum element is 55
解释
在上面的示例中，使用查询 [2, 4] 的子数组为 {55, 45, 63}。为了找到最大数字和的元素，像这样找到每个元素的和
55 = 5+5 = 10
45 = 4+5 = 9
63 = 6+3 = 9
最大和为 10，并且具有此最大和的元素为 55。
C++ 库函数
语法
size(): 它是 C++ 标准库的内置函数。它返回输入字符串的长度。
string_name.size();
pow(): 它在 <cmath> 头文件中定义。它接受两个参数，并返回第一个参数的第二个参数次幂。
pow(a, b);
vector: 它是一个动态数组，在 C++ 的 vector 头文件中定义。可以轻松地插入和删除其元素。
vector<data_type> vector_name;
ceil(): 它在 <cmath> 头文件中定义。它接受一个参数，并返回参数的最近大于或等于的值。
ceil(n);
sizeof(): 它在 C++ 标准库中定义。它在编译时计算变量、常量和数据类型的 size。
sizeof(variable);
算法 1
初始化一个元素数组 a[]。
定义查询以查找元素的索引。
使用 for 循环遍历查询中定义的数组索引。
通过将数字加在一起计算每个元素的和。
打印具有最大数字和的数字。
示例 1
我们使用简单的方法实现任务。在这种方法中，我们使用 for 循环遍历数组，查询中定义了起始和结束范围。计算元素的和，并打印具有最大数字和的元素。
#include <iostream>
using namespace std;
// Function for calculating the digit sum
int digitSum(int no){
int result = 0;
while (no > 0){
result += no % 10;
no /= 10;
}
return result;
}
// Function for finding the maximum sum digit number
int maximumDigitSum(int a[], int s, int i, int j){
int maxs = -1, maxn = -1;
for (int x = i; x <= j; x++){
int result = digitSum(a[x]);
if (result > maxs){
maxs = result;
maxn = a[x];
}
else if (result == maxs && a[x] > maxn){
maxn = a[x];
}
}
return maxn;
}
// code controller
int main(){
// Input array
int a[] = { 11, 14, 34, 51, 32 };
int s = sizeof(a) / sizeof(a[0]);
int i = 1, j = 4;
cout << "The maximum digit sum number is : "<<maximumDigitSum(a, s, i, j) << endl;
return 0;
}
输出
The maximum digit sum number is : 34
算法 2
初始化一个元素数组。
指定查询范围。
构建一个线段树，其中每个节点表示一个元素数组。
线段树的构建首先将其分成两半，每个节点表示两个值。
将值插入左孩子和右孩子。
线段树中的每个节点都有两个值：数字和 maxDigitSum。
使用查询中定义的范围，通过遍历线段树来查找最大数字和。
打印结果。
示例 2
在这里，我们通过构建线段树在 C++ 中实现该问题。构建线段树并使用查询查找最大数字和。递归调用用户定义的函数 maximumDigitSum 来迭代线段树并计算输出。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Function to calculate the digit sum of a number
int digitSumNumber(int no){
int result = 0;
while (no > 0){
result += no % 10;
no /= 10;
}
return result;
}
// Function to build the segment tree
void buildSegmentTree(vector<int>& segtree, const vector<int>& a, int l, int h, int p){
if (l == h){
segtree[p] = a[l];
return;
}
int m = (l + h) / 2;
buildSegmentTree(segtree, a, l, m, 2 * p + 1);
buildSegmentTree(segtree, a, m + 1, h, 2 * p + 2);
segtree[p] = max(segtree[2 * p + 1], segtree[2 * p + 2]);
}
// Function to query the segment tree for maximum digit sum in a given range
int querySegTree(vector<int>& segtree, int i, int j, int l, int h, int p){
if (i <= l && j >= h)
return segtree[p];
if (i > h || j < l)
return 0;
int m = (l + h) / 2;
return max(querySegTree(segtree, i, j, l, m, 2 * p + 1),
querySegTree(segtree, i, j, m + 1, h, 2 * p + 2));
}
// Function to initialize the segment tree
int maxDigitSum(const vector<int>& a, int s, int i, int j){
int segTreeHeight = ceil(log2(s));
int segTreeSize = 2 * pow(2, segTreeHeight) - 1;
vector<int> segtree(segTreeSize);
buildSegmentTree(segtree, a, 0, s - 1, 0);
return querySegTree(segtree, i, j, 0, s - 1, 0);
}
int main(){
vector<int> a = {12, 13, 45, 17, 10, 23};
int s = a.size();
int i = 1, j = 4;
int number = maxDigitSum(a, s, i, j);
cout << "Maximum digit sum in the range [" << i << ", " << j << "]: " << number << endl;
return 0;
}
输出
Maximum digit sum in the range [1, 4]: 45
结论
我们已经完成了本教程关于在查询范围内查找数字最大和的学习。我们使用了两种方法来解决本教程的任务：朴素方法和线段树。用一些示例演示了问题陈述，以便理解其目的。在 C++ 实现过程中，我们初始化一个数组并定义查询范围以查找最大数字和的数字。
214 次浏览
