# 算法：二进制字符串中具有奇数十进制值的子字符串数

2021年3月24日14:59:58 发表评论 671 次浏览

## 本文概述

``````Input : 101
Output : 3
Explanation : Substrigs with odd decimal
representation are:
{1, 1, 101}

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

## 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];
}

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 ];
}

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 ]

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];
}

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
\$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
?>``````

``6``

： 上)

： 上)