Her çaprazda aynı değer
Görev tanımı
Problem
Bir ekran için bir test deseni sayılardan oluşan bir grid olarak saklanıyor. Desen yalnız sol üstten sağ alta uzanan her çapraz tek bir tekrarlanan değer tutuyorsa geçerli. Grid verildiğinde geçerliyse True, değilse False döndür. Grid'in 1 ile 20 arasında satırı ve 1 ile 20 arasında sütunu (column) var; her değer 0 ile 99 arasında.
Örnekler
Input: grid = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output: True
Neden: çaprazlar [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3] ve [4]
Input: grid = [[1, 2], [2, 2]]
Output: False
Neden: ana çapraz 1 ve sonra 2 tutuyor
Input: grid = [[7]]
Output: True
Neden: edge case: tek hücre tek değerli bir çaprazdır
İpuçları
0 / 3
İki hücre tam olarak satır eksi sütunları aynı olduğunda aynı sol üstten sağ alta çaprazda durur.
Bütün çaprazları toplamana gerek yok. Her hücrenin hemen sol üstündeki hücreyle eşleşmesi yeter, çünkü eşitlik o zaman çapraz boyunca zincirlenir.
Sol üst komşusu olan her hücre, yani ilk satırın ve ilk sütunun dışındaki her hücre üzerinde döngü kur ve ilk uyuşmazlıkta False döndür.
- Hedef zaman
- O(rows · cols)
- Hedef alan
- O(1)
Kısıtlar
- 1 ≤ rows ≤ 20
- 1 ≤ cols ≤ 20
- 0 ≤ value ≤ 99
Çözüm
Bir adım aşağı ve bir adım sağa gitmek satır eksi sütunu değiştirmez; bu yüzden her hücrenin çaprazdaki öncülü row - 1, column - 1'deki hücredir. Her hücre bu öncüle eşitse eşitlik her çaprazın ilk hücresinden sonuncusuna zincirlenir, yani bütün çapraz tek bir değer tutar; tek bir uyuşmazlık onu bozar. Her hücreyi komşusuyla kontrol etmek ek depolama gerektirmez ve satırlar birer birer gelse de aynı kontrol çalışır, çünkü her yeni satırın yalnız bir sağa kaydırılmış önceki satırla eşleşmesi gerekir. Zaman O(rows × cols), alan 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]])) # -> TrueKodda değil de fikirde mi takıldın? In-place döndürme bunu anlatıyor.