Mesmo valor em cada diagonal
A missão
Problema
Um padrão de teste para uma tela é armazenado como um grid de números. Ele só é válido quando toda diagonal que vai do canto superior esquerdo ao inferior direito tem um único valor repetido. Dado o grid, retorne True se ele for válido e False caso contrário. O grid tem entre 1 e 20 linhas e entre 1 e 20 colunas, e cada valor está entre 0 e 99.
Exemplos
Input: grid = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output: True
Por quê: as diagonais são [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3] e [4]
Input: grid = [[1, 2], [2, 2]]
Output: False
Por quê: a diagonal principal tem 1 e depois 2
Input: grid = [[7]]
Output: True
Por quê: edge case: uma única célula é uma diagonal com um valor
Dicas
0 / 3
Duas células estão na mesma diagonal, do canto superior esquerdo ao inferior direito, exatamente quando a linha menos a coluna dá o mesmo valor nas duas.
Você não precisa coletar diagonais inteiras. Basta que cada célula seja igual à célula logo acima e à esquerda dela, porque aí a igualdade se encadeia ao longo da diagonal.
Percorra cada célula que tem um vizinho acima e à esquerda, ou seja, toda célula fora da primeira linha e da primeira coluna, e retorne False na primeira divergência.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(1)
Restrições
- 1 ≤ rows ≤ 20
- 1 ≤ cols ≤ 20
- 0 ≤ value ≤ 99
Solução
Andar um passo para baixo e um para a direita mantém a linha menos a coluna inalterada, então o antecessor diagonal de cada célula é a célula na linha - 1, coluna - 1. Se toda célula for igual a esse antecessor, a igualdade se encadeia da primeira célula de cada diagonal até a última, então a diagonal inteira tem um só valor; uma única divergência quebra isso. Comparar cada célula com o seu vizinho não precisa de armazenamento extra, e a mesma verificação funciona se as linhas chegarem uma de cada vez, já que cada nova linha só precisa bater com a linha anterior deslocada uma posição para a direita. O tempo é O(rows × cols) e o espaço é O(1).
def diagonal_constant(grid):
for r in range(1, len(grid)):
for c in range(1, len(grid[0])):
if grid[r][c] != grid[r - 1][c - 1]: # up-left neighbour differs
return False
return True
print(diagonal_constant([[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]])) # -> True
print(diagonal_constant([[1, 2], [2, 2]])) # -> False
print(diagonal_constant([[7]])) # -> TrueTravou na ideia, e não no código? Rotacionar in-place explica isso.