数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 从 K 个数组中移除部分后缀后计算最小公和
在使用 C++ 数组时，我们有时需要计算多个数组之间的最小公和，同时移除其后缀的一部分。在本文中，我们将探讨使用 C++ 解决此问题的有效方案。
语法
在我们继续在代码中实现之前，让我们先分析一下我们选择的方法的语法。
int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove);
算法
以下是解决移除数组后缀一部分后查找最小公和问题的分步算法：
首先定义函数 findMinimumCommonSum，该函数接受两个参数：arrays，一个表示数组的二维向量；suffixToRemove，一个整数，表示要从每个数组的后缀中移除的元素个数。
初始化一个变量 minimumSum 来存储最小公和，并将其最初设置为一个较大的值。
遍历 arrays 向量中的每个数组。
确定当前数组的大小。
为了避免最终得到空数组，应该考虑跳过 suffixToRemove 超过或等于当前数组总大小的迭代。在这种情况下，移除所有字符不会产生任何有意义的输出。
计算数组元素从索引 0 到 size - suffixToRemove - 1 的总和，并将结果存储在变量 currentSum 中。
如果 currentSum 小于 minimumSum，则使用 currentSum 的值更新 minimumSum。
遍历完所有数组后，minimumSum 将包含移除指定后缀后数组之间的最小公和。
方法 1：暴力法
在这种方法中，我们将生成要移除的后缀的所有可能组合，并计算每个组合的总和。所有组合中最小的是最小公和。
示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove) {
int minimumSum = INT_MAX;
int k = arrays.size();
for (int i = 0; i < k; i++) {
int size = arrays[i].size();
if (suffixToRemove >= size)
continue;
vector<bool> suffix(size, false);
fill(suffix.begin() + size - suffixToRemove, suffix.end(), true);
do {
int currentSum = 0;
for (int j = 0; j < k; j++) {
int arraySum = 0;
for (int l = 0; l < size; l++) {
if (!suffix[l])
arraySum += arrays[j][l];
}
currentSum += arraySum;
}
if (currentSum < minimumSum)
minimumSum = currentSum;
} while (next_permutation(suffix.begin(), suffix.end()));
}
return minimumSum;
}
int main() {
vector<vector<int>> arrays = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int suffixToRemove = 1;
int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);
cout << "Minimum Common Sum: " << minimumCommonSum << endl;
return 0;
}
输出
Minimum Common Sum: 27
解释
在暴力法中，我们的目标是在移除其后缀的指定数量的元素后，找到多个数组之间的最小公和。该方法涉及生成要移除的后缀的所有可能组合，并计算每个组合的总和。所有组合中最小的是最小公和。
为了实现此方法，我们定义了一个名为 findMinimumCommonSum 的函数，该函数接受两个参数：arrays，一个表示数组的二维向量；suffixToRemove，一个整数，表示要从每个数组的后缀中移除的元素个数。
在函数内部，我们初始化一个变量 minimumSum 来存储最小公和，最初设置为 int 的最大可能值。然后，我们遍历 arrays 向量中的每个数组。对于每个数组，我们确定其大小并检查 suffixToRemove 值是否小于大小。
如果条件满足，我们将使用布尔向量生成后缀的所有可能组合。我们将最后 suffixToRemove 个元素填充为 true，其余元素填充为 false。对于每个数组，我们确定其大小并检查 suffixToRemove 值是否小于大小。
我们继续计算对应于后缀向量中 false 指示符的数组值的总和，对于每个组合。我们对所有数组重复此过程，相应地更新 currentSum。
最后，我们将 currentSum 与 minimumSum 进行比较，如果 currentSum 更小，则更新它。在遍历完所有数组和组合后，minimumSum 将包含移除指定后缀后的最小公和。
方法 2：高效排序
在这种方法中，我们将数组按非递减顺序排序，并计算每个数组前 size - suffixToRemove 个元素的总和。所有数组中最小的是最小公和。
示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove) {
int minimumSum = INT_MAX;
int k = arrays.size();
for (int i = 0; i < k; i++) {
int size = arrays[i].size();
if (suffixToRemove >= size)
continue;
sort(arrays[i].begin(), arrays[i].end());
int currentSum = 0;
for (int j = 0; j < size - suffixToRemove; j++)
currentSum += arrays[i][j];
if (currentSum < minimumSum)
minimumSum = currentSum;
}
return minimumSum;
}
int main() {
vector<vector<int>> arrays = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int suffixToRemove = 1;
int minimumCommonSum = findMinimumCommonSum(arrays, suffixToRemove);
cout << "Minimum Common Sum: " << minimumCommonSum << endl;
return 0;
}
输出
Minimum Common Sum: 3
解释
在高效排序方法中，我们的目标是在移除其后缀的指定数量的元素后，找到多个数组之间的最小公和。此方法利用了排序数组可以简化最小和计算的事实。
为了实现此方法，我们定义了一个名为 findMinimumCommonSum 的函数，该函数接受两个参数：arrays，一个表示数组的二维向量；suffixToRemove，一个整数，表示要从每个数组的后缀中移除的元素个数。
在函数内部，我们初始化一个变量 minimumSum 来存储最小公和，最初设置为 int 的最大可能值。然后，我们遍历 arrays 向量中的每个数组。对于每个数组，我们确定其大小并检查 suffixToRemove 值是否小于大小。
满足此先决条件后，我们的下一步将是按升序对构成数组的所有单个组件进行排序；此方法主要有助于确保较小的对象位于其初始部分，以增强排列和可读性。
接下来，我们计算排序数组中前 size - suffixToRemove 个元素的总和。这对应于从后缀中移除指定数量的元素。我们相应地更新 currentSum。
最后，我们将 currentSum 与 minimumSum 进行比较，如果 currentSum 更小，则更新它。遍历完所有数组后，minimumSum 将包含移除指定后缀后的最小公和。
此方法效率很高，因为它消除了生成和遍历所有可能组合的需要，如暴力法中那样。相反，它利用排序属性来简化最小和的计算，从而提高性能。
结论
在本文中，我们探讨了一种在 C++ 中查找 K 个数组之间的最小公和的有效方法，同时移除其后缀的一部分。我们讨论了两种方法：暴力法和高效排序。暴力法涉及生成后缀的所有组合，而高效排序法则对数组进行排序并计算前几个元素的总和。根据数组的大小和要移除的后缀元素的数量，高效排序法通常效率更高。通过在您的 C++ 程序中实现这些方法，您可以轻松地找到多个数组中的最小公和，同时有效地处理后缀移除。
浏览量 107 次
