LeetCode生活5日目

はじめに

この前はこいつが難しくて、

眠くて連続生活が途切れた。

完璧主義にならずに気長にやっていこうと思う。

Product of Array Except Self

数字の配列numsが与えられる。

なお要素のprefix, suffixの数字は32bitであるので積が大きくなりすぎることはない

計算量はO(n)、計算に割り算は使えない。

そうした場合、以下のような条件を満たすanswerという数字の配列を返せ

• answer[i]はnums[i]以外のnumsの要素を掛け合わせた数字であること

解法1(マジでわからんかったのでAIからヒントもらった)

# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
  n = nums.length
  answer = Array.new(n, 1)

  # 左側の積を計算: answer[i] は nums[0] ~ nums[i-1] の積
  (1...n).each do |i|
    answer[i] = answer[i - 1] * nums[i - 1]
  end

  # 右側の積を計算しながら、左側の積と掛け合わせる
  right = 1
  (n - 1).downto(0) do |i|
    answer[i] *= right
    right *= nums[i]
  end

  answer
end

今回ばかりはギブ。

全くわからなかった。

制約がなかったら解けたかもしれないが、それでもいつもと違う感じで。

downtoなんて書き方もあるのか。

まだまだrubyは色々書き方があって面白い。

でもまだ読み込めてない。

終わりに

アルゴリズムの本を買った。

即効性があるとは思ってない。

気長に教養レベルで楽しめたらいいと思う。