Closed2023/04/27にクローズ6

泣きながらRustでLeetcodeを解く - Search Insert Position -

Rust

アルゴリズム

LeetCode

コーディング試験

skitzville

これは何

Rustにもっと慣れたい初心者が泣きながらLeetcodeの問題をRustで解いて、その過程を晒します。
初心者🔰なので暖かい目で見守っていただけると幸いです。

skitzville

今日の問題

skitzville

以前TS使って解いた時の回答

Binary Searchを使ってiterationの回数を減らせるようにしたコードです。
具体的には、

Arrayのちょうど真ん中（middle）のポジションの値をターゲットと比較
ターゲットの方が小さければ範囲のおしりをmidldleよりひとつ前に設定
ターゲットの方が大きければ範囲の始まりをmiddleよりひとつ後に設定

というような手順で処理していきます！

const searchInsert = (nums: number[], target: number): number => {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = left + Math.floor((right - left) / 2);
        if (target === nums[middle]) return middle;
        if (target < nums[middle]) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return left;
};

skitzville

Rustで解いてみる

実際に作成した回答がこちら！

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() - 1;
    
        while left <= right {
            let middle = (left + ((right - left) / 2)) as usize;
            
            match nums.get(middle) {
                Some(num) => {
                    if target.eq(num) {
                        return middle as i32;
                    } else if target.lt(num) {
                        right = middle - 1;
                    } else {
                        left = middle + 1;
                    }
                },
                None => {
                    return 0;
                }
            }
        }

        left as i32
    }
}

skitzville

実装中のあれこれ

以下実際に解いてる時に考えていたことや苦戦したポイントなど

実装中に考えてたこと

今回のコードはStringとか絡んでないので、ロジック部分はほぼ同じ仕組みででいけそう
Vectorなのでiterationはしやすそう
- indexでアクセスするとpanicしちゃう可能性あるので、一旦get でアクセスしておいてmatchを使う方向で対応してみる
あと超基礎的で当たり前のところだけどよく忘れるのでおさらい
- + - * / etc…これらのoperatorのoperandsは左右が同じタイプでないと計算ができない点に注意

fn main() {
    let a: usize = 2;
    let b: i32 = 2;
    println!("{}", a + b);
}

rustc /tmp/m9WYcCGqT3/main.rs
error[E0308]: mismatched types
 --> /tmp/m9WYcCGqT3/main.rs:7:24
  |
7 |     println!("{}", a + b);
  |                        ^ expected `i64`, found `i32`

error[E0277]: cannot add `i32` to `i64`
 --> /tmp/m9WYcCGqT3/main.rs:7:22
  |
7 |     println!("{}", a + b);
  |                      ^ no implementation for `i64 + i32`
  |

途中うまくいかなくて泣きそうになったところ

nums.get(middle)
- Vectorのget のパラメータはi32やu32ではなくusize型なのでleft + ((right - left) / 2) ではi32のためそのまま使用ができずusizeにasキャストしている
== < > などのcomparison operatorsをifの条件部分で使用しようとしたところ以下のようなエラーが

    if target == num {
    		return middle as i32;
    } else if target < num {
    		right = middle - 1;
    } else {
    		left = middle + 1;
    }

    rustc /tmp/m9WYcCGqT3/main.rs
    error[E0308]: mismatched types
      --> /tmp/m9WYcCGqT3/main.rs:25:34
       |
    25 |                     if target == num {
       |                                  ^^^ expected `i32`, found `&i32`
       |
    help: consider dereferencing the borrow
       |
    25 |                     if target == *num {
       |

エラーの内容的にはnum がのデータ型&i32のためそもそもi32と比較できないことが問題っぽそう。

調べて以下確認したところ、Vectorのgetはindexで指定された要素のreferenceがOptionでかえってくる仕様になっている。

なので最初は純粋にdereferenceしてあげる形で対応。

  if target == *num {
  		return middle as i32;
  } else if target < *num {
  		right = middle - 1;
  } else {
  		left = middle + 1;
  }

ただそのあと以下眺めていてeqやlt も使えるのでは？と試してみたところOKそうだった

    if target.eq(num) {
    		return middle as i32;
    } else if target.lt(num) {
    		right = middle - 1;
    } else {
    		left = middle + 1;
    }

その他

== < > などのcomparison operatorsをifの条件部分で使用しようとしたところ以下のようなエラーが

ここ最初は？？ってなったけど、よく考えたら値を比較したかったらデータタイプが違う時点で純粋に比較することはできないし、そもそも== < > も上で触れた+ - * / 同様左右のoperandsのデータタイプが違えば計算ができないのと一緒で比較はできない

skitzville

今日はなんとか泣かずに乗り切れました。

このスクラップは2023/04/27にクローズされました