Rustのリスト操作練習問題集#4(HashMap,HashSet,Deque,BinaryHeap編)

Rustのコレクション操作練習問題集

RustのHashMap、HashSet、VecDeque、BinaryHeapを使った練習問題集です。

基本的なコレクション操作から応用まで テスト用のコードも載せてあります。そのままコピペで使えるようにしてあります。

基本的なuse文とコレクションの説明

必要なuse文

use std::collections::{HashMap, HashSet, VecDeque, BinaryHeap};
use std::cmp::Reverse; // BinaryHeapで最小値を取得するために使用

各コレクションの特徴

HashMap<K, V>

• キーと値のペアを格納するハッシュマップ
• キーによる高速な検索・挿入・削除が可能
• 主なメソッド: insert(), get(), contains_key(), remove(), keys(), values()

HashSet<T>

• 重複のない要素の集合
• 要素の存在確認が高速
• 主なメソッド: insert(), contains(), remove(), is_empty(), len()

VecDeque<T>

• 両端での効率的な挿入・削除が可能な双方向キュー
• 先頭と末尾の両方から要素を追加・削除できる
• 主なメソッド: push_front(), push_back(), pop_front(), pop_back(), front(), back()

BinaryHeap<T>

• 最大値を効率的に取得できるヒープ
• デフォルトは最大ヒープ（最大値が先頭）
• 最小ヒープを使いたい場合は BinaryHeap<Reverse<T>> を使用
• 主なメソッド: push(), pop(), peek(), is_empty(), len()

HashMap問題集

問題1：文字の出現回数をカウント

問題

• 文字列が与えられる。各文字の出現回数をHashMapで管理して返す
• 入力：&str
• 出力：HashMap<char, usize>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(s: &str) -> HashMap<char, usize> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution("hello");
    assert_eq!(result1.get(&'l'), Some(&2));
    assert_eq!(result1.get(&'h'), Some(&1));
    
    let result2 = solution("aabbcc");
    assert_eq!(result2.get(&'a'), Some(&2));
    assert_eq!(result2.get(&'b'), Some(&2));
    
    let result3 = solution("");
    assert!(result3.is_empty());
}

解答と解説

use std::collections::HashMap;

fn solution(s: &str) -> HashMap<char, usize> {
    let mut counts = HashMap::new();
    for ch in s.chars() {
        *counts.entry(ch).or_insert(0) += 1;
    }
    counts
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution("hello");
    assert_eq!(result1.get(&'l'), Some(&2));
    assert_eq!(result1.get(&'h'), Some(&1));
    
    let result2 = solution("aabbcc");
    assert_eq!(result2.get(&'a'), Some(&2));
    assert_eq!(result2.get(&'b'), Some(&2));
    
    let result3 = solution("");
    assert!(result3.is_empty());
}

• 主要メソッド/イディオム:
  • entry(), or_insert(), get()
• 注意点:
  • entry() でキーの存在を確認し、or_insert() でデフォルト値を設定
  • * で参照を外して値を更新

問題2：配列の要素の頻度を求める

問題

• 整数配列が与えられる。最も頻繁に出現する値を返す
• 複数ある場合は最初に見つかったものを返す
• 入力：&[i32]
• 出力：Option<i32>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(nums: &[i32]) -> Option<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 2, 3, 2]), Some(2));
    assert_eq!(solution(&[1, 1, 2, 2]), Some(1));
    assert_eq!(solution(&[5]), Some(5));
    assert_eq!(solution(&[]), None);
}

解答と解説

use std::collections::HashMap;

fn solution(nums: &[i32]) -> Option<i32> {
    if nums.is_empty() {
        return None;
    }
    
    let mut counts = HashMap::new();
    for &num in nums {
        *counts.entry(num).or_insert(0) += 1;
    }
    
    let mut max_count = 0;
    let mut result = nums[0];
    
    for (&num, &count) in &counts {
        if count > max_count {
            max_count = count;
            result = num;
        }
    }
    
    Some(result)
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 2, 3, 2]), Some(2));
    assert_eq!(solution(&[1, 1, 2, 2]), Some(1));
    assert_eq!(solution(&[5]), Some(5));
    assert_eq!(solution(&[]), None);
}

• 主要メソッド/イディオム:
  • entry(), or_insert(), iter()
• 注意点:
  • 空配列の場合は None を返す
  • 同じ頻度の場合は最初に見つかったものを返す

問題3：2つの配列の共通要素を求める

問題

• 2つの整数配列が与えられる。両方に含まれる要素をVecで返す
• 重複は除去する
• 入力：&[i32], &[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[1, 2, 2, 1], &[2, 2]);
    result1.sort();
    assert_eq!(result1, vec![2]);
    
    let mut result2 = solution(&[4, 9, 5], &[9, 4, 9, 8, 4]);
    result2.sort();
    assert_eq!(result2, vec![4, 9]);
    
    let result3 = solution(&[1, 2, 3], &[4, 5, 6]);
    assert!(result3.is_empty());
}

解答と解説

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
    let set1: HashSet<i32> = nums1.iter().cloned().collect();
    let set2: HashSet<i32> = nums2.iter().cloned().collect();
    
    set1.intersection(&set2).cloned().collect()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[1, 2, 2, 1], &[2, 2]);
    result1.sort();
    assert_eq!(result1, vec![2]);
    
    let mut result2 = solution(&[4, 9, 5], &[9, 4, 9, 8, 4]);
    result2.sort();
    assert_eq!(result2, vec![4, 9]);
    
    let result3 = solution(&[1, 2, 3], &[4, 5, 6]);
    assert!(result3.is_empty());
}

• 主要メソッド/イディオム:
  • collect(), intersection(), cloned()
• 注意点:
  • HashSet を使って重複を除去
  • intersection() で共通要素を取得

問題4：配列の要素をグループ化

問題

• 文字列配列が与えられる。同じ長さの文字列をグループ化してHashMapで返す
• 入力：&[String]
• 出力：HashMap<usize, Vec<String>>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(strings: &[String]) -> HashMap<usize, Vec<String>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["hello".to_string(), "world".to_string(), "hi".to_string(), "rust".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.get(&5), Some(&vec!["hello".to_string(), "world".to_string()]));
    assert_eq!(result1.get(&2), Some(&vec!["hi".to_string()]));
    
    let input2 = vec![];
    let result2 = solution(&input2);
    assert!(result2.is_empty());
}

解答と解説

use std::collections::HashMap;

fn solution(strings: &[String]) -> HashMap<usize, Vec<String>> {
    let mut groups: HashMap<usize, Vec<String>> = HashMap::new();
    
    for s in strings {
        groups.entry(s.len()).or_insert_with(Vec::new).push(s.clone());
    }
    
    groups
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["hello".to_string(), "world".to_string(), "hi".to_string(), "rust".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.get(&5), Some(&vec!["hello".to_string(), "world".to_string()]));
    assert_eq!(result1.get(&2), Some(&vec!["hi".to_string()]));
    
    let input2 = vec![];
    let result2 = solution(&input2);
    assert!(result2.is_empty());
}

• 主要メソッド/イディオム:
  • entry(), or_insert_with(), push()
• 注意点:
  • or_insert_with() で新しいVecを作成
  • clone() で文字列をコピー

問題5：2つの配列の和集合と差集合

問題

• 2つの整数配列が与えられる。和集合と差集合（A-B）を返す
• 入力：&[i32], &[i32]
• 出力：(Vec<i32>, Vec<i32>)
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> (Vec<i32>, Vec<i32>) {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let (union, diff) = solution(&[1, 2, 3], &[2, 3, 4]);
    let mut union_sorted = union;
    union_sorted.sort();
    assert_eq!(union_sorted, vec![1, 2, 3, 4]);
    
    let mut diff_sorted = diff;
    diff_sorted.sort();
    assert_eq!(diff_sorted, vec![1]);
    
    let (union2, diff2) = solution(&[1, 2], &[3, 4]);
    let mut union2_sorted = union2;
    union2_sorted.sort();
    assert_eq!(union2_sorted, vec![1, 2, 3, 4]);
    assert!(diff2.is_empty());
}

