给定一个二进制字符串，计算以1开头和结尾的子字符串数。-yiteyi-C++库

给定一个二进制字符串，计算以1开头和结尾的子字符串数。例如，如果输入字符串为“00100101”，则有三个子字符串“1001”、“100101”和“101”。资料来源：亚马逊面试体验|第162集 难度等级： 菜鸟

null

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是运行两个循环。外部循环选择每1作为起点，内部循环搜索结束1，并在找到1时增加计数。

C++

                         // A simple C++ program to count number of                       
                         // substrings starting and ending with 1                       
                         #include<iostream>                       
                                   
                         using                                     namespace                                     std;                       
           
                         int                                     countSubStr(                                     char                                     str[])                       
                         {                       
                         int                                     res = 0;                                     // Initialize result                       
           
                         // Pick a starting point                       
                         for                                     (                                     int                                     i=0; str[i] !=                                     ' '                                     ; i++)                       
                         {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 {                       
                                                 // Search for all possible ending point                       
                                                 for                                     (                                     int                                     j=i+1; str[j] !=                                     ' '                                     ; j++)                       
                                                 if                                     (str[j] ==                                     '1'                                     )                       
                                                 res++;                       
                                                 }                       
                         }                       
                         return                                     res;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                         char                                     str[] =                                     "00100101"                                     ;                       
                         cout << countSubStr(str);                       
                         return                                     0;                       
                         }                       

