LeetCode: FloodFill Rust

Question

Cześć, implementuję kilka przykładów kodu leetcode w Rust. https://leetcode.com/problems/flood-fill/

(wygląda na to samo pytanie co LeetCode: FloodFill C # )

Dane wejściowe to jedna matryca, pozycja i jej nowy kolor. Wynikiem jest zmodyfikowana macierz

// 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.

Używam q.pop_front()wypełnić sąsiednie komórki w pierwszej kolejności. Czy VecDequenajlepsza struktura danych dla tej kolejki?

Rzucam dużo między i32i, usizeponieważ chcę być w stanie sprawdzić, czy indeks jest poza granicami, odejmując 1. Czy jest lepszy sposób?

Czy jest if (0..image.len()).contains(x1)lepsze niż if x1>=0 && x1<image.len()do sprawdzenia zasięgu?

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]]) ;
    }
}

Wygląda na to, że przydałaby mi się też optymalizacja pamięci.

Answer 1

Formatowanie

Zakładam, że wcięcie jest błędem kopiuj-wklej podczas usuwania standardowego struct Solutionarkusza wymaganego przez LeetCode.

Uruchom cargo fmtswój kod, aby zachować zgodność ze standardowymi wytycznymi dotyczącymi formatowania Rusta.

Berło

LeetCode dokonał złego wyboru, używając Vec<Vec<i32>>do reprezentowania dwuwymiarowej tablicy, która jest generalnie nieefektywna, ponieważ przechowuje elementy w alokacjach wielu segmentów, generuje podwójne koszty pośrednie i nie utrzymuje właściwej struktury (przeciwko tablicom postrzępionym). Nie możemy jednak nic z tym zrobić, więc zignoruję to do końca wpisu.

Podobnie i32nie jest idealny do odwzorowania kolorów - typ dedykowany (np. struct Color(i32);) Jest wyraźnie lepszy. Przynajmniej możemy w jakiś sposób poprawić czytelność, używając aliasu typu i konsekwentnie używając go dla kolorów w kodzie:

type Color = i32;

i32 vs. usize

Generalnie preferowane jest przechowywanie i obliczanie indeksów w usize, co jest typem naturalnym do tego celu. Jednym ze sposobów uniknięcia odejmowania 1jest użycie usize::MAXi wrapping_add.

Konwersja z i32wartości odbieranych przez funkcję try_fromjest preferowana as, ponieważ ta druga po cichu obcina nieprawidłowe wartości. unwrapmoże być tutaj użyty, ponieważ jest przeznaczony dla LeetCode; w kodzie świata rzeczywistego błąd powinien być odpowiednio obsłużony.

Czy jest if (0..image.len()).contains(x1)lepsze niż if x1>=0 && x1<image.len()do sprawdzenia zasięgu?

Powiedziałbym tak. Wyraźniej wskazuje na zamiar.

Uproszczenie przepływu sterowania

Zamiast zawijać wszystko w ifwyrażenie, sprawdź image[sr][sc] == new_colori wróć wcześniej.

while let

To:

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

to tylko zawiły sposób powiedzenia

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

---

Oto jak zmodyfikowałem twoją implementację:

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
}