解答と解説

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> (Vec<i32>, Vec<i32>) {
    let set1: HashSet<i32> = nums1.iter().cloned().collect();
    let set2: HashSet<i32> = nums2.iter().cloned().collect();
    
    let union: Vec<i32> = set1.union(&set2).cloned().collect();
    let diff: Vec<i32> = set1.difference(&set2).cloned().collect();
    
    (union, diff)
}

fn main() {
    //簡易テスト（2件）
    let (union, diff) = solution(&[1, 2, 3], &[2, 3, 4]);
    let mut union_sorted = union;
    union_sorted.sort();
    assert_eq!(union_sorted, vec![1, 2, 3, 4]);
    
    let mut diff_sorted = diff;
    diff_sorted.sort();
    assert_eq!(diff_sorted, vec![1]);
    
    let (union2, diff2) = solution(&[1, 2], &[3, 4]);
    let mut union2_sorted = union2;
    union2_sorted.sort();
    assert_eq!(union2_sorted, vec![1, 2, 3, 4]);
    assert!(diff2.is_empty());
}

HashMap中級問題集

問題21：文字列のアナグラムグループ化

問題

• 文字列配列が与えられる。アナグラム（文字の並び替え）でグループ化してHashMapで返す
• キーはソートされた文字列、値は元の文字列の配列
• 入力：&[String]
• 出力：HashMap<String, Vec<String>>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(strs: &[String]) -> HashMap<String, Vec<String>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.get("aet").unwrap().len(), 3); // eat, tea, ate
    assert_eq!(result1.get("ant").unwrap().len(), 2); // tan, nat
    
    let input2 = vec!["".to_string()];
    let result2 = solution(&input2);
    assert_eq!(result2.get("").unwrap().len(), 1);
}

解答と解説

use std::collections::HashMap;

fn solution(strs: &[String]) -> HashMap<String, Vec<String>> {
    let mut groups: HashMap<String, Vec<String>> = HashMap::new();
    
    for s in strs {
        let mut chars: Vec<char> = s.chars().collect();
        chars.sort();
        let key: String = chars.into_iter().collect();
        
        groups.entry(key).or_insert_with(Vec::new).push(s.clone());
    }
    
    groups
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.get("aet").unwrap().len(), 3); // eat, tea, ate
    assert_eq!(result1.get("ant").unwrap().len(), 2); // tan, nat
    
    let input2 = vec!["".to_string()];
    let result2 = solution(&input2);
    assert_eq!(result2.get("").unwrap().len(), 1);
}

• 主要メソッド/イディオム:
  • chars(), collect(), sort(), into_iter(), entry(), or_insert_with()
• 注意点:
  • 文字列を文字配列に変換→ソート→文字列に戻してキーとして使用
  • or_insert_with() で新しいVecを作成

問題22：配列の要素の累積和とインデックス

問題

• 整数配列が与えられる。各要素の累積和を計算し、値とインデックスのペアをHashMapで管理する
• 同じ累積和を持つインデックスをグループ化する
• 入力：&[i32]
• 出力：HashMap<i32, Vec<usize>>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(nums: &[i32]) -> HashMap<i32, Vec<usize>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, 2, 3, 4]);
    assert_eq!(result1.get(&6).unwrap(), &vec![2]); // インデックス2で累積和6
    assert_eq!(result1.get(&10).unwrap(), &vec![3]); // インデックス3で累積和10
    
    let result2 = solution(&[1, -1, 1, -1]);
    assert_eq!(result2.get(&0).unwrap().len(), 2); // インデックス1と3で累積和0
}

解答と解説

use std::collections::HashMap;

fn solution(nums: &[i32]) -> HashMap<i32, Vec<usize>> {
    let mut groups: HashMap<i32, Vec<usize>> = HashMap::new();
    let mut cumulative_sum = 0;
    
    for (index, &num) in nums.iter().enumerate() {
        cumulative_sum += num;
        groups.entry(cumulative_sum).or_insert_with(Vec::new).push(index);
    }
    
    groups
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, 2, 3, 4]);
    assert_eq!(result1.get(&6).unwrap(), &vec![2]); // インデックス2で累積和6
    assert_eq!(result1.get(&10).unwrap(), &vec![3]); // インデックス3で累積和10
    
    let result2 = solution(&[1, -1, 1, -1]);
    assert_eq!(result2.get(&0).unwrap().len(), 2); // インデックス1と3で累積和0
}

• 主要メソッド/イディオム:
  • iter(), enumerate(), entry(), or_insert_with()
• 注意点:
  • enumerate() でインデックスと値を同時に取得
  • 累積和を計算しながらHashMapに格納

問題23：文字列の文字頻度による分類

問題

• 文字列配列が与えられる。各文字列の文字頻度パターンでグループ化する
• 頻度パターンは文字の出現回数をソートした配列で表現
• 入力：&[String]
• 出力：HashMap<Vec<usize>, Vec<String>>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(strs: &[String]) -> HashMap<Vec<usize>, Vec<String>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["aab".to_string(), "bba".to_string(), "aba".to_string()];
    let result1 = solution(&input1);
    // aab: [2,1], bba: [2,1], aba: [2,1] は同じパターン
    assert_eq!(result1.values().next().unwrap().len(), 3);
    
    let input2 = vec!["abc".to_string(), "def".to_string()];
    let result2 = solution(&input2);
    // abc: [1,1,1], def: [1,1,1] は同じパターン
    assert_eq!(result2.values().next().unwrap().len(), 2);
}

解答と解説

use std::collections::HashMap;

fn solution(strs: &[String]) -> HashMap<Vec<usize>, Vec<String>> {
    let mut groups: HashMap<Vec<usize>, Vec<String>> = HashMap::new();
    
    for s in strs {
        let mut counts: HashMap<char, usize> = HashMap::new();
        
        // 文字の出現回数をカウント
        for ch in s.chars() {
            *counts.entry(ch).or_insert(0) += 1;
        }
        
        // 出現回数をソートしてパターンを作成
        let mut pattern: Vec<usize> = counts.values().cloned().collect();
        pattern.sort();
        
        groups.entry(pattern).or_insert_with(Vec::new).push(s.clone());
    }
    
    groups
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["aab".to_string(), "bba".to_string(), "aba".to_string()];
    let result1 = solution(&input1);
    // aab: [2,1], bba: [2,1], aba: [2,1] は同じパターン
    assert_eq!(result1.values().next().unwrap().len(), 3);
    
    let input2 = vec!["abc".to_string(), "def".to_string()];
    let result2 = solution(&input2);
    // abc: [1,1,1], def: [1,1,1] は同じパターン
    assert_eq!(result2.values().next().unwrap().len(), 2);
}

• 主要メソッド/イディオム:
  • chars(), entry(), or_insert(), values(), cloned(), collect(), sort()
• 注意点:
  • 文字頻度をカウント→ソート→パターンとして使用
  • 複数のHashMap操作を組み合わせ

問題24：配列の部分和とその出現位置

問題

• 整数配列と目標値が与えられる。部分和が目標値になる連続部分配列の開始・終了インデックスを返す
• 複数ある場合は最初に見つかったものを返す
• 入力：&[i32], i32
• 出力：Option<(usize, usize)>
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[2, 7, 11, 15], 9), Some((0, 1))); // 2+7=9
    assert_eq!(solution(&[1, 2, 3, 4, 5], 9), Some((1, 3))); // 2+3+4=9
    assert_eq!(solution(&[1, 2, 3], 7), None); // 見つからない
}

