Construct Target Array With Multiple Sums(Hard. LeetCode daily question 6/24)

はじめに

初めての記事なので、色々ご容赦ください。

今後自分がやりたい仕事をするために引き続きアルゴリズム問題をやる方がいいかもと、今回の問題は面白くて共有したいと思った。
それとともに、ただのアルゴリズム問題をやるのがちょっと足りない感じはするので、感想と考えたことをまとめて記事の形でいいかもしれないのでQiita始めました！！
(日本語はまだ色々勉強する必要があると思うが）

問題文

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < n and set the value of arr at index i to x.
• You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

英語が苦手の方は以下で：
配列targetではn個のintergerを含まれている。開始配列arrとしてのn個の1が含まれている配列から、次の原則にしたがって結果を導く。

• xを現在の配列の全要素和として
• 開始配列arrに対して、インデクス i(0 <= i < n )を選んで、値xを代わりに入れる。
• 何回のloopが必要かもしれない。

もし配列arrから何回を繰り返して、targetになることができれば、return true。逆に、return false。

入力サンプルと予想の結果

例1

Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

例2

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

考え方

問題読んだら、すぐ考えたのが：

• 次に追加した値は、現時点arrの全体値の和になること。
• 正方向（1から目標）より逆方向(目標から１)の方が簡単で計算ができる。その原因は、indexの選択が簡単であること。（例えば、一番大きい数字から取り出す）
• 逆方向の考え方で実現すると、毎回数列の中の一番大きい値を取って処理するので、PriorityQueueで効率よく簡単に実現できる。

一応、Golangで解答しようと思うけど、以下の問題点があります。

• GolangでのPriorityQueue
  GolangではC++などの言語と違って、PriorityQueueが入っていないので、自分で構築しなければならない。
  何か簡単な方法があるかなと思いつつ調べたら、PriorityQueueは用意されていないだが、heapには用意されている。
  "container/heap"を利用すればPriorityQueueを簡単に作ることができる。
  参考>>heap-golang
  
• isPossibleメソッドの書き方
  heapからPriorityQueueの生成。
  target数列の和(sum)を計算して、target数列の中の要素をPriorityQueueの中で追加。
  loopの止め条件としては、matrix内である全部の要素和が1より小さい、もしくはPriorityQueueのtopがsum/2より小さい時。
  最初の数列ではlen(matrix)=n個の1で形成したので、上記loopで得られたsumがlen(matrix)と同じであれば可能と判定ができる。

解答例

最後に解答例を共有します。

Construct Target Array With Multiple Sums

//heapを使うためにメソッドを作り出す
type PriorityQueue []int

//長さを獲得できるメソッド
func (pq PriorityQueue) Len() int {
    return len(pq)
}
//heapで使う時に比較する必要があります。
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i] > pq[j]
}

//heapを使うためのPushメソッド
func (pq *PriorityQueue) Push(x interface{})  {
    *pq = append(*pq, x.(int))
}

//heapを使うためのPopメソッド
func (pq *PriorityQueue) Pop () interface{} {
    old := *pq
    n := len(old)
    top := old[n-1]
    old[n-1] = 0
    *pq = old[0 : n-1]
    return top
}

//heapを使うためのSwapメソッド、二つの要素を交換することができる
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func isPossible(target []int) bool {
    sum := 0
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    //sum計算
    for _, val := range target {
        sum += val
        heap.Push(&pq, val)
    }
    
    for (sum>1) && (pq[0] > sum/2) {
        //一番大きい値を取り出してdurで保存
        dur := heap.Pop(&pq).(int)
        //現在のsumから対応の値をひく
        sum -= dur
        //特殊状況の判断
        if sum <=1 {
            return sum == 1
        }
        //durの代わりに数列に入る値をdur%sumにより計算して
        //数列の中に入る
        heap.Push(&pq, dur%sum)
        sum+= dur%sum
        
    }
    return sum == pq.Len()
}

結果

両方100のは気持ちよかったｗ。

ちなみに、C++で同じアルゴリズムでやったですが、性能はGolangより2倍ぐらい悪かった…

参照元

[Java/C++] O(n) Solution (Reaching Points)