Enunciado em inglês. Desde já, tenha em mente que o texto foi parcialmente alterado para diminuir a chance da solução seja encontrada por alguém que esteja fazendo a prova:
A hiker keeps records of their hikes registering when is uphill, sea level, or downhill. Hikes always start and end at sea level, and each step up or down represents a unit change in altitude. We define the following terms:
-
- A hill is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
- A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.
Given the sequence of up and down steps during a hike, find and print the number of valleys walked through.
Sample Input: 8, UDDDUDUU
Expected result: 1
Explanation: If we represent _ as sea level, a step up as /, and a step down as \, the hike can be drawn as:
_/\ _
\ /
\/\/
Explicando
Um caminhante registra todos seus passos durante suas caminhadas (a redundância está no texto original). Ele sempre começa as caminhadas no nível do mar, sempre que sobe registra um U (up) e sempre que desce registra um D (down).
No exemplo dado, o caminhante começa subindo um nível uma colina (UDDDUDUU), imediatamente após desce um nível (UDDDUDUU), o que faz com que ele volte ao nível do mar e depois começa a descer um vale (UDDDUDUU), sobre um nível (UDDDUDUU), volta a descer (UDDDUDUU) e depois sobe novamente até o nível do mar (UDDDUDUU). O exercício pede que seja retornado o número de vales pelo qual o caminhante passou (neste caso: 1).
Resolvendo
Há várias formas de resolver o problema, uma delas é ir contado o número de passos para cima e para baixo. Quando eles são iguais e o próximo passo for para baixo, está começando a descer um vale. Uma vez que o número de passos volte a ser iguais, parou de descer e voltou ao nível do mar. Apesar de funcionar, não é uma solução das mais eficiente.
Outra forma, com melhor performance, é comparar o nível em que o caminhante se encontra. Considere zero como sendo o nível do mar, cada vez que subir adicione uma unidade ao nível, quando ele descer, subtraia uma unidade. Desta forma, quando o nível for menor que zero, o caminhante se encontra num vale., quando o nível voltar a zero, ele saiu do vale. Então, basta contar quantas vezes ele entrou no vale. Abaixo o código devidamente comentado:
int contandoVales(int passos, string caminho) {
int nivel = 0; //nivel do mar
int numeroVales = 0;
bool estaNumVale = false; //comeca no nivel do mar
char desce = 'D';
//percorre toda a string "caminho"
for (int i = 0; i < passos; i++)
{
//se a posicao for igual a "D" subtrai uma unidade do "nivel"
//senao adiciona uma unidade (este é um IF ternário)
nivel = caminho[i] == desce ? --nivel : ++nivel;
//se o nível for menor que zero e nao está no vale
if (nivel < 0 && !estaNumVale)
{
numeroVales++; //incrementa o número de vales
}
//se nível for menor que zero está no vale
estaNumVale = nivel < 0;
}
return numeroVales;
}
| Origem da questão | ||
| País: Bélgica | Tipo: Teste de Código | Assunto: Manipulação de strings |
| Ramo de negócio da empresa: Banco | Grau de Dificuldade: Fácil | |