### A Pluto.jl notebook ###
# v0.15.1

using Markdown
using InteractiveUtils

# ╔═╡ f0a7e49a-e3e9-11eb-356b-3926060d8c13
md"""
# Chapter 8
#### Nicetak
 $(import Dates; Dates.format(Dates.today(), Dates.DateFormat("U d, Y")))
"""

# ╔═╡ 64d4f95a-6969-4b68-bdfa-e2fc308f2ec4
md"""
## 8.1
連結リストのコード8.6において, 連結リストの各ノードに格納された値を順に出力する関数`printList`の処理に要する計算量を評価してください.
"""

# ╔═╡ ca215632-c7c7-4ffc-a712-78868335644e
md"""
**答** 要素を一つずつ順番に出力するだけなので, $O(N)$
"""

# ╔═╡ 2ae58dfb-0086-44a2-a053-edeb6c8c5f54
md"""
## 8.2
サイズが$N$の連結リストにおいて, `get(i)`を`head`からスタートして$i$番目の要素を取得する関数とします. この時以下のコードの計算量を求めてください.

```
for (int i = 0; i < N; ++i){
	count << get(i) << endl;
}
```
"""

# ╔═╡ 9bb328a2-0fe2-48b9-8d9a-b71822bef6ae
md"""
**答** 連結リストにおいて$i$番目の要素を取得するためには, 最初の要素から順番に$i$回, 続く要素をたどる必要がある. したがって, `get(i)`は$O(N)$で実行され, それを$N$回繰り返すので$O(N^2)$. より正確に評価するなら$O\left(\frac{N(N + 1)}{2}\right)$と考えても良い.
"""

# ╔═╡ ead7ba60-3f49-47d5-bde1-cd4a73d38a8e
md"""
## 8.3
連結リストにおいて, サイズを$O(1)$で取得できるようにする方法を述べてください.
"""

# ╔═╡ 14b8b97b-39f9-417e-bd67-a625b8d05d4f
md"""
**答**
連結リストの実装において, 連結リストのサイズを常に保持するようにする. すなわち,

- 初期値は0
- 挿入(+1)と削除(-1)のたびにサイズを変更

となるように実装しておけば, サイズは$O(1)$で取得できる.
"""

# ╔═╡ df96aa07-7dfa-4d86-b11c-2471b9caa46a
md"""
## 8.4
単方向連結リストにおいて, 特定のノード$v$を削除する方法を述べてください. ただし, $O(N)$の計算量を要してもよいものとします.
"""

# ╔═╡ 73cdc535-703c-47df-a3dc-328ad3cd96a2
md"""
**答** ノード$v$の前の要素を取得すれば, 後のノードと繋ぎかえるだけである(自明に$O(1)$の操作).
ノード$v$の要素の取得は, 先頭のノードから順に次のノードが$v$であるかを判定していけばよい.
この繰り返す回数は$O(N)$であり, 全体の操作も$O(N)$となる.
"""

# ╔═╡ 0b8fe944-4a94-47f3-b0a3-42a35723cc9d
md"""
## 8.5
 $N$個の相異なる整数$a_0, a_1, \dots, a_{N-1}$と, $M$個の相異なる整数$b_0, b_1, \dots, b_{M-1}$が与えられます. $a$と$b$で共通する整数の個数を, 平均的に$O(N + M)$の計算量で求めるアルゴリズムを設計してください.

"""

# ╔═╡ 128f181f-6a33-43b7-b465-55ec0bdce845
md"""
**答**
1. ハッシュテーブルを$a_0, a_1, \dots, a_{N-1}$で構築する, $O(N)$
2. この中に, $b_0, b_1, \dots, b_{M-1}$ が存在するかを順番にチェクする. ハッシュテーブルの要素の検索は$O(1)$ であるから,この操作は $O(M)$

したがって, 全体の操作は$O(N + M)$. 
"""

# ╔═╡ 34c3a14e-5e39-4465-b91a-eb403b2d9cda
function f₅(as::Vector{Int}, bs::Vector{Int})
	asₕ = Set(as)
	ans = 0
	for b in bs
		if b ∈ asₕ
			ans += 1
		end
	end
	
	return ans
end

# ╔═╡ 29fb9255-c233-46d0-a81f-c7b8c53d7ef0
f₅(collect(1:100), collect(1:3:100))

# ╔═╡ fba3be40-eec9-4489-9822-28c2bb2a3216
md"""
## 8.6
 $N$個の整数$a_0, a_1, \dots, a_{N-1}$と, $M$個の整数$b_0, b_1, \dots, b_{M-1}$が与えられます. $a_i = b_j$となるような添字$i, j$の組の個数を, 平均的に$O(N + M)$の計算量で求めるアルゴリズムを設計してください.
"""

