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

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package 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(i+1)的值。如果位置i的字符是'0'，那么 * 位置i+1的字符必须是'1'，穷举剩下字符的所有可能性，符合要求的字符串数量就是p(i＋1)的值。所以p(i)=p(i+1)+p(i+2)。 * p(N-1)表示除了最后位置的字符，前面的子串全符合要求，并且倒数第二个字符为'1'，此时剩下的最后一个字符既可以是'1'，也可 * 以是'0'，所以p(N-1)=2。p(N)表示所有的字符串已经完全确定，并且符合要求，最后一个字符(N-1)为'1'，所以，此时符合要求 * 的字符串数量就是0~N-1的全体，而不再有后续的可能性，所以p(N)=1。即p(i)如下： * i<N-1时，p(i)=p(i+1)+p(i+2) * i=N-1时，p(i)=2 * i=N时，p(i)=1 * 很明显，可以写成时间复杂度为O(2^N)的递归方法。具体请参看如下的getNum1方法。 * * 根据O(2^N)的方法，当N分别为1，2，3，4，5，6，7，8时，结算的结果为1，2，3，5，8，13，21，34。可以看出，这就是一个 * 形如斐波那契数列的结果，唯一的区别就是斐波那契数列的初始项为1，1。而这个数列的初始项为1，2。所以可很轻易地写出时间复 * 杂度为O(N)，额外空间复杂度为O(1)的方法。 * 具体请参看如下代码中的getNum2方法。 * * 打开了斐波那契数列的这个天窗，我们知道求解斐波那契数列的过程，有时间复杂度为O(logN)方法就是用矩阵乘法的办法求解，具体 * 解释请参考本书"斐波那契数列的3种解法"，这里不再详述。 * 代码实现请参看如下代码中的getNum3方法。 * * @author Created by LiveEveryDay */ public class ZeroLeft1BinaryStrNum3 { public static int getNum3(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return n; } int[][] base = {{1, 1}, {1, 0}}; int[][] res = matrixPower(base, n - 2); return 2 * res[0][0] + res[1][0]; } private static int[][] matrixPower(int[][] m, int p) { int[][] res = new int[m.length][m[0].length]; for (int i = 0; i < res.length; i++) { res[i][i] = 1; } int[][] tmp = m; for (; p != 0; p >>= 1) { if ((p & 1) != 0) { res = multiMatrix(res, tmp); } tmp = multiMatrix(tmp, tmp); } return res; } private static int[][] multiMatrix(int[][] m1, int[][] m2) { int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m2[0].length; i++) { for (int j = 0; j < m1.length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; } public static void main(String[] args) { int n = 8; System.out.printf("The count is: %d", getNum3(n)); } } // ------ Output ------ /* The count is: 34 */