Compte tenu d'une chaîne de chiffres décimaux, je dois trouver le nombre de toutes les sous-séquences divisibles par 6.
for(i=0 ; i<n ; i++) {
for(j=0 ; j<3 ; j++) {
dp[i][j]=0 ;
}
int dig = (str[i]-'0')%3 ;
dp[i][dig]++ ;
if(i>0) {
for(j=0 ; j<3 ; j++) {
if(dig % 3 == 0) {
dp[i][j] += dp[i-1][j];
}
if(dig % 3 == 1) {
dp[i][j] += dp[i-1][(j+2)%3];
}
if(dig % 3 == 2) {
dp[i][j] += dp[i-1][(j+1)%3];
}
}
}
}
long long ans = 0;
for(i=0 ; i<n ; i++) {
ans += dp[i][0] ;
}
return ans;
3 Réponses :
Solution de récursive exponentielle (pour le cas général) qui se traduit par linéaire si la valeur max pouvant correspondre peut représenter est 1E6.
def recurse(x, substr, input):
if x%6 == 0:
print(x)
if len(substr) == 6: // as the value represented by string may not be > 1e6
return
if input:
recurse(x+input[0], substr + input[0], input[1:]) // grow the "window"
recurse(x, substr, input[1:]) // shift the "window"
input = "123163736395067251284059573634848487474"
recurse(input)
Ce problème peut être résolu en temps linéaire, O (n) fort> et espace linéaire O (n) strong>, n étant la longueur de la chaîne si nous ne considérons que deux Substrings. J'essaie de construire un algorithme pour les sous-séquences. points de clé strong>: p> 1 fort>. Toutes les sous-chaînes divisibles de 6 sont divisibles par 2 et 3 et nous nous concentrerons sur la divisibilité par ces deux nombres. P> maintenant, nous prenons un tableau Array code>, de longueur N. Nous remplissons est telle que P> track[i] = x, if there are x number of 1's in array arr1 for indices j < i.
@Varungarg N'oubliez pas que cela fonctionnera uniquement pour les sous-chaînes.
let c'est-à-dire si vous ajoutez un chiffre à x, alors les sous-successes que la somme à K sont des sous-séquences de x cette somme à K, ainsi que des sous-préquections de x cette somme à J où (10 * j) plus le nouveau chiffre est k modulo m. qui se transforme en un bon programme dynamique, lequel si N est la longueur de la chaîne et que vous voulez. Les sous-séquences doivent être divisibles par, fonctionne dans O (NM + M ^ 2) et utilise un espace O (m). Pour m = 6, c'est o (n) l'espace et o (1) espace. Note de bas de page: la définition de ss (x, k, m) = le nombre de remplaçances de la chaîne x représentant un numéro égal à k modulo m . ss compte le vide Liste comme 0 mais la chaîne vide n'est pas un numéro valide, la fonction soustrait une avant de revenir.
Belle solution. Puis-je suggérer de changer certaines de vos utilisations du mot "somme", cependant - qui semble décrire un problème différent (par exemple "123" est une chaîne "dont les sommes de chiffres sont égales à 0 modulo 6", mais ce n'est pas ce que Nous voulons ici).
Pouvez-vous coller du code, montrez-vous ce que vous avez essayé jusqu'à présent afin que nous puissions vous aider.
Êtes-vous sûr que la longueur de la chaîne peut être 10⁶, ou la valeur que la chaîne représente limitée à cela?
@Sekekaddo Monsieur, j'ai ajouté mon code.
@Trincot C'est la valeur que la chaîne représente.Merci.
La correction sur ce que 10 ^ 6 limites est probablement fausse - si la valeur de la chaîne est bornée de 10 ^ 6, le nombre est au plus 6 chiffres et il est trivial juste pour énumérer toutes les sous-chaînes (il n'y a que 21 sous-chaînes). Prendre le résultat Modulo 10 ^ 9 + 7 n'a pas non plus de sens si le résultat <= 21. Je suppose que la longueur de la chaîne est borné par 10 ^ 6.