找到数组中非相邻 K 项的最小总和
find minimum sum of non-neighbouring K entries inside an array
给定一个大小为 N 的整数数组 A，找出 K 个非相邻条目的最小总和（条目不能彼此相邻，例如，如果 K 为 2，则您不能添加 A[2]、A[3] 并称其为最小总和，即使它是，因为它们彼此 adjacent/neighboring），示例：
A[] = {355, 46, 203, 140, 28}, k = 2, result would be 74 (46 + 28)
A[] = {9, 4, 0, 9, 14, 7, 1}, k = 3, result would be 10 (9 + 0 + 1)
这个问题有点类似于 leetcode 上的 House Robber，除了我们的任务是寻找最小和并限制 K 个条目，而不是寻找非相邻条目的最大总和。
从我的角度来看，这显然是一个动态规划问题，所以我试图递归地分解问题并实现如下：
#include <vector>
#include <iostream>
using namespace std;
int minimal_k(vector<int>& nums, int i, int k)
{
if (i == 0) return nums[0];
if (i < 0 || !k) return 0;
return min(minimal_k(nums, i - 2, k - 1) + nums[i], minimal_k(nums, i - 1, k));
}
int main()
{
// example above
vector<int> nums{9, 4, 0, 9, 14, 7, 1};
cout << minimal_k(nums, nums.size() - 1, 3);
// output is 4, wrong answer
}
这是我对解决方案的尝试，我对此进行了很多尝试但没有运气，那么解决这个问题的方法是什么？
这一行：
if (i < 0 || !k) return 0;
如果k为0，你可能应该return return0。但是如果i < 0或者数组的有效长度小于k，你可能需要 return 一个非常大的值，以便求和结果高于任何有效的解决方案。
在我的解决方案中，当递归到无效子集或当 k 超过剩余长度时，我将递归 return INT_MAX 作为 long long。
对于这些动态规划和递归问题中的任何一个，缓存结果以便您不重复相同的递归搜索将有助于解决很多问题。对于非常大的输入集，这会将速度提高几个数量级。
这是我的解决方案。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
// the "cache" is a map from offset to another map
// that tracks k to a final result.
typedef unordered_map<size_t, unordered_map<size_t, long long>> CACHE_MAP;
bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result);
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result);
long long minimal_k_impl(const vector<int>& nums, size_t offset, size_t k, CACHE_MAP& cache)
{
long long result = INT_MAX;
size_t len = nums.size();
if (k == 0)
{
return 0;
}
if (offset >= len)
{
return INT_MAX; // exceeded array boundary, return INT_MAX
}
size_t effective_length = len - offset;
// If we have more k than remaining elements, return INT_MAX to indicate
// that this recursion is invalid
// you might be able to reduce to checking (effective_length/2+1 < k)
if ( (effective_length < k) || ((effective_length == k) && (k != 1)) )
{
return INT_MAX;
}
if (get_cache_result(cache, offset, k, result))
{
return result;
}
long long sum1 = nums[offset] + minimal_k_impl(nums, offset + 2, k - 1, cache);
long long sum2 = minimal_k_impl(nums, offset + 1, k, cache);
result = std::min(sum1, sum2);
insert_into_cache(cache, offset, k, result);
return result;
}
long long minimal_k(const vector<int>& nums, size_t k)
{
CACHE_MAP cache;
return minimal_k_impl(nums, 0, k, cache);
}
bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result)
{
// effectively this code does this:
// result = cache[offset][k]
bool ret = false;
auto itor1 = cache.find(offset);
if (itor1 != cache.end())
{
auto& inner_map = itor1->second;
auto itor2 = inner_map.find(k);
if (itor2 != inner_map.end())
{
ret = true;
result = itor2->second;
}
}
return ret;
}
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result)
{
cache[offset][k] = result;
}
int main()
{
vector<int> nums1{ 355, 46, 203, 140, 28 };
vector<int> nums2{ 9, 4, 0, 9, 14, 7, 1 };
vector<int> nums3{8,6,7,5,3,0,9,5,5,5,1,2,9,-10};
long long result = minimal_k(nums1, 2);
std::cout << result << std::endl;
result = minimal_k(nums2, 3);
std::cout << result << std::endl;
result = minimal_k(nums3, 3);
std::cout << result << std::endl;
return 0;
}
核心排序相关问题。要找到最小 k 个非相邻元素的总和，需要最小值元素通过排序彼此相邻。来看看这个排序方式，
给定输入数组 = [9, 4, 0, 9, 14, 7, 1] 和 k = 3
创建另一个包含输入数组元素的数组，索引如下所示，
[9, 0], [4, 1], [0, 2], [9, 3], [14, 4], [7, 5], [1, 6]
然后对这个数组进行排序。
这个元素和索引数组背后的动机是，排序后每个元素的索引信息不会丢失。
需要多一个数组来记录使用过的索引，所以排序后的初始信息如下图，
Element and Index array
..............................
| 0 | 1 | 4 | 7 | 9 | 9 | 14 |
..............................
2 6 1 5 3 0 4 <-- Index
Used index record array
..............................
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
..............................
0 1 2 3 4 5 6 <-- Index
In used index record array 0 (false)表示该索引处的元素尚未包含在最小和中。
排序数组的前面元素是最小值元素，我们将它包含在最小和中，并更新使用索引记录数组以表明使用了该元素，如下所示，
字体元素在索引 2 处为 0 并且由于此集合 1(true) 在所用索引记录数组的索引 2 处显示如下，
min sum = 0
Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
..............................
0 1 2 3 4 5 6
迭代到排序数组中的下一个元素，正如您在上面看到的那样，它是 1 并且索引为 6。要将 1 包含在最小和中，我们必须找到 1 的左或右相邻元素是否已被使用，因此 1 具有索引 6 并且它是最后一个元素在输入数组中，这意味着我们只需要检查索引 5 的值是否已被使用，这可以通过查看已使用的索引记录数组来完成，如上所示 usedIndexRerocd[5] = 0 所以 1可以考虑作为最小和。使用1后，状态更新为
min sum = 0 + 1
Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
0 1 2 3 4 5 6
而不是迭代到索引 1 处 4 的下一个元素，但这不能被考虑，因为索引 0 处的元素已经被使用，元素 [=43 也会发生同样的情况=] 因为它们分别位于索引 5, 3 并且与使用的元素相邻。
最后在索引 = 0 迭代到 9 并通过查看使用的索引记录数组 usedIndexRecordArray[1] = 0 这就是为什么 9 可以包含在最小总和和最终状态达到以下的原因，
min sum = 0 + 1 + 9
Used index record array
..............................
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
0 1 2 3 4 5 6
终于minimum sum = 10,
最坏情况 场景之一，当输入数组已经排序时，至少需要迭代 2*k - 1 个元素以找到非相邻 k 元素的最小总和，如图所示以下
input array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 4
则应考虑以下突出显示的元素以获得最小和，
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
注意：您必须包括所有输入验证，例如验证之一是，如果您想找到 k 非相邻元素的最小总和，则输入至少应具有 2*k - 1 个元素。我不包括这些验证，因为我知道问题的所有输入限制。
#include <iostream>
#include <vector>
#include <algorithm>
using std::cout;
long minSumOfNonAdjacentKEntries(std::size_t k, const std::vector<int>& arr){
if(arr.size() < 2){
return 0;
}
std::vector<std::pair<int, std::size_t>> numIndexArr;
numIndexArr.reserve(arr.size());
for(std::size_t i = 0, arrSize = arr.size(); i < arrSize; ++i){
numIndexArr.emplace_back(arr[i], i);
}
std::sort(numIndexArr.begin(), numIndexArr.end(), [](const std::pair<int, std::size_t>& a,
const std::pair<int, std::size_t>& b){return a.first < b.first;});
long minSum = numIndexArr.front().first;
std::size_t elementCount = 1;
std::size_t lastIndex = arr.size() - 1;
std::vector<bool> usedIndexRecord(arr.size(), false);
usedIndexRecord[numIndexArr.front().second] = true;
for(std::vector<std::pair<int, std::size_t>>::const_iterator it = numIndexArr.cbegin() + 1,
endIt = numIndexArr.cend(); elementCount < k && endIt != it; ++it){
bool leftAdjacentElementUsed = (0 == it->second) ? false : usedIndexRecord[it->second - 1];
bool rightAdjacentElementUsed = (lastIndex == it->second) ? false : usedIndexRecord[it->second + 1];
if(!leftAdjacentElementUsed && !rightAdjacentElementUsed){
minSum += it->first;
++elementCount;
usedIndexRecord[it->second] = true;
}
}
return minSum;
}
int main(){
cout<< "k = 2, [355, 46, 203, 140, 28], min sum = "<< minSumOfNonAdjacentKEntries(2, {355, 46, 203, 140, 28})
<< '\n';
cout<< "k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = "<< minSumOfNonAdjacentKEntries(3, {9, 4, 0, 9, 14, 7, 1})
<< '\n';
}
输出：
k = 2, [355, 46, 203, 140, 28], min sum = 74
k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = 10
给定一个大小为 N 的整数数组 A，找出 K 个非相邻条目的最小总和（条目不能彼此相邻，例如，如果 K 为 2，则您不能添加 A[2]、A[3] 并称其为最小总和，即使它是，因为它们彼此 adjacent/neighboring），示例：
A[] = {355, 46, 203, 140, 28}, k = 2, result would be 74 (46 + 28)
A[] = {9, 4, 0, 9, 14, 7, 1}, k = 3, result would be 10 (9 + 0 + 1)
这个问题有点类似于 leetcode 上的 House Robber，除了我们的任务是寻找最小和并限制 K 个条目，而不是寻找非相邻条目的最大总和。
从我的角度来看，这显然是一个动态规划问题，所以我试图递归地分解问题并实现如下：
#include <vector>
#include <iostream>
using namespace std;
int minimal_k(vector<int>& nums, int i, int k)
{
if (i == 0) return nums[0];
if (i < 0 || !k) return 0;
return min(minimal_k(nums, i - 2, k - 1) + nums[i], minimal_k(nums, i - 1, k));
}
int main()
{
// example above
vector<int> nums{9, 4, 0, 9, 14, 7, 1};
cout << minimal_k(nums, nums.size() - 1, 3);
// output is 4, wrong answer
}
这是我对解决方案的尝试，我对此进行了很多尝试但没有运气，那么解决这个问题的方法是什么？
这一行：
if (i < 0 || !k) return 0;
如果k为0，你可能应该return return0。但是如果i < 0或者数组的有效长度小于k，你可能需要 return 一个非常大的值，以便求和结果高于任何有效的解决方案。
在我的解决方案中，当递归到无效子集或当 k 超过剩余长度时，我将递归 return INT_MAX 作为 long long。
对于这些动态规划和递归问题中的任何一个，缓存结果以便您不重复相同的递归搜索将有助于解决很多问题。对于非常大的输入集，这会将速度提高几个数量级。
这是我的解决方案。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
// the "cache" is a map from offset to another map
// that tracks k to a final result.
typedef unordered_map<size_t, unordered_map<size_t, long long>> CACHE_MAP;
bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result);
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result);
long long minimal_k_impl(const vector<int>& nums, size_t offset, size_t k, CACHE_MAP& cache)
{
long long result = INT_MAX;
size_t len = nums.size();
if (k == 0)
{
return 0;
}
if (offset >= len)
{
return INT_MAX; // exceeded array boundary, return INT_MAX
}
size_t effective_length = len - offset;
// If we have more k than remaining elements, return INT_MAX to indicate
// that this recursion is invalid
// you might be able to reduce to checking (effective_length/2+1 < k)
if ( (effective_length < k) || ((effective_length == k) && (k != 1)) )
{
return INT_MAX;
}
if (get_cache_result(cache, offset, k, result))
{
return result;
}
long long sum1 = nums[offset] + minimal_k_impl(nums, offset + 2, k - 1, cache);
long long sum2 = minimal_k_impl(nums, offset + 1, k, cache);
result = std::min(sum1, sum2);
insert_into_cache(cache, offset, k, result);
return result;
}
long long minimal_k(const vector<int>& nums, size_t k)
{
CACHE_MAP cache;
return minimal_k_impl(nums, 0, k, cache);
}
bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result)
{
// effectively this code does this:
// result = cache[offset][k]
bool ret = false;
auto itor1 = cache.find(offset);
if (itor1 != cache.end())
{
auto& inner_map = itor1->second;
auto itor2 = inner_map.find(k);
if (itor2 != inner_map.end())
{
ret = true;
result = itor2->second;
}
}
return ret;
}
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result)
{
cache[offset][k] = result;
}
int main()
{
vector<int> nums1{ 355, 46, 203, 140, 28 };
vector<int> nums2{ 9, 4, 0, 9, 14, 7, 1 };
vector<int> nums3{8,6,7,5,3,0,9,5,5,5,1,2,9,-10};
long long result = minimal_k(nums1, 2);
std::cout << result << std::endl;
result = minimal_k(nums2, 3);
std::cout << result << std::endl;
result = minimal_k(nums3, 3);
std::cout << result << std::endl;
return 0;
}
核心排序相关问题。要找到最小 k 个非相邻元素的总和，需要最小值元素通过排序彼此相邻。来看看这个排序方式，
给定输入数组 = [9, 4, 0, 9, 14, 7, 1] 和 k = 3
创建另一个包含输入数组元素的数组，索引如下所示，
[9, 0], [4, 1], [0, 2], [9, 3], [14, 4], [7, 5], [1, 6]
然后对这个数组进行排序。
这个元素和索引数组背后的动机是，排序后每个元素的索引信息不会丢失。
需要多一个数组来记录使用过的索引，所以排序后的初始信息如下图，
Element and Index array
..............................
| 0 | 1 | 4 | 7 | 9 | 9 | 14 |
..............................
2 6 1 5 3 0 4 <-- Index
Used index record array
..............................
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
..............................
0 1 2 3 4 5 6 <-- Index
In used index record array 0 (false)表示该索引处的元素尚未包含在最小和中。
排序数组的前面元素是最小值元素，我们将它包含在最小和中，并更新使用索引记录数组以表明使用了该元素，如下所示，
字体元素在索引 2 处为 0 并且由于此集合 1(true) 在所用索引记录数组的索引 2 处显示如下，
min sum = 0
Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
..............................
0 1 2 3 4 5 6
迭代到排序数组中的下一个元素，正如您在上面看到的那样，它是 1 并且索引为 6。要将 1 包含在最小和中，我们必须找到 1 的左或右相邻元素是否已被使用，因此 1 具有索引 6 并且它是最后一个元素在输入数组中，这意味着我们只需要检查索引 5 的值是否已被使用，这可以通过查看已使用的索引记录数组来完成，如上所示 usedIndexRerocd[5] = 0 所以 1可以考虑作为最小和。使用1后，状态更新为
min sum = 0 + 1
Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
0 1 2 3 4 5 6
而不是迭代到索引 1 处 4 的下一个元素，但这不能被考虑，因为索引 0 处的元素已经被使用，元素 [=43 也会发生同样的情况=] 因为它们分别位于索引 5, 3 并且与使用的元素相邻。
最后在索引 = 0 迭代到 9 并通过查看使用的索引记录数组 usedIndexRecordArray[1] = 0 这就是为什么 9 可以包含在最小总和和最终状态达到以下的原因，
min sum = 0 + 1 + 9
Used index record array
..............................
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
0 1 2 3 4 5 6
终于minimum sum = 10,
最坏情况 场景之一，当输入数组已经排序时，至少需要迭代 2*k - 1 个元素以找到非相邻 k 元素的最小总和，如图所示以下
input array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 4
则应考虑以下突出显示的元素以获得最小和，
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
注意：您必须包括所有输入验证，例如验证之一是，如果您想找到 k 非相邻元素的最小总和，则输入至少应具有 2*k - 1 个元素。我不包括这些验证，因为我知道问题的所有输入限制。
#include <iostream>
#include <vector>
#include <algorithm>
using std::cout;
long minSumOfNonAdjacentKEntries(std::size_t k, const std::vector<int>& arr){
if(arr.size() < 2){
return 0;
}
std::vector<std::pair<int, std::size_t>> numIndexArr;
numIndexArr.reserve(arr.size());
for(std::size_t i = 0, arrSize = arr.size(); i < arrSize; ++i){
numIndexArr.emplace_back(arr[i], i);
}
std::sort(numIndexArr.begin(), numIndexArr.end(), [](const std::pair<int, std::size_t>& a,
const std::pair<int, std::size_t>& b){return a.first < b.first;});
long minSum = numIndexArr.front().first;
std::size_t elementCount = 1;
std::size_t lastIndex = arr.size() - 1;
std::vector<bool> usedIndexRecord(arr.size(), false);
usedIndexRecord[numIndexArr.front().second] = true;
for(std::vector<std::pair<int, std::size_t>>::const_iterator it = numIndexArr.cbegin() + 1,
endIt = numIndexArr.cend(); elementCount < k && endIt != it; ++it){
bool leftAdjacentElementUsed = (0 == it->second) ? false : usedIndexRecord[it->second - 1];
bool rightAdjacentElementUsed = (lastIndex == it->second) ? false : usedIndexRecord[it->second + 1];
if(!leftAdjacentElementUsed && !rightAdjacentElementUsed){
minSum += it->first;
++elementCount;
usedIndexRecord[it->second] = true;
}
}
return minSum;
}
int main(){
cout<< "k = 2, [355, 46, 203, 140, 28], min sum = "<< minSumOfNonAdjacentKEntries(2, {355, 46, 203, 140, 28})
<< '\n';
cout<< "k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = "<< minSumOfNonAdjacentKEntries(3, {9, 4, 0, 9, 14, 7, 1})
<< '\n';
}
输出：
k = 2, [355, 46, 203, 140, 28], min sum = 74
k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = 10