十进制等效项大于或等于K的子字符串的计数

本文概述

C ++
Java
Python3
C#

给定一个整数K和一个二进制字符串小号长度N, 任务是找出子串其十进制等效值大于或等于K.
例子：

输入：K = 3, S =" 11100"
输出：8
说明：有8个这样的子字符串, 其十进制等效值大于或等于3, 如下所述：
子字符串–十进制等效值" 100" – 4, " 1100" – 12, " 11100" – 28, " 110" – 6, " 1110" – 14, " 11" – 3, " 111" – 7, " 11" – 3
输入：K = 5, S =" 10110110"
输出： 19
说明：有19个这样的子字符串, 其十进制等效值大于或等于5

简单的方法：找出所有子串对于每个子字符串, 将其从二进制转换为十进制, 然后检查它是否大于或等于K。计算找到的每个此类子字符串的数量。
高效方法：使用两指针技术

这个想法是要保持两分球大号和[R.
将子字符串的右指针" R"的位置固定为长度– 1并循环循环直到R的值为正：
- 考虑长度1的子串, 将L的值初始化为R
- 将L的值减1, 直到长度的子字符串的十进制等效R – L + 1大于或等于K
- 将计数器增加L左边的位数。

下面是上述方法的实现：
C ++

//C++ implementation to count the //substrings whose decimal equivalent //is greater than or equal to K #include < bits/stdc++.h> using namespace std; //Function to count number of //substring whose decimal equivalent //is greater than or equal to K unsigned long long countSubstr( string& s, int k) {int n = s.length(); //Left pointer of the substring int l = n - 1; //Right pointer of the substring int r = n - 1; int arr[n]; int last_indexof1 = -1; //Loop to maintain the last //occurrence of the 1 in the string for ( int i = 0; i < n; i++) { if (s[i] == '1' ) { arr[i] = i; last_indexof1 = i; } else { arr[i] = last_indexof1; } }//Variable to count the substring unsigned long long no_of_substr = 0; //Loop to maintain the every //possible end index of the substring for (r = n - 1; r> = 0; r--) { l = r; //Loop to find the substring //whose decimal equivalent is //greater than or equal to K while (l> = 0 & & (r - l + 1) < = 64 & & stoull( s.substr(l, r - l + 1), 0, 2) < k) { l--; }//Condition to check no //of bits is out of bound if (r - l + 1 < = 64) no_of_substr += l + 1; else { no_of_substr += arr[l + 1] + 1; } } return no_of_substr; }//Driver Code int main() { string s = "11100" ; unsigned long long int k = 3; cout < < countSubstr(s, k); }

Java

//Java implementation to count the //subStrings whose decimal equivalent //is greater than or equal to K import java.util.*; class GFG{//Function to count number of //subString whose decimal equivalent //is greater than or equal to K static long countSubstr( String s, int k) {int n = s.length(); //Left pointer of the subString int l = n - 1 ; //Right pointer of the subString int r = n - 1 ; int []arr = new int [n]; int last_indexof1 = - 1 ; //Loop to maintain the last //occurrence of the 1 in the String for ( int i = 0 ; i < n; i++) { if (s.charAt(i) == '1' ) { arr[i] = i; last_indexof1 = i; } else { arr[i] = last_indexof1; } }//Variable to count the subString long no_of_substr = 0 ; //Loop to maintain the every //possible end index of the subString for (r = n - 1 ; r> = 0 ; r--) { l = r; //Loop to find the subString //whose decimal equivalent is //greater than or equal to K while (l> = 0 & & (r - l + 1 ) < = 64 & & Integer.valueOf(s.substring(l, r + 1 ), 2 ) < k) { l--; }//Condition to check no //of bits is out of bound if (r - l + 1 < = 64 ) no_of_substr += l + 1 ; else { no_of_substr += arr[l + 1 ] + 1 ; } } return no_of_substr; }//Driver Code public static void main(String[] args) { String s = "11100" ; int k = 3 ; System.out.println(countSubstr(s, k)); } }//This code is contributed by PrinciRaj1992

Python3

# Python3 implementation to count the # substrings whose decimal equivalent # is greater than or equal to K# Function to count number of # substring whose decimal equivalent # is greater than or equal to K def countSubstr(s, k):n = len (s)# Left pointer of the substring l = n - 1# Right pointer of the substring r = n - 1 arr = [ 0 ] * n last_indexof1 = - 1# Loop to maintain the last # occurrence of the 1 in the string for i in range (n): if (s[i] = = '1' ): arr[i] = i last_indexof1 = ielse : arr[i] = last_indexof1# Variable to count the substring no_of_substr = 0# Loop to maintain the every # possible end index of the substring for r in range (n - 1 , - 1 , - 1 ): l = r# Loop to find the substring # whose decimal equivalent is # greater than or equal to K while (l> = 0 and (r - l + 1 ) < = 64 and int (s[l:r + 1 ], 2 )< k): l - = 1# Condition to check no # of bits is out of bound if (r - l + 1 < = 64 ): no_of_substr + = l + 1 else : no_of_substr + = arr[l + 1 ] + 1return no_of_substr# Driver Codes = "11100" k = 3 print (countSubstr(s, k))# This code is contributed by mohit kumar 29

//C# implementation to count the //subStrings whose decimal equivalent //is greater than or equal to K using System; class GFG{//Function to count number of //subString whose decimal equivalent //is greater than or equal to K static long countSubstr( String s, int k) {int n = s.Length; //Left pointer of the subString int l = n - 1; //Right pointer of the subString int r = n - 1; int []arr = new int [n]; int last_indexof1 = -1; //Loop to maintain the last //occurrence of the 1 in the String for ( int i = 0; i < n; i++) { if (s[i] == '1' ) { arr[i] = i; last_indexof1 = i; } else { arr[i] = last_indexof1; } }//Variable to count the subString long no_of_substr = 0; //Loop to maintain the every //possible end index of the subString for (r = n - 1; r> = 0; r--) { l = r; //Loop to find the subString //whose decimal equivalent is //greater than or equal to K while (l> = 0 & & (r - l + 1) < = 64 & & ( int )(Convert.ToInt32(s.Substring(l, r + 1-l), 2)) < k) { l--; }//Condition to check no //of bits is out of bound if (r - l + 1 < = 64) no_of_substr += l + 1; else { no_of_substr += arr[l + 1] + 1; } } return no_of_substr; }//Driver Code public static void Main(String[] args) { String s = "11100" ; int k = 3; Console.WriteLine(countSubstr(s, k)); } }//This code is contributed by Rajput-Ji

【十进制等效项大于或等于K的子字符串的计数】输出如下：