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

2021年5月15日18:23:10 发表评论 519 次浏览

## 本文概述

1. 这个想法是要保持两分球 大号和[R.
2. 将子字符串的右指针" 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 = i

else :
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 ] + 1

return no_of_substr

# Driver Code

s = "11100"
k = 3
print (countSubstr(s, k))

# This code is contributed by mohit kumar 29``````

## C#

``````//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``````

``8`` 