LeetCode: FloodFill Rust

Question

Hallo, ich implementiere ein paar Leetcode-Beispiele in Rust. https://leetcode.com/problems/flood-fill/

( scheint dieselbe Frage zu sein wie LeetCode: FloodFill C # )

Die Eingabe ist eine Matrix, eine Position und ihre neue Farbe. Die Ausgabe ist die modifizierte Matrix

// Input: 
// image = [[1,1,1],[1,1,0],[1,0,1]]
// sr = 1, sc = 1, newColor = 2
// Output: [[2,2,2],[2,2,0],[2,0,1]]
// Explanation: 
// From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
// by a path of the same color as the starting pixel are colored with the new color.
// Note the bottom corner is not colored 2, because it is not 4-directionally connected
// to the starting pixel.

Ich benutze q.pop_front(), um zuerst die benachbarten Zellen zu füllen. Ist VecDequedie beste Datenstruktur für diese Warteschlange?

Ich mache viel Casting von dazwischen i32und usizemöchte überprüfen können, ob der Index außerhalb der Grenzen liegt, indem ich 1 subtrahiere. Gibt es einen besseren Weg?

Ist if (0..image.len()).contains(x1)besser als if x1>=0 && x1<image.len()für die Reichweitenprüfung?

use std::collections::VecDeque;

  fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, new_color: i32) -> Vec<Vec<i32>> {

      let mut q:VecDeque<(i32,i32)> = VecDeque::new();
      q.push_back((sr,sc));

      let c0 = image[sr as usize][sc as usize];
      if c0 != new_color {
          while ! q.is_empty() {
              if let Some((sr,sc))=q.pop_front() {  
                  if image[sr as usize][sc as usize] == c0 {
                      image[sr as usize][sc as usize] = new_color;
                      for delta in vec![(-1,0),(1,0),(0,-1),(0,1)] {
                          let new_r:i32 = sr+delta.0;
                          let new_c:i32 = sc+delta.1;
                          if (0..image.len() as i32).contains( &new_r ) && (0..image[0].len() as i32).contains( &new_c){
                              q.push_back((new_r,new_c));
                          }
                      }
                  }
              }
          }
      }
      image
  }

#[cfg(test)]
mod test{
#[test]
    fn test_lc_default(){
        assert_eq!(super::flood_fill(vec![vec![1 as i32 ,1,1],vec![1,1 as i32,0],vec![1,0,1]],1, 1, 2),vec![vec![2,2,2],vec![2,2,0],vec![2,0,1]]) ;
    }
}

Es sieht so aus, als könnte ich auch eine Speicheroptimierung gebrauchen.

Answer 1

Formatierung

Ich struct Solutiongehe davon aus, dass der Einzug ein Fehler beim Kopieren und Einfügen ist, wenn die von LeetCode vorgeschriebene Boilerplate entfernt wird.

Führen Sie cargo fmtIhren Code aus, um den Standardrichtlinien für die Rust-Formatierung zu entsprechen.

Schnittstelle

LeetCode traf eine schlechte Wahl, indem Vec<Vec<i32>>es ein zweidimensionales Array darstellte, das im Allgemeinen ineffizient ist, da es Elemente in mehreren segmentierten Zuordnungen speichert, doppelte Indirektionskosten verursacht und keine ordnungsgemäße Struktur beibehält (gegenüber gezackten Arrays). Wir können jedoch nichts dagegen tun, deshalb werde ich es für den Rest des Beitrags ignorieren.

Ebenso i32ist es nicht ideal für die Farbdarstellung - ein dedizierter Typ (z. B. struct Color(i32);) ist eindeutig überlegen. Zumindest können wir die Lesbarkeit irgendwie verbessern, indem wir einen Typalias verwenden und ihn konsistent für Farben im Code verwenden:

type Color = i32;

i32 vs. usize

Im Allgemeinen wird es bevorzugt, Indizes in zu speichern und zu berechnen usize, was der natürliche Typ für diesen Zweck ist. Eine Möglichkeit, das Subtrahieren zu vermeiden, 1ist die Verwendung von usize::MAXund wrapping_add.

Das Konvertieren von den i32Werten, die die Funktion empfängt, try_fromwird asder Wertung vorgezogen , da letztere ungültige Werte stillschweigend abschneidet. unwrapkann hier verwendet werden, da es für LeetCode ist; Im realen Code sollte der Fehler entsprechend behandelt werden.

Ist if (0..image.len()).contains(x1)besser als if x1>=0 && x1<image.len()für die Reichweitenprüfung?

Ich würde ja sagen. Es zeigt die Absicht deutlicher an.

Kontrollfluss vereinfachen

Anstatt alles in einen ifAusdruck zu packen, suchen Sie nach image[sr][sc] == new_colorund kehren Sie früh zurück.

while let

Diese:

while !cells.is_empty() {
    if let Some((sr, sc)) = cells.pop_front() {

ist nur eine verschlungene Art zu sagen

while let Some((sr, sc)) = cells.pop_front() {

---

So habe ich Ihre Implementierung geändert:

type Color = i32;

pub fn flood_fill(
    mut image: Vec<Vec<Color>>,
    sr: i32,
    sc: i32,
    new_color: Color,
) -> Vec<Vec<Color>> {
    use std::collections::VecDeque;
    use std::convert::TryFrom;

    let sr = usize::try_from(sr).unwrap();
    let sc = usize::try_from(sc).unwrap();

    let initial_color = image[sr][sc];

    if initial_color == new_color {
        return image;
    }

    let height = image.len();
    let width = image[0].len();

    let mut cells: VecDeque<(usize, usize)> = VecDeque::new();
    cells.push_back((sr, sc));

    while let Some((sr, sc)) = cells.pop_front() {
        let cell = &mut image[sr][sc];

        if *cell != initial_color {
            continue;
        }

        *cell = new_color;

        const OFFSETS: &[(usize, usize)] = &[(0, usize::MAX), (usize::MAX, 0), (0, 1), (1, 0)];

        for (delta_r, delta_c) in OFFSETS.iter().copied() {
            let new_r = sr.wrapping_add(delta_r);
            let new_c = sc.wrapping_add(delta_c);

            if new_r < height && new_c < width {
                cells.push_back((new_r, new_c));
            }
        }
    }

    image
}