Help us understand the problem. What is going on with this article?

アルゴリズムとデータ構造の要点メモ in ruby(配列)

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページに全部まとめる。
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: 2つの配列に、共通して含まれている値を探し出すプログラムを作成してください

[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("")で統一するなど
  • 特殊なメソッドにこだわらずに基本的なメソッドのみで考えて書く
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away