解答と解説

use std::collections::HashMap;

fn solution(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut prefix_sums: HashMap<i32, usize> = HashMap::new();
    prefix_sums.insert(0, 0); // 空の部分配列の和は0
    
    let mut current_sum = 0;
    
    for (i, &num) in nums.iter().enumerate() {
        current_sum += num;
        
        // 目標値との差を計算
        let complement = current_sum - target;
        
        if let Some(&start_idx) = prefix_sums.get(&complement) {
            return Some((start_idx, i));
        }
        
        // 現在の累積和を記録
        prefix_sums.insert(current_sum, i + 1);
    }
    
    None
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[2, 7, 11, 15], 9), Some((0, 1))); // 2+7=9
    assert_eq!(solution(&[1, 2, 3, 4, 5], 9), Some((1, 3))); // 2+3+4=9
    assert_eq!(solution(&[1, 2, 3], 7), None); // 見つからない
}

• 主要メソッド/イディオム:
  • iter(), enumerate(), get(), insert()
• 注意点:
  • 累積和の差を利用して部分和を効率的に検索
  • ハッシュマップで累積和の位置を記録

問題25：文字列の文字頻度による類似度判定

問題

• 2つの文字列が与えられる。文字頻度の類似度を計算する
• 類似度は共通文字の最小出現回数の合計で計算
• 入力：&str, &str
• 出力：usize
• 制約: なし

テンプレートとテスト

use std::collections::HashMap;

fn solution(s1: &str, s2: &str) -> usize {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution("abc", "bca"), 3); // 全ての文字が共通
    assert_eq!(solution("aab", "abb"), 2); // a:1, b:1
    assert_eq!(solution("hello", "world"), 1); // l:1
}

解答と解説

use std::collections::HashMap;

fn solution(s1: &str, s2: &str) -> usize {
    let mut counts1: HashMap<char, usize> = HashMap::new();
    let mut counts2: HashMap<char, usize> = HashMap::new();
    
    // 各文字列の文字頻度をカウント
    for ch in s1.chars() {
        *counts1.entry(ch).or_insert(0) += 1;
    }
    
    for ch in s2.chars() {
        *counts2.entry(ch).or_insert(0) += 1;
    }
    
    let mut similarity = 0;
    
    // 共通文字の最小出現回数を合計
    for (ch, &count1) in &counts1 {
        if let Some(&count2) = counts2.get(ch) {
            similarity += count1.min(count2);
        }
    }
    
    similarity
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution("abc", "bca"), 3); // 全ての文字が共通
    assert_eq!(solution("aab", "abb"), 2); // a:1, b:1
    assert_eq!(solution("hello", "world"), 1); // l:1
}

• 主要メソッド/イディオム:
  • chars(), entry(), or_insert(), get(), min()
• 注意点:
  • 2つのHashMapで文字頻度を管理
  • 共通文字の最小出現回数を合計

HashSet中級問題集

問題26：配列の要素の組み合わせ検出

問題

• 整数配列と目標値が与えられる。2つの要素の和が目標値になる組み合わせのインデックスを返す
• 複数ある場合は最初に見つかったものを返す
• 入力：&[i32], i32
• 出力：Option<(usize, usize)>
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[2, 7, 11, 15], 9), Some((0, 1))); // 2+7=9
    assert_eq!(solution(&[3, 2, 4], 6), Some((1, 2))); // 2+4=6
    assert_eq!(solution(&[3, 3], 6), Some((0, 1))); // 3+3=6
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashSet<i32> = HashSet::new();
    
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        
        if seen.contains(&complement) {
            // 補数を探してインデックスを取得
            for (j, &val) in nums.iter().enumerate() {
                if val == complement && j != i {
                    return Some((j, i));
                }
            }
        }
        
        seen.insert(num);
    }
    
    None
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[2, 7, 11, 15], 9), Some((0, 1))); // 2+7=9
    assert_eq!(solution(&[3, 2, 4], 6), Some((1, 2))); // 2+4=6
    assert_eq!(solution(&[3, 3], 6), Some((0, 1))); // 3+3=6
}

• 主要メソッド/イディオム:
  • contains(), insert(), iter(), enumerate()
• 注意点:
  • HashSetで既に見た値を記録
  • 補数を計算して存在チェック

問題27：文字列の文字セットによる分類

問題

• 文字列配列が与えられる。同じ文字セットを持つ文字列をグループ化する
• 文字セットは重複を除去した文字の集合
• 入力：&[String]
• 出力：Vec<Vec<String>>
• 制約: なし

テンプレートとテスト

use std::collections::{HashMap, HashSet};

fn solution(strs: &[String]) -> Vec<Vec<String>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.len(), 3); // 3つのグループ
    
    let input2 = vec!["abc".to_string(), "def".to_string()];
    let result2 = solution(&input2);
    assert_eq!(result2.len(), 2); // 2つのグループ
}

解答と解説

use std::collections::{HashMap, HashSet};

fn solution(strs: &[String]) -> Vec<Vec<String>> {
    let mut groups: HashMap<String, Vec<String>> = HashMap::new();
    
    for s in strs {
        let mut chars: HashSet<char> = s.chars().collect();
        let mut sorted_chars: Vec<char> = chars.into_iter().collect();
        sorted_chars.sort();
        let key: String = sorted_chars.into_iter().collect();
        
        groups.entry(key).or_insert_with(Vec::new).push(s.clone());
    }
    
    groups.into_values().collect()
}

fn main() {
    //簡易テスト（2件）
    let input1 = vec!["eat".to_string(), "tea".to_string(), "tan".to_string(), "ate".to_string(), "nat".to_string(), "bat".to_string()];
    let result1 = solution(&input1);
    assert_eq!(result1.len(), 3); // 3つのグループ
    
    let input2 = vec!["abc".to_string(), "def".to_string()];
    let result2 = solution(&input2);
    assert_eq!(result2.len(), 2); // 2つのグループ
}

• 主要メソッド/イディオム:
  • chars(), collect(), into_iter(), sort(), entry(), or_insert_with()
• 注意点:
  • HashSetで重複を除去→ソート→キーとして使用
  • into_values() でHashMapの値を取得

問題28：配列の連続部分配列の一意性判定

問題

• 整数配列が与えられる。全ての連続部分配列の中で、要素が全て異なるものの個数を返す
• 入力：&[i32]
• 出力：usize
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32]) -> usize {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3]), 6); // 全ての部分配列が一意
    assert_eq!(solution(&[1, 2, 1]), 4); // [1,2], [2,1], [1], [2] が一意
    assert_eq!(solution(&[1, 1, 1]), 3); // [1] のみが一意
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32]) -> usize {
    let mut count = 0;
    
    for i in 0..nums.len() {
        let mut seen = HashSet::new();
        
        for j in i..nums.len() {
            if !seen.insert(nums[j]) {
                break; // 重複が見つかったら終了
            }
            count += 1;
        }
    }
    
    count
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3]), 6); // 全ての部分配列が一意
    assert_eq!(solution(&[1, 2, 1]), 4); // [1,2], [2,1], [1], [2] が一意
    assert_eq!(solution(&[1, 1, 1]), 3); // [1] のみが一意
}

• 主要メソッド/イディオム:
  • insert(), len()
• 注意点:
  • ネストしたループで全ての部分配列をチェック
  • insert() が false を返したら重複なので終了

問題29：文字列の文字の出現パターン分析

問題

• 文字列が与えられる。各文字の出現位置を記録し、同じ出現パターンを持つ文字をグループ化する
• 出現パターンは文字の出現位置の配列
• 入力：&str
• 出力：Vec<Vec<char>>
• 制約: なし

テンプレートとテスト

use std::collections::{HashMap, HashSet};

