算法（二进制字符串中具有奇数十进制值的子字符串数） _十进制

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
的PHP

【算法（二进制字符串中具有奇数十进制值的子字符串数）】给定一个仅包含0和1的二进制字符串。编写程序以查找此字符串的子字符串数, 其十进制表示形式为奇数。
例子：

Input : 101Output : 3Explanation : Substrigs with odd decimal representation are:{1, 1, 101}Input : 1101Output : 6Explanation : Substrigs with odd decimal representation are:{1, 1, 1, 11, 101, 1011}

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。蛮力法：解决上述问题的最简单方法是生成给定字符串的所有可能的子字符串, 并将它们转换为十进制, 然后检查十进制表示形式是否为奇数。你可以参考这个二进制到十进制转换的文章。
时间复杂度：O(n * n)
高效的方法：一种有效的方法是观察如果二进制数的最后一位是1, 那么它是奇数, 否则是偶数。因此, 现在我们的问题简化为检查最后一个索引值为1的所有子字符串。通过从末尾遍历, 可以轻松地在单个遍历中解决此问题。如果字符串中第i个索引的值为1, 则该索引之前有i个奇数子字符串。但这还包括前导零的字符串。因此, 为了解决这个问题, 我们可以采用一个辅助数组来保持第i个索引之前的1的数量计数。我们只计算1对。
以下是此方法的实现：
C ++

// CPP program to count substrings // with odd decimal value #include< iostream> using namespace std; // function to count number of substrings // with odd decimal representation int countSubstr(string s) { int n = s.length(); // auxiliary array to store count // of 1's before ith index int auxArr[n] = {0}; if (s[0] == '1' ) auxArr[0] = 1; // storecount of 1's before // i-thindex for ( int i=1; i< n; i++) { if (s[i] == '1' ) auxArr[i] = auxArr[i-1]+1; else auxArr[i] = auxArr[i-1]; }// variable to store answer int count = 0; // traverse the string reversely to // calculate number of odd substrings // before i-th index for ( int i=n-1; i> =0; i--) if (s[i] == '1' ) count += auxArr[i]; return count; }// Driver code int main() { string s = "1101" ; cout < < countSubstr(s); return 0; }

Java

// Java program to count substrings // with odd decimal value import java.io.*; import java.util.*; class GFG {// function to count number of substrings // with odd decimal representation static int countSubstr(String s) { int n = s.length(); // auxiliary array to store count // of 1's before ith index int [] auxArr= new int [n]; if (s.charAt( 0 ) == '1' ) auxArr[ 0 ] = 1 ; // store count of 1's before // i-th index for ( int i= 1 ; i< n; i++) { if (s.charAt(i) == '1' ) auxArr[i] = auxArr[i- 1 ]+ 1 ; else auxArr[i] = auxArr[i- 1 ]; }// variable to store answer int count = 0 ; // traverse the string reversely to // calculate number of odd substrings // before i-th index for ( int i=n- 1 ; i> = 0 ; i--) if (s.charAt(i) == '1' ) count += auxArr[i]; return count; }public static void main (String[] args) { String s = "1101" ; System.out.println(countSubstr(s)); } }// This code is contributed by Gitanjali.

Python3

# python program to count substrings # with odd decimal value import math # function to count number of substrings # with odd decimal representation def countSubstr( s):n = len (s)# auxiliary array to store count # of 1's before ith index auxArr = [ 0 for i in range (n)]if (s[ 0 ] = = '1' ): auxArr[ 0 ] = 1# store count of 1's before # i-th index for i in range ( 0 , n):if (s[i] = = '1' ): auxArr[i] = auxArr[i - 1 ] + 1 else : auxArr[i] = auxArr[i - 1 ]# variable to store answer count = 0# traverse the string reversely to # calculate number of odd substrings # before i-th index for i in range (n - 1 , - 1 , - 1 ): if (s[i] = = '1' ): count + = auxArr[i] return count # Driver method s = "1101" print (countSubstr(s))# This code is contributed by Gitanjali.

// C# program to count substrings // with odd decimal value using System; class GFG {// Function to count number of substrings // with odd decimal representation static int countSubstr( string s) { int n = s.Length; // auxiliary array to store count // of 1's before ith index int [] auxArr = new int [n]; if (s[0] == '1' ) auxArr[0] = 1; // store count of 1's before // i-th index for ( int i = 1; i < n; i++) { if (s[i] == '1' ) auxArr[i] = auxArr[i - 1] + 1; else auxArr[i] = auxArr[i - 1]; }// variable to store answer int count = 0; // Traverse the string reversely to // calculate number of odd substrings // before i-th index for ( int i = n - 1; i > = 0; i--) if (s[i] == '1' ) count += auxArr[i]; return count; }// Driver Code public static void Main () { string s = "1101" ; Console.WriteLine(countSubstr(s)); } }// This code is contributed by vt_m.

的PHP

< ?php // PHP program to count // substrings with odd // decimal value// function to count number // of substrings with odd // decimal representation function countSubstr( $s ) { $n = strlen ( $s ); // auxiliary array to // store count of 1's // before ith index $auxArr = array (); if ( $s [0] == '1' ) $auxArr [0] = 1; // store count of 1's // before i-th index for ( $i = 1; $i < $n ; $i ++) { if ( $s [ $i ] == '1' ) $auxArr [ $i ] = $auxArr [ $i - 1] + 1; else $auxArr [ $i ] = $auxArr [ $i - 1]; }// variable to // store answer $count = 0; // traverse the string // reversely to calculate // number of odd substrings // before i-th index for ( $i = $n - 1; $i > = 0; $i --) if ( $s [ $i ] == '1' ) $count += $auxArr [ $i ]; return $count ; }// Driver code $s = "1101" ; echo countSubstr( $s ); // This code is contributed by aj_36 ?>

输出：