LeetCode：FloodFill Rust
こんにちは私はRustでいくつかのleetcodeの例を実装しています。 https://leetcode.com/problems/flood-fill/
（LeetCode：FloodFill C＃と同じ質問のようです）
入力は、1つの行列、位置、およびその新しい色です。出力は変更された行列です
// 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]]) ;
}
}
回答
フォーマット
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
}