极客笔记C++ 在移除一部分后缀的 K 个数组中计算最小公共和
在使用 C++ 数组时，有时我们可能需要计算多个数组中移除部分后缀后的最小公共和。在本文中，我们将使用 C++ 探讨解决这个问题的有效方法。
语法
在我们开始实现方法之前，让我们先分析一下我们选择的方法的语法。
int findMinimumCommonSum(vector<vector<int>>& arrays, int suffixToRemove);
步骤
以下是解决在移除数组后缀的一部分后找到最小公共和的问题的逐步算法：
- 首先定义一个名为findMinimumCommonSum的函数，它接受两个参数——数组arrays，表示2D向量，以及suffixToRemove，一个表示要从每个数组的后缀中移除的元素数量的整数。
-
初始化一个变量minimumSum来存储最小公共和并将其初始值设为一个很大的值。
-
遍历数组向量中的每个数组。
-
确定当前数组的大小。
-
为了避免得到一个空数组，应考虑跳过后缀数量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
解释
在Brute Force方法中，我们的目标是找到从多个数组中在删除指定数量的后缀元素之后的最小公共和。这种方法涉及到生成所有可能的要删除的后缀的组合，并对每个组合计算和。所有组合中的最小和将是最小公共和。
要实现这种方法，我们定义一个名为findMinimumCommonSum的函数，它接受两个参数 – arrays，表示数组的二维向量，和suffixToRemove，表示要从每个数组的后缀中删除的元素的数量的整数。
在函数内部，我们初始化一个名为minimumSum的变量来存储最小公共和，初始值设置为int的最大可能值。然后，我们迭代每个数组在数组向量中。对于每个数组，我们确定其大小，并检查suffixToRemove值是否小于大小。
如果条件满足，我们使用一个布尔向量来生成所有可能的后缀组合。我们用true填充最后suffixToRemove个元素，用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。在迭代所有数组之后，minimumSum将包含在删除指定后缀之后的最小公共和。
这种方法是高效的，因为它消除了生成和迭代所有可能组合的需要，就像暴力方法一样。相反，它利用排序属性来简化最小和的计算，从而提高了性能。
结论
在本文中，我们探讨了在C++中在删除它们的后缀的一部分后，找到K个数组的最小公共和的高效方法。我们讨论了两种方法－暴力方法和高效排序方法。暴力方法涉及生成所有后缀的组合，而高效排序方法对数组进行排序并计算前几个元素的和。根据数组的大小和后缀元素的数量，高效排序方法通常更有效率。通过在您的C++程序中实现这些方法，您可以轻松地找到多个数组中的最小公共和，并有效地处理删除后缀。