121. Best Time to Buy and Sell Stock

問題概要

• integerの配列 prices が入力値
• prices[i] - prices[j] ( i < j ) が最も大きい組み合わせを見つければ良い

単純にループを二重にすると Time Limit Exceeded になるので工夫が必要

問題URL：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

解法

先頭からループしていき、その時点での最小値が現れたら購入し、それ以外のときに売却。
これを繰り返して最大利益を求めれば良い。

func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfit := 0

    for i := 1; i < len(prices); i++ {
        if prices[i] < minPrice {
            // 最小値のときに売っても利益にならない(マイナスになる）
            // minを更新して次へ
            minPrice = prices[i]
            continue
        }

        // 利益を求める。利益が最大ならmaxProfitを更新
        if profit := prices[i] - minPrice; maxProfit < profit {
            maxProfit = profit
        }
    }

    if maxProfit > 0 {
        return maxProfit
    }

    return 0
}

感想

私は、もっとややこしい解き方をして、上記の解法はSolutionsで見つけた。

なんでこんな簡単なことを思いつかなかったのかなーと。

紙とペンで問題を解いてみて、「頭の中で考えたこと」をコードで表現できると良いのかも。

いきなりコードを書きながら考えるのは悪手。

189. Rotate Array

問題概要

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

integerの配列を右にk回ローテートする。

問題URL：https://leetcode.com/problems/rotate-array/description/

解法1

ブルートフォースな解法。
Beats 5.05% 激遅

一つずつ右にローテートするのをk回行う。

func rotate(nums []int, k int)  {
    size := len(nums)
    for k > 0 {
        tail := nums[size-1]
        for i := size - 1; i > 0; i-- {
            nums[i] = nums[i-1]
        }
        nums[0] = tail
        k--
    }
}

解法2

time O(n) の解法。
Beats 92.37% まずまず。

スライスを先頭からループして、各要素を右にkローテートする。
解法1では右に1ローテートするのをk回繰り返していたが、今回は一気にkローテートしている。

nums のcopyして保持しているのは、ローテートするときに、元々ローテート先にあった要素がわからなくなるから。

func rotate(nums []int, k int)  {
    size := len(nums)
    if size == k {
        return
    }
    backup := make([]int, 0, size)
    backup = append(backup, nums...)

    for i := 0; i < size; i++ {
        rotatedIdx := (k % size) + i
        if rotatedIdx >= size {
            rotatedIdx = rotatedIdx - size
        }
        nums[rotatedIdx] = backup[i]
    }
}

解法3

Time O(n) Space O(1) の解法。

要素の反転（リバース）をうまく使えば良いらしい。

func rotate(nums []int, k int) {
    size := len(nums)
    // k が len(nums) より大きいときを考慮した処理
    // 【詳細】
    // k = len(nums) のとき要素は一周して元の位置に戻る。
    // したがって、k > len(nums)の場合は `k % size`（余り）回ローテートすれば良い。
    // len(nums) [f:id:nomuyoshi0111:20240328005046p:plain]>= k の場合は `k % size` = k なので、常に k = k % size としても問題ない。
    k = k % size
    if k == 0 {
        return
    }

    reverse(nums, 0, size-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, size-1)
}

