LeetCode 解題紀錄 2550. Count Collisions of Monkeys on a Polygon

Count Collisions of Monkeys on a Polygon - LeetCode

題目

在 n 多邊形的每個頂點上各站了一隻猴子，每隻猴子可以任意往左或往右移動一個位置，在所有的移動方式中，要求返回有任何一次碰撞的總次數

條件

• 3 ≤ n ≤ 10⁹

觀察

• 每隻猴子有兩個選擇，所以總共移動方式有 2^n
• 不會發生碰撞的方式只有兩種，同時往左或同時往右，因此答案是 2^n -2
• 要計算 2 的 10⁹次方不能靠內建或是逐一乘上去

解法(Recursive + Memorize)

• 2⁸ 可以變成 2⁴ * 2⁴，2⁴ => 2²*2² .. 一直到 2⁰，透過 recursive 來減少計算次數
• 把計算過的結果儲存到 HashMap 中避免重複計算
• 需要小心取完餘數後減 2 可能變負數

class Solution {
    Map<Integer,Long> memo;
    int M = 1_000_000_007;
    public int monkeyMove(int n) {        
        memo = new HashMap();
        memo.put(0, 1L);
        int ans = (int)(fastPower(n)+M-2)%M;
        return ans;
    }

    long fastPower(int n) {        
        if(!memo.containsKey(n)) 
            memo.put(n, (fastPower(n/2)%M)*(fastPower(n/2)%M)*(n%2==1?2:1)%M);        
        return memo.get(n);        
    }

}

結果

TC：O(log n)

SC：O(n)