fn solution(s: &str) -> Vec<Vec<char>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution("hello");
    // 'l' は位置2,3に出現
    assert!(result1.iter().any(|group| group.contains(&'l')));
    
    let result2 = solution("aabbcc");
    // 同じ文字は同じグループになる
    assert_eq!(result2.len(), 3); // a, b, c の3グループ
}

解答と解説

use std::collections::{HashMap, HashSet};

fn solution(s: &str) -> Vec<Vec<char>> {
    let mut char_positions: HashMap<char, Vec<usize>> = HashMap::new();
    
    // 各文字の出現位置を記録
    for (i, ch) in s.chars().enumerate() {
        char_positions.entry(ch).or_insert_with(Vec::new).push(i);
    }
    
    // 出現パターンでグループ化
    let mut pattern_groups: HashMap<Vec<usize>, Vec<char>> = HashMap::new();
    
    for (ch, positions) in char_positions {
        pattern_groups.entry(positions).or_insert_with(Vec::new).push(ch);
    }
    
    pattern_groups.into_values().collect()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution("hello");
    // 'l' は位置2,3に出現
    assert!(result1.iter().any(|group| group.contains(&'l')));
    
    let result2 = solution("aabbcc");
    // 同じ文字は同じグループになる
    assert_eq!(result2.len(), 3); // a, b, c の3グループ
}

• 主要メソッド/イディオム:
  • chars(), enumerate(), entry(), or_insert_with(), into_values()
• 注意点:
  • 文字の出現位置を記録→パターンでグループ化
  • 複数のHashMap操作を組み合わせ

問題30：配列の要素の範囲と一意性

問題

• 整数配列が与えられる。連続する要素の範囲で、全ての要素が一意である最長の範囲の長さを返す
• 入力：&[i32]
• 出力：usize
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32]) -> usize {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), 5); // 全体が一意
    assert_eq!(solution(&[1, 2, 3, 2, 4]), 3); // [1,2,3] が最長
    assert_eq!(solution(&[1, 1, 1]), 1); // 単一要素のみ
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32]) -> usize {
    let mut max_len = 0;
    let mut left = 0;
    let mut seen = HashSet::new();
    
    for right in 0..nums.len() {
        // 重複が見つかるまで右端を拡張
        while seen.contains(&nums[right]) {
            seen.remove(&nums[left]);
            left += 1;
        }
        
        seen.insert(nums[right]);
        max_len = max_len.max(right - left + 1);
    }
    
    max_len
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), 5); // 全体が一意
    assert_eq!(solution(&[1, 2, 3, 2, 4]), 3); // [1,2,3] が最長
    assert_eq!(solution(&[1, 1, 1]), 1); // 単一要素のみ
}

• 主要メソッド/イディオム:
  • contains(), remove(), insert(), max()
• 注意点:
  • スライディングウィンドウで最長の一意範囲を探索
  • HashSetで重複を効率的に管理

HashSet問題集

問題6：重複要素の検出

問題

• 整数配列が与えられる。重複する要素があるかどうかを判定する
• 入力：&[i32]
• 出力：bool
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32]) -> bool {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3, 1]), true);
    assert_eq!(solution(&[1, 2, 3, 4]), false);
    assert_eq!(solution(&[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]), true);
    assert_eq!(solution(&[]), false);
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32]) -> bool {
    let mut seen = HashSet::new();
    for &num in nums {
        if !seen.insert(num) {
            return true;
        }
    }
    false
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3, 1]), true);
    assert_eq!(solution(&[1, 2, 3, 4]), false);
    assert_eq!(solution(&[1, 1, 1, 3, 3, 4, 3, 2, 4, 2]), true);
    assert_eq!(solution(&[]), false);
}

• 主要メソッド/イディオム:
  • insert(), contains()
• 注意点:
  • insert() は既に存在する場合は false を返す
  • この性質を利用して重複を検出

問題7：配列の要素を一意にする

問題

• 整数配列が与えられる。重複を除去した配列を返す
• 順序は保持する
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 1, 2]), vec![1, 2]);
    assert_eq!(solution(&[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]), vec![0, 1, 2, 3, 4]);
    assert_eq!(solution(&[1, 2, 3]), vec![1, 2, 3]);
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut seen = HashSet::new();
    let mut result = Vec::new();
    
    for &num in nums {
        if seen.insert(num) {
            result.push(num);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 1, 2]), vec![1, 2]);
    assert_eq!(solution(&[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]), vec![0, 1, 2, 3, 4]);
    assert_eq!(solution(&[1, 2, 3]), vec![1, 2, 3]);
}

• 主要メソッド/イディオム:
  • insert(), push()
• 注意点:
  • insert() が true を返した場合のみ結果に追加
  • これにより順序を保持しながら重複を除去

問題8：2つの配列が同じ要素を持つか判定

問題

• 2つの整数配列が与えられる。同じ要素を持つかどうかを判定する
• 順序や重複は考慮しない
• 入力：&[i32], &[i32]
• 出力：bool
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> bool {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3], &[2, 1, 3]), true);
    assert_eq!(solution(&[1, 2], &[2, 2]), true);
    assert_eq!(solution(&[1, 2, 3], &[1, 2, 4]), false);
    assert_eq!(solution(&[], &[]), true);
}

解答と解説

use std::collections::HashSet;

fn solution(nums1: &[i32], nums2: &[i32]) -> bool {
    let set1: HashSet<i32> = nums1.iter().cloned().collect();
    let set2: HashSet<i32> = nums2.iter().cloned().collect();
    
    set1 == set2
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3], &[2, 1, 3]), true);
    assert_eq!(solution(&[1, 2], &[2, 2]), true);
    assert_eq!(solution(&[1, 2, 3], &[1, 2, 4]), false);
    assert_eq!(solution(&[], &[]), true);
}

• 主要メソッド/イディオム:
  • collect(), ==
• 注意点:
  • HashSetに変換することで重複を除去
  • HashSet同士の比較で同じ要素を持つか判定

問題9：配列の要素が全て異なるか判定

問題

• 整数配列が与えられる。全ての要素が異なるかどうかを判定する
• 入力：&[i32]
• 出力：bool
• 制約: なし

テンプレートとテスト

use std::collections::HashSet;

fn solution(nums: &[i32]) -> bool {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3, 4]), true);
    assert_eq!(solution(&[1, 2, 3, 1]), false);
    assert_eq!(solution(&[1, 1, 1, 1]), false);
    assert_eq!(solution(&[]), true);
}

解答と解説

use std::collections::HashSet;

fn solution(nums: &[i32]) -> bool {
    let set: HashSet<i32> = nums.iter().cloned().collect();
    set.len() == nums.len()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 3, 4]), true);
    assert_eq!(solution(&[1, 2, 3, 1]), false);
    assert_eq!(solution(&[1, 1, 1, 1]), false);
    assert_eq!(solution(&[]), true);
}

• 主要メソッド/イディオム:
  • collect(), len()
• 注意点:
  • HashSetのサイズと元配列のサイズを比較
  • 同じなら全て異なる要素

問題10：配列の要素の出現回数が全て異なるか判定

問題

• 整数配列が与えられる。各要素の出現回数が全て異なるかどうかを判定する
• 入力：&[i32]
• 出力：bool
• 制約: なし

テンプレートとテスト

use std::collections::{HashMap, HashSet};

fn solution(nums: &[i32]) -> bool {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 2, 1, 1, 3]), true); // 1:3回, 2:2回, 3:1回
    assert_eq!(solution(&[1, 2]), true); // 1:1回, 2:1回
    assert_eq!(solution(&[1, 1, 2, 2]), false); // 1:2回, 2:2回
    assert_eq!(solution(&[]), true);
}

解答と解説

use std::collections::{HashMap, HashSet};

