LeetCode - 4. Median of Two Sorted Arraysを解く

３日坊主を乗り切るんだ！

問題へのリンク

https://leetcode.com/problems/median-of-two-sorted-arrays/

問題を解く前に

• 中央値
  中央値 - Wikipedia

中央値について一部誤解していたみたい。数字が偶数個の場合は算術平均を取るのだった。

• 計算量について
  計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita

log(n) は 2の対数ということで、計算量O(log (m+n))ということはm+nが16なら2の4乗だから4ループで処理できるようにということか。

解き方を考えてみる

計算量の制約があるので、半分に切っていくようなやり方がよさそう。これはバイナリサーチ（2分探索）という方法。 しかし配列が2つあるので単純に処理する方法が思いつかない。例えば[1,2,3,4], [5,6,7,8]のような配列の場合はどう考えればいいんだろう？
わからずじまいなので、とりあえずリニアサーチ（線形探索）で処理するコードを書いた。

解答

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Float}
def find_median_sorted_arrays(nums1, nums2)
    total_size = nums1.size + nums2.size
    
    is_even = total_size % 2 == 0 ? true : false
    if is_even
        medium_index = total_size / 2
    else
        medium_index = total_size / 2 + 1
    end
    
    count = 0
    index1 = 0
    index2 = 0
    medium = 0
    tmp = 0
    while count <= medium_index do
        if nums1.size == index1
            tmp = nums2[index2]
            index2 = index2 + 1
        elsif nums2.size == index2
            tmp = nums1[index1]
            index1 = index1 + 1
        elsif nums1[index1] > nums2[index2]
            tmp = nums2[index2]
            index2 = index2 + 1
        else
            tmp = nums1[index1]
            index1 = index1 + 1
        end
        count = count + 1
        
        if count == medium_index
            if is_even
                if nums1.size == index1
                    medium = (tmp.to_f + nums2[index2].to_f) / 2
                elsif nums2.size == index2
                    medium = (tmp.to_f + nums1[index1].to_f) / 2
                elsif nums1[index1] > nums2[index2]
                    medium = (tmp.to_f + nums2[index2].to_f) / 2
                else
                    medium = (tmp.to_f + nums1[index1].to_f) / 2
                end
            else
                medium = tmp.to_f
            end
        end
    end
    return medium
end

解説の理解と正解の写経は後日やろう。

atcoder茶色になった

ようやくまがいものからの卒業。やったね。

LeetCode - 3. Longest Substring Without Repeating Charactersを解く

連休で家にいないといけないのは、こういうチャレンジをする分にはありがたいなと思っていたけど、
3つ続けられることで改めて実感しますね。

問題へのリンク

https://leetcode.com/problems/longest-substring-without-repeating-characters/

問題を解く前に

今回の問題文でわからない単語はなかった。

解き方を考えてみる

同じ文字が2回出てきたらだめなので、ハッシュテーブルの衝突を使うのはどうだろう。
ハッシュテーブルで文字をキーにしていってキーが衝突したらカウント終了。一番大きいカウントが正解。

解答（NG）

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    h = {}
    arr = s.chars
    
    max = 0
    count = 0
    arr.each do |c|
        if h[c].nil?
            h[c] = 0
            count = count + 1
        else
            h = {c => 0}
            max = count if max < count
            count = 1
        end
    end
    max = count if max < count

    return max
end

Wrong Answer	Details
Input	"dvdf"
Output	2
Expected	3

あかん、衝突は検知できても数え直しのスタート位置が取得できない。じゃあスタート位置も持っておかないといけないか、ハッシュテーブルもスタート位置から作り直し？巻き戻るのか、そんなことしたら終わらないよな・・・ うーむ1時間悩んでギブアップ。

解法を参考に

# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
    h = {}
    arr = s.chars
    
    max = 0
    start = 0
    index = 0
    arr.each do |c|
        if !h[c].nil? && h[c] >= start
            start = h[c] + 1
        end
        h[c] = index
        index = index + 1
        max = index - start if max < index - start
    end
    max = index - start if max < index - start

    return max
end

