给定一个只包含0和1的二进制字符串。编写一个程序来查找该字符串中十进制表示为奇数的子字符串的数量。
null
例如：
Input : 101Output : 3Explanation : Substrings with odd decimal representation are: {1, 1, 101}Input : 1101Output : 6Explanation : Substrings with odd decimal representation are: {1, 1, 1, 11, 101, 1011}
暴力手段 ：解决上述问题的最简单方法是生成给定字符串的所有可能子字符串，并将其转换为十进制，然后检查十进制表示是否为奇数。你可以参考 这 文章介绍了二进制到十进制的转换。 时间复杂度：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; // 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 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#
// 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 ?> |
Javascript
<script> // Javascript program to count substrings // with odd decimal value // Function to count number of substrings // with odd decimal representation function countSubstr(s) { let n = s.length; // auxiliary array to store count // of 1's before ith index let auxArr = new Array(n); if (s[0] == '1 ') auxArr[0] = 1; // Store count of 1' s before // i-th index for (let 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 let count = 0; // Traverse the string reversely to // calculate number of odd substrings // before i-th index for (let i = n - 1; i >= 0; i--) if (s[i] == '1' ) count += auxArr[i]; return count; } // Driver code let s = "1101" ; document.write(countSubstr(s)); // This code is contributed by rameshtravel07 </script> |
输出：
6
时间复杂性 ：O（n） 辅助空间 ：O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