fn solution(nums: &[i32]) -> bool {
    let mut counts = HashMap::new();
    for &num in nums {
        *counts.entry(num).or_insert(0) += 1;
    }
    
    let frequencies: HashSet<usize> = counts.values().cloned().collect();
    frequencies.len() == counts.len()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution(&[1, 2, 2, 1, 1, 3]), true); // 1:3回, 2:2回, 3:1回
    assert_eq!(solution(&[1, 2]), true); // 1:1回, 2:1回
    assert_eq!(solution(&[1, 1, 2, 2]), false); // 1:2回, 2:2回
    assert_eq!(solution(&[]), true);
}

VecDeque中級問題集

問題31：配列の要素を双方向にソート

問題

• 整数配列が与えられる。VecDequeを使って要素を双方向にソートする
• 奇数インデックスは昇順、偶数インデックスは降順でソート
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), vec![3, 5, 1, 4, 1]); // 奇数:昇順, 偶数:降順
    assert_eq!(solution(&[1, 2, 3, 4]), vec![3, 4, 1, 2]);
    assert_eq!(solution(&[5]), vec![5]);
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut odd_indices = VecDeque::new();
    let mut even_indices = VecDeque::new();
    
    // インデックス別に要素を分離
    for (i, &num) in nums.iter().enumerate() {
        if i % 2 == 0 {
            even_indices.push_back(num);
        } else {
            odd_indices.push_back(num);
        }
    }
    
    // 奇数インデックスは昇順、偶数インデックスは降順でソート
    let mut odd_sorted: Vec<i32> = odd_indices.into_iter().collect();
    let mut even_sorted: Vec<i32> = even_indices.into_iter().collect();
    
    odd_sorted.sort();
    even_sorted.sort_by(|a, b| b.cmp(a));
    
    // 元の位置に戻す
    let mut result = Vec::new();
    let mut odd_iter = odd_sorted.into_iter();
    let mut even_iter = even_sorted.into_iter();
    
    for i in 0..nums.len() {
        if i % 2 == 0 {
            result.push(even_iter.next().unwrap());
        } else {
            result.push(odd_iter.next().unwrap());
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), vec![3, 5, 1, 4, 1]); // 奇数:昇順, 偶数:降順
    assert_eq!(solution(&[1, 2, 3, 4]), vec![3, 4, 1, 2]);
    assert_eq!(solution(&[5]), vec![5]);
}

• 主要メソッド/イディオム:
  • push_back(), into_iter(), collect(), sort(), sort_by(), cmp()
• 注意点:
  • インデックス別に要素を分離→ソート→元の位置に戻す
  • sort_by() でカスタムソート条件を指定

問題32：配列の要素を双方向にフィルタリング

問題

• 整数配列が与えられる。VecDequeを使って要素を双方向にフィルタリングする
• 先頭からは偶数、末尾からは奇数を取り出す
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), vec![2, 4, 5, 3, 1]); // 偶数→奇数
    assert_eq!(solution(&[2, 4, 6]), vec![2, 4, 6]); // 偶数のみ
    assert_eq!(solution(&[1, 3, 5]), vec![5, 3, 1]); // 奇数のみ
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut result = Vec::new();
    
    while !deque.is_empty() {
        // 先頭から偶数を取り出す
        while let Some(front) = deque.front() {
            if *front % 2 == 0 {
                result.push(deque.pop_front().unwrap());
            } else {
                break;
            }
        }
        
        // 末尾から奇数を取り出す
        while let Some(back) = deque.back() {
            if *back % 2 == 1 {
                result.push(deque.pop_back().unwrap());
            } else {
                break;
            }
        }
        
        // 残りの要素を処理
        if !deque.is_empty() {
            result.push(deque.pop_front().unwrap());
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), vec![2, 4, 5, 3, 1]); // 偶数→奇数
    assert_eq!(solution(&[2, 4, 6]), vec![2, 4, 6]); // 偶数のみ
    assert_eq!(solution(&[1, 3, 5]), vec![5, 3, 1]); // 奇数のみ
}

• 主要メソッド/イディオム:
  • front(), back(), pop_front(), pop_back(), is_empty()
• 注意点:
  • 先頭から偶数、末尾から奇数を交互に取り出し
  • 条件に合わない要素は残して次のループで処理

問題33：配列の要素を双方向にグループ化

問題

• 整数配列が与えられる。VecDequeを使って要素を双方向にグループ化する
• 先頭からは正の数、末尾からは負の数を取り出してグループ化
• 入力：&[i32]
• 出力：Vec<Vec<i32>>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<Vec<i32>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, -2, 3, -4, 5]);
    assert_eq!(result1.len(), 2); // 正の数と負の数の2グループ
    assert!(result1.iter().any(|group| group.contains(&1)));
    assert!(result1.iter().any(|group| group.contains(&-2)));
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 1); // 正の数のみ
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut positive_group = Vec::new();
    let mut negative_group = Vec::new();
    
    // 先頭から正の数を取り出す
    while let Some(front) = deque.front() {
        if *front > 0 {
            positive_group.push(deque.pop_front().unwrap());
        } else {
            break;
        }
    }
    
    // 末尾から負の数を取り出す
    while let Some(back) = deque.back() {
        if *back < 0 {
            negative_group.push(deque.pop_back().unwrap());
        } else {
            break;
        }
    }
    
    // 残りの要素を処理
    while !deque.is_empty() {
        if let Some(front) = deque.front() {
            if *front > 0 {
                positive_group.push(deque.pop_front().unwrap());
            } else {
                negative_group.push(deque.pop_front().unwrap());
            }
        }
    }
    
    let mut result = Vec::new();
    if !positive_group.is_empty() {
        result.push(positive_group);
    }
    if !negative_group.is_empty() {
        result.push(negative_group);
    }
    
    result
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, -2, 3, -4, 5]);
    assert_eq!(result1.len(), 2); // 正の数と負の数の2グループ
    assert!(result1.iter().any(|group| group.contains(&1)));
    assert!(result1.iter().any(|group| group.contains(&-2)));
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 1); // 正の数のみ
}

• 主要メソッド/イディオム:
  • front(), back(), pop_front(), pop_back(), is_empty()
• 注意点:
  • 先頭から正の数、末尾から負の数を取り出し
  • 残りの要素も適切にグループ化

問題34：配列の要素を双方向に変換

問題

• 整数配列が与えられる。VecDequeを使って要素を双方向に変換する
• 先頭からは2倍、末尾からは3倍して交互に配置
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4]), vec![2, 12, 4, 9]); // 1*2, 4*3, 2*2, 3*3
    assert_eq!(solution(&[1, 2]), vec![2, 6]); // 1*2, 2*3
    assert_eq!(solution(&[5]), vec![10]); // 5*2
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut result = Vec::new();
    
    while !deque.is_empty() {
        // 先頭から2倍して取り出す
        if let Some(front) = deque.pop_front() {
            result.push(front * 2);
        }
        
        // 末尾から3倍して取り出す
        if let Some(back) = deque.pop_back() {
            result.push(back * 3);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4]), vec![2, 12, 4, 9]); // 1*2, 4*3, 2*2, 3*3
    assert_eq!(solution(&[1, 2]), vec![2, 6]); // 1*2, 2*3
    assert_eq!(solution(&[5]), vec![10]); // 5*2
}

• 主要メソッド/イディオム:
  • pop_front(), pop_back(), is_empty()
• 注意点:
  • 先頭から2倍、末尾から3倍して交互に取り出し
  • 要素数が奇数の場合は最後の要素のみ処理

問題35：配列の要素を双方向に分割・統合

問題

