settembre 2010 Blog Posts
Problema: Considera di rappresentare un numero attraverso una lista semplice come quella implementata in un precedente post. Ogni elemeneto della lista rappresenta una delle cifre del numero. Le cifre sono memorizzate nell’ordine inverso. Quindi il primo elemento della lista sara’ la cifra delle unita’. Prese due liste che rappresentano due numeri a e b, ritornare una nuova lista che rappresenta il risultato a + b. Inputs: Due liste semplici di interi: a e b Output: Una lista semplice di interi Esempio: Inputs: a: 6, 5,...
Problema: Considerare una Single Linked List di interi. Scrivere un metodo che ritorna il valore dell’elemento distante nth dall’ultimo elemento. Se non esiste sollevare una eccezione. Il codice della struttura dati e’ presente in un precedente post. Input: Un intero (nht) che rappresenta la distanza dall’ultimo elemento della lista Output: Un intero che rappresenta il valore dell’elemento desiderato. Esempio: Lista: 5, 7, 2, 4, 3, 9 Input: 0 Output: 9 Input: 1 Output: 3 Input: 5...
Problema: Considerare una semplice classe che implementa una SingleLinkedList non ordinata di interi. Realizzare un metodo per rimuovere tutti i duplicati dalla lista. Input: Niente Output: Niente. Internamente gli elementi duplicati saranno rimossi dalla lista. Esempio: Lista iniziale: 1, 1, 1, 1, 3, 4, 5, 3, 5, 1, 2, 1, 2, 3, 4 ,1 , 2, 3, 5, 1, 2, 5, 6, 7, 2, 8, 2, 9, 9 Lista finale: 1, 3, 4, 5, 2, 6, 7, 8, 9 ...
Problema: Dato un insieme I di n intervalli [a, b] con a e b interi determinare il sottoinsieme piu’ grande di intervalli mutuamente non sovrapposti che possono essere selezionati da I. Input: Due vettori di n interi che rappresentano l’insieme I. a = { a0, a1, … } b = { b0, b1, … } Ogni intervallo e’ identificato da un numero intero k. L’intervallo generico k e’ rappresentato dagli estremi a[k] e b[k]. Output: Una lista di interi ordinata (List<int>) che contiene gli identificatori degli intervalli...
Problema: Abbiamo una matrice quadrata (N x N) di interi che rappresenta una immagine. Scrivere un algoritmo che ruota l’immagine di 90 gradi in senso orario. Input: Una matrice quadrata (N x N) di interi. Output: Una matrice quadrata (N x N) di interi. Esempio: Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ...
Problema: Date due parole (stringhe) dire se sono anagrammi. Input: Due stringhe che rappresentano due parole (spazi esclusi) Output: Un booleano Esempio: Input: “nave” e “vena” Output: true Input: “nave” e “neve” Output: false Il mio ragionamento: Se le due parole hanno un numero di caratteri differenti non possono essere anagrammi. Calcolo il numero di occorrenze di ciascun carattere nella prima parola. Per ogni carattere della seconda parola verifico se ce...
Problema: Rimuovere tutti i caratteri duplicati da una stringa. Gli spazi devono essere preservati. Vincoli: Se si utilizza C++ modificare direttamente il parametro di input senza utilizzare buffer aggiuntivi. Se si utilizza C# ritornare una nuova stringa. In quanto le stringhe sono immutabili, e’ consentito l’utilizzo del metodo ToCharArray() per attenere un buffer su cui lavorare. Input: Una stringa Output: Una stringa Esempio: Input: “Microsoft .Net Framework” Output: “Microsft .Ne Famwk” Il mio ragionamento: Itero il buffer della stringa e costruisco all’inizio di...
Problema: Data una stringa, calcolare e ritornare una nuova stringa con gli stessi caratteri ma in ordine inverso. Esempio: ABCDE Risultato: EDCBA Input: Una stringa. Output: La stringa di input con i caratteri in ordine inverso. Il mio ragionamento: Costruisco un vettore di caratteri lungo quanto la stringa e lo riempio con un semplice ciclo for. La mia soluzione: public static string Reverse(string s) { if (s == null) throw new ArgumentNullException("s"); if (s.Length < 2) return s; char[] vc = new...
Problema 1: Determinare se in una stringa tutti i caratteri sono diversi tra loro. Problema 2: Risolvere il problema 1 senza usare strutture dati aggiuntive. Input: Una stringa Output: Un booleano Il mio ragionamento: Sfrutto un vettore di booleani con un numero di elementi pari a tutti i possibili caratteri. Itero la stringa e per ogni carattere setto il corrispondente elemento del vettore a true. Se prima di settare lo trovo gia’ a true significa che quello e’ un carattere ripetuto e restituisco subito false. Se si termina...
Problema 1: Fino ad ora non sapevo cosa fosse una ransom note. Praticamente si tratta di un testo realizzato utilizzando ritagli da una rivista. Dato il testo di una ransom note e il testo della rivista, dire se e’ possibile realizzare la ransom note. Problema 2: Risolvere lo stesso problema ma ritagliando parole invece che singoli caratteri. Input: Testo della ransom note che si vuole creare (stringa). Testo della rivista da cui si vuole ritagliare (stringa). Output: True se...
Problema: Dato un array di interi ordinato in modo crescente ma ruotato, calcolare il valore minimo. Input: Un vettore di interi. Output: Un intero che rappresenta il minimo elemento del vettore. Esempio: Dato l’array ordinato ruotato: 20, 30, 50, 108, 6, 8, 9, 19 il valore minimo e’ 6 Il mio ragionamento: Fare una scansione totale dell’array avrebbe complessita’ O(n) e non sfrutterebbe l’informazione aggiuntiva che l’array e’ ordinato e ruotato. Si puo’ allora pensare di fare una specie di ricerca binaria con complessita’ O(log(n))...
Problema: Data un’ora, calcolare l’angolo in gradi compreso tra la lancetta dei minuti e la lancetta dei secondi in un orologio analogico (sempre il piu’ piccolo dei due). Input: L’input e’ costituito da due interi che rappresentano rispettivamente il valore delle ore (h) e il valore dei minuti (m). Il valore delle ore e’ un intero compreso tra 0 e 11 estremi compresi. Il valore dei minuti e’ un intero compreso tra 0 e 59 estremi compresi. Output: L’output e’ un numero reale (compreso tra 0 e 180...