mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-01 21:24:27 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
102 lines
6.0 KiB
Markdown
102 lines
6.0 KiB
Markdown
# 練習問題
|
||
|
||
## 知識の確認
|
||
|
||
### ハッシュ衝突が起きた後の探索
|
||
|
||
バケット数 5、ハッシュ関数 $h(x)=x \bmod 5$ のハッシュテーブルがあります。衝突した要素は、そのバケットのリストに順に格納します。
|
||
`[1, 6, 11, 7]` を順に挿入します。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 0～4 番のバケットの内容を書いてください。
|
||
2. 6 を探すとき、まずどのバケットに入り、どの要素を順に調べますか。
|
||
3. 問い 1 のバケットの内容を見ると、後から挿入した要素が先に挿入した要素を上書きしていますか。この衝突の処理方法に基づいて理由を説明してください。
|
||
|
||
??? success "解答例"
|
||
|
||
1. $1\bmod5=6\bmod5=11\bmod5=1$、$7\bmod5=2$ なので、各バケットは次のとおりです。
|
||
|
||
```text
|
||
0: []
|
||
1: [1, 6, 11]
|
||
2: [7]
|
||
3: []
|
||
4: []
|
||
```
|
||
|
||
2. 6 を探すときは、まず 1 番のバケットに入り、1、6 の順に比較します。二回目の比較で見つかります。
|
||
|
||
3. ハッシュ値が同じでも、同じバケットに入るというだけで、要素が等しいわけではありません。チェイン法では衝突した要素をすべてバケット内に保存し、
|
||
照会時に一つずつ比較するため、1、6、11 が互いを上書きすることはありません。
|
||
|
||
### ハッシュテーブルの拡張後、要素はどこへ行くか
|
||
|
||
チェイン法を使うハッシュテーブルに、もともと 5 個のバケットがあり、ハッシュ関数は $h(x)=x\bmod5$ です。
|
||
キー `[1, 6, 11]` は、すべて 1 番のバケットに入っています。
|
||
|
||
バケット数を 7 に拡張し、ハッシュ関数も $h(x)=x\bmod7$ に変えます。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 1、6、11 の新しいバケット番号をそれぞれ計算してください。
|
||
2. 拡張後は、どのバケットに要素がありますか。
|
||
3. 拡張時に、元の 1 番のバケットのリストを、新しい 1 番のバケットへそのままコピーできますか。問い 1、2 の結果を使って理由を説明してください。
|
||
|
||
??? success "解答例"
|
||
|
||
1. 新しいバケット番号は、それぞれ次のとおりです。
|
||
|
||
- $1\bmod7=1$
|
||
- $6\bmod7=6$
|
||
- $11\bmod7=4$
|
||
|
||
2. 1 番のバケットに 1、4 番に 11、6 番に 6 が入ります。三つのキーは、同じバケットに集中しなくなります。
|
||
|
||
3. そのままコピーすることはできません。バケット番号は「キーをバケット数で割った余り」で決まります。バケット数が 5 から 7 に変わると、同じキーでも番号が変わることがあるため、
|
||
各キーの位置を計算し直す必要があります。古い 1 番のバケットをそのままコピーすると、その後、新しい式で 6 と 11 を探す際に、
|
||
それぞれ 6 番と 4 番のバケットへ進むため、見つけられません。
|
||
|
||
### 6 を削除しても 11 を見つけられるか
|
||
|
||
インデックス `0～4` の 5 か所に格納できるハッシュテーブルがあり、ハッシュ関数は $h(x)=x\bmod5$ です。
|
||
衝突した場合は、ハッシュ関数で求めたインデックスから右へ進み、最初の空き位置を探します。
|
||
|
||
`[1, 6, 11]` を順に挿入します。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 三つの数は、最終的にそれぞれどのインデックスに置かれますか。
|
||
2. 11 を探すとき、どのインデックスを順に調べますか。
|
||
3. 6 を削除するとき、その位置を単に「一度も使われていない空き位置」に変え、探索では空き位置に出会うと停止する場合、
|
||
再び 11 を探すと何が起きますか。その探索結果は正しいですか。問題があれば、どうすれば避けられますか。
|
||
|
||
??? success "解答例"
|
||
|
||
1. 1 はインデックス 1 に置かれます。6 もインデックス 1 に対応しますが、衝突するためインデックス 2 に置かれます。
|
||
11 もインデックス 1 から始め、使用中のインデックス 1、2 を順に飛ばして、最終的にインデックス 3 に置かれます。
|
||
|
||
2. 11 を探すときは、インデックス `1、2、3` を順に調べ、インデックス 3 で見つけます。
|
||
|
||
3. インデックス 2 を「一度も使われていない」空き位置に変えると、11 の探索はインデックス 1 を調べた後、インデックス 2 で停止し、
|
||
11 は存在しないと誤って判断します。削除時には「削除済み」の印を残す必要があります。
|
||
探索ではその印に出会っても次のインデックスへ進みます（インデックス 4 を越えると 0 に戻ります）。一方、その後の挿入では、この位置を再利用できます。
|
||
|
||
## プログラミング演習
|
||
|
||
### 二つの文字列の文字構成を比べる
|
||
|
||
英小文字だけからなる二つの文字列 `s` と `t` が与えられます。
|
||
`s` の文字の位置は自由に入れ替えられますが、文字の追加、削除、置換はできません。
|
||
|
||
入れ替えによって `t` にできるかを判定し、できれば `true`、できなければ `false` を返してください。
|
||
各文字の出現回数をハッシュテーブルに記録し、文字をソートせずに解いてください。
|
||
|
||
??? tip "解くためのヒント"
|
||
|
||
1. 二つの文字列の長さが違えば、文字の構成も必ず違います
|
||
2. ハッシュテーブルに各文字の個数を記録します。s を走査するときは、対応する個数を 1 増やします
|
||
3. t を走査するときは、対応する個数を 1 減らします。最後にすべての個数が 0 であれば、文字の構成が同じです
|
||
|
||
[LeetCode](https://leetcode.com/problems/valid-anagram/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|