Java 中没有连续 1 的二进制字符串

2024年9月10日 | 阅读10分钟

给定一个整数 'N'。我们的任务是找出长度等于 N 的二进制字符串的总数，并且这些字符串不包含连续的 1。

示例 1

输入

int N = 4

输出 8

解释： 对于 N 等于 4，我们有以下二进制字符串。

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111。在这些二进制字符串中，只有字符串：0000, 0001, 0010, 0100, 0101, 1000, 1001 和 1010 不包含连续的 1，这些字符串的数量是 8。因此答案是 8。

示例 2

输入

int N = 2

输出 3

解释： 对于 N 等于 2，我们有以下二进制字符串。

00, 01, 10, 11。在这些二进制字符串中，只有 00, 01 和 10 是不包含连续 1 的字符串，这些字符串的数量是 3。因此答案是 3。

递归方法

对于长度 N，有 2N 个可能的二进制字符串。我们可以使用标准的递归回溯技术进行一些剪枝，并仅组合符合给定条件的字符串。我们将应用简单的递归。对于每个 j 位置，只有两种可能的位可以放置，因为我们只需要生成二进制字符串。显然，只有当 (j - 1) 位置不包含 1 时，才能在 j 位置放置 1。简单来说，在 j 位置放置 1 创建的二进制字符串数量与在 (j - 1) 位置放置 0 创建的二进制字符串数量相同。此外，在 j 位置放置 0 创建的二进制字符串数量与在 (j - 1) 位置放置 1 或 0 创建的二进制字符串数量相同。这形成了一个完美的递归方法。

算法

步骤 1： 初始化变量 'sol' 的值为 0。它存储没有连续 1 的二进制字符串的最终数量。

步骤 2： 调用两次递归方法。在第一次递归调用中，将 0 位和最后一个位置作为方法参数传递；在第二次递归调用中，将 1 位和最后一个位置作为方法参数传递。

第一次递归调用给出了以 0 作为最后一个位的所有二进制字符串的总数。此外，它们不包含连续的 1。
第一次递归调用给出了以 1 作为最后一个位的所有二进制字符串的总数。此外，它们不包含连续的 1。

步骤 3： 在递归方法中

定义递归终止的基本条件：如果当前索引 'indx' 变为 0，则返回 1。
如果当前位（要放置的位）'currBit' 是 0，则对前一个索引进行递归调用，一次传递 'currBit' 作为 0，另一次传递 'currBit' 作为 1。
如果当前位（要放置的位）'currBit' 是 1，则对前一个索引进行唯一递归调用，传递 'currBit' 作为 0，并将从此递归调用发送的值发送回来。

实施

以下是上述算法的实现。

文件名： BinaryString.java

public class BinaryString 
{
public int numberOfBinaryStrings(int n) 
{
// Initializing the variable 'sol' for keeping the final outcome.
int sol = 0;
// The recursive calls.
sol = numberOfBinaryStringsUtil(n - 1, 0);
sol = sol + numberOfBinaryStringsUtil(n - 1, 1);
// Returning the end result.
return sol;
}
// The util method.
public int numberOfBinaryStringsUtil(int indx, int currBit) 
{
// Handling the Base condition.
if (indx == 0) 
{
return 1;
}
// If 'currBit' equals 0, then the previous bit 
// can either be 1 or 0.
if (currBit == 0) 
{
return (numberOfBinaryStringsUtil(indx - 1, 1) +
    numberOfBinaryStringsUtil(indx - 1, 0));
}
// If 'currBit' is 1, then the previous bit has to be 0.
else if (currBit == 1) 
{
return numberOfBinaryStringsUtil(indx - 1, 0);
}
return 0;
}
// Main method
public static void main(String[] argvs) 
{
// creating an object of the class BinaryString
BinaryString obj = new BinaryString();
// input 1
int N = 4;
int sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
System.out.println("\n");
// input 2
N = 2;
sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
}
}

输出

For the binary strings of size: 4
There are only 8 binary strings that do not have consecutive ones.

For the binary strings of size: 2
There are only 3 binary strings that do not have consecutive ones.

复杂度分析： 由于程序使用了两次递归调用，因此程序的时间复杂度为 O(2ⁿ)，其中 n 是二进制字符串的大小。程序空间复杂度为 O(1)，因为程序不使用任何数据结构（不包括递归调用期间的隐式内存消耗）。

