Algoritmi grezzi - minimizzare "rotonde parentesi" per ottenere un'espressione valida

Question

Algoritmi grezzi - minimizzare "rotonde parentesi" per ottenere un'espressione valida

#1 da (1 voti)
#2 da (1 voti)

1

Mi sto preparando per un esame sul quale ci saranno problemi risolvibili con DP, algoritmi grezzi. E uno dei problemi è - dato che una stringa contenente parentesi in nessun ordine particolare restituisce un numero minimo di "rotazioni" necessarie per fare un'espressione valida, per esempio ())) non è un'espressione valida ma puoi "ruotare" il secondo paren- ottieni (()) che è un'espressione valida (la risposta sarebbe 1).

Mi è stato detto che questo può essere risolto con qualche algoritmo avido. È facile trovare la soluzione DP di O (n ^ 3) quindi stiamo cercando qualcos'altro (possibilmente O (n)?). Qual è la strategia quando cerchi di trovare una soluzione avida per questo problema?

algorithms

posta qiubit 19.01.2015 - 15:41

fonte

2 risposte

Leggi altre domande sui tag algorithms

Utilizzo di molti URI risorse per creare un record e gestire errori È normale che i metodi di servizio siano correlati alle viste?

score 1 · Answer 1

Greedy significa intraprendere l'azione che tenta immediatamente di migliorare il problema.

Sostituisci ogni coppia \() che racchiude solo periodi . con punti. Poi alla fine ti ritroverai con una sequenza di parenti di chiusura seguita da una sequenza di parenti aperti (intervallati da punti).

Quindi devi solo ruotare la prima metà del parens di chiusura e la seconda metà del paren aperto.

L'ultimo passo sarà quello di correggere il caso )( in modo che diventi il () corretto.

Questo è O(n²) con un algoritmo di corrispondenza ingenuo. Anche se può essere accelerato pensando al passaggio di sostituzione come l'espansione delle esecuzioni del periodo.

score 1 · Answer 2

Non ho risolto questo particolare problema, ma c'è un approccio generale da prendere. La prima cosa da guardare è quali informazioni è possibile calcolare in O(n) . In questo caso:

Il conteggio di parentesi aperte e chiuse.
Il numero minimo assoluto di rotazioni, basato sul conteggio non uniforme.
La profondità attuale di nidificazione di ciascun paren, a partire dal lato destro e sinistro della stringa.
La massima profondità di annidamento consentita in qualsiasi punto, in base ai parenti opposti rimanenti disponibili, iniziando dal lato destro e sinistro della stringa.
Quali paren sono già correttamente bilanciati.

Quindi risolvi un gruppo di casi di test manualmente, e guarda le informazioni calcolate sopra per i parents che hai lanciato. Prova a confrontare, sottrarre, aggiungere, ecc. I parametri che hai calcolato. Ci sono schemi che puoi discernere? Riesci a capire come regolare le informazioni calcolate in O(1) dopo aver eseguito un flip?

Questa parte richiede una certa quantità di pratica. Può aiutare a passare attraverso l'esercizio per algoritmi noti, cercando di "decodificarli".