読書感想:「「心」の危機管理術」
読んだ本を忘れないように。あとアソシエイトの練習。
会社で随分と嫌な目にあったので読んでみたものの一つ。 https://www.amazon.co.jp/gp/product/4413017900/ref=as_li_qf_asin_il_tl?ie=UTF8&tag=ticktackst4hi-22&creative=1211&linkCode=as2&creativeASIN=4413017900&linkId=1316186f8183e22f6b78a39d5e37b1f4www.amazon.co.jp
仕事でミスがあったときに立場が上の人間から責任を要求されることがあるわけですよ。反論できない状況を作ってから攻撃するってされる側としてはいやな話ですね。
随分と気持ちが落ち込んで休日を無駄にすることが増えたので、そういった気持ちが追い込まれたときどうするかという形で読んだ。
対処法の充実を望んでいたけど、そういう情報は腹式呼吸をしましょう、ビタミン・ミネラルをとりましょうくらい。
この本は対処法というよりもしかして鬱なんじゃないかと疑っている人向けの本。鬱をめちゃくちゃ細かい分類をしているようでどれも似た症状ばかり書いているのでどれか当てはまって鬱なんだと安心させるスタイルなのかな。
20年前の本であるのでこの時代はまだこれくらいの認識だったのだとすると、繊細ヤクザな自分は昭和のサラリーマンでなくてよかったなと思う。
LeetCode - 4. Median of Two Sorted Arraysを解く
3日坊主を乗り切るんだ!
問題へのリンク
https://leetcode.com/problems/median-of-two-sorted-arrays/
問題を解く前に
- 中央値
中央値 - Wikipedia
中央値について一部誤解していたみたい。数字が偶数個の場合は算術平均を取るのだった。
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(n2)で書かれていた。 これではダメなやつ。
修正
# @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
あとでブログ書き直しつつ復習しよう。
参考にさせていただいた記事