資料結構
網路
關係資料庫管理系統
作業系統
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 次
