组合数学与排列

不同路径（LeetCode 62）

C(m+n-2, min(m,n)-1)，用滚动乘法避免溢出：

public int uniquePaths(int m, int n) {
    long result = 1;
    int k = Math.min(m-1, n-1);
    for (int i = 0; i < k; i++)
        result = result * (m + n - 2 - i) / (i + 1);
    return (int) result;
}

第 k 个排列（LeetCode 60）

康拓展开逐位确定：

public String getPermutation(int n, int k) {
    int[] fac = new int[n+1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
    List<Integer> digits = new ArrayList<>();
    for (int i = 1; i <= n; i++) digits.add(i);
    k--;
    StringBuilder sb = new StringBuilder();
    for (int i = n; i >= 1; i--) {
        int idx = k / fac[i-1];
        sb.append(digits.remove(idx));
        k %= fac[i-1];
    }
    return sb.toString();
}

下一个排列（LeetCode 31）

public void nextPermutation(int[] nums) {
    int n = nums.length, i = n-2;
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    if (i >= 0) {
        int j = n-1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i+1, n-1);
}