算法题（计算字符串的子字符串的数字是否能被11整除） _字符串

本文概述

C ++
Java
Python3
C#

给定一个大数n(数字位数最多为10^6)和以下形式的各种查询：

Query(l, r) : 找出索引l和r(包括)之间的子字符串是否能被11整除。

例子：

Input: n = 122164154695 Queries: l = 0 r = 3, l = 1 r = 2, l = 5 r = 9, l = 0 r = 11 Output: True False False TrueExplanation: 在第一个查询中，1221能被11整除在第二个查询中，22可以被11整除，以此类推。

我们知道, 如果将奇数索引的数字之和与偶数索引的数字之和之差除以11, 即总和(奇数位的数字)–总和(奇数位的数字)应被11整除。
因此，我们的想法是预处理一个辅助数组，该数组将存储奇数和偶数位的数字和。
要计算一个查询，我们可以使用辅助数组在O(1)中解决它。
C ++

// C++ program to check divisibility by 11 in // substrings of a number string #include < iostream> using namespace std; const int MAX = 1000005; // To store sums of even and odd digits struct OddEvenSums { // Sum of even placed digits int e_sum; // Sum of odd placed digits int o_sum; }; // Auxiliary array OddEvenSums sum[MAX]; // Utility function to evaluate a character's // integer value int toInt( char x) { return int (x) - 48; } // This function receives the string representation // of the number and precomputes the sum array void preCompute(string x) { // Initialize everb sum[0].e_sum = sum[0].o_sum = 0; // Add the respective digits depending on whether // they're even indexed or odd indexed for ( int i=0; i< x.length(); i++) { if (i%2==0) { sum[i+1].e_sum = sum[i].e_sum+toInt(x[i]); sum[i+1].o_sum = sum[i].o_sum; } else { sum[i+1].o_sum = sum[i].o_sum+toInt(x[i]); sum[i+1].e_sum = sum[i].e_sum; } } } // This function receives l and r representing // the indices and prints the required output bool query( int l, int r) { int diff = (sum[r+1].e_sum - sum[r+1].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff%11==0); } //driver function to check the program int main() { string s = "122164154695" ; preCompute(s); cout < < query(0, 3) < < endl; cout < < query(1, 2) < < endl; cout < < query(5, 9) < < endl; cout < < query(0, 11) < < endl; return 0; }

Java

// Java program to check divisibility by 11 in // subStrings of a number String class GFG {static int MAX = 1000005 ; // To store sums of even and odd digits static class OddEvenSums { // Sum of even placed digits int e_sum; // Sum of odd placed digits int o_sum; }; // Auxiliary array static OddEvenSums []sum = new OddEvenSums[MAX]; // Utility function to evaluate a character's // integer value static int toInt( char x) { return x - 48 ; }// This function receives the String representation // of the number and precomputes the sum array static void preCompute(String x) { // Initialize everb sum[ 0 ].e_sum = sum[ 0 ].o_sum = 0 ; // Add the respective digits depending on whether // they're even indexed or odd indexed for ( int i = 0 ; i < x.length(); i++) { if (i % 2 == 0 ) { sum[i + 1 ].e_sum = sum[i].e_sum + toInt(x.charAt(i)); sum[i + 1 ].o_sum = sum[i].o_sum; } else { sum[i + 1 ].o_sum = sum[i].o_sum + toInt(x.charAt(i)); sum[i + 1 ].e_sum = sum[i].e_sum; } } }// This function receives l and r representing // the indices and prints the required output static boolean query( int l, int r) { int diff = (sum[r + 1 ].e_sum - sum[r + 1 ].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff % 11 == 0 ); }//driver function to check the program public static void main(String[] args) { for ( int i = 0 ; i < MAX; i++) { sum[i] = new OddEvenSums(); } String s = "122164154695" ; preCompute(s); System.out.println(query( 0 , 3 ) ? 1 : 0 ); System.out.println(query( 1 , 2 ) ? 1 : 0 ); System.out.println(query( 5 , 9 ) ? 1 : 0 ); System.out.println(query( 0 , 11 ) ? 1 : 0 ); } } // This code is contributed by Rajput-Ji

Python3

# Python3 program to check divisibility by # 11 in subStrings of a number String MAX = 1000005 # To store sums of even and odd digits class OddEvenSums:def __init__( self , e_sum, o_sum):# Sum of even placed digits self .e_sum = e_sum# Sum of odd placed digits self .o_sum = o_sum sum = [OddEvenSums( 0 , 0 ) for i in range ( MAX )] # This function receives the String # representation of the number and # precomputes the sum array def preCompute(x): # Initialize everb sum [ 0 ].e_sum = sum [ 0 ].o_sum = 0# Add the respective digits # depending on whether # they're even indexed or # odd indexed for i in range ( len (x)): if (i % 2 = = 0 ): sum [i + 1 ].e_sum = ( sum [i].e_sum + int (x[i])) sum [i + 1 ].o_sum = sum [i].o_sumelse : sum [i + 1 ].o_sum = ( sum [i].o_sum + int (x[i])) sum [i + 1 ].e_sum = sum [i].e_sum# This function receives l and r representing # the indices and prints the required output def query(l, r): diff = (( sum [r + 1 ].e_sum - sum [r + 1 ].o_sum) - ( sum [l].e_sum - sum [l].o_sum))if (diff % 11 = = 0 ): return True else : return False # Driver code if __name__ = = "__main__" :s = "122164154695"preCompute(s)print ( 1 if query( 0 , 3 ) else 0 ) print ( 1 if query( 1 , 2 ) else 0 ) print ( 1 if query( 5 , 9 ) else 0 ) print ( 1 if query( 0 , 11 ) else 0 ) # This code is contributed by rutvik_56

// C# program to check // divisibility by 11 in // subStrings of a number String using System; class GFG{static int MAX = 1000005; // To store sums of even // and odd digits public class OddEvenSums { // Sum of even placed digits public int e_sum; // Sum of odd placed digits public int o_sum; }; // Auxiliary array static OddEvenSums []sum = new OddEvenSums[MAX]; // Utility function to // evaluate a character's // integer value static int toInt( char x) { return x - 48; }// This function receives the // String representation of the // number and precomputes the sum array static void preCompute(String x) { // Initialize everb sum[0].e_sum = sum[0].o_sum = 0; // Add the respective digits // depending on whether they're // even indexed or odd indexed for ( int i = 0; i < x.Length; i++) { if (i % 2 == 0) { sum[i + 1].e_sum = sum[i].e_sum + toInt(x[i]); sum[i + 1].o_sum = sum[i].o_sum; } else { sum[i + 1].o_sum = sum[i].o_sum + toInt(x[i]); sum[i + 1].e_sum = sum[i].e_sum; } } }// This function receives l and r // representing the indices and // prints the required output static bool query( int l, int r) { int diff = (sum[r + 1].e_sum - sum[r + 1].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff % 11 == 0); }// Driver function to check the program public static void Main(String[] args) { for ( int i = 0; i < MAX; i++) { sum[i] = new OddEvenSums(); }String s = "122164154695" ; preCompute(s); Console.WriteLine(query(0, 3) ? 1 : 0); Console.WriteLine(query(1, 2) ? 1 : 0); Console.WriteLine(query(5, 9) ? 1 : 0); Console.WriteLine(query(0, 11) ? 1 : 0); } } // This code is contributed by gauravrajput1

【算法题（计算字符串的子字符串的数字是否能被11整除）】输出如下：