LeetCode周记 EP25

2024-12-16

字数统计: 1.5k字 | 阅读时长: 7分

前言

本周主题：记忆化搜索、最小堆、快速幂

题目：

241210每日一题—Knight Dialer
241214每日一题—Final Array State After K Multiplication Operations II
Knight Dialer

和上周的一道记忆化搜索的题目类似，每走一步可以变为规模更小的子问题，主要是找到递归状态。首先第一步打表，比较容易想到，然后定义原问题为$Q(n)$，则走一步后的问题规模变成了$Q(n-1)$，这一类问题一般可以抽象为这样。

记忆化搜索

这类问题的关键是找到状态定义，这类状态不仅要注意剩余部分，也要注意操作，由前序操作+剩余问题构成状态定义。状态的转移为原状态->操作->新状态。对于这道题来说，定义原问题的状态为：把马放在单元格$i$上，然后移动$n-1$步，一共有多少种移动方案？

假设$i=6, n=3$，则移动一步后的子问题状态为：把马放在单元格$6$上，然后移动$n-2=1$步，一共有多少种移动方案？

可以定义状态为$dfs(i, j)$，即把马放在单元格$i$上，然后移动$j$步，一共有多少种移动方案？枚举马能移动到的单元格 $k$, 问题变成: 把马放在单元格 $k$ 上, 然后移动 $j-1$ 步, 有多少种移动方案, 即 $d f s(k, j-1)$ 。

累加得

$d f s(i, j)=\sum_k d f s(k, j-1)$

2个参数可以用二维数组进行记忆化。
递归边界： $dfs(i, 0)=1$ 。无法移动, 算作一种移动方案, 对应格子$i$。
递归入口: $\sum_{i=0}^9 d f s(i, n-1)$, 这是原问题, 也是答案。对本体根据打表可以注意到 $d f s(5,n-1)=0$ 。

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int[][] NEXT = {
        {4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}
    };
    private static final int[][] memo = new int[10][5000];

    public int knightDialer(int n) {
        if (n == 1) {
            return 10;
        }
        int ans = 0;
        for (int i = 0; i < 10; i++) {
            ans = (ans + dfs(i, n-1)) % MOD;
        }
        return ans;
    }

    private int dfs(int i, int j) {
        if (j == 0) {
            return 1;
        }
        if (memo[i][j] > 0) { // 之前计算过
            return memo[i][j];
        }
        int res = 0;
        for (int k : NEXT[i]) {
            res = (res + dfs(k, j-1)) % MOD;
        }
        return memo[i][j] = res; // 记忆化
    }
}

Final Array State After K Multiplication Operations II

根据选择元素的规则，在值相同时要考虑下标靠前的元素，因此应将值与下标组合存储。随后就是利用最小堆进行模拟，这一步可以直接模拟如下：

// author: SilenceZheng66
class Solution {
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if (multiplier == 1) {
            return nums;
        }
        int n = nums.length;
        long m = 1000000007L;
        PriorityQueue<long[]> v = new PriorityQueue<>((x, y) -> {
            if (x[0] != y[0]) {
                return Long.compare(x[0], y[0]);
            } else {
                return Long.compare(x[1], y[1]);
            }
        });
        for (int i = 0; i < n; i++) {
            v.offer(new long[]{nums[i], i});
        }
        for (; k > 0; k--) {
            long[] x = v.poll();
            x[0] *= multiplier;
            x[0] %= m;  // 这一步不加则存在单元素数组case无法通过
            v.offer(x);
        }
        for (int i = 0; i < n; i++) {
            long[] x = v.poll();
            nums[(int)x[1]] = (int)(x[0] % m);
        }
        return nums;
    }
}

这种模拟存在一些问题：

乘法运算后直接取模会影响最小数的判断；
x[0] *= multiplier和x[0] %= m;部分可基于数学规律优化；
k较大时，可以由快速幂算法加速计算；

最小堆+快速幂

假如数组中的所有数都处于这样一个范围[a, b]，其中b是nums数组中的最大值，而a 是 (b - 1) / multiplier + 1，这个范围的含义是其中任何一个数乘以 multiplier 都会大于等于原数组最大值b，也就是说对于当前最小数x，乘完multiplier之后不会被连续再乘以multiplier。

对于操作次数 k 的分配是按下标从小到大一个一个依次分配，不断循环直达 k 分配完，令t1 = k / n, t2 = k % n，对于下标小于 t2 的数，会被分配到 t1 + 1 次，而大于大于 t2 的下标会被分配到 t1 次。

那么接下来就是考虑怎么把原数组过渡到这么一个范围了，通过优先队列，不断分配，因为这个范围的上界是数组的最大值，所以在采用优先级队列分配 k 时不用进行取模运算。分配直到

如果在将数组全部扩大到范围 [a, b] 之后 k >= 0，则直接可以得出每个数组中每个数字应该被分配的次数，通过快速幂计算出最后的结果即可。

以上思路来源于RnFreno。

class Solution {
    private long quickMul(long x, long y, long m) {
        long res = 1;
        while (y > 0) {
            if ((y & 1) == 1) {
                res = (res * x) % m;
            }
            y >>= 1;
            x = (x * x) % m;
        }
        return res;
    }

    public int[] getFinalState(int[] nums, int k, int multiplier) {
        if (multiplier == 1) {
            return nums;
        }
        int n = nums.length, mx = 0;
        long m = 1000000007L;
        PriorityQueue<long[]> v = new PriorityQueue<>((x, y) -> {
            if (x[0] != y[0]) {
                return Long.compare(x[0], y[0]);
            } else {
                return Long.compare(x[1], y[1]);
            }
        });
        for (int i = 0; i < n; i++) {
            mx = Math.max(mx, nums[i]);
            v.offer(new long[]{nums[i], i});
        }
        for (; v.peek()[0] <= (mx-1)/multiplier + 1 && k > 0; k--) {
            long[] x = v.poll();
            x[0] *= multiplier;
            v.offer(x);
        }
        for (int i = 0; i < n; i++) {
            long[] x = v.poll();
            int t = k / n + (i < k % n ? 1 : 0);
            nums[(int)x[1]] = (int)((x[0] % m) * quickMul(multiplier, t, m) % m);
        }
        return nums;
    }
}

参考文献

[1] https://leetcode.cn/problems/knight-dialer/solutions/3004116/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-x06l/?envType=daily-question&envId=2024-12-10
[2] https://leetcode.cn/problems/final-array-state-after-k-multiplication-operations-ii/solutions/2892178/zui-xiao-dui-mo-ni-shu-xue-gong-shi-pyth-z4zw/?envType=daily-question&envId=2024-12-14

后记

首发于 silencezheng.top，转载请注明出处。

前言

Knight Dialer

记忆化搜索

Final Array State After K Multiplication Operations II

最小堆+快速幂

参考文献

后记