计数为1的最长子串大于0-yiteyi-C++库

给定一个二进制字符串，找出包含1大于0的最长子字符串。 例如：

null

Input : 1010Output : 3Substring 101 has 1 occurring more number of times than 0.Input : 101100Output : 5Substring 10110 has 1 occurring more number of times than 0.

建议：请先在IDE上尝试您的方法，然后再查看解决方案。

A. 易于理解的 解决方案是逐一考虑所有子串，并检查该子串是否具有1以上0的计数。如果计数大于将其长度与迄今为止找到的最大长度子字符串进行比较。该解的时间复杂度为O（n^2）。一 有效率的 解决方案是使用哈希。其思想是找到迄今为止遍历的字符串的总和。如果当前字符为“1”，则在结果中加1，否则减去1。现在问题归结为找到和大于零的最大子阵列。为了找到和大于零的最大子阵列，我们检查和的值。如果和大于零，那么和大于零的最大子阵列是arr[0..i]。如果和小于零，则找到子数组arr[j+1..i]的大小，其中j是子数组arr[0..j]的和为和-1且j 以下是上述方法的实施情况：

C++

                         // CPP program to find largest substring                       
                         // having count of 1s more than count                       
                         // count of 0s.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to find longest substring                       
                         // having count of 1s more than count                       
                         // of 0s.                       
                         int                                     findLongestSub(string bin)                       
                         {                       
                                                 int                                     n = bin.length(), i;                       
           
                                                 // To store sum.                       
                                                 int                                     sum = 0;                       
           
                                                 // To store first occurrence of each                       
                                                 // sum value.                       
                                                 unordered_map<                                     int                                     ,                                     int                                     > prevSum;                       
           
                                                 // To store maximum length.                       
                                                 int                                     maxlen = 0;                       
           
                                                 // To store current substring length.                       
                                                 int                                     currlen;                       
           
                                                 for                                     (i = 0; i < n; i++) {                       
           
                                                 // Add 1 if current character is 1                       
                                                 // else subtract 1.                       
                                                 if                                     (bin[i] ==                                     '1'                                     )                       
                                                 sum++;                       
                                                 else                       
                                                 sum--;                       
           
                                                 // If sum is positive, then maximum                       
                                                 // length substring is bin[0..i]                       
                                                 if                                     (sum > 0) {                       
                                                 maxlen = i + 1;                       
                                                 }                       
           
                                                 // If sum is negative, then maximum                       
                                                 // length substring is bin[j+1..i], where                       
                                                 // sum of substring bin[0..j] is sum-1.                       
                                                 else                                     if                                     (sum <= 0) {                       
                                                 if                                     (prevSum.find(sum - 1) != prevSum.end()) {                       
                                                 currlen = i - prevSum[sum - 1];                       
                                                 maxlen = max(maxlen, currlen);                       
                                                 }                       
                                                 }                       
           
                                                 // Make entry for this sum value in hash                       
                                                 // table if this value is not present.                       
                                                 if                                     (prevSum.find(sum) == prevSum.end())                       
                                                 prevSum[sum] = i;                       
                                                 }                       
           
                                                 return                                     maxlen;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string bin =                                     "1010"                                     ;                       
                                                 cout << findLongestSub(bin);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find largest substring                       
                         // having count of 1s more than count                       
                         // count of 0s.                       
                         import                                     java.util.HashMap;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // Function to find longest substring                       
                                                 // having count of 1s more than count                       
                                                 // of 0s.                       
                                                 static                                     int                                     findLongestSub(String bin)                       
                                                 {                       
                                                 int                                     n = bin.length(), i;                       
           
                                                 // To store sum.                       
                                                 int                                     sum =                                     0                                     ;                       
           
                                                 // To store first occurrence of each                       
                                                 // sum value.                       
                                                 HashMap<Integer,                       
                                                 Integer> prevSum =                                     new                                     HashMap<>();                       
           
                                                 // To store maximum length.                       
                                                 int                                     maxlen =                                     0                                     ;                       
           
                                                 // To store current substring length.                       
                                                 int                                     currlen;                       
                                                 for                                     (i =                                     0                                     ; i < n; i++)                       
                                                 {                       
           
                                                 // Add 1 if current character is 1                       
                                                 // else subtract 1.                       
                                                 if                                     (bin.charAt(i) ==                                     '1'                                     )                       
                                                 sum++;                       
                                                 else                       
                                                 sum--;                       
           
                                                 // If sum is positive, then maximum                       
                                                 // length substring is bin[0..i]                       
                                                 if                                     (sum >                                     0                                     )                       
                                                 {                       
                                                 maxlen = i +                                     1                                     ;                       
                                                 }                       
           
                                                 // If sum is negative, then maximum                       
                                                 // length substring is bin[j+1..i], where                       
                                                 // sum of substring bin[0..j] is sum-1.                       
                                                 else                                     if                                     (sum <=                                     0                                     )                       
                                   
                                                 {                       
                                                 if                                     (prevSum.containsKey(sum -                                     1                                     ))                       
                                                 {                       
                                                 currlen = i - (prevSum.get(sum -                                     1                                     ) ==                                     null                                     ?                                     1                                     :                       
                                                 prevSum.get(sum -                                     1                                     ));                       
                                                 maxlen = Math.max(maxlen, currlen);                       
                                                 }                       
                                                 }                       
           
                                                 // Make entry for this sum value in hash                       
                                                 // table if this value is not present.                       
                                                 if                                     (!prevSum.containsKey(sum))                       
                                                 prevSum.put(sum, i);                       
                                                 }                       
                                                 return                                     maxlen;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 String bin =                                     "1010"                                     ;                       
                                                 System.out.println(findLongestSub(bin));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by                       
                         // sanjeev2552                       

Python3

                         # Python 3 program to find largest substring                       
                         # having count of 1s more than count                       
                         # count of 0s.                       
           
                         # Function to find longest substring                       
                         # having count of 1s more than count                       
                         # of 0s.                       
                         def                                     findLongestSub(bin1):                       
                                                 n                                     =                                     len                                     (bin1)                       
           
                                                 # To store sum.                       
                                                 sum                                     =                                     0                       
           
                                                 # To store first occurrence of each                       
                                                 # sum value.                       
                                                 prevSum                                     =                                     {i:                                     0                                     for                                     i                                     in                                     range                                     (n)}                       
           
                                                 # To store maximum length.                       
                                                 maxlen                                     =                                     0                       
           
                                                 # To store current substring length.                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # Add 1 if current character is 1                       
                                                 # else subtract 1.                       
                                                 if                                     (bin1[i]                                     =                                     =                                     '1'                                     ):                       
                                                 sum                                     +                                     =                                     1                       
                                                 else                                     :                       
                                                 sum                                     -                                     =                                     1                       
           
                                                 # If sum is positive, then maximum                       
                                                 # length substring is bin1[0..i]                       
                                                 if                                     (                                     sum                                     >                                     0                                     ):                       
                                                 maxlen                                     =                                     i                                     +                                     1                       
           
                                                 # If sum is negative, then maximum                       
                                                 # length substring is bin1[j+1..i], where                       
                                                 # sum of substring bin1[0..j] is sum-1.                       
                                                 elif                                     (                                     sum                                     <                                     =                                     0                                     ):                       
                                                 if                                     ((                                     sum                                     -                                     1                                     )                                     in                                     prevSum):                       
                                                 currlen                                     =                                     i                                     -                                     prevSum[                                     sum                                     -                                     1                                     ]                       
                                                 maxlen                                     =                                     max                                     (maxlen, currlen)                       
                                   
                                                 # Make entry for this sum value in hash                       
                                                 # table if this value is not present.                       
                                                 if                                     ((                                     sum                                     )                                     not                                     in                                     prevSum):                       
                                                 prevSum[                                     sum                                     ]                                     =                                     i                       
           
                                                 return                                     maxlen                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 bin1                                     =                                     "1010"                       
                                                 print                                     (findLongestSub(bin1))                       
           
                         # This code is contributed by                       
                         # Surendra_Gangwar                       

C#

                         // C# program to find largest substring                       
                         // having count of 1s more than count                       
                         // count of 0s.                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
                         class                                     GFG                       
                         {                       
           
                                                 // Function to find longest substring                       
                                                 // having count of 1s more than count                       
                                                 // of 0s.                       
                                                 static                                     int                                     findLongestSub(String bin)                       
                                                 {                       
                                                 int                                     n = bin.Length, i;                       
           
                                                 // To store sum.                       
                                                 int                                     sum = 0;                       
           
                                                 // To store first occurrence of each                       
                                                 // sum value.                       
                                                 Dictionary<                                     int                                     ,                       
                                                 int                                     > prevSum =                                     new                                     Dictionary<                                     int                                     ,                       
                                                 int                                     >();                       
           
                                                 // To store maximum length.                       
                                                 int                                     maxlen = 0;                       
           
                                                 // To store current substring length.                       
                                                 int                                     currlen;                       
                                                 for                                     (i = 0; i < n; i++)                       
                                                 {                       
           
                                                 // Add 1 if current character is 1                       
                                                 // else subtract 1.                       
                                                 if                                     (bin[i] ==                                     '1'                                     )                       
                                                 sum++;                       
                                                 else                       
                                                 sum--;                       
           
                                                 // If sum is positive, then maximum                       
                                                 // length substring is bin[0..i]                       
                                                 if                                     (sum > 0)                       
                                                 {                       
                                                 maxlen = i + 1;                       
                                                 }                       
           
                                                 // If sum is negative, then maximum                       
                                                 // length substring is bin[j+1..i], where                       
                                                 // sum of substring bin[0..j] is sum-1.                       
                                                 else                                     if                                     (sum <= 0)                       
                                   
                                                 {                       
                                                 if                                     (prevSum.ContainsKey(sum - 1))                       
                                                 {                       
                                                 currlen = i - (prevSum[sum - 1] == 0 ? 1 :                       
                                                 prevSum[sum - 1]);                       
                                                 maxlen = Math.Max(maxlen, currlen);                       
                                                 }                       
                                                 }                       
           
                                                 // Make entry for this sum value in hash                       
                                                 // table if this value is not present.                       
                                                 if                                     (!prevSum.ContainsKey(sum))                       
                                                 prevSum.Add(sum, i);                       
                                                 }                       
                                                 return                                     maxlen;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 String bin =                                     "1010"                                     ;                       
                                                 Console.WriteLine(findLongestSub(bin));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Javascript

                         <script>                       
                         // Javascript program to find largest substring                       
                         // having count of 1s more than count                       
                         // count of 0s.                       
           
                         // Function to find longest substring                       
                                                 // having count of 1s more than count                       
                                                 // of 0s.                       
                         function                                     findLongestSub(bin)                       
                         {                       
                                                 let n = bin.length, i;                       
                                   
                                                 // To store sum.                       
                                                 let sum = 0;                       
                                   
                                                 // To store first occurrence of each                       
                                                 // sum value.                       
                                                 let prevSum =                                     new                                     Map();                       
                                   
                                                 // To store maximum length.                       
                                                 let maxlen = 0;                       
                                   
                                                 // To store current substring length.                       
                                                 let currlen;                       
                                                 for                                     (i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Add 1 if current character is 1                       
                                                 // else subtract 1.                       
                                                 if                                     (bin[i] ==                                     '1'                                     )                       
                                                 sum++;                       
                                                 else                       
                                                 sum--;                       
                                   
                                                 // If sum is positive, then maximum                       
                                                 // length substring is bin[0..i]                       
                                                 if                                     (sum > 0)                       
                                                 {                       
                                                 maxlen = i + 1;                       
                                                 }                       
                                   
                                                 // If sum is negative, then maximum                       
                                                 // length substring is bin[j+1..i], where                       
                                                 // sum of substring bin[0..j] is sum-1.                       
                                                 else                                     if                                     (sum <= 0)                       
                                   
                                                 {                       
                                                 if                                     (prevSum.has(sum - 1))                       
                                                 {                       
                                                 currlen = i - (prevSum.get(sum - 1) ==                                     null                                     ? 1 :                       
                                                 prevSum.get(sum - 1));                       
                                                 maxlen = Math.max(maxlen, currlen);                       
                                                 }                       
                                                 }                       
                                   
                                                 // Make entry for this sum value in hash                       
                                                 // table if this value is not present.                       
                                                 if                                     (!prevSum.has(sum))                       
                                                 prevSum.set(sum, i);                       
                                                 }                       
                                                 return                                     maxlen;                       
                         }                       
           
                         // Driver code                       
                         let bin =                                     "1010"                                     ;                       
                         document.write(findLongestSub(bin));                       
           
                         // This code is contributed by rag2127                       
                         </script>                       

输出：

时间复杂性： O（n） 辅助空间： O（n）

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

THE END

技术文章