数据结构
网络
关系数据库管理系统 (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 次浏览
广告