作者推薦

視頻算法專題

本文涉及知識(shí)點(diǎn)

動(dòng)態(tài)規(guī)劃匯總
數(shù)學(xué)

805 數(shù)組的均值分割

給定你一個(gè)整數(shù)數(shù)組 nums
我們要將 nums 數(shù)組中的每個(gè)元素移動(dòng)到 A 數(shù)組 或者 B 數(shù)組中，使得 A 數(shù)組和 B 數(shù)組不為空，并且 average(A) == average(B) 。
如果可以完成則返回true ， 否則返回 false 。
注意：對(duì)于數(shù)組 arr , average(arr) 是 arr 的所有元素的和除以 arr 長(zhǎng)度。
示例 1:
輸入: nums = [1,2,3,4,5,6,7,8]
輸出: true
解釋: 我們可以將數(shù)組分割為 [1,4,5,8] 和 [2,3,6,7], 他們的平均值都是4.5。
示例 2:
輸入: nums = [3,1]
輸出: false
參數(shù)范圍:
1 <= nums.length <= 30
0 <= nums[i] <= 10⁴

動(dòng)態(tài)規(guī)劃

令n=nums.length half=n/2。不失一般性，令A(yù)的長(zhǎng)度小于等于B，則lena的長(zhǎng)度取值范圍[1,half]，lenb=n-lena。
數(shù)組A的和為：Sum${}_{i=0}^{:n?1}$nums[i]*lena/n ,數(shù)組A的和必須是整數(shù)。nums[i]的和最大為10⁴*30 ，lean最大為15，可以直接相乘，看對(duì)n的余數(shù)是否為0。如果超出整數(shù)范圍，可以先對(duì)lena和n約分。

預(yù)處理CountToTotal

將nums分成兩部分。vLeft[i]記錄所有從nums[0,half)選擇i個(gè)數(shù) 可能的和。 vRight[i]記錄所有從nums[half,n)中選擇i個(gè)數(shù)的和。下面以vLeft為例，vRightei類似。三層循環(huán)
第一層循環(huán)：枚舉[0,half)。時(shí)間復(fù)雜度O(n)
第二層循環(huán)：從大到小枚舉vLeft[j]。 時(shí)間復(fù)雜度(n)。
第三層循環(huán)：枚舉vLeft[j-1]。 時(shí)間復(fù)雜度O(2^n)
動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程：本輪的vLeft[j]一定是上一輪的vLeft[j-1]+nums[i]?？倳r(shí)間復(fù)雜度O(15152¹⁵) 約10⁶

處理

第一層循環(huán)：用變量i枚舉lena。
第二層循環(huán)：枚舉A從左邊選擇了j個(gè)元素，j的取值范圍[0,i]。
第三層循環(huán)：通過iLeft枚舉vLeft[j]，看vRight[i-j]是否存在totalA - iLeft。
時(shí)間復(fù)雜度: O(nn2ⁿ)

代碼

核心代碼

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的和必定為整數(shù)
			}
			const int totalA = total * i / n;
			for (int j = 0; j <= i; j++)
			{// A數(shù)組總共選擇i個(gè)，其中從左邊選擇j個(gè)
				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]);
				}
			}
		}
	}
};

測(cè)試用例

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;
}
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)下載

想高屋建瓴的學(xué)習(xí)算法，請(qǐng)下載《喜缺全書算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

測(cè)試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用**C++**實(shí)現(xiàn)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-829444.html

到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃】【數(shù)學(xué)】【C++算法】805 數(shù)組的均值分割的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！