例题

1. 丑数

描述

思路
三指针，指向最小值的向前移动。
代码
Python代码:

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        q = [1]
        i, j, k = 0, 0, 0
        for _ in range(n-1):
            t = min(q[i] * 2, q[j] * 3, q[k] * 5)
            q.append(t)
            if q[i] * 2 == t:
                i += 1
            if q[j] * 3 == t:
                j += 1
            if q[k] * 5 == t:
                k += 1
        return q[-1]

c++代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> q(1, 1);
        int i=0, j=0, k = 0;
        while (-- n) {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if (t == q[i] * 2) i++;
            if (t == q[j] * 3) j++;
            if (t == q[k] * 5) k++;
        }
        return q.back();
    }
};

Java代码：

class Solution {
    public int nthUglyNumber(int n) {
        List<Integer> q = new ArrayList<>();
        q.add(1);
        int i = 0, j = 0, k = 0;
        while (n > 1) {
            int t = Math.min(q.get(i) * 2, Math.min(q.get(j)* 3, q.get(k) * 5));
            q.add(t);
            if (q.get(i) * 2 == t) i++;
            if (q.get(j) * 3 == t) j++;
            if (q.get(k) * 5 == t) k++;
            n--;
        }
        return q.get(q.size() - 1);
    }
}

2. 最大公约数

C++代码：

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

Java代码：

public static int gcd(int a, int b) {
        return b > 0? gcd(b, a % b) : a;
    }

Python代码：

def gcd(a, b):
    return gcd(b, a % b) if b else a

3. 最小公倍数

Java代码：

public static int gcd(int a, int b) {
        return b > 0? gcd(b, a % b) : a;
    }
public static int lcm(int a , int b) {
    return a * b / gcd(a, b);
}

Python代码：

def gcd(a, b):
    return gcd(b, a % b) if b else a


def lcm(a, b):
    return a * b // gcd(a, b)

4. 判断质数

Python代码：

def is_prime(a):
    if a < 2:
        return False
    for i in range(2, a // 2 + 1):
        if a % i == 0:
            return False
    return True

Java代码：

public static boolean isPrime(int a) {
        if (a < 2) return false;
        for (int i = 2; i < a / 2 + 1; i++) {
            if (a % i == 0) return false;
        }
        return true;
    }

5. 判断闰年

Python代码：

def is_leap(year):
    if year % 4 == 0 and year % 100 != 0 or year % 400 == 0:
        return True
    return False

6. 快速幂

c++代码：

// 求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

Java代码：

public static int mul(int m, int k, int p) {
        int res = 1 % p;
        while (k > 0) {
            if ((k & 1) == 1) {
                res = res * m % p;
            }
            m = m * m % p;
            k >>= 1;
        }
        return res;
    }

Python代码：

def mul(m, k, p):
    res = 1 % p
    t = m
    while k:
        if k & 1:
            res = res * t % p
        t = t * t % p
        k >>= 1
    return res