• 整数配列が与えられる。VecDequeを使って要素を双方向に分割・統合する
• 先頭からは小さい順、末尾からは大きい順に取り出して統合
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5]);
    result1.sort();
    assert_eq!(result1, vec![1, 1, 3, 4, 5]); // 全ての要素が含まれる
    
    let mut result2 = solution(&[2, 1]);
    result2.sort();
    assert_eq!(result2, vec![1, 2]);
    
    let result3 = solution(&[5]);
    assert_eq!(result3, vec![5]);
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut result = Vec::new();
    
    while !deque.is_empty() {
        // 先頭から最小値を探して取り出す
        if let Some(min_idx) = deque.iter().enumerate().min_by_key(|(_, &x)| x).map(|(i, _)| i) {
            let min_val = deque.remove(min_idx).unwrap();
            result.push(min_val);
        }
        
        // 末尾から最大値を探して取り出す
        if !deque.is_empty() {
            if let Some(max_idx) = deque.iter().enumerate().max_by_key(|(_, &x)| x).map(|(i, _)| i) {
                let max_val = deque.remove(max_idx).unwrap();
                result.push(max_val);
            }
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5]);
    result1.sort();
    assert_eq!(result1, vec![1, 1, 3, 4, 5]); // 全ての要素が含まれる
    
    let mut result2 = solution(&[2, 1]);
    result2.sort();
    assert_eq!(result2, vec![1, 2]);
    
    let result3 = solution(&[5]);
    assert_eq!(result3, vec![5]);
}

• 主要メソッド/イディオム:
  • iter(), enumerate(), min_by_key(), max_by_key(), remove()
• 注意点:
  • 先頭から最小値、末尾から最大値を交互に取り出し
  • remove() でインデックス指定で要素を削除

VecDeque問題集

問題11：双方向キューの基本操作

問題

• 整数配列が与えられる。先頭と末尾から交互に要素を取り出してVecで返す
• 先頭から開始する
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), vec![1, 5, 2, 4, 3]);
    assert_eq!(solution(&[1, 2, 3, 4]), vec![1, 4, 2, 3]);
    assert_eq!(solution(&[1]), vec![1]);
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut result = Vec::new();
    
    while !deque.is_empty() {
        if let Some(front) = deque.pop_front() {
            result.push(front);
        }
        if let Some(back) = deque.pop_back() {
            result.push(back);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), vec![1, 5, 2, 4, 3]);
    assert_eq!(solution(&[1, 2, 3, 4]), vec![1, 4, 2, 3]);
    assert_eq!(solution(&[1]), vec![1]);
}

• 主要メソッド/イディオム:
  • pop_front(), pop_back(), is_empty()
• 注意点:
  • pop_front() と pop_back() を交互に呼び出し
  • is_empty() で終了条件をチェック

問題12：スライディングウィンドウの最大値

問題

• 整数配列とウィンドウサイズkが与えられる。各ウィンドウの最大値をVecで返す
• 入力：&[i32], usize
• 出力：Vec<i32>
• 制約: k > 0, k <= nums.len()

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 3, -1, -3, 5, 3, 6, 7], 3), vec![3, 3, 5, 5, 6, 7]);
    assert_eq!(solution(&[1], 1), vec![1]);
    assert_eq!(solution(&[1, -1], 1), vec![1, -1]);
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    let mut deque = VecDeque::new();
    let mut result = Vec::new();
    
    for (i, &num) in nums.iter().enumerate() {
        // ウィンドウの範囲外のインデックスを削除
        while let Some(&front_idx) = deque.front() {
            if front_idx <= i.saturating_sub(k) {
                deque.pop_front();
            } else {
                break;
            }
        }
        
        // 現在の要素より小さい要素を削除
        while let Some(&back_idx) = deque.back() {
            if nums[back_idx] <= num {
                deque.pop_back();
            } else {
                break;
            }
        }
        
        deque.push_back(i);
        
        // ウィンドウが完成したら最大値を追加
        if i >= k - 1 {
            result.push(nums[*deque.front().unwrap()]);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 3, -1, -3, 5, 3, 6, 7], 3), vec![3, 3, 5, 5, 6, 7]);
    assert_eq!(solution(&[1], 1), vec![1]);
    assert_eq!(solution(&[1, -1], 1), vec![1, -1]);
}

• 主要メソッド/イディオム:
  • push_back(), pop_front(), pop_back(), front(), back()
• 注意点:
  • インデックスを保存してウィンドウの範囲を管理
  • デクリーディングキュー（単調減少）を維持

問題13：回文判定（双方向キュー使用）

問題

• 文字列が与えられる。双方向キューを使って回文かどうかを判定する
• 大文字小文字は区別しない
• 入力：&str
• 出力：bool
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(s: &str) -> bool {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution("racecar"), true);
    assert_eq!(solution("hello"), false);
    assert_eq!(solution("A man a plan a canal Panama"), true);
    assert_eq!(solution(""), true);
}

解答と解説

use std::collections::VecDeque;

fn solution(s: &str) -> bool {
    let mut deque: VecDeque<char> = s.chars()
        .filter(|c| c.is_alphanumeric())
        .map(|c| c.to_lowercase().next().unwrap())
        .collect();
    
    while deque.len() > 1 {
        if deque.pop_front() != deque.pop_back() {
            return false;
        }
    }
    
    true
}

fn main() {
    //簡易テスト（4件）
    assert_eq!(solution("racecar"), true);
    assert_eq!(solution("hello"), false);
    assert_eq!(solution("A man a plan a canal Panama"), true);
    assert_eq!(solution(""), true);
}

• 主要メソッド/イディオム:
  • pop_front(), pop_back(), len()
• 注意点:
  • アルファベットと数字のみを対象
  • 大文字小文字を統一してから比較

問題14：配列の要素を双方向に移動

問題

• 整数配列と移動回数nが与えられる。先頭の要素を末尾に移動する操作をn回行った結果を返す
• 入力：&[i32], usize
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32], n: usize) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5], 3), vec![4, 5, 1, 2, 3]);
    assert_eq!(solution(&[1, 2, 3, 4, 5], 0), vec![1, 2, 3, 4, 5]);
    assert_eq!(solution(&[1, 2], 1), vec![2, 1]);
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32], n: usize) -> Vec<i32> {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    
    for _ in 0..n {
        if let Some(front) = deque.pop_front() {
            deque.push_back(front);
        }
    }
    
    deque.into_iter().collect()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5], 3), vec![4, 5, 1, 2, 3]);
    assert_eq!(solution(&[1, 2, 3, 4, 5], 0), vec![1, 2, 3, 4, 5]);
    assert_eq!(solution(&[1, 2], 1), vec![2, 1]);
}

• 主要メソッド/イディオム:
  • pop_front(), push_back(), into_iter()
• 注意点:
  • 先頭から取り出して末尾に追加
  • into_iter() でVecに変換

問題15：配列の要素を双方向に分割

問題

• 整数配列が与えられる。先頭と末尾から交互に要素を取り出して2つのVecに分割する
• 先頭から開始して奇数番目は左、偶数番目は右に配置
• 入力：&[i32]
• 出力：(Vec<i32>, Vec<i32>)
• 制約: なし

テンプレートとテスト

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> (Vec<i32>, Vec<i32>) {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), (vec![1, 3, 5], vec![2, 4]));
    assert_eq!(solution(&[1, 2, 3, 4]), (vec![1, 3], vec![2, 4]));
    assert_eq!(solution(&[1]), (vec![1], vec![]));
}

解答と解説

use std::collections::VecDeque;

fn solution(nums: &[i32]) -> (Vec<i32>, Vec<i32>) {
    let mut deque: VecDeque<i32> = nums.iter().cloned().collect();
    let mut left = Vec::new();
    let mut right = Vec::new();
    let mut is_left = true;
    
    while !deque.is_empty() {
        if is_left {
            if let Some(front) = deque.pop_front() {
                left.push(front);
            }
        } else {
            if let Some(back) = deque.pop_back() {
                right.push(back);
            }
        }
        is_left = !is_left;
    }
    
    (left, right)
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[1, 2, 3, 4, 5]), (vec![1, 3, 5], vec![2, 4]));
    assert_eq!(solution(&[1, 2, 3, 4]), (vec![1, 3], vec![2, 4]));
    assert_eq!(solution(&[1]), (vec![1], vec![]));
}

