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

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

本文概述

给定一个仅包含0和1的二进制字符串。编写程序以查找此字符串的子字符串数, 其十进制表示形式为奇数。

例子 ：

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}

推荐：请尝试以下方法{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;
      
     // 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
?>

输出：

6

时间复杂度

： 上)

辅助空间

： 上)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: