概要

「ゼロから作るDeep Learning」をRustで実装する前に，Rustに慣れるため，leetcodeの問題を解きましょう．

本稿では最も基本的なデータ構造である，配列操作を扱います． 問題はコーディングテストで出題されやすい問題がまとめられている教育用サイトであるleetcodeから最も基本的なデータ構造である配列操作を行う問題のうち難易度Easyの問題を4問選びました．

leetcodeの問題は全部で2000問以上あるので，面接で聞かれやすい問題を集めたGrind 75等を解いて対策するのがいいと思います．

ルール

  • 問題を解いているとき，AIには問題にそのものについて質問してはいけません．

    • 例えば、問題文をAIに投げて解答コードを得るなど．

  • AIに質問していいこと

    • Rustの文法事項(データ構造や文法の解説等)
    • 概念に関する質問

  • 解答を理解するフェーズでは，Ask AI First(まずAIに聞け)．の姿勢でお願いします．(何も見ずに，解答コードを書けるようになれば，いったん，その問題を解けたといってもいいと思います．)

  • ここに記載してある解が最も優れているわけではありません．

問題

問題1

これより下には解答があります．まずは，15分考えてみましょう．

解答・解説

クリックで展開 (問題に15分向き合っていない場合は展開しないでください)
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        // 1. ハッシュマップを用意する
        let mut map: std::collections::HashMap<i32, usize> =
            std::collections::HashMap::with_capacity(nums.len()); // capacityを読み込むとプログラムが安定する

        // 2. hashMapの中にあるかどうかを判定する
        for (i, &n) in nums.iter().enumerate() {
            // hashMapの中にあるかどうかを判定して、存在すればそれを返却する
            if let Some(&prev_index) = map.get(&n) {
                return vec![prev_index as i32, i as i32];
            }
            // 現在の値の相方が必要な値として、今のインデックスを保存
            map.insert(target - n, i);
        }
        // ここには到達しないけど返却
        vec![]
    }
}

問題2

これより下には解答があります．まずは，15分考えてみましょう．

解答・解説

クリックで展開 (問題に15分向き合っていない場合は展開しないでください)
impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut buy = 0;
        let mut sell = 1;
        let mut max_profit = 0;
        while sell < prices.len() {
            if prices[buy] < prices[sell] {
                let profit = prices[sell] - prices[buy];
                if profit > max_profit {
                    max_profit = profit;
                }
            } else {
                buy = sell;
            }
            sell += 1;
        }
        max_profit
    }
}

問題3

これより下には解答があります．まずは，15分考えてみましょう．

解答・解説

クリックで展開 (問題に15分向き合っていない場合は展開しないでください)
impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {
        let mut hash_map: std::collections::HashMap<i32, bool> =
            std::collections::HashMap::with_capacity(nums.len());

        for n in nums {
            // 値がハッシュマップに存在するかどうかを確認する
            if hash_map.contains_key(&n) {
                return true;
            }
            hash_map.insert(n, true);
        }
        false
    }
}

問題4

これより下には解答があります．まずは，15分考えてみましょう．

解答・解説

クリックで展開 (問題に15分向き合っていない場合は展開しないでください)
impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }
        // key : 文字列, value : 出現頻度計測数値
        let mut hash_map: std::collections::HashMap<char, i32> =
            std::collections::HashMap::with_capacity(s.len());

        for (cs, ct) in s.chars().zip(t.chars()) {
            // csがあるかどうかを確認してない場合は0を挿入しておく
            // あった場合はその値に+1する
            *hash_map.entry(cs).or_insert(0) += 1;
            // tsがあるかどうかを確認してない場合は0を挿入しておく
            // あった場合はその値に-1する
            *hash_map.entry(ct).or_insert(0) -= 1;
        }

        // 全てがゼロであることを判定する
        /* この判定ロジックは以下のように一行で記述可能
        hash_map.values().all(|&val| val == 0)
         */
        for (_, val) in hash_map {
            // もし0でないものが1つでもあればfalseを返却する
            if val != 0 {
                return false;
            }
        }
        true
    }
}