BinaryHeap中級問題集

問題36：配列の要素をヒープでソート・フィルタリング

問題

• 整数配列が与えられる。BinaryHeapを使って要素をソートし、条件に合う要素のみを返す
• 偶数のみを昇順で返す
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5, 2]), vec![2, 4]); // 偶数のみ昇順
    assert_eq!(solution(&[1, 3, 5]), vec![]); // 偶数なし
    assert_eq!(solution(&[2, 4, 6]), vec![2, 4, 6]); // 全て偶数
}

解答と解説

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    
    // 偶数のみを最小ヒープに追加
    for &num in nums {
        if num % 2 == 0 {
            heap.push(Reverse(num));
        }
    }
    
    // 最小ヒープから昇順で取り出し
    let mut result = Vec::new();
    while let Some(Reverse(val)) = heap.pop() {
        result.push(val);
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5, 2]), vec![2, 4]); // 偶数のみ昇順
    assert_eq!(solution(&[1, 3, 5]), vec![]); // 偶数なし
    assert_eq!(solution(&[2, 4, 6]), vec![2, 4, 6]); // 全て偶数
}

• 主要メソッド/イディオム:
  • push(), pop(), Reverse
• 注意点:
  • 条件に合う要素のみをヒープに追加
  • Reverse で最小ヒープを実現

問題37：配列の要素をヒープでグループ化

問題

• 整数配列が与えられる。BinaryHeapを使って要素をグループ化する
• 各グループは同じ値を持つ要素の最大ヒープ
• 入力：&[i32]
• 出力：Vec<Vec<i32>>
• 制約: なし

テンプレートとテスト

use std::collections::{BinaryHeap, HashMap};

fn solution(nums: &[i32]) -> Vec<Vec<i32>> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, 1, 2, 2, 3]);
    assert_eq!(result1.len(), 3); // 3つのグループ
    assert!(result1.iter().any(|group| group.len() == 2)); // 重複要素のグループ
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 3); // 3つのグループ
}

解答と解説

use std::collections::{BinaryHeap, HashMap};

fn solution(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut groups: HashMap<i32, BinaryHeap<i32>> = HashMap::new();
    
    // 値ごとにヒープに追加
    for &num in nums {
        groups.entry(num).or_insert_with(BinaryHeap::new).push(num);
    }
    
    // 各ヒープをVecに変換
    groups.into_values()
        .map(|heap| heap.into_iter().collect())
        .collect()
}

fn main() {
    //簡易テスト（2件）
    let result1 = solution(&[1, 1, 2, 2, 3]);
    assert_eq!(result1.len(), 3); // 3つのグループ
    assert!(result1.iter().any(|group| group.len() == 2)); // 重複要素のグループ
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 3); // 3つのグループ
}

• 主要メソッド/イディオム:
  • entry(), or_insert_with(), push(), into_values(), into_iter()
• 注意点:
  • HashMapで値ごとにヒープを管理
  • into_values() でヒープを取得

問題38：配列の要素をヒープで変換・統合

問題

• 整数配列が与えられる。BinaryHeapを使って要素を変換し、統合する
• 最大値を2倍、最小値を3倍して交互に配置
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5]);
    result1.sort();
    assert_eq!(result1, vec![2, 3, 6, 8, 10]); // 変換後の値
    
    let mut result2 = solution(&[1, 2]);
    result2.sort();
    assert_eq!(result2, vec![2, 6]); // 1*2, 2*3
    
    let result3 = solution(&[5]);
    assert_eq!(result3, vec![10]); // 5*2
}

解答と解説

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut max_heap = BinaryHeap::new();
    let mut min_heap = BinaryHeap::new();
    
    // 要素を2つのヒープに分ける
    for &num in nums {
        max_heap.push(num);
        min_heap.push(Reverse(num));
    }
    
    let mut result = Vec::new();
    
    // 交互に最大値と最小値を取り出して変換
    while !max_heap.is_empty() && !min_heap.is_empty() {
        // 最大値を2倍
        if let Some(max_val) = max_heap.pop() {
            result.push(max_val * 2);
        }
        
        // 最小値を3倍
        if let Some(Reverse(min_val)) = min_heap.pop() {
            result.push(min_val * 3);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5]);
    result1.sort();
    assert_eq!(result1, vec![2, 3, 6, 8, 10]); // 変換後の値
    
    let mut result2 = solution(&[1, 2]);
    result2.sort();
    assert_eq!(result2, vec![2, 6]); // 1*2, 2*3
    
    let result3 = solution(&[5]);
    assert_eq!(result3, vec![10]); // 5*2
}

• 主要メソッド/イディオム:
  • push(), pop(), Reverse
• 注意点:
  • 最大ヒープと最小ヒープを同時に使用
  • 交互に要素を取り出して変換

問題39：配列の要素をヒープで分割・統合

問題

• 整数配列が与えられる。BinaryHeapを使って要素を分割・統合する
• 正の数は最大ヒープ、負の数は最小ヒープで管理し、交互に取り出す
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution(&[1, -2, 3, -4, 5]);
    assert_eq!(result1.len(), 5); // 全ての要素が含まれる
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2, vec![3, 2, 1]); // 正の数のみ
    
    let result3 = solution(&[-1, -2, -3]);
    assert_eq!(result3, vec![-1, -2, -3]); // 負の数のみ
}

解答と解説

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut positive_heap = BinaryHeap::new();
    let mut negative_heap = BinaryHeap::new();
    
    // 正の数と負の数に分ける
    for &num in nums {
        if num > 0 {
            positive_heap.push(num);
        } else if num < 0 {
            negative_heap.push(Reverse(num));
        }
    }
    
    let mut result = Vec::new();
    
    // 交互に取り出す
    while !positive_heap.is_empty() || !negative_heap.is_empty() {
        if let Some(pos_val) = positive_heap.pop() {
            result.push(pos_val);
        }
        
        if let Some(Reverse(neg_val)) = negative_heap.pop() {
            result.push(neg_val);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution(&[1, -2, 3, -4, 5]);
    assert_eq!(result1.len(), 5); // 全ての要素が含まれる
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2, vec![3, 2, 1]); // 正の数のみ
    
    let result3 = solution(&[-1, -2, -3]);
    assert_eq!(result3, vec![-1, -2, -3]); // 負の数のみ
}

• 主要メソッド/イディオム:
  • push(), pop(), Reverse
• 注意点:
  • 正の数は最大ヒープ、負の数は最小ヒープで管理
  • 交互に要素を取り出して統合

問題40：配列の要素をヒープで分析・統合

問題

• 整数配列が与えられる。BinaryHeapを使って要素を分析し、統合する
• 各要素の出現回数をカウントし、出現回数順にソートして返す
• 入力：&[i32]
• 出力：Vec<(i32, usize)>
• 制約: なし

テンプレートとテスト

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<(i32, usize)> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution(&[1, 1, 2, 2, 2, 3]);
    assert_eq!(result1, vec![(2, 3), (1, 2), (3, 1)]); // 出現回数順
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 3); // 全て1回ずつ
    
    let result3 = solution(&[1, 1, 1]);
    assert_eq!(result3, vec![(1, 3)]); // 1つだけ
}

