目的
技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページに全部まとめる。
Rubyでそそくさと実装できることを目的とする。
参考
- https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)
配列（データ構造）
要点
- 配列は要素の追加・削除が苦手なので、その場合は連結リスト利用を考える
- indexが分かっていればO(1)、線形探索ならO(N)
- 探索の効率は高くない。ソート済みなら、二分探索を使う等して効率を高められる
アルゴリズム
要素の探索が主
配列の中に、目的の値があるかどうか知りたい
irb(main):055:0> "Hello, World!!".split("").include?("l")
=> true
irb(main):056:0> "Hello, World!!".split("").include?("X")
=> false
配列の中に、目的の値が何個あるか知りたい
irb(main):034:0> [3, 6, 32, 22, 4].count(6)
=> 1
irb(main):036:0> "Hello, World!!".count("l")
=> 3
irb(main):037:0> "Hello, World!!".count("Hl")
=> 4
# 無駄にscanを使う
irb(main):045:0> "Hello, World!!".scan(/l/)
=> ["l", "l", "l"]
irb(main):046:0> "Hello, World!!".scan(/l/).count()
=> 3
# 無駄にinjectを使う
irb(main):053:0> "Hello, World!!".split("").inject(0) {|res, v| v == "l"? res + 1 : res }
=> 3
配列のどの位置に、目的の値があるか知りたい。ただし、一番最初に見つけたものだけで構わない
irb(main):057:0> "Hello, World!!".index("l")
=> 2
- 配列のどの位置に、目的の値があるか知りたい。ただし、一番最後に見つけたものだけで構わない（逆順の探索）
irb(main):012:0> "Hello, World!!".rindex("l")
=> 10
配列のどの位置に、目的の値があるか知りたい。しかも、すべて抜き出したい
irb(main):013:0> "Hello, World!!".split("").each_with_index.inject([]) { |res, (v, i)| res << (i if v == "l") }.compact
=> [2, 3, 10]
練習1: 配列の中身を逆順にする
unshift: 配列の先頭要素への値の追加
irb(main):014:0> "Hello, World!!".reverse
=> "!!dlroW ,olleH"
# 新しい配列にunshiftでどんどん先頭に要素を追加する、それをjoinして文字列にする
irb(main):018:0> "Hello, World!!".split("").inject([]) {|res, v| res.unshift(v) }.join()
=> "!!dlroW ,olleH"
練習2: 整数が格納された配列から、偶数の値を持つ要素数を数えるプログラムを作成してください
irb(main):030:0> (1..10).map {|v| v if v%2 == 0 }.compact
=> [2, 4, 6, 8, 10]
# selectを使う
irb(main):029:0> (1..10).select {|v| v%2 == 0 }
=> [2, 4, 6, 8, 10]
練習3: ２つの配列に、共通して含まれている値を探し出すプログラムを作成してください
[1, 2, 3, 4, 4].select {|i| [3, 5, 6, 8].include?(i) }.uniq
練習4: 多次元配列で、任意の行を削除する方法を考えてください
多次元配列削除するのめんどいな、slice!(0..-1)で行ごと空配列にして、
delete_ifで空配列を削除するしかないのか。
2次元以上の配列は使うのはしんどいな。
irb(main):093:0> a=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):094:0> b=[a.dup,a.dup,a.dup]
=> [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 5, 6], [7, 8, 9]]]
irb(main):095:0> b[0].slice!(0..-1)
=> [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
irb(main):096:0> b.delete_if(&:empty?)
=> [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 2, 3], [4, 5, 6], [7, 8, 9]]]
学び
- rubyは無駄にメソッドが多いので使うものを決める
.charsは使わずに.split("")で統一するなど - 特殊なメソッドにこだわらずに基本的なメソッドのみで考えて書く