J'ai rencontré le problème suivant. Ce problème existe déjà sur ce lien sur Stack Overflow mais la réponse là-bas ne résout pas mon problème car il n'y a aucune explication donnée ici.
Il y a N ampoules, numérotées de 1 à N disposées en ligne. Le numéro d'ampoule i est câblé au numéro d'ampoule i-1 et la première ampoule est connectée à la prise de courant.
Au départ, toutes les ampoules sont éteintes, puis nous allumons les ampoules en fonction d'un tableau donné (expliqué dans l'exemple suivant). Une ampoule brille si elle est allumée et toutes les ampoules précédentes sont déjà allumées. Nous devons trouver le nombre de moments pendant lesquels chaque ampoule allumée brille ( Clarification comme indiqué dans les commentaires de @Prune: Supposons que j'allume les ampoules une par une selon le tableau donné (de gauche à droite), alors si j'allume une ampoule et que toutes les ampoules précédentes sont allumées, alors elle brille et cela s'appelle un moment. Nous devons donc trouver le nombre total de ces moments lorsque j'allume une ampoule et qu'elle brille).
par exemple Étant donné le tableau [2, 1, 3, 5, 4] , nous devrions obtenir la réponse 3 comme suit:
N est un entier dont la plage est [1, 100000] ; Tous les éléments de A sont distincts; Chaque élément du tableau donné est un entier compris dans la plage [1, N]
Je pourrais penser à une approche naïve en revérifiant à chaque index du tableau si les ampoules d'index précédentes sont ACTIVÉES . Cela me donne une solution O (n ^ 2) . Mais y a-t-il une meilleure solution?
#Suppose A is the given array
moment = 0
ON = set()
for i in range(len(A)):
flag = TRUE
for idx in range(1, A[i]):
if idx not in ON:
flag = False
if flag:
moment+=1
ON.add(A[i])
Quelques autres exemples de sortie attendue pour clarifier la question: Tableau donné [2, 3, 4, 1, 5] solution est 2; pour le tableau [1, 3, 4, 2, 5] , la solution est 3.
5 Réponses :
Construisez un tableau qui représente l'état des ampoules.
0 signifie OFF
1 signifie ON
Au départ, tous les éléments du tableau sont 0. p>
If sum==x
Construisez une arborescence de segments sur le tableau avec la somme des éléments.
Pour chaque requête x , mettez à jour la position correspondante dans le arborescence de segments.
puis interrogez la somme des valeurs dans la plage [1,x .
arr=[0,0,0,0,0]
alors votre condition est satisfait.
Complexité temporelle: - O (n log (n))
Les requêtes de mise à jour et de somme prennent un temps de log (n).
Traversée du tableau des requêtes prend n temps.
Solution O (N)
func bulbsSolution(_ switches: [Int]) -> Int {
var max_position_on = 0
var moments = 0
for (pos, v) in switches.enumerated() {
max_position_on = max(max_position_on, v)
if max_position_on == pos + 1 {
moments += 1
}
}
return moments
}
et dans SWIFT^
on_sched = [2, 3, 4, 1, 5]
max_on = 0 # Number of the highest bulb turned on
moment_ct = 0 # Count of moments with all bulbs on
for pos, bulb in enumerate(on_sched):
max_on = max(max_on, bulb) #Keep track of maximum bulb turned on
# Is that bulb number the quantity of bulbs?
if max_on == pos+1: # Adjust for 0-indexed list
moment_ct += 1
p>
Je pense que cela ne donnera pas la bonne réponse. Prenons le cas on_sched = [4, 3, 1, 2] . Ici, nous devrions avoir 2 moments (d'abord à 1 puis à 2 ) mais le code ci-dessus ne donne que 1. Tous les commentaires.
Non, nous ne devrions pas avoir 2 moments. Puisque l'ampoule 4 (la plus à droite) est la première allumée, la seule fois où toutes les ampoules "ON" brillent est à la fin, lorsque les ampoules 1, 2 et 3 sont finalement allumées.
Mais nous n'avons pas besoin que toutes les ampoules soient allumées pour faire briller l'ampoule actuelle. Nous n'avons besoin que d'ampoules pour qu'il soit allumé pour qu'il brille comme l'exemple que j'ai mentionné dans ma question?
Votre énoncé de problème se termine par: Nous devons trouver le nombre de moments pendant lesquels chaque ampoule allumée brille. Pas l'ampoule la plus récemment allumée - toutes les ampoules allumées doivent briller .
Oh, je pense que je n'ai pas été clair avec cette déclaration; J'ai copié les termes exacts mentionnés dans la question d'origine, mais ce que je voulais dire par "Nous devons trouver le nombre de moments pendant lesquels chaque ampoule allumée brille" est que je suppose que j'allume les ampoules une par une en fonction du tableau donné (à partir de de gauche à droite), alors si j'allume une ampoule et que toutes les ampoules précédentes sont allumées seulement, alors elle brille et cela s'appelle un moment. Nous devons donc trouver le nombre total de ces moments lorsque j'allume une ampoule et qu'elle brille. Je mentionnerai la même chose dans la question elle-même pour éviter toute confusion.
C'est une solution super intelligente. J'ai eu l'audace et j'ai ajouté ma version en réponse. S'il vous plaît excusez-moi. :)
Pour tous ceux qui cherchent encore une réponse à cette question, voici la mienne réalisée en python:
import sys
import math
Array = [1,3,4,2,5]
def solution(A):
state_array = [False] * len(A)
moment = 0;
for index, bulb in enumerate(A):
state_array[bulb - 1] = True;
if bulb == 1:
moment = moment + 1
else:
if all(state == True for state in state_array[0: index+1]) and index != 0:
moment = moment + 1
if all(state == True for state in state_array):
return moment
print(solution(Array))
int Total = 0;
int[] aaa = { 1, 2, 4, 6, 3, 5, };
for (int i =0; i < aaa.Length; i++)
{
if (Checkonoroff(aaa[i],i+1) == 1)
Total++;
}
return Total;
private int Checkonoroff(int Value, int Position)
{
int e = 0;
int[] ArrayTwo = new int[Position];
Array.Copy(aaa, ArrayTwo, Position);
for (int i = Value; i > 0; i--)
{
if (ArrayTwo.Contains(i))
e++;
}
if (e==Value)
return 1;
return 0;
}
Bonjour! Bien que ce code puisse résoudre la question, y compris une explication sur comment et pourquoi cela résout le problème aiderait vraiment à améliorer la qualité de votre message et entraînera probablement plus de votes positifs. N'oubliez pas que vous répondez à la question des lecteurs à l'avenir, pas seulement à la personne qui la pose maintenant. Veuillez modifier votre réponse pour ajouter des explications et donner une indication des limitations et hypothèses applicables.
Voici des solutions complètes pour le cas O (n).
public class Test {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int A[] = {2, 1, 3, 5, 4};
System.err.println(solution(A));
}
public static int solution(int[] a) {
Set<Integer> missing = new HashSet<>();
Set<Integer> store = new HashSet<>();
int count = 0;
for (int i = 0; i < a.length; i++) {
if (!store.contains(i + 1) && i + 1 != a[i]) {
missing.add(i + 1);
}
if (i + 1 < a[i]) {
store.add(a[i]);
} else {
missing.remove(a[i]);
}
if (missing.isEmpty()) {
count++;
}
}
return count;
}
}
il suffit de garder dans certaines var l'ampoule d'éclairage la plus élevée, si c'est la précédente, puis de la réaffecter à une nouvelle et de vérifier si la suivante est allumée et la suivante jusqu'à ce que le chaon ne soit pas cassé
@DmitryReutov: c'est toujours O (N ^ 2) .