Cea mai lungă cale crescătoare într-o matrice de la leetcode (Revizuirea codului, Python, Algoritm, Căutare În Profunzime Mai Întâi)

noman pouigt a intrebat.
a intrebat.

Rezolvat this:

Dată fiind o matrice întreagă, găsiți lungimea celei mai lungi căi crescătoare.

Din fiecare celulă, se poate trece fie în patru direcții: stânga, dreapta, sus sau jos. NU puteți să vă deplasați pe diagonală sau să vă deplasați în afara limitei (adică nu este permisă mișcarea de tip wrap-around).

Soluție: efectuați o traversare dfs de la fiecare nod mai mare la un nod mai mic și stocați rezultatul. Reutilizați rezultatul atunci când se parcurge din nou același nod. Se ia maximul tuturor direcțiilor și se returnează rezultatul.

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        def check_boundary(matrix, (row, col)):
            if row >= len(matrix) or row < 0:
                return False
            if col >= len(matrix[0]) or col < 0:
                return False
            return True

        def dfs(current, matrix, visited, memory):
            cost = 0
            if not check_boundary(matrix, current):
                return -1
            if current in visited:
                return memory[current]
            for direction in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                new = current[0] + direction[0], current[1] + direction[1]
                visited.add(current)
                if check_boundary(matrix, new) and matrix[current[0]][current[1]] > matrix[new[0]][new[1]]:
                    cost = max(cost, 1 + dfs(new, matrix, visited, memory))
            memory[(current)] = cost
            return cost

        if not matrix:
            return 0
        maximum = 0
        visited, memory = set(), {}
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                maximum = max(maximum, dfs((i, j), matrix, visited, memory))
        return maximum + 1

Comentarii

  • codul dvs. este stricat def check_boundary(matrix, (row, col)): nu este valid.-  > Por Oscar Smith.
1 răspunsuri
Oscar Smith

În general, este un cod destul de curat. Utilizarea de către dvs. a închiderilor funcționează destul de bine pentru a ascunde detaliile de implementare. cel mai evident lucru care trebuie schimbat este să eliminați clasa. În python, lucrurile nu trebuie să fie într-o clasă și nimic nu este îmbunătățit aici prin utilizarea uneia.

Iată alte câteva mici îmbunătățiri Această versiune a check_boundary este mai mică, mai rapidă și, probabil, mai curată.

def check_boundary(matrix, point):
    return 0 < point[0] < len(matrix) and 0 < point[1] < len(matrix[0])

dfs ar trebui să folosească argumente de tip cuvânt cheie, astfel încât să nu fie nevoie să treceți condițiile inițiale.

def dfs(current, matrix, visited=set(), memory={}):

Acest lucru va simplifica sfârșitul metodei principale la

if not matrix:
    return 0
maximum = 0
for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        maximum = max(maximum, dfs((i, j), matrix))
return maximum + 1

Această linie for direction in [[-1, 0], [1, 0], [0, -1], [0, 1]]: ar trebui să aibă Directions și ar trebui probabil să fie o mulțime de mulțimi de mulțimi în loc de o listă de liste, pentru o creștere minoră a performanței.În afară de asta, arată bine.

Comentarii

  • Ce vreți să spuneți prin faptul că nu treceți condițiile inițiale? Poți rescrie acest cod după îmbunătățirile tale?-  > Por noman pouigt.
  • are sens?-  > Por Oscar Smith.
  • Nu se compilează. Vă rugăm să verificați.-  > Por noman pouigt.
  • asta a rezolvat problema?-  > Por Oscar Smith.
  • ideone.com/kGNK2z nu-  > Por noman pouigt.