LeetCode: FloodFill Rust

Question

Xin chào, tôi đang triển khai một vài ví dụ về leetcode trong Rust. https://leetcode.com/problems/flood-fill/

(có vẻ giống câu hỏi với LeetCode: FloodFill C # )

Đầu vào là một ma trận, một vị trí và màu mới của nó. Đầu ra là ma trận đã sửa đổi

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

Tôi sử dụng q.pop_front()để điền vào các ô lân cận trước. Là VecDequecấu trúc dữ liệu tốt nhất cho hàng đợi này?

Tôi thực hiện rất nhiều lần truyền từ giữa i32và usizekhi tôi muốn có thể kiểm tra xem chỉ mục có nằm ngoài giới hạn hay không bằng cách trừ đi 1. Có cách nào tốt hơn không?

Là if (0..image.len()).contains(x1)tốt hơn so if x1>=0 && x1<image.len()với kiểm tra phạm vi?

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

Có vẻ như tôi cũng có thể sử dụng một số tối ưu hóa bộ nhớ.

Answer 1

Định dạng

Tôi cho rằng thụt đầu dòng là lỗi sao chép-dán khi xóa bảng soạn sẵn struct Solutiondo LeetCode ủy quyền.

Chạy cargo fmttrên mã của bạn để tuân theo các nguyên tắc định dạng Rust tiêu chuẩn.

Giao diện

LeetCode đã đưa ra một lựa chọn tồi khi sử dụng Vec<Vec<i32>>để biểu diễn một mảng hai chiều, nhìn chung không hiệu quả vì nó lưu trữ các phần tử trong nhiều phân bổ được phân đoạn, phải chịu chi phí chuyển hướng gấp đôi và không duy trì cấu trúc thích hợp (chống lại các mảng răng cưa). Tuy nhiên, chúng tôi không thể làm bất cứ điều gì chống lại điều này, vì vậy tôi sẽ bỏ qua nó trong phần còn lại của bài đăng.

Tương tự, i32không phải là lý tưởng để biểu diễn màu sắc - một loại chuyên dụng (ví dụ, struct Color(i32);) rõ ràng là ưu việt hơn. Ít nhất, bằng cách nào đó, chúng tôi có thể cải thiện khả năng đọc bằng cách sử dụng bí danh loại và sử dụng nó nhất quán cho các màu trong mã:

type Color = i32;

i32 vs. usize

Nói chung, ưu tiên lưu trữ và tính toán các chỉ mục usize, đây là kiểu tự nhiên cho mục đích này. Một cách bạn có thể tránh trừ 1là sử dụng usize::MAXvà wrapping_add.

Để chuyển đổi từ các i32giá trị mà hàm nhận được, try_fromđược ưu tiên hơn as, vì hàm này sẽ âm thầm cắt bớt các giá trị không hợp lệ. unwrapcó thể được sử dụng ở đây vì nó dành cho LeetCode; trong mã thế giới thực, lỗi cần được xử lý tương ứng.

Là if (0..image.len()).contains(x1)tốt hơn so if x1>=0 && x1<image.len()với kiểm tra phạm vi?

Tôi sẽ nói có. Nó chỉ ra ý định rõ ràng hơn.

Đơn giản hóa quy trình kiểm soát

Thay vì gói mọi thứ trong một ifbiểu thức, hãy kiểm tra image[sr][sc] == new_colorvà quay lại sớm.

while let

Điều này:

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

chỉ là một cách nói phức tạp

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

---

Đây là cách tôi sửa đổi cách triển khai của bạn:

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
}