LeetCode: FloodFill Rust

Question

Hai, saya menerapkan beberapa contoh leetcode di Rust. https://leetcode.com/problems/flood-fill/

(sepertinya pertanyaan yang sama dengan LeetCode: FloodFill C # )

Inputnya adalah satu matriks, satu posisi dan warna barunya. Outputnya adalah matriks yang dimodifikasi

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

Saya gunakan q.pop_front()untuk mengisi sel tetangga terlebih dahulu. Apakah VecDequestruktur data terbaik untuk antrian ini?

Saya melakukan banyak casting dari antara i32dan usizekarena saya ingin dapat memeriksa apakah indeks di luar batas dengan mengurangi 1. Apakah ada cara yang lebih baik?

Apakah if (0..image.len()).contains(x1)lebih baik daripada if x1>=0 && x1<image.len()untuk pemeriksaan jangkauan?

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

Sepertinya saya juga bisa menggunakan beberapa pengoptimalan memori.

Answer 1

Pemformatan

Saya menganggap lekukan sebagai kesalahan salin-tempel saat menghapus struct Solutionpelat boiler yang diamanatkan oleh LeetCode.

Jalankan cargo fmtkode Anda agar sesuai dengan pedoman pemformatan Rust standar.

Antarmuka

LeetCode membuat pilihan yang buruk dengan menggunakan Vec<Vec<i32>>untuk mewakili larik dua dimensi, yang umumnya tidak efisien karena menyimpan elemen dalam alokasi tersegmentasi berganda, menimbulkan biaya indireksi ganda, dan gagal mempertahankan struktur yang tepat (terhadap larik bergerigi). Kami tidak dapat melakukan apa pun terhadap ini, jadi saya akan mengabaikannya untuk sisa posting.

Demikian pula, i32tidak ideal untuk representasi warna - tipe khusus (misalnya, struct Color(i32);) jelas lebih unggul. Setidaknya, entah bagaimana kami dapat meningkatkan keterbacaan dengan menggunakan alias tipe dan menggunakannya secara konsisten untuk warna dalam kode:

type Color = i32;

i32 vs. usize

Umumnya, lebih disukai untuk menyimpan dan menghitung indeks usize, yang merupakan tipe alami untuk tujuan ini. Salah satu cara untuk menghindari pengurangan 1adalah dengan menggunakan usize::MAXdan wrapping_add.

Untuk mengonversi dari i32nilai yang diterima fungsi, try_fromlebih disukai daripada as, karena yang terakhir secara diam-diam memotong nilai yang tidak valid. unwrapdapat digunakan di sini karena ini untuk LeetCode; dalam kode dunia nyata, kesalahan harus ditangani sebagaimana mestinya.

Apakah if (0..image.len()).contains(x1)lebih baik daripada if x1>=0 && x1<image.len()untuk pemeriksaan jangkauan?

Saya akan mengatakan ya. Ini menunjukkan maksud dengan lebih jelas.

Menyederhanakan aliran kontrol

Alih-alih membungkus semuanya dalam sebuah ifekspresi, periksa image[sr][sc] == new_colordan kembali lebih awal.

while let

Ini:

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

hanyalah cara bicara yang berbelit-belit

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

---

Berikut cara saya mengubah penerapan Anda:

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
}