程序的时间复杂度太高。因此，上述解决方案对于较大的输入是不可行的。因此，需要进行一些优化。以下方法展示了相同的。

方法：使用动态规划（递归）

算法

步骤 1： 初始化变量 'sol' 的值为 0。它存储没有连续 1 的二进制字符串的最终数量。

步骤 2： 创建一个大小为 (2 * N) 的二维数组 'dpArr'。将所有 dpArr 元素设置为 -1。这里，dpArr[p][q] 表示长度等于 p 且最后一个位等于 q 的二进制字符串的计数。基本条件为 dpArr[0][0] = 1，dpArr[0][1] = 1。

步骤 3： 在计算不包含连续 1 的二进制字符串总数的方法中进行两次递归调用。在第一次递归调用中，将 dpArr、0 位和最后一个位置作为参数传递。在第二次递归调用中，将 dpArr、1 位和最后一个位置作为参数传递。

第一次递归调用给出了以 0 作为最后一个位的所有二进制字符串的总数。此外，它们不包含连续的 1。
第一次递归调用给出了以 1 作为最后一个位的所有二进制字符串的总数。此外，它们不包含连续的 1。

步骤 3： 在递归方法中

定义递归终止的基本条件：如果当前索引 'indx' 变为 0，则返回 dpArr 中对应的值。
如果 dp[indx][currBit] 的值不等于 -1，则表示索引 indx 和 currBit 的值已计算。因此，返回 dp[indx][currBit] 的值。
如果当前位（要放置的位）'currBit' 是 0，则对前一个索引进行递归调用，一次传递 'currBit' 作为 0，另一次传递 'currBit' 作为 1。将这些递归调用的答案之和存储在 dpArr 中。
如果当前位（要放置的位）'currBit' 是 1，则对前一个索引进行唯一递归调用，传递 'currBit' 作为 0，并将此递归调用的值存储在 dpArr 中。

实施

以下是上述算法的实现。

文件名： BinaryString1.java

public class BinaryString1 
{
public int numberOfBinaryStrings(int num) 
{
// Initializing the variable 'sol' for keeping the final outcome.
int sol = 0;
int[][] dpArr = new int[num][2];
// Initializing the array dpArr elements 
// with the value -1
for(int j = 0; j < num; j++)
{
dpArr[j][0] = -1;
dpArr[j][1] = -1;
}
dpArr[0][0] = 1;
dpArr[0][1] = 1;
// The recursive calls.
sol = numberOfBinaryStringsUtil(num - 1, 0, dpArr);
sol = sol + numberOfBinaryStringsUtil(num - 1, 1, dpArr);
// Returning the end result.
return sol;
}
// The util method.
public int numberOfBinaryStringsUtil(int indx, int currBit, int dpArr[][]) 
{
// Handling the Base condition.
if (indx == 0) 
{
return dpArr[indx][currBit];
}
// for the indx and currBit value if dpArr[indx][currBit] is 
// not equal to - 1, then it means its value has already been 
// computed. All we have to do is to return the value.
if (dpArr[indx][currBit] != -1) 
{
return dpArr[indx][currBit];
}
// If 'currBit' equals 0, then the previous bit 
// can either be 1 or 0.
if (currBit == 0) 
{
dpArr[indx][currBit] = (numberOfBinaryStringsUtil(indx - 1, 1, dpArr) +
    numberOfBinaryStringsUtil(indx - 1, 0, dpArr));
}
// If 'currBit' is 1, then the previous bit has to be 0.
else if (currBit == 1) 
{
dpArr[indx][currBit] = numberOfBinaryStringsUtil(indx - 1, 0, dpArr);
}
return dpArr[indx][currBit];
}
// Main method
public static void main(String[] argvs) 
{
// creating an object of the class BinaryString1
BinaryString1 obj = new BinaryString1();
// input 1
int N = 4;
int sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
System.out.println("\n");
// input 2
N = 2;
sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
}
}

输出

For the binary strings of size: 4
There are only 8 binary strings that do not have consecutive ones.

For the binary strings of size: 2
There are only 3 binary strings that do not have consecutive ones.

