LeetCode: FloodFill Rust

Question

Merhaba, Rust'ta birkaç leetcode örneği uyguluyorum. https://leetcode.com/problems/flood-fill/

( LeetCode: FloodFill C # ile aynı soru gibi görünüyor )

Girdi bir matris, bir konum ve yeni rengidir. Çıktı, değiştirilmiş matristir

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

q.pop_front()Önce komşu hücreleri doldurmak için kullanırım . Mı VecDequebu que en iyi veri yapısı?

Aradan çok fazla çevrim yapıyorum i32ve usize1'i çıkararak indeksin sınırlar dışında olup olmadığını kontrol edebilmek istediğim için daha iyi bir yol var mı?

Menzil kontrolünden if (0..image.len()).contains(x1)daha mı iyi if x1>=0 && x1<image.len()?

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

Görünüşe göre biraz hafıza optimizasyonu kullanabilirim.

Answer 1

Biçimlendirme

struct SolutionLeetCode tarafından zorunlu kılınan kazan plakasını kaldırırken girintinin bir kopyala-yapıştır hatası olduğunu varsayıyorum.

cargo fmtStandart Rust biçimlendirme kurallarına uymak için kodunuzu çalıştırın .

Arayüz

LeetCode, Vec<Vec<i32>>iki boyutlu bir diziyi temsil etmek için kullanarak zayıf bir seçim yaptı ; bu, öğeleri birden çok bölümlü ayırmada depoladığından, çift yönlendirme maliyetlerine neden olduğundan ve uygun yapıyı (pürüzlü dizilere karşı) koruyamadığından genellikle verimsizdir. Yine de buna karşı hiçbir şey yapamayız, bu yüzden yazının geri kalanı için bunu görmezden geleceğim.

Benzer şekilde, i32renk gösterimi için ideal değildir - özel bir tür (örneğin struct Color(i32);) açıkça üstündür. En azından, bir tür takma adı kullanarak okunabilirliği bir şekilde artırabilir ve koddaki renkler için tutarlı bir şekilde kullanabiliriz:

type Color = i32;

i32 vs. usize

Genel olarak, usizebu amaç için doğal tip olan indekslerin saklanması ve hesaplanması tercih edilir . Çıkarmayı önlemenin bir yolu ve 1kullanmaktır .usize::MAXwrapping_add

i32Fonksiyonun aldığı değerlerden dönüştürmek yerine, işlev geçersiz değerleri sessizce kısalttığı için try_fromtercih edilir as. unwrapLeetCode için olduğu için burada kullanılabilir; gerçek dünya kodunda, hata buna göre ele alınmalıdır.

Menzil kontrolünden if (0..image.len()).contains(x1)daha mı iyi if x1>=0 && x1<image.len()?

Evet derdim. Niyeti daha net gösterir.

Kontrol akışını basitleştirme

Her şeyi bir ififadeye sarmak yerine , kontrol edin image[sr][sc] == new_colorve erken dönün.

while let

Bu:

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

sadece karmaşık bir söylem

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

---

Uygulamanızı şu şekilde değiştirdim:

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
}