LeetCode: FloodFill Rust

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โครงสร้างข้อมูลที่ดีที่สุดสำหรับ que นี้หรือไม่?

ฉันทำการแคสต์จากระหว่าง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 SolutionLeetCode ออก

เรียกใช้cargo fmtโค้ดของคุณเพื่อให้เป็นไปตามแนวทางการจัดรูปแบบสนิมมาตรฐาน

อินเตอร์เฟซ

LeetCode เป็นตัวเลือกที่ไม่ดีโดยใช้Vec<Vec<i32>>เพื่อเป็นตัวแทนของอาร์เรย์สองมิติซึ่งโดยทั่วไปจะไม่มีประสิทธิภาพเนื่องจากเก็บองค์ประกอบในการจัดสรรแบบแบ่งส่วนหลาย ๆ ส่วนทำให้เกิดต้นทุนสองทิศทางและไม่สามารถรักษาโครงสร้างที่เหมาะสมได้ (เทียบกับอาร์เรย์ที่ขรุขระ) อย่างไรก็ตามเราไม่สามารถทำอะไรกับสิ่งนี้ได้ดังนั้นฉันจะเพิกเฉยต่อสิ่งที่เหลือ

ในทำนองเดียวกันi32ไม่เหมาะสำหรับการแสดงสี - ประเภทเฉพาะ (เช่นstruct Color(i32);) นั้นเหนือกว่าอย่างชัดเจน อย่างน้อยที่สุดเราสามารถปรับปรุงความสามารถในการอ่านได้โดยใช้นามแฝงประเภทและใช้อย่างสม่ำเสมอสำหรับสีในรหัส:

type Color = i32;

i32 เทียบกับ usize

โดยทั่วไปนิยมจัดเก็บและคำนวณดัชนีusizeซึ่งเป็นประเภทธรรมชาติเพื่อจุดประสงค์นี้ วิธีการหนึ่งที่คุณสามารถหลีกเลี่ยงการลบ1คือการใช้และusize::MAXwrapping_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
}