888. 公平的糖果棒交换
16lz
2021-02-25
题目如下：
爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j]是鲍勃拥有的第 j 根糖果棒的大小。因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。（一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。）返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1] 是 Bob 必须交换的糖果棒的大小。如果有多个答案，你可以返回其中任何一个。保证答案存在。第一步，求和，算差值
第二步，得出需要交换的数
#include <iostream>#include <vector>bool findElesInArrays(std::vector<int>& arrays, int begin, int end, int ele){ if (begin > end) { return false; } int mid = (begin + end) / 2; if (ele == arrays[mid]) { return true; } else { bool bRet = findElesInArrays(arrays, begin, mid - 1, ele); if (!bRet) { bRet = findElesInArrays(arrays, mid + 1, end, ele); } return bRet; }}bool findElesInArrays(std::vector<int>& arrays, int ele){ for (int i = 0; i < arrays.size(); ++i) { if (arrays[i] == ele) { return true; } } return false;}int getSum(std::vector<int>& vct){ int res = 0; for (int i = 0; i < vct.size(); ++i) { res += vct[i]; } return res;}int main(){ std::vector<int> vct1{1,2,5}; std::vector<int> vct2{2,4}; int sum1 = getSum(vct1); int sum2 = getSum(vct2); if (sum1 > sum2) { if (((sum1 - sum2) % 2) != 0) { std::cout << "not found..." << std::endl; return -1; } int interval = (sum1 - sum2) / 2; for (int i = 0; i < vct2.size(); ++i) { if (findElesInArrays(vct1, 0, vct1.size() - 1, vct2[i] + interval)) { //std::cout << "value1:" << vct2[i] + interval << ", value2:" << vct2[i] << std::endl; std::cout << "found..." << std::endl; return 1; } } std::cout << "not found..." << std::endl; return -1; } else { if (((sum2 - sum1) % 2) != 0) { return -1; } int interval = (sum2 - sum1) / 2; for (int i = 0; i < vct1.size(); ++i) { if (findElesInArrays(vct2, 0, vct2.size() - 1, vct1[i] + interval)) { //std::cout << "value2:" << vct1[i] + interval << ", value1:" << vct1[i] << std::endl; std::cout << "found..." << std::endl; return 1; } } std::cout << "not found..." << std::endl; return -1; }}本解法没有过多的利用STL的特性来提升效率，说下思路：
1、求和。然后计算两个和的插值，因为要两边的值相等，所以调整的数值只能是差值的一半
2、计算要交换的数。这个从和较小的一边开始（和较大的一边开始也可以，只不过换下思路就行了），查找的函数写了两个，一个是二分查找，这种前提是给的数是有序的；如果无序，就只能挨个比较。当然最方便的还是利用STL，不过既然是锻炼思维，还是尽可能不要第一时间采用STL提供的优势。