資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用C++查詢以1開頭的二進位制字串的唯一排列數
在本題中，我們得到一個由0和1組成的字串；我們需要找到以1開頭的字串的排列總數。由於答案可能是一個很大的數字，因此我們將結果模1000000007。
Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56
我們將透過應用一些組合數學原理並建立一些公式來解決這個問題。
解決方法
在這個方法中，我們將計算0和1的個數。假設n是字串中1的個數，m是字串中0的個數，L是給定字串的長度，那麼我們用來解決這個問題的公式是：(L-1)!/(n-1)! * m!。
示例
#include <bits/stdc++.h>
#define MOD 1000000007 // defining 1e9 + 7 as MOD
using namespace std;
long long fact(long long n) {
if(n <= 1)
return 1;
return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
int main() {
string s = "101110011";
long long L = s.size(); // length of given string
long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's
for(auto x : s) {
if(x == '1')
count_1++; // frequency of 1's
else
count_0++; // frequency of 0's
}
if(count_1 == 0){
cout << "0\n"; // if string only consists of 0's so our answer will be 0
} else {
long long factL = fact(L-1); // (L-1)!
long long factn = fact(count_1 - 1); // (n-1)!
long long factm = fact(count_0); // m!
long long ans = factL / (factn * factm); // putting the formula
cout << ans << "\n";
}
return 0;
}輸出
56
該程式的時間複雜度為O(N)，其中n是給定字串的長度。
上述程式碼的解釋
在這個方法中，我們首先計算字串中1和0的個數。然後，我們將1放在開頭，然後計算長度為L-1的字串中0和1的所有可能的排列。透過這個公式，我們得到公式：(L-1)! / (n-1)! * m!，其中(n-1)!是剩餘1的排列數，m!是0的排列數。
結論
在本文中，我們透過應用一些組合數學原理併為其建立一個公式來解決一個問題，即查詢以1開頭的二進位制字串的唯一排列數。
我們還學習了這個問題的C++程式以及我們解決這個問題的完整方法（常規方法）。我們可以使用其他語言（例如C、Java、Python等）編寫相同的程式。希望本文對您有所幫助。
更新於：2021年11月25日
360 次瀏覽
廣告