LeetCode: FloodFill Ржавчина

Question

Привет, я реализую несколько примеров leetcode в Rust. https://leetcode.com/problems/flood-fill/

(похоже, тот же вопрос, что и LeetCode: FloodFill C # )

На входе одна матрица, позиция и ее новый цвет. На выходе получается модифицированная матрица

// 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()сначала для заполнения соседних ячеек. Является VecDequeлучшие структуры данных для этого дия?

Я делаю много приведений между ними, i32и usizeпоскольку я хочу иметь возможность проверить, выходит ли индекс за пределы, вычитая 1. Есть ли лучший способ?

Является ли if (0..image.len()).contains(x1)лучше , чем 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]]) ;
    }
}

Похоже, я тоже мог бы использовать оптимизацию памяти.

Answer 1

Форматирование

Я предполагаю, что отступ является ошибкой копирования и вставки при удалении шаблона, struct Solutionпредписанного LeetCode.

Запустите cargo fmtсвой код в соответствии со стандартными правилами форматирования Rust.

Интерфейс

LeetCode сделал неудачный выбор, использовав Vec<Vec<i32>>для представления двумерного массива, что обычно неэффективно, поскольку хранит элементы в нескольких сегментированных распределениях, несет двойные косвенные затраты и не поддерживает правильную структуру (против зубчатых массивов). Однако мы ничего не можем с этим сделать, поэтому я проигнорирую это до конца поста.

Точно так же i32не идеален для представления цвета - выделенный тип (например, struct Color(i32);) явно лучше. По крайней мере, мы можем как-то улучшить читаемость, используя псевдоним типа и последовательно использовать его для цветов в коде:

type Color = i32;

i32 vs. usize

Как правило, предпочтительнее хранить и вычислять индексы usize, что является естественным типом для этой цели. Один из способов избежать вычитания 1- использовать usize::MAXи wrapping_add.

Преобразование из i32значений, которые получает функция, try_fromпредпочтительнее as, так как последняя автоматически усекает недопустимые значения. unwrapздесь можно использовать, так как это для LeetCode; в реальном коде ошибка должна обрабатываться соответствующим образом.

Является ли if (0..image.len()).contains(x1)лучше , чем if x1>=0 && x1<image.len()для проверки диапазона?

Я бы сказал да. Это более четко указывает на намерение.

Упрощение потока управления

Вместо того, чтобы заключать все в ifвыражение, проверьте image[sr][sc] == new_colorи вернитесь раньше.

while let

Этот:

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

это просто запутанный способ сказать

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

---

Вот как я изменил вашу реализацию:

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
}