LeetCode: FloodFill Rouille

Question

Salut, j'implémente quelques exemples de leetcode dans Rust. https://leetcode.com/problems/flood-fill/

(semble être la même question que LeetCode: FloodFill C # )

L'entrée est une matrice, une position et sa nouvelle couleur. La sortie est la matrice modifiée

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

J'utilise d'abord q.pop_front()pour remplir les cellules voisines. La VecDequemeilleure structure de données pour ce que?

Je fais beaucoup de casting entre i32et usizecomme je veux être en mesure de vérifier si l'index est hors limites en soustrayant 1. Y a-t-il un meilleur moyen?

Est-ce if (0..image.len()).contains(x1)mieux que if x1>=0 && x1<image.len()pour le contrôle de portée?

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

Il semble que je pourrais aussi utiliser une optimisation de la mémoire.

Answer 1

Mise en page

Je suppose que l'indentation est une erreur de copier-coller lors de la suppression du passe-partout struct Solutionmandaté par LeetCode.

Exécutez cargo fmtvotre code pour vous conformer aux directives de formatage standard de Rust.

Interface

LeetCode a fait un mauvais choix en utilisant Vec<Vec<i32>>pour représenter un tableau bidimensionnel, ce qui est généralement inefficace car il stocke des éléments dans plusieurs allocations segmentées, entraîne des coûts d'indirection doubles et ne parvient pas à maintenir une structure appropriée (contre des tableaux déchiquetés). Nous ne pouvons rien faire contre cela, donc je vais l'ignorer pour le reste du message.

De même, ce i32n'est pas idéal pour la représentation des couleurs - un type dédié (par exemple struct Color(i32);) est clairement supérieur. À tout le moins, nous pouvons en quelque sorte améliorer la lisibilité en utilisant un alias de type et l'utiliser de manière cohérente pour les couleurs du code:

type Color = i32;

i32 contre. usize

En général, il est préférable de stocker et de calculer les index dans usize, qui est le type naturel à cet effet. Une façon d'éviter de soustraire 1est d'utiliser usize::MAXet wrapping_add.

La conversion à partir des i32valeurs que la fonction reçoit try_fromest préférable as, car cette dernière tronque silencieusement les valeurs invalides. unwrappeut être utilisé ici car c'est pour LeetCode; dans le code du monde réel, l'erreur doit être gérée en conséquence.

Est-ce if (0..image.len()).contains(x1)mieux que if x1>=0 && x1<image.len()pour le contrôle de portée?

Je dirais oui. Il indique plus clairement l'intention.

Simplifier le flux de contrôle

Au lieu de tout envelopper dans une ifexpression, vérifiez image[sr][sc] == new_coloret revenez tôt.

while let

Ce:

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

est juste une façon alambiquée de dire

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

---

Voici comment j'ai modifié votre implémentation:

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
}