LeetCodeの復習(1)

Minimum Number of Operations to Move All Balls to Each Box

どんな問題？

• n個の箱が横一列に並んでいて、それぞれの箱の中には「ボールがある」または「ボールがない」という状態があります。

• 1回の操作では、隣り合う箱の間で「ボールを1つ動かす」ことができます。

• 、ある1つの箱に集めたいとき、を考えます。

• 全部のボールを「1番目の箱に集めるなら何回操作をすればよいか？」「2番目なら何回？」「3番目なら何回？」... というふうに、それぞれの最小操作回数を求めたいわけです。

考え方１ (私の回答)

• i番目の箱に集めるなら

  • ボールが入ってる箱[j]からi番目の箱までの距離を出す。abs(i - j)

  • そしてそれぞれを合計する。

function minOperations(boxes: string): number[] {
    const answer = new Array(boxes.length).fill(0)

    for (let i = 0; i < boxes.length; i++) {
        let count = 0
        for (let j = 0; j < boxes.length; j++) {
            if (i === j || boxes[j] === "0") {
                continue;
            }
            count += Math.abs(i - j);
        }
        answer[i] = count;
    }
    return answer;
};

考え方２(公式の回答1)

• i番目の箱に集めるのではなく、i番目の箱に入ってるボールがそれぞれj番目の箱に移動するなら何回操作が必要？を足していく

function minOperations(boxes: string): number[] {
    const answer = new Array(boxes.length).fill(0);

    for (let currentBox = 0; currentBox < boxes.length; currentBox++) {
        if (boxes[currentBox] === "1") {
            for (let newPosition = 0; newPosition < boxes.length; newPosition++) {
                answer[newPosition] += Math.abs(newPosition - currentBox);
            }
        }
    }
    return answer;
};

考え方3(公式の回答2)

• ボールが左側から動いてくるときにかかる操作回数」と「ボールが右側から動いてくるときにかかる操作回数」を、それぞれまとめて計算しよう！

• 1. 左側から来るボールの操作回数を調べる

  • 箱を 左から右へ 1つずつ見ていく

  • 今まで通り過ぎてきた箱の中にあるボールの数を数えておき、「この箱に来るまでに、ボールを何回動かしたか」という合計を毎回更新する

• 2. 右側から来るボールの操作回数を調べる

  • 今度は箱を 右から左へ 1つずつ見ていく

  • やり方は1と同じで、右にあるボールたちがこの箱まで動いてくるために必要な操作回数を合計していく

• 3. 左からの分と右からの分を足す

  • 1と2で計算した値を、それぞれの箱ごとに足し合わせると、「その箱にすべてのボールを集めるのに必要な操作回数」がわかる

function minOperations(boxes: string): number[] {
    const n = boxes.length;
    const answer = new Array(n).fill(0);

    let leftBallCount = 0;
    let rightBallCount = 0;
    let leftBallMove = 0;
    let rightBallMove = 0;

    for (let i = 0; i < n; i++) {
        answer[i] += leftBallMove;
        leftBallCount += Number(boxes[i])
        leftBallMove += leftBallCount;
        // ------------
        const j = n - 1 - i;
        answer[j] += rightBallMove;
        rightBallCount += Number(boxes[j])
        rightBallMove += rightBallCount;
    }
    
    return answer;
};

感想

考え方３の内容は正直何回読んでもわからんかった
ChatGPTにめっちゃ解説してもらって、やっとわかった
この考え方最初からできる人天才なんじゃないかって思った