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

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

本文概述

给定一个整数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。计算找到的每个此类子字符串的数量。

高效方法：使用两指针技术

  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
木子山

发表评论

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