复杂度分析： 数组 dpArr[] 有 2 * N 个元素，每个元素的值只计算一次。因此，程序的时间复杂度为 O(N)（考虑渐近表示法）。由于数组 dpArr[] 中有 2 * N 个元素，因此程序空间复杂度为 O(N)（再次考虑渐近表示法），其中 N 是二进制字符串的大小。

我们仍然可以在空间复杂度上进行一些优化。请观察以下方法。

方法：使用动态规划（迭代）

这里我们也定义 dpArr[p][q] 为它表示长度为 'p' 且最后一个位为 'q' 的二进制字符串的计数。现在我们定义转换，如 dpArr[p][1] = dpArr[p - 1][0] 和 dpArr[p][1] = dpArr[p - 1][0] + dpArr[p - 1][1]。请注意，不需要保留 'p' 从 0 到 N - 1 的所有 dp 结果。相反，我们需要保留前一个索引的结果，这可以使用两个变量来完成。它节省了大量空间，并将线性空间复杂度优化为常数空间复杂度。

算法

步骤 1： 初始化两个变量 'prv0' 和 'prv1' 为 1。变量 prv0 将保留终止于前一个索引且结尾位为 0 的二进制字符串的总数。类似地，prv1 保留终止于前一个索引且结尾位为 1 的二进制字符串的数量。另外，再声明两个变量 'curr0' 和 'curr1'。

步骤 2： 运行一个从 i 0 到 N 的 for 循环。在 for 循环内，执行以下操作

将 'curr0' 更新为 prv0 + prv1。
将 'curr1' 更新为 prv0。
现在，将 'curr0' 保存在 'prv0' 中，将 'curr1' 保存在 'prv1' 中。

步骤 3： 最后，返回 'curr0' 和 'curr1' 的总和

实施

以下是上述算法的实现。

文件名： BinaryString2.java

public class BinaryString2
{
public int numberOfBinaryStrings(int num) 
{
// Declaring and initializing the variables.
int prv0 = 1;
int prv1 = 1;
int curr0 = 1;
int curr1 = 1;
// Iterating using the for loop
for (int k = 2; k <= num; k++) 
{
// Let dp[p][q] be the total number of binary strings that are of
// the size 'p' and contains the last bit as 'q'.
// curr0 = dp[k][0] = dp[k - 1][0] + dp[k - 1][1]
curr0 = (prv0 + prv1);
// curr1 = dp[k][1] = dp[k - 1][1]
curr1 = prv0;
prv0 = curr0;
prv1 = curr1;
}
// Eventually, return dp[num - 1][0] + dp[num - 1][1].
return (curr0 + curr1);
}
// Main method
public static void main(String[] argvs) 
{
// creating an object of the class BinaryString2
BinaryString2 obj = new BinaryString2();
// input 1
int N = 4;
int sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
System.out.println("\n");
// input 2
N = 2;
sol = obj.numberOfBinaryStrings(N);
System.out.println("For the binary strings of size: " + N);
if(sol != 0)
{
System.out.println("There are only " + sol + " binary strings that do not have consecutive ones.");
}
else
{
System.out.println("There is no binary string that has the consecutive ones.");   
}
}
}

输出

For the binary strings of size: 4
There are only 8 binary strings that do not have consecutive ones.

For the binary strings of size: 2
There are only 3 binary strings that do not have consecutive ones.

复杂度分析： 由于程序使用单个循环，因此程序的时间复杂度为 O(N)，其中 N 是二进制字符串的大小。程序空间复杂度为 O(1)，即常数。

下一主题Java 中将 IP 转换为二进制

Java 中没有连续 1 的二进制字符串

递归方法

算法

实施

方法：使用动态规划（递归）

算法

实施

方法：使用动态规划（迭代）

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中没有连续 1 的二进制字符串

递归方法

算法

实施

方法：使用动态规划（递归）

算法

实施

方法：使用动态规划（迭代）

算法

实施

相关帖子

Java 中查找矩阵的马鞍点

Java 中二叉树的左视图

Arrange an Array in Alternate Positive Negative Elements Using Java

How to Create Package in Java

如何在 Java 中创建具有特定文件属性的文件

Java 中继承和接口的区别

Amicable Pair Number in Java

Java 运算符选择题

Java 8 过滤器

Java 中的图像处理 - 创建随机像素图像

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器