LeetCode : FloodFill Rust
안녕하세요 저는 Rust에서 몇 가지 leetcode 예제를 구현하고 있습니다. 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]]) ;
}
}
답변
서식
struct SolutionLeetCode에서 요구 하는 상용구를 제거 할 때 들여 쓰기가 복사-붙여 넣기 오류라고 가정합니다 .
cargo fmt표준 Rust 형식화 지침을 준수하도록 코드에서 실행하십시오 .
상호 작용
LeetCode는 Vec<Vec<i32>>2 차원 배열을 나타내는 데 사용하여 잘못된 선택을했습니다. 일반적으로 여러 세그먼트 할당에 요소를 저장하고 두 배의 간접 비용이 발생하고 적절한 구조를 유지하지 못하기 때문에 비효율적입니다 (들쭉날쭉 한 배열에 대해). 우리는 이것에 대해 아무것도 할 수 없으므로 나머지 게시물에서는 무시하겠습니다.
마찬가지로 i32색상 표현에 적합하지 않습니다. 전용 유형 (예 :) struct Color(i32);이 분명히 우수합니다. 최소한 타입 별칭을 사용하여 가독성을 높이고 코드의 색상에 일관되게 사용할 수 있습니다.
type Color = i32;
i32 대 usize
일반적으로 인덱스를 저장하고 계산하는 것이 좋습니다 usize. 이는이 목적을위한 자연 유형입니다. 당신이 감산을 피할 수있는 한 가지 방법은 1사용하는 것입니다 usize::MAX및 wrapping_add.
i32함수가 수신 하는 값 에서 변환하려면 후자가 유효하지 않은 값을 자동으로 자르기 때문에를 try_from선호 as합니다. unwrapLeetCode 용이므로 여기에서 사용할 수 있습니다. 실제 코드에서 오류는 그에 따라 처리되어야합니다.
인가
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
}