作者推薦

【動(dòng)態(tài)規(guī)劃】【字符串】【行程碼】1531. 壓縮字符串

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

動(dòng)態(tài)規(guī)劃匯總
深度優(yōu)先搜索 組合數(shù)學(xué)

LeetCode1467 兩個(gè)盒子中球的顏色數(shù)相同的概率

桌面上有 2n 個(gè)顏色不完全相同的球，球上的顏色共有 k 種。給你一個(gè)大小為 k 的整數(shù)數(shù)組 balls ，其中 balls[i] 是顏色為 i 的球的數(shù)量。
所有的球都已經(jīng) 隨機(jī)打亂順序 ，前 n 個(gè)球放入第一個(gè)盒子，后 n 個(gè)球放入另一個(gè)盒子（請(qǐng)認(rèn)真閱讀示例 2 的解釋部分）。
注意：這兩個(gè)盒子是不同的。例如，兩個(gè)球顏色分別為 a 和 b，盒子分別為 [] 和 ()，那么 [a] (b) 和 [b] (a) 這兩種分配方式是不同的（請(qǐng)認(rèn)真閱讀示例的解釋部分）。
請(qǐng)返回「兩個(gè)盒子中球的顏色數(shù)相同」的情況的概率。答案與真實(shí)值誤差在 10^-5 以內(nèi)，則被視為正確答案
示例 1：
輸入：balls = [1,1]
輸出：1.00000
解釋：球平均分配的方式只有兩種：

• 顏色為 1 的球放入第一個(gè)盒子，顏色為 2 的球放入第二個(gè)盒子
• 顏色為 2 的球放入第一個(gè)盒子，顏色為 1 的球放入第二個(gè)盒子
  這兩種分配，兩個(gè)盒子中球的顏色數(shù)都相同。所以概率為 2/2 = 1 。
  示例 2：
  輸入：balls = [2,1,1]
  輸出：0.66667
  解釋：球的列表為 [1, 1, 2, 3]
  隨機(jī)打亂，得到 12 種等概率的不同打亂方案，每種方案概率為 1/12 ：
  [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
  然后，我們將前兩個(gè)球放入第一個(gè)盒子，后兩個(gè)球放入第二個(gè)盒子。
  這 12 種可能的隨機(jī)打亂方式中的 8 種滿足「兩個(gè)盒子中球的顏色數(shù)相同」。
  概率 = 8/12 = 0.66667
  示例 3：
  輸入：balls = [1,2,1,2]
  輸出：0.60000
  解釋：球的列表為 [1, 2, 2, 3, 4, 4]。要想顯示所有 180 種隨機(jī)打亂方案是很難的，但只檢查「兩個(gè)盒子中球的顏色數(shù)相同」的 108 種情況是比較容易的。
  概率 = 108 / 180 = 0.6 。
  提示：
  1 <= balls.length <= 8
  1 <= balls[i] <= 6
  sum(balls) 是偶數(shù)

深度優(yōu)先搜索

極端情況下，8種球，6種顏色。每種球選擇0到6個(gè)，共7種選擇。7⁸ 約等于5e6。再加上剪支，能過(guò)。
m_iCan 記錄，合法選擇的可能數(shù)。
m_iAns 記錄，符合題意的可能數(shù)。
注意： 從ball[i]種選擇m個(gè)求，是組合$C_{balls[i]}^m$

代碼

核心代碼

template<class Result =int >
class CCombination
{
public:
	CCombination()
	{
		m_v.assign(1, vector<Result>(1,1));
	}
	Result Get(int sel, int total)
	{
		while (m_v.size() <= total)
		{
			int iSize = m_v.size();
			m_v.emplace_back(iSize + 1, 1);
			for (int i = 1; i < iSize; i++)
			{
				m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i - 1];
			}
		}
		return m_v[total][sel];
	}
protected:
	vector<vector<Result>> m_v;
};

class Solution {
public:
	double getProbability(vector<int>& balls) {
		m_iN = std::accumulate(balls.begin(), balls.end(), 0) / 2;
		DFS(balls, 0, 0, 0, 0,1);
		return (double)m_iiAns / m_iiSel;
	}
	void DFS(const vector<int>& balls,int iCur,int iHasSel,int iSelAll,int iSel0,long long iiMul)
	{
		if (iHasSel == m_iN)
		{
			m_iiSel += iiMul;
			if (iSelAll == iSel0 + balls.size()- iCur )
			{//余下的球全部不選擇
				m_iiAns += iiMul;
			}
			return;
		}
		if (iCur >= balls.size())
		{
			return ;
		}
		for (int curSel = 0; (curSel <= balls[iCur])&&(curSel+iHasSel <= m_iN); curSel++)
		{
			DFS(balls, iCur + 1, curSel + iHasSel, iSelAll + (curSel == balls[iCur]), iSel0 + (0 == curSel),iiMul*m_com.Get(curSel, balls[iCur]));
		}
	}
	long long m_iN, m_iiSel=0, m_iiAns=0;
	CCombination<int> m_com;
};

