É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 10% da nota desta componente. Como existem 12 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Conteúdos das teóricas
Nesta e nas próximas aulas práticas iremos usar listas ligadas. Será por isso conveniente ver o que foi falado nas teóricas:
A partir desta aula, as dicas passaram normalmente a estar escondidas atrás de um botão do tipo "spoiler": só carregando é que aparecem. Assim, se preferirem, podem optar por primeiro pensar um pouco no problema "sozinhos" (sendo que podem também carregar logo para ver).
Exercício 1) Compreender listas ligadas
Código de listas.
Faça download do código dado nas teóricas e compile-o (precisa de ter os 3 ficheiros):
SinglyLinkedList - lista ligada simples (ex operações: tamanho, adicionar no início e no fim, retirar no início e no fim)
Um primeiro teste.
Abra o ficheiro TestSinglyLinkedList.java no seu
editor. Execute o código desse ficheiro ($
java TestSinglyLinkedList) e procure acompanhar cada uma das linhas de código e o seu efeito.
Abra também o ficheiro SinglyLinkedList.java para espreitar como os métodos referidos no TestSinglyLinkedList.java são implementados.
Genéricos, wrappers e autoboxing.
Tal como explicado nas aulas, a implementação de listas ligadas usa a noção de genéricos e por isso suporta qualquer qualquer tipo de objectos (não apenas inteiros). Para usar inteiros o exemplo do TestSinglyLinkedList usou o tipo Integer que é uma classe cujo objectivo é conter um inteiro (e com isso poder ser usada onde o Java espera um Objecto, como é o caso aqui).
Este é um exemplo das classes que encapsulam tipos primitivos (os wrappers), que são as seguintes:
Byte, Short, Integer, Long, Float, Double, Character, Boolean. Estas classes suportam a noção de autoboxing.
Para testar pelo menos um outro wrapper, adicione ao main um pedaço de código para criar uma lista com as vogais 'a', 'e', 'i', 'o', 'u'e imprima-a para se certificar que a criou correctamente.
Lista de tipos customizados: um exemplo com uma lista de pares.
Crie uma lista para conter em cada posição um par de números, adicione-lhe todas as coordenadas inteiras entre (1,1) e (3,3) e imprima a lista. O output deverá ser algo como: {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}
Deverá criar uma nova classe Pair
para representar um par de inteiros.
Deverá criar uma SinglyLinkedList de... Pair!
Para poder simplesmente mandar imprimir a lista deverá criar o método toString na classe Pair (que define o que a classe devolve quando é esperada uma String).
Exercício 2) Vários exercícios de listas no Mooshak
Este exercício consiste na implementação de vários métodos para manipular listas. Todos eles são para serem integrados na classe SinglyLinkedList e estão disponíveis para submissão no Mooshak de EDados no "Volume 3 (Listas Ligadas)", problemas 188 a 193.
Para testar as implementações no seu computador deve chamar os métodos no main depois de ter criado as listas com os exemplos que quiser verificar.
Não se esqueça de usar o método equals para comparar (ex: var1.equals(var2) compara o conteúdo de var1 com var2 e retorna true se forem iguais, ou false caso contrário). Um == apenas compara se as referências "apontam" para o mesmo endereço de memória.
Exercícios extra para consolidação de conhecimentos
Cuidado com a remoção de vários números seguidos...
Implementando um .equals
Experimente tentar usar o método count numa lista de pares como atrás definiiu (objectos do tipo Pair). O que acontece? Os objectos têm um .equals padrão que é equivalente ao ==. Para ter o comportamento desejado (comparar os dois números do par) é necessário implementar esse método. Faça override do método padrão e implemente um equals correcto para a sua classe Pair. Teste a sua implementação fazendo contagens e verificando a correção do resultado.
Mais métodos de listas
Implemente mais alguns métodos de listas fazendo operações que julgue serem úteis, treinando também a parte de perceber como deve ser a assinatura do método. Aqui ficam algumas sugestões para métodos:
Devolver a posição da primeira (ou última) ocorrência de um dado elemento na lista
Retirar todos os elementos que estão numa posição ímpar (ou par)
Concatenar (juntar) duas listas
Acesso eficiente ao último elemento
Para melhorar a eficiência dos métodos que necessitam de aceder ao final da lista (getLast e addLast) adicione um atributo private Node<T> last à sua classe de lista ligada. Faça as devidas modificações em todos os métodos implementados (no final têm que deixar correctos não só os valores de first e size, mas também de last). Este é um tradeoff típico: melhorar a eficiência tornando (ligeiramente) mais complexa a implementação.
Desafio
Para esta semana vou colocar um problema diferente dos anteriores e um pouco mais fácil, na esperança de que mais alunos voltem a tentar fazer (e a conseguir). É novamente um problema da minha autoria quefoi usado nas Olimpíadas de Informática, mas neste caso na qualificação (uma fase mais preliminar) e vários miúdos do secundário conseguiram resolvê-lo completamente:
O limite de tempo de execução para cada caso de teste é de 1 segundo, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for eficiente (note que a frase pode ter um milhão de caracteres).
Para estes problemas de desafios não vou dar logo dicas, para vos deixar pensar, mas se quiserem mesmo resolver o problema e não estejam a conseguir (mesmo depois de terem realmente tentado), podem falar comigo para obter pistas, ou ter uma ideia de como os "atacar"