# ╔═╡ 1a6f9771-cd95-4568-8a4f-3498d0cd55a1
md"""
**答**　

1. 連想配列を用いて, $a_0, a_1, \dots, a_{N-1}$の中の各整数の個数を数える, $O(N)$
1. 各$b_i$に対応する上の連想配列の値を足し上げる, $O(M)$

よって, $O(N + M)$.
"""

# ╔═╡ 7e0eddba-4c9d-4c89-a3c5-abdd3170c232
function f₆(as::Vector{Int}, bs::Vector{Int})
	d = Dict{Int, Int}()
	for a in as
		if haskey(d, a)
			d[a] += 1
		else
			d[a] = 1
		end
	end
	
	ans = 0
	for b in bs
		if haskey(d, b)
			ans += d[b]
		end
	end
	
	return ans
end

# ╔═╡ 44358936-b446-420c-9db5-16df16b0de2b
f₆([1, 2, 3, 3], [2, 3])

# ╔═╡ 06d3fa80-a3f4-4c99-acf0-ee2d7ee030ee
md"""
## 8.7
 $N$個の整数$a_0, a_1, \dots, a_{N-1}$と, $N$個の整数$b_0, b_1, \dots, b_{N-1}$が与えられます. 2組の整数列からそれぞれ1個ずつ整数を選んで和を$K$とすることができるかどうかを, 平均的に
$O(N)$の計算量で判定するアルゴリズムを設計してください.　なお, 6.6節では, 類似の問題に対する, 二分探索法に基づいた$O(N \log N)$の計算量のアルゴリズムを示しました.
"""

# ╔═╡ d49be868-3522-452e-9615-9b096c713704
md"""
**答**
1. ハッシュテーブル $b_H$ を $b_0, b_1, \dots, b_{N-1}$ から作る ($O(N)$)
2.  $K - a_i$ が $b_H$の要素にあるかどうかを順番に確認する (一回あたり$O(1)$, 全体は$O(N)$)
3. ある $a_i$に対して2の条件が満たされた時, "Yes", そうでなければ "No" を出力

これは明らかに$O(N)$で動作する
"""

# ╔═╡ 1cd82896-c72b-4ad5-885d-a8a25382faa7
function f₇(as::Vector{Int}, bs::Vector{Int}, K::Int)
	bsₕ = Set(bs)
	
	ans = "No"
	for a in as
		if (K - a) ∈ bsₕ
			ans = "Yes"
			break
		end
	end
	
	return ans
end

# ╔═╡ c179229f-de71-4381-a0a6-562f9bab2f38
f₇([1, 2, 4], [8, 16, 32], 9)

# ╔═╡ Cell order:
# ╟─f0a7e49a-e3e9-11eb-356b-3926060d8c13
# ╟─64d4f95a-6969-4b68-bdfa-e2fc308f2ec4
# ╟─ca215632-c7c7-4ffc-a712-78868335644e
# ╟─2ae58dfb-0086-44a2-a053-edeb6c8c5f54
# ╟─9bb328a2-0fe2-48b9-8d9a-b71822bef6ae
# ╟─ead7ba60-3f49-47d5-bde1-cd4a73d38a8e
# ╟─14b8b97b-39f9-417e-bd67-a625b8d05d4f
# ╟─df96aa07-7dfa-4d86-b11c-2471b9caa46a
# ╟─73cdc535-703c-47df-a3dc-328ad3cd96a2
# ╟─0b8fe944-4a94-47f3-b0a3-42a35723cc9d
# ╟─128f181f-6a33-43b7-b465-55ec0bdce845
# ╠═34c3a14e-5e39-4465-b91a-eb403b2d9cda
# ╠═29fb9255-c233-46d0-a81f-c7b8c53d7ef0
# ╟─fba3be40-eec9-4489-9822-28c2bb2a3216
# ╟─1a6f9771-cd95-4568-8a4f-3498d0cd55a1
# ╠═7e0eddba-4c9d-4c89-a3c5-abdd3170c232
# ╠═44358936-b446-420c-9db5-16df16b0de2b
# ╟─06d3fa80-a3f4-4c99-acf0-ee2d7ee030ee
# ╟─d49be868-3522-452e-9615-9b096c713704
# ╠═1cd82896-c72b-4ad5-885d-a8a25382faa7
# ╠═c179229f-de71-4381-a0a6-562f9bab2f38
