给定的数字最多为100位。我们必须检查，在删除某些数字后，是否有可能获得至少一个数字的数字，该数字可以被8整除。我们被禁止重新排列数字。
null
例如：
Input : 1787075866Output : YesThere exist more one or more subsequencesdivisible by 8. Example subsequences are176, 16 and 8.Input : 6673177113Output : No No subsequence is divisible by 8.Input : 3144Output : YesThe subsequence 344 is divisible by 8.
财产 八整除 ：数字可以被8除，当且仅当其最后三位数字构成一个可以被8除的数字。因此，只测试可以通过划线从原始数字中获得且最多包含三位数字的数字就足够了，即我们检查所有一位数字、两位数字和三位数字组合。
方法1（暴力）： 我们采用暴力手段。我们使用迭代阶梯排列所有可能的一位数、两位数和三位数组合。如果我们遇到一个可以被8整除的一位数，或者一个可以被8整除的两位数组合，或者一个可以被8整除的三位数组合，那么这就是我们问题的解决方案。
C++
// C++ program to check if a subsequence of digits // is divisible by 8. #include <bits/stdc++.h> using namespace std; // Function to calculate any permutation divisible // by 8. If such permutation exists, the function // will return that permutation else it will return -1 bool isSubSeqDivisible(string str) { // Converting string to integer array for ease // of computations (Indexing in arr[] is // considered to be starting from 1) int l = str.length(); int arr[l]; for ( int i = 0; i < l; i++) arr[i] = str[i] - '0' ; // Generating all possible permutations and checking // if any such permutation is divisible by 8 for ( int i = 0; i < l; i++) { for ( int j = i; j < l; j++) { for ( int k = j; k < l; k++) { if (arr[i] % 8 == 0) return true ; else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j) return true ; else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 && i != j && j != k && i != k) return true ; } } } return false ; } // Driver function int main() { string str = "3144" ; if (isSubSeqDivisible(str)) cout << "Yes" ; else cout << "No" ; return 0; } |
JAVA
// Java program to check if a subsequence // of digits is divisible by 8. import java.io.*; class GFG { // Function to calculate any permutation // divisible by 8. If such permutation // exists, the function will return // that permutation else it will return -1 static boolean isSubSeqDivisible(String str) { int i, j, k, l = str.length(); int arr[] = new int [l]; // Converting string to integer array for ease // of computations (Indexing in arr[] is // considered to be starting from 1) for (i = 0 ; i < l; i++) arr[i] = str.charAt(i) - '0' ; // Generating all possible permutations // and checking if any such // permutation is divisible by 8 for (i = 0 ; i < l; i++) { for (j = i; j < l; j++) { for (k = j; k < l; k++) { if (arr[i] % 8 == 0 ) return true ; else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j) return true ; else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 && i != j && j != k && i != k) return true ; } } } return false ; } // Driver function public static void main(String args[]) { String str = "3144" ; if (isSubSeqDivisible(str)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Nikita Tiwari. |
Python3
# Python3 program to # check if a subsequence of digits # is divisible by 8. # Function to calculate any # permutation divisible # by 8. If such permutation # exists, the function # will return that permutation # else it will return -1 def isSubSeqDivisible(st) : l = len (st) arr = [ int (ch) for ch in st] # Generating all possible # permutations and checking # if any such permutation # is divisible by 8 for i in range ( 0 , l) : for j in range (i, l) : for k in range (j, l) : if (arr[i] % 8 = = 0 ) : return True elif ((arr[i] * 10 + arr[j]) % 8 = = 0 and i ! = j) : return True elif ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 = = 0 and i ! = j and j ! = k and i ! = k) : return True return False # Driver function st = "3144" if (isSubSeqDivisible(st)) : print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Nikita Tiwari. |
C#
// C# program to check if a subsequence // of digits is divisible by 8. using System; class GFG { // Function to calculate any permutation // divisible by 8. If such permutation // exists, the function will return // that permutation else it will return -1 static bool isSubSeqDivisible( string str) { int i, j, k, l = str.Length; int [] arr = new int [l]; // Converting string to integer array for ease // of computations (Indexing in arr[] is // considered to be starting from 1) for (i = 0; i < n; i++) arr[i] = str[i] - '0' ; // Generating all possible permutations // and checking if any such // permutation is divisible by 8 for (i = 0; i < l; i++) { for (j = i; j < l; j++) { for (k = j; k < l; k++) { if (arr[i] % 8 == 0) return true ; else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j) return true ; else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 && i != j && j != k && i != k) return true ; } } } return false ; } // Driver function public static void Main() { string str = "3144" ; if (isSubSeqDivisible(str)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m. |
Javascript
<script> // JavaScript program to check if a subsequence // of digits is divisible by 8. // Function to calculate any permutation // divisible by 8. If such permutation // exists, the function will return // that permutation else it will return -1 function isSubSeqDivisible(str) { let i, j, k, l = str.length; let arr = []; // Converting string to integer array for ease // of computations (Indexing in arr[] is // considered to be starting from 1) for (i = 0; i < l; i++) arr[i] = str[i] - '0' ; // Generating all possible permutations // and checking if any such // permutation is divisible by 8 for (i = 0; i < l; i++) { for (j = i; j < l; j++) { for (k = j; k < l; k++) { if (arr[i] % 8 == 0) return true ; else if ((arr[i] * 10 + arr[j]) % 8 == 0 && i != j) return true ; else if ((arr[i] * 100 + arr[j] * 10 + arr[k]) % 8 == 0 && i != j && j != k && i != k) return true ; } } } return false ; } // Driver Code let str = "3144" ; if (isSubSeqDivisible(str)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by susmitakundugoaldanga </script> |
输出
Yes
方法2（动态规划）： 虽然我们只有100位数字，但对于大于100位的较长示例，我们的程序可能会超过给定的时间限制。 因此，我们通过使用 动态规划 方法 允许
是样本的第i位。我们生成一个矩阵dp[i][j]，1<=i<=n和0<=j<8。如果我们可以从长度i的前缀中划掉一些数字，使剩余的数字得到模8的j，那么dp的值为真，否则为假。为了更广泛地理解这个概念，如果在一个索引中，我们找到了元素模8，我们把它的值
![dp[i][a_{i}mod8] = 1](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-0ff615cfd31f026316449696fada1ab3_l3.png "Rendered by QuickLaTeX.com")
对于所有其他数字，我们建立在一个简单的概念上，即该数字的加法将贡献一个可被8整除的数字的信息，或者将其忽略。
注： 我们还必须记住，我们不能改变订单 现在
![dp[i][(j*10+a_{i}) mod 8]=max(dp[i][(j*10+a_{i}) mod 8], dp[i-1][j])](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-033a4ea8debf13174cceaeb77560a25f_l3.png "Rendered by QuickLaTeX.com")
如果我们把当前的数字加到之前的结果上。
![dp[i][(j*10) mod 8]=max(dp[i][(j*10) mod 8], dp[i-1][j])](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-40b58fb7810b6de06e3a4738afd265cd_l3.png "Rendered by QuickLaTeX.com")
如果我们排除队形中的当前数字。 现在，如果存在这样一个数字，我们将得到一个“真”的数字 我 在dp[i][0]中
C++
// C++ program to find if there is a subsequence // of digits divisible by 8. #include <bits/stdc++.h> using namespace std; // Function takes in an array of numbers, // dynamically goes on the location and // makes combination of numbers. bool isSubSeqDivisible(string str) { int n = str.length(); int dp[n + 1][10]; memset (dp, 0, sizeof (dp)); // Converting string to integer array for ease // of computations (Indexing in arr[] is // considered to be starting from 1) int arr[n + 1]; for ( int i = 1; i <= n; i++) arr[i] = str[i - 1] - '0' ; for ( int i = 1; i <= n; i++) { dp[i][arr[i] % 8] = 1; for ( int j = 0; j < 8; j++) { // If we consider the number in our combination, // we add it to the previous combination if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8]) dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j]; // If we exclude the number from our combination if (dp[i - 1][j] > dp[i][j]) dp[i][j] = dp[i - 1][j]; } } for ( int i = 1; i <= n; i++) { // If at dp[i][0], we find value 1/true, it shows // that the number exists at the value of 'i' if (dp[i][0] == 1) return true ; } return false ; } // Driver function int main() { string str = "3144" ; if (isSubSeqDivisible(str)) cout << "Yes" ; else cout << "No" ; return 0; } |
JAVA
// Java program to find if there is a // subsequence of digits divisible by 8. import java.io.*; import java.util.*; class GFG { // Function takes in an array of numbers, // dynamically goes on the location and // makes combination of numbers. static boolean isSubSeqDivisible(String str) { int n = str.length(); int dp[][] = new int [n + 1 ][ 10 ]; // Converting string to integer array // for ease of computations (Indexing in // arr[] is considered to be starting // from 1) int arr[] = new int [n + 1 ]; for ( int i = 1 ; i <= n; i++) arr[i] = ( int )(str.charAt(i - 1 ) - '0' ); for ( int i = 1 ; i <= n; i++) { dp[i][arr[i] % 8 ] = 1 ; for ( int j = 0 ; j < 8 ; j++) { // If we consider the number in // our combination, we add it to // the previous combination if (dp[i - 1 ][j] > dp[i][(j * 10 + arr[i]) % 8 ]) dp[i][(j * 10 + arr[i]) % 8 ] = dp[i - 1 ][j]; // If we exclude the number from // our combination if (dp[i - 1 ][j] > dp[i][j]) dp[i][j] = dp[i - 1 ][j]; } } for ( int i = 1 ; i <= n; i++) { // If at dp[i][0], we find value 1/true, // it shows that the number exists at // the value of 'i' if (dp[i][ 0 ] == 1 ) return true ; } return false ; } // Driver function public static void main(String args[]) { String str = "3144" ; if (isSubSeqDivisible(str)) System.out.println( "Yes" ); else System.out.println( "No" ); } } /* This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 program to find # if there is a subsequence # of digits divisible by 8. # Function takes in an array of numbers, # dynamically goes on the location and # makes combination of numbers. def isSubSeqDivisible( str ): n = len ( str ) dp = [[ 0 for i in range ( 10 )] for i in range (n + 1 )] # Converting string to integer # array for ease of computations # (Indexing in arr[] is considered # to be starting from 1) arr = [ 0 for i in range (n + 1 )] for i in range ( 1 , n + 1 ): arr[i] = int ( str [i - 1 ]); for i in range ( 1 , n + 1 ): dp[i][arr[i] % 8 ] = 1 ; for j in range ( 8 ): # If we consider the number # in our combination, we add # it to the previous combination if (dp[i - 1 ][j] > dp[i][(j * 10 + arr[i]) % 8 ]): dp[i][(j * 10 + arr[i]) % 8 ] = dp[i - 1 ][j] # If we exclude the number # from our combination if (dp[i - 1 ][j] > dp[i][j]): dp[i][j] = dp[i - 1 ][j] for i in range ( 1 , n + 1 ): # If at dp[i][0], we find # value 1/true, it shows # that the number exists # at the value of 'i' if (dp[i][ 0 ] = = 1 ): return True return False # Driver Code str = "3144" if (isSubSeqDivisible( str )): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by sahilshelangia |
C#
// C# program to find if there is a // subsequence of digits divisible by 8. using System; class GFG { // Function takes in an array of numbers, // dynamically goes on the location and // makes combination of numbers. static bool isSubSeqDivisible(String str) { int n = str.Length; int [, ] dp = new int [n + 1, 10]; // Converting string to integer array // for ease of computations (Indexing in // arr[] is considered to be starting // from 1) int [] arr = new int [n + 1]; for ( int i = 1; i <= n; i++) arr[i] = ( int )(str[i - 1] - '0' ); for ( int i = 1; i <= n; i++) { dp[i, arr[i] % 8] = 1; for ( int j = 0; j < 8; j++) { // If we consider the number in // our combination, we add it to // the previous combination if (dp[i - 1, j] > dp[i, (j * 10 + arr[i]) % 8]) dp[i, (j * 10 + arr[i]) % 8] = dp[i - 1, j]; // If we exclude the number from // our combination if (dp[i - 1, j] > dp[i, j]) dp[i, j] = dp[i - 1, j]; } } for ( int i = 1; i <= n; i++) { // If at dp[i][0], we find value // 1/true, it shows that the number // exists at the value of 'i' if (dp[i, 0] == 1) return true ; } return false ; } // Driver function public static void Main() { string str = "3144" ; if (isSubSeqDivisible(str)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find if there // is a subsequence of digits // divisible by 8. // Function takes in an array of numbers, // dynamically goes on the location and // makes combination of numbers. function isSubSeqDivisible( $str ) { $n = strlen ( $str ); $dp = array_fill (0, $n + 1, array_fill (0, 10, NULL)); // Converting string to integer // array for ease of computations // (Indexing in arr[] is considered // to be starting from 1) $arr = array_fill (0, ( $n + 1), NULL); for ( $i = 1; $i <= $n ; $i ++) $arr [ $i ] = $str [ $i - 1] - '0' ; for ( $i = 1; $i <= $n ; $i ++) { $dp [ $i ][ $arr [ $i ] % 8] = 1; for ( $j = 0; $j < 8; $j ++) { // If we consider the number in // our combination, we add it to // the previous combination if ( $dp [ $i - 1][ $j ] > $dp [ $i ][( $j * 10 + $arr [ $i ]) % 8]) $dp [ $i ][( $j * 10 + $arr [ $i ]) % 8] = $dp [ $i - 1][ $j ]; // If we exclude the number // from our combination if ( $dp [ $i - 1][ $j ] > $dp [ $i ][ $j ]) $dp [ $i ][ $j ] = $dp [ $i - 1][ $j ]; } } for ( $i = 1; $i <= $n ; $i ++) { // If at dp[i][0], we find value 1/true, // it shows that the number exists at // the value of 'i' if ( $dp [ $i ][0] == 1) return true; } return false; } // Driver Code $str = "3144" ; if (isSubSeqDivisible( $str )) echo "Yes" ; else echo "No" ; // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to find if there is a // subsequence of digits divisible by 8. // Function takes in an array of numbers, // dynamically goes on the location and // makes combination of numbers. function isSubSeqDivisible(str) { let n = str.length; let dp = new Array(n + 1); for (let i = 0; i < 10; i++) { dp[i] = new Array(10); for (let j = 0; j < 10; j++) { dp[i][j] = 0; } } // Converting string to integer array // for ease of computations (Indexing in // arr[] is considered to be starting // from 1) let arr = new Array(n + 1); for (let i = 1; i <= n; i++) arr[i] = (str[i - 1].charCodeAt() - '0' .charCodeAt()); for (let i = 1; i <= n; i++) { dp[i][arr[i] % 8] = 1; for (let j = 0; j < 8; j++) { // If we consider the number in // our combination, we add it to // the previous combination if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8]) dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j]; // If we exclude the number from // our combination if (dp[i - 1][j] > dp[i][j]) dp[i][j] = dp[i - 1][j]; } } for (let i = 1; i <= n; i++) { // If at dp[i][0], we find value 1/true, // it shows that the number exists at // the value of 'i' if (dp[i][0] == 1) return true ; } return false ; } let str = "3144" ; if (isSubSeqDivisible(str)) document.write( "Yes" ); else document.write( "No" ); </script> |
输出
Yes
使用动态方法，我们的时间复杂度降低到O（8*n），其中8是数字应该可以整除的数字，n是输入的长度。因此，总体复杂度为O（n）。
方法3 对于这个问题，我们只需要检查是否存在可被8整除的两位数子序列（8的整除性测试） 我们首先找到所有可被8整除的两位数，并将十位数与单位位数进行映射 i、 e:-16,24,32,40,48,56,64,72,80,88,96 忽略48，因为8总是可以被8整除，类似地，80和88中有8，这使得这样的子序列总是可以被8整除 所以我们用C++中的map I.STL映射将1到6, 2到4, 3到2，等等。 构建映射后，我们遍历上一个索引中的字符串，并检查当前索引号的映射值是否已访问，因此我们需要一个已访问数组，该数组将在访问该编号时存储true，否则存储false 例：3769 最后一个索引的第一个字符是9，所以我们检查是否访问了6（即96是否为子序列），我们在访问数组中标记9 下一个字符是6，所以我们检查是4访问（即64），我们在访问数组中标记6 下一个字符是7，所以我们检查是2访问（即72），我们在访问数组中标记7 下一个字符是3，所以我们检查是6（即36），是6被标记，因此我们打印是。
C++
// C++ program to check if given string // has a subsequence divisible by 8 #include<bits/stdc++.h> using namespace std; // Driver function int main(){ string str = "129365" ; // map key will be tens place digit of number // that is divisible by 8 and value will // be units place digit map< int , int > mp; // For filling the map let start // with initial value 8 int no = 8; while (no < 100){ no = no + 8; // key is digit at tens place and value is // digit at units place mp.insert({key, value}) mp.insert({(no / 10) % 10, no % 10}); } // Create a hash to check if we visited a number vector< bool > visited(10, false ); int i; // Iterate from last index to 0th index for (i = str.length() - 1; i >= 0; i--){ // If 8 is present in string then // 8 divided 8 hence print yes if (str[i] == '8' ) { cout << "Yes" ; break ; } // considering present character as the second // digit of two digits no we check if the value // of this key is marked in hash or not // If marked then we a have a number divisible by 8 if (visited[mp[str[i] - '0' ]]){ cout << "Yes" ; break ; } visited[str[i] - '0' ] = true ; } // If no subsequence divisible by 8 if (i == -1) cout << "No" ; return 0; } |
JAVA
// Java program to check if // given String has a subsequence // divisible by 8 import java.util.*; class GFG{ // Driver code public static void main(String[] args) { String str = "129365" ; // map key will be tens place // digit of number that is // divisible by 8 and value will // be units place digit HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // For filling the map let start // with initial value 8 int no = 8 ; while (no < 100 ) { no = no + 8 ; // key is digit at tens place // and value is digit at units // place mp.add({key, value}) //if(mp.containsKey((no / 10) % 10)) mp.put((no / 10 ) % 10 , no % 10 ); } // Create a hash to check if // we visited a number boolean [] visited = new boolean [ 10 ]; int i; // Iterate from last index // to 0th index for (i = str.length() - 1 ; i >= 0 ; i--) { // If 8 is present in String then // 8 divided 8 hence print yes if (str.charAt(i) == '8' ) { System.out.print( "Yes" ); break ; } // considering present character // as the second digit of two // digits no we check if the value // of this key is marked in hash or not // If marked then we a have a number // divisible by 8 if (visited[mp.get(str.charAt(i)- '0' )]) { System.out.print( "Yes" ); break ; } visited[str.charAt(i) - '0' ] = true ; } // If no subsequence divisible // by 8 if (i == - 1 ) System.out.print( "No" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to check if given string # has a subsequence divisible by 8 Str = "129365" # map key will be tens place digit of number # that is divisible by 8 and value will # be units place digit mp = {} # For filling the map let start # with initial value 8 no = 8 while (no < 100 ) : no = no + 8 # key is digit at tens place and value is # digit at units place mp.insert({key, value}) mp[(no / / 10 ) % 10 ] = no % 10 # Create a hash to check if we visited a number visited = [ False ] * 10 # Iterate from last index to 0th index for i in range ( len ( Str ) - 1 , - 1 , - 1 ) : # If 8 is present in string then # 8 divided 8 hence print yes if ( Str [i] = = '8' ) : print ( "Yes" , end = "") break # considering present character as the second # digit of two digits no we check if the value # of this key is marked in hash or not # If marked then we a have a number divisible by 8 if visited[mp[ ord ( Str [i]) - ord ( '0' )]] : print ( "Yes" , end = "") break visited[ ord ( Str [i]) - ord ( '0' )] = True # If no subsequence divisible by 8 if (i = = - 1 ) : print ( "No" ) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to check if given // String has a subsequence // divisible by 8 using System; using System.Collections.Generic; class GFG{ // Driver code public static void Main(String[] args) { String str = "129365" ; // Map key will be tens place // digit of number that is // divisible by 8 and value will // be units place digit Dictionary< int , int > mp = new Dictionary< int , int >(); // For filling the map let start // with initial value 8 int no = 8; while (no < 100) { no = no + 8; // Key is digit at tens place // and value is digit at units // place mp.Add({key, value}) if (mp.ContainsKey((no / 10) % 10)) mp[(no / 10) % 10] = no % 10; else mp.Add((no / 10) % 10, no % 10); } // Create a hash to check if // we visited a number bool [] visited = new bool [10]; int i; // Iterate from last index // to 0th index for (i = str.Length - 1; i >= 0; i--) { // If 8 is present in String then // 8 divided 8 hence print yes if (str[i] == '8' ) { Console.Write( "Yes" ); break ; } // Considering present character // as the second digit of two // digits no we check if the value // of this key is marked in hash or not // If marked then we a have a number // divisible by 8 if (visited[mp[str[i] - '0' ]]) { Console.Write( "Yes" ); break ; } visited[str[i] - '0' ] = true ; } // If no subsequence divisible // by 8 if (i == -1) Console.Write( "No" ); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to check if // given String has a subsequence // divisible by 8 // Driver code let str = "129365" ; // map key will be tens place // digit of number that is // divisible by 8 and value will // be units place digit let mp = new Map(); // For filling the map let start // with initial value 8 let no = 8; while (no < 100) { no = no + 8; // key is digit at tens place // and value is digit at units // place mp.add({key, value}) //if(mp.containsKey((no / 10) % 10)) mp.set((Math.floor(no / 10)) % 10, no % 10); } // Create a hash to check if // we visited a number let visited = new Array(10); for (let i=0;i<visited.length;i++) { visited[i]= false ; } let i; // Iterate from last index // to 0th index for (i = str.length - 1; i >= 0; i--) { // If 8 is present in String then // 8 divided 8 hence print yes if (str[i] == '8' ) { document.write( "Yes" ); break ; } // considering present character // as the second digit of two // digits no we check if the value // of this key is marked in hash or not // If marked then we a have a number // divisible by 8 if (visited[mp.get(str[i].charCodeAt(0)- '0' .charCodeAt(0))]) { document.write( "Yes" ); break ; } visited[str[i].charCodeAt(0) - '0' .charCodeAt(0)] = true ; } // If no subsequence divisible // by 8 if (i == -1) document.write( "No" ); // This code is contributed by rag2127 </script> |
输出
Yes
如果仔细观察，访问的数组将始终有10个字段，映射将始终具有相同的大小，因此遍历字符串的空间复杂度将为O（1），时间复杂度将为O（n）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
