当前位置: 首页 > news >正文

门户网站开发 论文淘宝流量助手平台

门户网站开发 论文,淘宝流量助手平台,专门做淘宝收藏可以赚钱的网站,代做土木毕业设计网站作者推荐 【动态规划】【数学】【C算法】18赛车 本文涉及知识点 动态规划 数学 805 数组的均值分割 给定你一个整数数组 nums 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中,使得 A 数组和 B 数组不为空,并且 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

动态规划

令n=nums.length half=n/2。不失一般性,令A的长度小于等于B,则lena的长度取值范围[1,half],lenb=n-lena。
数组A的和为:Sum i = 0 : n − 1 \Large_{i=0}^{:n-1} i=0:n1nums[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(vector<int>& nums) {const int n = nums.size();const int half = n / 2;vector<unordered_set<int>> 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::vector<std::unordered_set<int>>& 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]);}}}}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<int> 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;
vector<std::unordered_set> vLeftLenSums(iLeftMaxLen+1),vRightLenSums(iRightMaxLen+1);
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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

http://www.hrbkazy.com/news/19040.html

相关文章:

  • 网站 蓝色引擎优化seo
  • 用js做网站的滚屏效果湖南疫情最新情况
  • 广州网站建设市场关键词代发排名
  • asp网站建设报告书外链推广网站
  • 网站制作.网站如何推广运营
  • 无锡阿里巴巴做网站网站优化技巧
  • 怎么制作幼儿园公众号比较好的网络优化公司
  • 专做定制网站建设b2b外贸接单平台
  • html旅游网页完整代码seo导航
  • 做壁纸的网站网络推广发帖网站
  • 做个政府网站要多少钱微信营销平台
  • 郑州做网站元辰郑州网站seo
  • 顺义区住房和城乡建设委员会网站网站优化+山东
  • php学校网站源码seo怎么优化方案
  • 软件工程考研要考哪些科目长春seo关键词排名
  • 别的网站做相关链接怎么做郑州关键词排名公司电话
  • 商城网站 没有什么文章 怎样优化淘宝指数查询
  • 有什么做图片赚钱的网站超级seo外链工具
  • 校园文化建设图片网站搜索引擎营销
  • aspcms网站模板google play官网入口
  • 建设网站需要用到哪些软件软件外包公司排行榜
  • 网站建立的研究方案互联网广告投放公司
  • 深圳网站建设找哪家好搜索关键词排行榜
  • 网站logo下载网站优化是什么意思
  • 产品展示网站建设关键词优化seo优化
  • 微信下载网址是多少深圳搜索引擎优化收费
  • 孝感网站建设专家网络的推广方式有哪些
  • wordpress分类目录和页面朝阳区seo技术
  • seo的形式有哪些seo 关键词优化
  • 学生为学校做网站附近哪里有计算机培训班