JAVA

                         // A simple C++ program to count number of                       
                         //substrings starting and ending with 1                       
           
                         class                                     CountSubString                       
                         {                       
                                                 int                                     countSubStr(                                     char                                     str[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     res =                                     0                                     ;                                     // Initialize result                       
           
                                                 // Pick a starting point                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i<n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 {                       
                                                 // Search for all possible ending point                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j< n; j++)                       
                                                 {                       
                                                 if                                     (str[j] ==                                     '1'                                     )                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
           
                                                 // Driver program to test the above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 CountSubString count =                                     new                                     CountSubString();                       
                                                 String string =                                     "00100101"                                     ;                       
                                                 char                                     str[] = string.toCharArray();                       
                                                 int                                     n = str.length;                       
                                                 System.out.println(count.countSubStr(str,n));                       
                                                 }                       
                         }                       

Python3

                         # A simple Python 3 program to count number of                       
                         # substrings starting and ending with 1                       
           
                         def                                     countSubStr(st, n) :                       
                                   
                                                 # Initialize result                       
                                                 res                                     =                                     0                       
                                   
                                                 # Pick a starting point                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n) :                       
                                                 if                                     (st[i]                                     =                                     =                                     '1'                                     ) :                       
           
                                                 # Search for all possible ending point                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n) :                       
                                                 if                                     (st[j]                                     =                                     =                                     '1'                                     ) :                       
                                                 res                                     =                                     res                                     +                                     1                       
                                   
                                                 return                                     res                       
                                   
                                   
                         # Driver program to test above function                       
                         st                                     =                                     "00100101"                                     ;                       
                         list                                     (st)                       
                         n                                     =                                     len                                     (st)                       
                         print                                     (countSubStr(st, n), end                                     =                                     "")                       
           
           
                         # This code is contributed                       
                         # by Nikita Tiwari.                       

C#

                         // A simple C# program to count number of                       
                         // substrings starting and ending with 1                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         public                                     virtual                                     int                                     countSubStr(                                     char                                     [] str,                       
                                                 int                                     n)                       
                         {                       
                                                 int                                     res = 0;                                     // Initialize result                       
           
                                                 // Pick a starting point                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 {                       
                                                 // Search for all possible                       
                                                 // ending point                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 {                       
                                                 if                                     (str[j] ==                                     '1'                                     )                       
                                                 {                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                                 GFG count =                                     new                                     GFG();                       
                                                 string                                     s =                                     "00100101"                                     ;                       
                                                 char                                     [] str = s.ToCharArray();                       
                                                 int                                     n = str.Length;                       
                                                 Console.WriteLine(count.countSubStr(str,n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Shrikant13                       

PHP

                         <?php                       
                         // A simple PHP program to count number of                       
                         // substrings starting and ending with 1                       
           
                         function                                     countSubStr(                                     $str                                     )                       
                         {                       
                                                 $res                                     = 0;                                     // Initialize result                       
           
                                                 // Pick a starting point                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $str                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $str                                     [                                     $i                                     ] ==                                     '1'                                     )                       
                                                 {                       
                                                 // Search for all possible                       
                                                 // ending point                       
                                                 for                                     (                                     $j                                     =                                     $i                                     + 1;                       
                                                 $j                                     <                                     strlen                                     (                                     $str                                     );                                     $j                                     ++)                       
                                                 if                                     (                                     $str                                     [                                     $j                                     ] ==                                     '1'                                     )                       
                                                 $res                                     ++;                       
                                                 }                       
                                                 }                       
                                                 return                                     $res                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $str                                     =                                     "00100101"                                     ;                       
                         echo                                     countSubStr(                                     $str                                     );                       
           
                         // This code is contributed by ita_c                       
                         ?>                       

Javascript

                         <script>                       
           
                         // A simple javascript program to count number of                       
                         // substrings starting and ending with 1                       
                                   
                                                 function                                     countSubStr(str,n)                       
                                                 {                       
                                                 let res = 0;                                     // Initialize result                       
                                                 // Pick a starting point                       
                                                 for                                     (let i = 0; i<n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 {                       
                                                 // Search for all possible ending point                       
                                                 for                                     (let j = i + 1; j< n; j++)                       
                                                 {                       
                                                 if                                     (str[j] ==                                     '1'                                     )                       
                                                 res++;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 // Driver program to test the above function                       
                                                 let string =                                     "00100101"                                     ;                       
                                                 let n=string.length;                       
                                                 document.write(countSubStr(string,n));                       
                                   
                                   
                                                 // This code is contributed by rag2127                       
                                   
                         </script>                       

输出：

上述解的时间复杂度为O（n） ^2. ).我们可以找到伯爵 在O（n）中使用单次遍历 输入字符串的类型。以下是步骤。 a）数一数1的数量，让1的数量为m。 b）返回m（m-1）/2 这个想法是计算可能的1对的总数。

C++

                         // A O(n) C++ program to count number of                       
                         // substrings starting and ending with 1                       
                         #include<iostream>                       
           
                         using                                     namespace                                     std;                       
           
                         int                                     countSubStr(                                     char                                     str[])                       
                         {                       
                                                 int                                     m = 0;                                     // Count of 1's in input string                       
           
                                                 // Traverse input string and count of 1's in it                       
                                                 for                                     (                                     int                                     i=0; str[i] !=                                     ' '                                     ; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 m++;                       
                                                 }                       
           
                                                 // Return count of possible pairs among m 1's                       
                                                 return                                     m*(m-1)/2;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 char                                     str[] =                                     "00100101"                                     ;                       
                                                 cout << countSubStr(str);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A O(n) C++ program to count number of substrings                       
                         //starting and ending with 1                       
           
                         class                                     CountSubString                       
                         {                       
                                                 int                                     countSubStr(                                     char                                     str[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     m =                                     0                                     ;                                     // Count of 1's in input string                       
           
                                                 // Traverse input string and count of 1's in it                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 m++;                       
                                                 }                       
           
                                                 // Return count of possible pairs among m 1's                       
                                                 return                                     m * (m -                                     1                                     ) /                                     2                                     ;                       
                                                 }                       
           
                                                 // Driver program to test the above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 CountSubString count =                                     new                                     CountSubString();                       
                                                 String string =                                     "00100101"                                     ;                       
                                                 char                                     str[] = string.toCharArray();                       
                                                 int                                     n = str.length;                       
                                                 System.out.println(count.countSubStr(str, n));                       
                                                 }                       
                         }                       

Python3

                         # A Python3 program to count number of                       
                         # substrings starting and ending with 1                       
           
                         def                                     countSubStr(st, n) :                       
           
                                                 # Count of 1's in input string                       
                                                 m                                     =                                     0                       
                                   
                                                 # Traverse input string and                       
                                                 # count of 1's in it                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n) :                       
                                                 if                                     (st[i]                                     =                                     =                                     '1'                                     ) :                       
                                                 m                                     =                                     m                                     +                                     1                       
                                   
                                                 # Return count of possible                       
                                                 # pairs among m 1's                       
                                                 return                                     m                                     *                                     (m                                     -                                     1                                     )                                     /                                     /                                     2                       
                                   
                                   
                         # Driver program to test above function                       
                         st                                     =                                     "00100101"                                     ;                       
                         list                                     (st)                       
                         n                                     =                                     len                                     (st)                       
                         print                                     (countSubStr(st, n), end                                     =                                     "")                       
           
           
                         # This code is contributed                       
                         # by Nikita Tiwari.                       

C#

                         // A O(n) C# program to count                       
                         // number of substrings starting                       
                         // and ending with 1                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         int                                     countSubStr(                                     char                                     []str,                                     int                                     n)                       
                         {                       
                                                 int                                     m = 0;                                     // Count of 1's in                       
                                                 // input string                       
           
                                                 // Traverse input string and                       
                                                 // count of 1's in it                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 m++;                       
                                                 }                       
           
                                                 // Return count of possible                       
                                                 // pairs among m 1's                       
                                                 return                                     m * (m - 1) / 2;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main(String[] args)                       
                         {                       
                                                 GFG count =                                     new                                     GFG();                       
                                                 String strings =                                     "00100101"                                     ;                       
                                                 char                                     []str = strings.ToCharArray();                       
                                                 int                                     n = str.Length;                       
                                                 Console.Write(count.countSubStr(str, n));                       
                         }                       
                         }                       
           
                         // This code is contributed by princiraj                       

PHP

                         <?php                       
                         // A simple PHP program to count number of                       
                         // substrings starting and ending with 1                       
           
                         function                                     countSubStr(                                     $str                                     )                       
                         {                       
                                                 $m                                     = 0;                                     // Initialize result                       
           
                                                 // Pick a starting point                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $str                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $str                                     [                                     $i                                     ] ==                                     '1'                                     )                       
                                                 {                       
                                                 $m                                     ++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Return count of possible                       
                                                 // pairs among m 1's                       
                                                 return                                     $m                                     * (                                     $m                                     - 1) / 2;                       
                         }                       
           
                         // Driver Code                       
                         $str                                     =                                     "00100101"                                     ;                       
                         echo                                     countSubStr(                                     $str                                     );                       
           
                         // This code is contributed                       
                         // by Akanksha Rai                       
                         ?>                       

Javascript

                         <script>                       
                         // A O(n) javascript program to count number of substrings                       
                         //starting and ending with 1                       
           
                                                 function                                     countSubStr(str,n)                       
                                                 {                       
                                                 let m = 0;                                     // Count of 1's in input string                       
                                   
                                                 // Traverse input string and count of 1's in it                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 if                                     (str[i] ==                                     '1'                                     )                       
                                                 m++;                       
                                                 }                       
                                   
                                                 // Return count of possible pairs among m 1's                       
                                                 return                                     m * Math.floor((m - 1) / 2);                       
                                                 }                       
                                   
                                                 // Driver program to test the above function                       
                                                 let str =                                     "00100101"                                     ;                       
                                                 let n = str.length;                       
                                                 document.write(countSubStr(str, n));                       
                                   
                                                 //  This code is contributed by avanitrachhadiya2155                       
                         </script>                       

输出：

本文由 希瓦姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章