如何维护自己的网站,南昌市住房和城乡建设网站,中国建设银行招聘,怎样做网站seo优化作者推荐
【动态规划】【数学】【C算法】18赛车
本文涉及知识点
动态规划 数学
805 数组的均值分割
给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中#xff0c;使得 A 数组和 B 数组不为空#xff0c;并且 average(A) average(B)…作者推荐
【动态规划】【数学】【C算法】18赛车
本文涉及知识点
动态规划 数学
805 数组的均值分割
给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中使得 A 数组和 B 数组不为空并且 average(A) average(B) 。 如果可以完成则返回true 否则返回 false 。 注意对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。 示例 1: 输入: nums [1,2,3,4,5,6,7,8] 输出: true 解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。 示例 2: 输入: nums [3,1] 输出: false 参数范围: 1 nums.length 30 0 nums[i] 104
动态规划
令nnums.length halfn/2。不失一般性令A的长度小于等于B则lena的长度取值范围[1,half]lenbn-lena。 数组A的和为Sum i 0 : n − 1 \Large_{i0}^{:n-1} i0:n−1nums[i]*lena/n ,数组A的和必须是整数。nums[i]的和最大为104*30 lean最大为15可以直接相乘看对n的余数是否为0。如果超出整数范围可以先对lena和n约分。
预处理CountToTotal
将nums分成两部分。vLeft[i]记录所有从nums[0,half)选择i个数 可能的和。 vRight[i]记录所有从nums[half,n)中选择i个数的和。下面以vLeft为例vRightei类似。三层循环 第一层循环枚举[0,half)。时间复杂度O(n) 第二层循环从大到小枚举vLeft[j]。 时间复杂度(n)。 第三层循环枚举vLeft[j-1]。 时间复杂度O(2^n) 动态规划的转移方程本轮的vLeft[j]一定是上一轮的vLeft[j-1]nums[i]。总时间复杂度O(1515215) 约106
处理
第一层循环用变量i枚举lena。 第二层循环枚举A从左边选择了j个元素j的取值范围[0,i]。 第三层循环通过iLeft枚举vLeft[j]看vRight[i-j]是否存在totalA - iLeft。 时间复杂度: O(nn2n)
代码
核心代码
int GCD(int n1, int n2)
{int t1 min(n1, n2);int t2 max(n1, n2);if (0 t1){return t2;}return GCD(t2 % t1, t1);
}class Solution {
public:bool splitArraySameAverage(vectorint nums) {const int n nums.size();const int half n / 2;vectorunordered_setint vLeft(1), vRight(1); CountToTotal( vLeft, nums.data(),0, half);CountToTotal(vRight, nums.data()half, 0, n-half);const int total std::accumulate(nums.begin(), nums.end(),0);for (int i 1; i half; i){const int iGCD GCD(i, n);if (0 ! total % (n / iGCD)){continue;//A的和必定为整数}const int totalA total * i / n;for (int j 0; j i; j){// A数组总共选择i个其中从左边选择j个for (const auto iLeft : vLeft[j]){if (vRight[i - j].count(totalA - iLeft)){return true;}}}}return false;}void CountToTotal(std::vectorstd::unordered_setint v, const int* p,int left,int r){v[0].emplace(0);for (int i left; i r ; i){v.emplace_back();for (int j v.size() - 1; j 1; j--){for (const auto pre : v[j - 1]){v[j].emplace(pre p[i]);}}}}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{vectorint nums;{Solution sln;nums { 1,2,3,4,5,6,7,8 };auto res sln.splitArraySameAverage(nums);Assert(true, res);}{Solution sln;nums { 3,1};auto res sln.splitArraySameAverage(nums);Assert(false, res);}{Solution sln;nums { 18,10,5,3 };auto res sln.splitArraySameAverage(nums);Assert(false, res);}}
2023年1月
class Solution { public: bool splitArraySameAverage(vector nums) { if (1 nums.size()) { return false; } const int iLeftMaxLen nums.size() / 2; const int iRightMaxLen nums.size() - iLeftMaxLen; vectorstd::unordered_set vLeftLenSums(iLeftMaxLen1),vRightLenSums(iRightMaxLen1); vLeftLenSums[0].insert(0); for (int i 0; i iLeftMaxLen; i) { for (int j i ; j 0 ; j-- ) { for (auto it : vLeftLenSums[j]) { vLeftLenSums[j 1].insert(it nums[i]); } } vLeftLenSums[1].insert(nums[i]); } vRightLenSums[0].insert(0); for (int i iLeftMaxLen; i nums.size(); i) { for (int j i - iLeftMaxLen; j 0; j–) { for (auto it : vRightLenSums[j]) { vRightLenSums[j 1].insert(it nums[i]); } } } int iTotalSum std::accumulate(nums.begin(), nums.end(), 0); for (int iALen 1; iALen 1 nums.size(); iALen) { double dSum iTotalSum 1.0 / nums.size() iALen; int iSum dSum; bool bInt ((dSum - iSum) 0.0001) || ((dSum - iSum) 0.9999); if (!bInt) { continue; } for (int iLeftLen max(0,iALen-iRightMaxLen); (iLeftLen min(iALen, iLeftMaxLen)); iLeftLen) { for (const auto it : vLeftLenSums[iLeftLen]) { if (vRightLenSums[iALen - iLeftLen].count(iSum - it)) { return true; } } } } return false; } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
