Leetcode刷題學習筆記–Math數學解法

Code snippet

pow with modulo









int modPow(long long x, long long y)
{
    if (y == 0)
        return 1;
    long long p = modPow(x, y / 2);
    p = (p * p) % mod;
    return y % 2 ? (p * (x % mod)) % mod : p;
}

Problems

1969. Minimum Non-Zero Product of the Array Elements

這題的重點是實現pow with mod.


































class Solution {
    int mod = 1e9 + 7;
public:
    int modPow(long long x, long long y)
    {
        if (y == 0)
            return 1;
        long long p = modPow(x, y / 2);
        p = (p * p) % mod;
        return y % 2 ? (p * (x % mod)) % mod : p;
    }
    int minNonZeroProduct(int p) {
        long long cnt = ((1ll << p) - 1) % mod;
        return cnt * modPow(cnt - 1, cnt / 2) % mod;
    }
};
/*
p = 4, 2^4 - 1 = 15 -> 0b1111
0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
        |_____|_____|_____|_____|_____|_____|_____|_____|_____|_____|______| 0001, 1110
              |_____|_____|_____|_____|_____|_____|_____|_____|_____| 0001, 1110
                    |_____|_____|_____|_____|_____|_____|_____| 0001, 1110
                          |_____|_____|_____|_____|_____| 0001, 1110
                                |_____|_____|_____| 0001, 1110
                                      |_____| 0001, 1110

    (2^p - 1) * (2^p - 2) / 2 * (2^p - 2)
    (2^p - 1) * pow(2^p - 2, (2^p - 1) / 2)

    pow(14, 8) = (14 * 14) * (14 * 14) * (14 * 14) * (14 * 14)
                 ---------------------   ---------------------
               =  pow(14, 4) * pow(14, 4)
*/

441. Arranging Coins(Easy)

給你n個硬幣，試問可以排出幾階的樓梯形狀。例如n=8只可以排出3階樓梯。
staircase

解題思路

記得某種解題方法是，如果沒有好的想法，就先想一下special case。
這邊的special case是，如果給你的n剛好可以排出staircase則會是幾階？
因為staircase的總數為(1+2+3+…)的等差級數所以可以用下面的公式
\[ n = {(1+m)*m \over 2} = {{1 \over 2}m^2 + {1 \over 2}m} \]
所以要得到幾階的m就是解一元二次方程式。
\[ x = {-b \pm \sqrt{b^2-4ac} \over 2a}. \]
所以
\[ m = {-{1 \over 2} + \sqrt{{1 \over 2}^2 + 2 *n}} \]

程式碼：




int arrangeCoins(int n) {
    return sqrt(0.25 + 2.0 * n) - 0.5;
}
tags: leetcode 刷題
Select a repo