根据给定的条件,将数组拆分成相等的部分(C++)
接下来,我们来看个问题。假设给定了一个数组 arr。我们必须检查数组是否可以分成两部分,满足以下条件:
- 两个子数组相减结果相同
- 所有 5 的倍数元素都必须在同组中
- 所有 3 的倍数但不是 5 的倍数的元素都必须在同组中
- 其他所有元素都必须在其他组中。
假设数组元素为 {1, 4, 3},那么可以拆分,因为 {1, 3} 的和与 {4} 的和相同,并且给定的条件也符合这些分组。
算法
isSplitArray(arr, n, start, left_sum, right_sum) −
Begin if start = n, then return true when left_sum = right_sum, otherwise false if arr[start] is divisible by 5, then add arr[start] with the left_sum else if arr[start] is divisible by 3, then add arr[start] with the right_sum else return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]) isSplitArray(arr, n, start + 1, left_sum, right_sum) End
示例
#include <iostream> using namespace std; bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) { if (start == n) //when it reaches at the end return left_sum == right_sum; if (arr[start] % 5 == 0) //when the element is divisible by 5, add to left sum left_sum += arr[start]; else if (arr[start] % 3 == 0) //when the element is divisible by 3 but not 5, add to right sum right_sum += arr[start]; else // otherwise it can be added to any of the sub-arrays return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]); // For cases when element is multiple of 3 or 5. return isSplitArray(arr, n, start + 1, left_sum, right_sum); } int main() { int arr[] = {1, 4, 3}; int n = sizeof(arr)/sizeof(arr[0]); if(isSplitArray(arr, n, 0, 0, 0)){ cout <<"Can be split"; } else { cout <<"Can not be split"; } }
输出
Can be split
广告