測(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> balls;
	
	{
		Solution sln;
		balls = { 1, 1 };
		auto res = sln.getProbability(balls);
		assert(abs(res -  1 ) < 0.0001);
	}

	{
		Solution sln;
		balls = { 2,1,1 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.66667) < 0.0001);
	}

	{
		Solution sln;
		balls = { 1,2,1,2 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.6) < 0.0001);
	}
	{
		Solution sln;
		balls = { 6, 6, 6, 6, 6, 6, 6, 6 };
		auto res = sln.getProbability(balls);
		assert(abs(res - 0.85571) < 0.0001);
	}
	
}

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

動(dòng)態(tài)規(guī)劃的狀態(tài)表示

pre[sel][c]記錄可能排列數(shù)量。sel表示第一個(gè)盒子的球數(shù)，c表示顏色差。c等于0，表示左邊全選的球的數(shù)量 比 右邊全先的求的數(shù)量 少6。 c = 全部在第一個(gè)盒子的顏色數(shù)- 全部在第二個(gè)盒子的顏色+6。
不在兩種顏色相差8的情況：那樣一個(gè)盒子為空，和n個(gè)球矛盾。
不存在顏色相差7的情況：全選7種顏色，至少有7個(gè)球。全先1種顏色頂多6個(gè)球。無(wú)法相等。
存在相差6的情況：{** 1 1 1 1 1 1 ** 3 3} 。前6個(gè)球是1，全選。

class Solution {
public:
	double getProbability(vector<int>& balls) {		
		const int n = std::accumulate(balls.begin(), balls.end(), 0) / 2;
		vector<vector<long long>> pre(n + 1, vector<long long>(13, 0));
		pre[0][6] = 1;
		for (const auto& b : balls)
		{
			vector<vector<long long>> dp(n + 1, vector<long long>(13, 0));
			for (int col = 0; col < 13; col++)
			{
				for (int preSel = 0; preSel <= n; preSel++)
				{
					for (int curSel = 0; (curSel <= b) && (preSel + curSel <= n); curSel++)
					{
						int col1 = col + (curSel == b) - (curSel == 0);
						if ((col1 >= 0) && (col1 < 13))
						{
							dp[preSel + curSel][col1] += pre[preSel][col]*m_com.Get(curSel,b);
						}
					}
				}
			}
			pre.swap(dp);
		}
		long long llAns = pre.back()[6], llSel = std::accumulate(pre.back().begin(), pre.back().end(),0LL);
		return (double)llAns / llSel;
	}
	CCombination<int> m_com;
};

2023年2月版

class Solution {
public:
double getProbability(const vector& balls) {
const int iTotal = std::accumulate(balls.begin(), balls.end(), 0);
m_c = balls.size();
vector<vector> combinations(6 + 1, vector(6 + 1, 1));
for (int i = 1; i <= 6; i++)
{
for (int j = 1; j < i; j++)
{
combinations[i][j] = combinations[i - 1][j - 1] + combinations[i - 1][j];
}
}
vector<vector> pre(13, vector(iTotal + 1));
pre[6][0] = 1;
for (int i = 0; i < balls.size(); i++)
{
vector<vector> dp(13, vector(iTotal + 1));
for (int colorDiff = 0; colorDiff < 13; colorDiff++)
{
for (int selBallNum = 0; selBallNum <= iTotal; selBallNum++)
{
if (0 == pre[colorDiff][selBallNum])
{
continue;
}
for (int k = 0; k <= balls[i]; k++)
{
int iNewColorDiff = colorDiff;
if (0 == k)
{
iNewColorDiff–;
}
if (balls[i] == k)
{
iNewColorDiff++;
}
if ((iNewColorDiff<0) || (iNewColorDiff >12))
{
continue;
}
const int iNewSelBallNum = selBallNum + k;
if ( iNewSelBallNum > iTotal)
{
continue;
}
dp[iNewColorDiff][iNewSelBallNum] += pre[colorDiff][selBallNum] * combinations[balls[i]][k];
}
}
}
pre.swap(dp);
}
double dNum = 0, dEqualNum = 0;
for (int colorDiff = 0; colorDiff < 13; colorDiff++)
{
const int selBallNum = iTotal / 2;
//for (int selBallNum = 0; selBallNum <= iTotal; selBallNum++)
{
const double dAdd = (double)pre[colorDiff][selBallNum] ;
dNum += dAdd;
if (6 == colorDiff)
{
dEqualNum += dAdd;
}
}
}
return (double)dEqualNum / dNum;
}
int m_c;
};

擴(kuò)展閱讀

視頻課程

有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適），可以先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽(tīng)白銀講師（也就是鄙人）的講解。
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)下載《喜缺全書(shū)算法冊(cè)》doc版
https://download.csdn.net/download/he_zhidan/88348653

。也就是我們常說(shuō)的專業(yè)的人做專業(yè)的事。 |
|如果程序是一條龍，那算法就是他的是睛|

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

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

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-833482.html

到了這里，關(guān)于【深度優(yōu)先搜索】【組合數(shù)學(xué)】【動(dòng)態(tài)規(guī)劃】1467.兩個(gè)盒子中球的顏色數(shù)相同的概率的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！