func reverse(nums []int, start, end int) {
    for end > start {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

パッと理解できなかったので図を書いた。

やりたいこと

例: nums = [1,2,3,4,5,6,7], k = 3 のとき

感想

解法3は思いつかず、submissionsを見た。

思いつかなかったし、解答を見てもすぐ理解できなかったけど、「やりたいこと」の画像の図を書いたときにイメージがついた。

紙に図を書きながら取り組むことが大切 だと感じた。

良い教訓を得られて良かった。

ちなみに

80. Remove Duplicates from Sorted Array II

問題概要

• 入力値は integerの配列 nums
• nums は昇順にソート済み
• nums を重複する要素が最大2回出現するように、重複要素を削除する
• nums のソート順は維持する（昇順のまま）
• 重複除去の結果は、nums の先頭部分に配置する
  • 重複を削除した後に k 個要素がある場合、nums の最初の k 要素を最終結果とする
  • k以降にどんな要素が残っていようと関係ない

例

Input: nums = [1,1,1,2,2,3]
Output: k = 5, nums = [1,1,2,2,3, x] xは何でも良い

問題URL：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/

解法1

真っ先に思いついたのはハッシュテーブルを使ってカウントする方法。

func removeDuplicates(nums []int) int {
    counter := map[int]int{}
    k := 0
    for _, v := range nums {
        counter[v]++
        if counter[v] <= 2 {
            nums[k] = v
            k++
        }
    }

    return k
}

解法2

解法1だと「nums は昇順にソート済み」の条件を活用しきれていない。昇順にソート済みなら、前後の要素を比較するだけで済むはず。

そこで、ハッシュテーブルを使わない方法を考えてみた。

1. 重複は最大2回許されるため、先頭の2要素は確定
2. 3個目の要素から重複チェックをしていく
3. 「昇順ソート済み」かつ「重複は2回まで許される」という条件より、2個前の要素と比較すれば「除去すべきか」を判断できる
4. e.g. [0, 1, 1, 1, 2] の nums[3] の1を除去するかどうかは、nums[1] と同値かを見れば良い
5. 除去対象外なら先頭から順に値を入れていく

func removeDuplicates(nums []int) int {
    if len(nums) < 3 { // 要素2個以下なら除去する要素はない
        return len(nums)
    }

    // 要素が3個以上の場合、ここにくる
    // 先頭2個は除去対象にはならないので、2個からスタート
    k := 2
    for i := 2; i < len(nums); i++ {
        if nums[i] != nums[k-2] {
            nums[k] = nums[i]
            k++
        }
    }

    return k
}

感想

解法1はすぐに思いついたが、2は15分かかった。
ただ、Submissionsを見ずに思いついたので少し成長を感じれた。

次は、5分で解法2を思いつけるようになりたい。

27. Remove Element

問題URL

https://leetcode.com/problems/remove-element/description/

解法1

シンプルにslices packageを使って解いた。

func removeElement(nums []int, val int) int {
    nums = slices.DeleteFunc(nums, func(n int) bool {
        return n == val
    })

    return len(nums)
}

標準ライブラリに任せただけ。これで終わりだとつまらないので、ライブラリの実装を見てみる。

func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
    //  del関数を満たす最初の要素のindexを返す。満たす要素が無ければ、-1
    // i は削除対象の最初の要素のindex
    i := IndexFunc(s, del)
    if i == -1 {
        return s
    }
    // Don't start copying elements until we find one to delete.
    // 削除対象の要素の次indexからループスタート
    // 削除対象外の要素がs[0:i] 間に来るように値を詰め替える
    for j := i + 1; j < len(s); j++ {
     
        if v := s[j]; !del(v) {
            s[i] = v
            i++
        }
    }
    clear(s[i:]) // zero/nil out the obsolete elements, for GC
    return s[:i] // 削除対象外の要素部分のみを返す
}

slices package DeleteFuncのソースコード

解法2

1. 削除対象外の要素のスライスを作る
2. copy で nums を上書く

func removeElement(nums []int, val int) int {
    filtered := make([]int, 0, len(nums))
    for _, v := range nums {
        if v != val {
            filtered = append(filtered, v)
        }
    }

    copy(nums, filtered)
    return len(filtered)
}

解法3

問題文には下記のように書いてある。

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.

• 削除対象外の要素が先頭に並んでいること
• 削除対象外の要素数を返すこと

上記2点さえ満たせば良いので、シンプルに次のようにするだけでOK。

func removeElement(nums []int, val int) int {
    k := 0
    for _, v := range nums {
        if v != val {
            nums[k] = v
            k++
        }
    }
    return k
}

感想

解法3は思いつかず、Solutionsで見つけた解法。 たったこれだけで済む問題だとは気づかなかった。まだまだ頭が硬い。

ただ、ぱっと解法3を思いつくよりも、 DeleteFunc の実装をササッと自前で書けるようになりたい。 slices packageのコードを見る良い機会になった。

（実務だと解法1で十分だからね... 😅）

88. Merge Sorted Array

問題URL

https://leetcode.com/problems/merge-sorted-array/description/

解法1

nums1とnums2をガッチャンコしてソートする。

func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1 = append(nums1[:m], nums2...)
    slices.Sort(nums1)
}

解法2

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order

問題文にある「nums1とnums2は昇順にソートされている」という条件を利用する。

nums1とnums2の末尾（大きい値）から順に、大小比較して並べていく。

func merge(nums1 []int, m int, nums2 []int, n int) {
    for n > 0 {
        if m == 0 || nums2[n-1] > nums1[m-1] {
            nums1[n+m-1] = nums2[n-1]
            n--
        } else {
            nums1[n+m-1] = nums1[m-1]
            m--
        }
    }
}

感想

計算量の少ない解法2を、パッと思いつけるようになりたい。