ハッシュテーブルを利用して、keyに文字、valueにindexを保持する。またsubstringのスタート位置を個別に保持する。
スタート位置はkeyの衝突時にvalueがstartより大きいか小さいかを判断してstartより大きい場合にだけ更新する。
最大値は毎回startからindex位置までを取得する。


ハッシュテーブル作り直しに気を取られて死にました。思い込みで詰まるのは自分の弱点だなあ。
それはともかくleetcodeは計算量とかもちゃんと解説しているので、これ説明できるようになったらきっと強くなれるだろうなあと思った。

LeetCode - 2. Add Two Numbersを解く

LeetCode2日目、なんとなく予測できて解けるときは楽しいなと思う。進研ゼミのマンガみたいな感じ。

問題へのリンク

https://leetcode.com/problems/add-two-numbers/

問題を解く前に

• 連結リストの復習
  連結リスト - Wikipedia

配列との違いは連結リストではデータの追加がより容易で、データの検索にはコストがかかってしまうこと。
なので毎回数字を探しに行かないように組んでみた。

解答

def add_two_numbers(l1, l2)

    num1 = to_num(l1)
    num2 = to_num(l2)

    sum = num1 + num2
    size = sum.to_s.length - 1
    sumStr = sum.to_s
    ans = ListNode.new
    tmp = ans
    size.step(0, -1) do |i|
        tmp.val = sumStr[i]
        if i == 0
            tmp.next = nil
        else
            tmp.next = ListNode.new
            tmp = tmp.next
        end
    end
    
    return ans
end

def to_num(list_node)
    l = list_node
    index = 0
    num = 0
    while !l.nil? do
        num = num + l.val * (10 ** index)
        l = l.next
        index = index + 1
    end
    return num
end

Runtime	Memory
64 ms	9.8 MB

別解

公式の解答例では1桁ずつ処理する方法を紹介しているのでrubyで書いてみる。

def add_two_numbers(l1, l2)

    p = l1
    q = l2
    ans = ListNode.new
    tmp = ans
    carry = 0
    while !p.nil? || !q.nil? do
        tmp.next = ListNode.new
        tmp = tmp.next

        num1 = p.nil? ? 0 : p.val
        num2 = q.nil? ? 0 : q.val
        sum = num1 + num2 + carry
        
        carry = sum / 10
        tmp.val = sum % 10
        
        p = p.nil? ? nil : p.next
        q = q.nil? ? nil : q.next
    end
    if carry == 1
        tmp.next = ListNode.new(1, nil)
    end
    return ans.next
end

Runtime	Memory
44 ms	9.8 MB

LeetCode - 1. Two Sumを解く

とあるブログを見てみてだいぶ感動したので一つだけマネして、LeetCodeを始めてみた。 やってみてだいぶレベルが足りないのを確認してとりあえず凹む。
とあるブログとはこちら

ガチ三流エンジニアが米国マイクロソフトのドリームチームのメンバーになれた話とそのためにやった事 - メソッド屋のブログ

問題へのリンク

https://leetcode.com/problems/two-sum/

解答

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    candidates = nums.select { |num| num < target }
    candidates.map.with_index do |c1, index1|
        candidates.map.with_index do |c2, index2|
            return [index1, index2] if (target - c1 == c2)
        end
    end
end

時間制限超過して失敗。ブルードフォースで計算量O(n²)で書かれていた。 これではダメなやつ。

修正

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    h = {}
    nums.each_with_index do |n1, index1|
        h[n1] = index1
    end
    nums.each_with_index do |c2, index2|
        tmp = target - c2
        next if h[tmp].nil? || index2 == h[tmp]
        return [index2, h[tmp]]
    end
end

あとでブログ書き直しつつ復習しよう。

参考にさせていただいた記事

https://euro.qrunch.io/entries/IMtqWEs4GTw6XJCf

標準入力

atcoder向けメモ。言語は追記。

Ruby

• １項目の取り込み（文字列）

  line = gets.chomp

• １項目の取り込み（数値）

  line = gets.to_i

• １行の取り込み、空白区切り（文字列）

  line = gets.split

• １行の取り込み、空白区切り（数値）

  line = gets.split.map(&:to_i)

2018年09月02日のツイート