解答と解説

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> Vec<(i32, usize)> {
    let mut counts: HashMap<i32, usize> = HashMap::new();
    
    // 出現回数をカウント
    for &num in nums {
        *counts.entry(num).or_insert(0) += 1;
    }
    
    // 出現回数でソートするためのヒープ
    let mut heap = BinaryHeap::new();
    
    for (num, count) in counts {
        heap.push((count, num)); // (出現回数, 値) でソート
    }
    
    // 出現回数順に取り出し
    let mut result = Vec::new();
    while let Some((count, num)) = heap.pop() {
        result.push((num, count));
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let result1 = solution(&[1, 1, 2, 2, 2, 3]);
    assert_eq!(result1, vec![(2, 3), (1, 2), (3, 1)]); // 出現回数順
    
    let result2 = solution(&[1, 2, 3]);
    assert_eq!(result2.len(), 3); // 全て1回ずつ
    
    let result3 = solution(&[1, 1, 1]);
    assert_eq!(result3, vec![(1, 3)]); // 1つだけ
}

• 主要メソッド/イディオム:
  • entry(), or_insert(), push(), pop()
• 注意点:
  • HashMapで出現回数をカウント
  • ヒープで出現回数順にソート

BinaryHeap問題集

問題16：配列の最大値と最小値

問題

• 整数配列が与えられる。最大値と最小値を返す
• BinaryHeapを使って実装する
• 入力：&[i32]
• 出力：(i32, i32)
• 制約: 配列は空でない

テンプレートとテスト

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> (i32, i32) {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), (5, 1));
    assert_eq!(solution(&[1, 2, 3]), (3, 1));
    assert_eq!(solution(&[5]), (5, 5));
}

解答と解説

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32]) -> (i32, i32) {
    let mut max_heap = BinaryHeap::new();
    let mut min_heap = BinaryHeap::new();
    
    for &num in nums {
        max_heap.push(num);
        min_heap.push(Reverse(num));
    }
    
    let max_val = max_heap.peek().unwrap();
    let min_val = min_heap.peek().unwrap().0;
    
    (*max_val, min_val)
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), (5, 1));
    assert_eq!(solution(&[1, 2, 3]), (3, 1));
    assert_eq!(solution(&[5]), (5, 5));
}

• 主要メソッド/イディオム:
  • push(), peek(), Reverse
• 注意点:
  • Reverse で最小ヒープを実現
  • peek() で値を取得（削除しない）

問題17：配列のk番目に大きい要素

問題

• 整数配列とkが与えられる。k番目に大きい要素を返す
• 入力：&[i32], usize
• 出力：Option<i32>
• 制約: k > 0

テンプレートとテスト

use std::collections::BinaryHeap;

fn solution(nums: &[i32], k: usize) -> Option<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5], 2), Some(4));
    assert_eq!(solution(&[1, 2, 3], 1), Some(3));
    assert_eq!(solution(&[1, 2, 3], 4), None);
}

解答と解説

use std::collections::BinaryHeap;

fn solution(nums: &[i32], k: usize) -> Option<i32> {
    if k > nums.len() {
        return None;
    }
    
    let mut heap = BinaryHeap::new();
    for &num in nums {
        heap.push(num);
    }
    
    for _ in 0..k - 1 {
        heap.pop();
    }
    
    heap.pop()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5], 2), Some(4));
    assert_eq!(solution(&[1, 2, 3], 1), Some(3));
    assert_eq!(solution(&[1, 2, 3], 4), None);
}

• 主要メソッド/イディオム:
  • push(), pop()
• 注意点:
  • k-1回popしてからk番目を取得
  • kが配列サイズより大きい場合はNone

問題18：配列のk個の最大要素

問題

• 整数配列とkが与えられる。k個の最大要素をVecで返す
• 入力：&[i32], usize
• 出力：Vec<i32>
• 制約: k > 0

テンプレートとテスト

use std::collections::BinaryHeap;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5], 3);
    result1.sort();
    assert_eq!(result1, vec![3, 4, 5]);
    
    let mut result2 = solution(&[1, 2, 3], 2);
    result2.sort();
    assert_eq!(result2, vec![2, 3]);
    
    let result3 = solution(&[1, 2, 3], 5);
    assert_eq!(result3.len(), 3);
}

解答と解説

use std::collections::BinaryHeap;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for &num in nums {
        heap.push(num);
    }
    
    let mut result = Vec::new();
    let count = k.min(heap.len());
    
    for _ in 0..count {
        if let Some(val) = heap.pop() {
            result.push(val);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5], 3);
    result1.sort();
    assert_eq!(result1, vec![3, 4, 5]);
    
    let mut result2 = solution(&[1, 2, 3], 2);
    result2.sort();
    assert_eq!(result2, vec![2, 3]);
    
    let result3 = solution(&[1, 2, 3], 5);
    assert_eq!(result3.len(), 3);
}

• 主要メソッド/イディオム:
  • push(), pop(), min()
• 注意点:
  • kが配列サイズより大きい場合は全ての要素を返す
  • min() で安全にカウントを制限

問題19：配列のk個の最小要素

問題

• 整数配列とkが与えられる。k個の最小要素をVecで返す
• 入力：&[i32], usize
• 出力：Vec<i32>
• 制約: k > 0

テンプレートとテスト

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5], 3);
    result1.sort();
    assert_eq!(result1, vec![1, 1, 3]);
    
    let mut result2 = solution(&[1, 2, 3], 2);
    result2.sort();
    assert_eq!(result2, vec![1, 2]);
    
    let result3 = solution(&[1, 2, 3], 5);
    assert_eq!(result3.len(), 3);
}

解答と解説

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn solution(nums: &[i32], k: usize) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for &num in nums {
        heap.push(Reverse(num));
    }
    
    let mut result = Vec::new();
    let count = k.min(heap.len());
    
    for _ in 0..count {
        if let Some(Reverse(val)) = heap.pop() {
            result.push(val);
        }
    }
    
    result
}

fn main() {
    //簡易テスト（3件）
    let mut result1 = solution(&[3, 1, 4, 1, 5], 3);
    result1.sort();
    assert_eq!(result1, vec![1, 1, 3]);
    
    let mut result2 = solution(&[1, 2, 3], 2);
    result2.sort();
    assert_eq!(result2, vec![1, 2]);
    
    let result3 = solution(&[1, 2, 3], 5);
    assert_eq!(result3.len(), 3);
}

• 主要メソッド/イディオム:
  • push(), pop(), Reverse
• 注意点:
  • Reverse で最小ヒープを実現
  • パターンマッチで Reverse を外す

問題20：配列の要素をヒープソート

問題

• 整数配列が与えられる。BinaryHeapを使ってソートした結果をVecで返す
• 昇順でソートする
• 入力：&[i32]
• 出力：Vec<i32>
• 制約: なし

テンプレートとテスト

use std::collections::BinaryHeap;

fn solution(nums: &[i32]) -> Vec<i32> {
    //ここに解答を書いてください
    unimplemented!()
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), vec![1, 1, 3, 4, 5]);
    assert_eq!(solution(&[5, 4, 3, 2, 1]), vec![1, 2, 3, 4, 5]);
    assert_eq!(solution(&[]), vec![]);
}

解答と解説

use std::collections::BinaryHeap;

fn solution(nums: &[i32]) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for &num in nums {
        heap.push(num);
    }
    
    let mut result = Vec::new();
    while let Some(val) = heap.pop() {
        result.push(val);
    }
    
    result.reverse();
    result
}

fn main() {
    //簡易テスト（3件）
    assert_eq!(solution(&[3, 1, 4, 1, 5]), vec![1, 1, 3, 4, 5]);
    assert_eq!(solution(&[5, 4, 3, 2, 1]), vec![1, 2, 3, 4, 5]);
    assert_eq!(solution(&[]), vec![]);
}

• 主要メソッド/イディオム:
  • push(), pop(), reverse()
• 注意点:
  • 最大ヒープから降順で取り出し
  • reverse() で昇順に変換