【困难】0左边必有1的二进制字符串数量－Java：解法二

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.String; /** * 0左边必有1的二进制字符串数量 * * 【题目】 * 给定一个整数N求由0字符与1字符组成的长度为N的所有字符串中满足0字符的左边必有1字符的字符串数量。 * * 【难度】 * 困难 * * 【解答】 * 先说一种最暴力的方法就是检查每一个长度为N的二进制字符串看有多少符合要求。一个长度为N的二进制字符串检查是否符合要 * 求的时间复杂度为O(N)长度为N的二进制字符串数量为O(2^N)所以该方法整体的时间复杂度为O(2^NxN)本文不再详述。 * * O(2^N)的方法。假设第0位的字符为最高位字符很明显第0位的字符不能为0。假设p(i)表示0~i-1位置上的字符已经确定这 * 一段符合要求且第i-1位置的字符为1时如果穷举i~N-1位置上的所有情况会产生多少种符合要求的字符串。有了p(i)的定义同 * 时知道不管N是多少最高位的字符只能为1那么只要求出p(1)就是所有符合要求的字符串数量。 * * 那到底p(i)应该怎么求呢根据p(i)的定义在位置i-1的字符已经为1的情况下位置i的宇符可以是1也可以是0。如果 * 位置i的字符是1那么穷举剩下字符的所有可能性并且符合要求的字符串数量就是p(i1)的值。如果位置i的字符是0那么 * 位置i1的字符必须是1穷举剩下字符的所有可能性符合要求的字符串数量就是p(i1)的值。所以p(i)p(i1)p(i2)。 * p(N-1)表示除了最后位置的字符前面的子串全符合要求并且倒数第二个字符为1此时剩下的最后一个字符既可以是1也可 * 以是0所以p(N-1)2。p(N)表示所有的字符串已经完全确定并且符合要求最后一个字符(N-1)为1所以此时符合要求 * 的字符串数量就是0~N-1的全体而不再有后续的可能性所以p(N)1。即p(i)如下 * iN-1时p(i)p(i1)p(i2) * iN-1时p(i)2 * iN时p(i)1 * 很明显可以写成时间复杂度为O(2^N)的递归方法。具体请参看如下的getNum1方法。 * * 根据O(2^N)的方法当N分别为12345678时结算的结果为12358132134。可以看出这就是一个 * 形如斐波那契数列的结果唯一的区别就是斐波那契数列的初始项为11。而这个数列的初始项为12。所以可很轻易地写出时间复 * 杂度为O(N)额外空间复杂度为O(1)的方法。 * 具体请参看如下代码中的getNum2方法。 * * author Created by LiveEveryDay */ public class ZeroLeft1BinaryStrNum2 { public static int getNum2(int n) { if (n 1) { return 0; } if (n 1) { return 1; } int pre 1; int cur 1; int tmp 0; for (int i 2; i n 1; i) { tmp cur; cur pre; pre tmp; } return cur; } public static void main(String[] args) { int n 8; System.out.printf(The count is: %d, getNum2(n)); } } // ------ Output ------ /* The count is: 34 */