标签： 数学

目标

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

• 'N'：向北移动 1 个单位。
• 'S'：向南移动 1 个单位。
• 'E'：向东移动 1 个单位。
• 'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

示例 1：

输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
移动操作 位置 (x, y) 曼哈顿距离 最大值
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

说明：

• 1 <= s.length <= 10^5
• 0 <= k <= s.length
• s 仅由 'N'、'S'、'E' 和 'W' 。

思路

从原点 (0, 0) 出发，根据操作序列 s 朝四个方向移动，最多可以修改序列中 k 个方向，求能够到达的距离原点的最大曼哈顿距离。

遍历过程中记录距离变小的次数，每修改一次可以使得最大距离加 2。

网友指出每走一步可能增大的距离最多为 2 * k，但是不能超过往一个方向一直走的情况，即当前走的步数 i + 1。

代码

/**
 * @date 2025-06-20 21:47
 */
public class MaxDistance3443 {

    private static final Map<Character, int[]> MAP = new HashMap<>();

    static {
        MAP.put('N', new int[]{0, 1});
        MAP.put('S', new int[]{0, -1});
        MAP.put('E', new int[]{1, 0});
        MAP.put('W', new int[]{-1, 0});
    }

    public int maxDistance(String s, int k) {
        int res = 0;
        int d = 0;
        int prev = 0;
        int backCnt = 0;
        int[] curPos = new int[]{0, 0};
        char[] move = s.toCharArray();
        for (char dir : move) {
            prev = d;
            int[] delta = MAP.get(dir);
            int dx = delta[0];
            int dy = delta[1];
            curPos[0] += dx;
            curPos[1] += dy;
            d = Math.abs(curPos[0]) + Math.abs(curPos[1]);
            if (prev > d) {
                backCnt++;
            }
            res = Math.max(res, d + Math.min(backCnt, k) * 2);
        }
        return res;
    }
}

性能

目标

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

输入：n = 5, limit = 2
输出：3
解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

示例 2：

输入：n = 3, limit = 3
输出：10
解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

说明：

• 1 <= n <= 10^6
• 1 <= limit <= 10^6

思路

将 n 颗糖果分给 3 位小朋友，每个小朋友分到的糖果数量不超过 limit，求分配的方案数。注意，糖果必须分完，比如示例 1，不存在分得糖果数量为 0 的情况。

• 第一个小朋友分到的糖果数为 a ∈ [0, Math.min(n, limit)]
• 第二个小朋友分到的糖果数为 b ∈ [Math.max(0, n - a - limit), Math.min(n - a, limit)]
• 第三个小朋友分到的糖果数为 n - a - b

代码

/**
 * @date 2025-06-01 21:49
 */
public class DistributeCandies2929 {

    public long distributeCandies(int n, int limit) {
        long res = 0L;
        for (int i = 0; i <= Math.min(n, limit); i++) {
            if (n - i > 2 * limit) {
                continue;
            }
            res += Math.min(n - i, limit) - Math.max(0, n - i - limit) + 1;
        }
        return res;
    }
}

性能

目标

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 

说明：

• 1 <= n, k <= 50

思路

定义 k-avoiding 数组是由不同的正整数组成，并且任意两个元素的和不等于 k 的数组。求长度为 n 的 k-avoiding 数组的最小和。

构造一个长度为 n 的正整数数组，要使和最小，需要从 num = 1 开始选，跳过 k - num。

网友指出可以使用等差数列求和来计算，第一部分是 1 ~ m, m = min(k / 2, n) 和为 m * (m + 1) / 2，第二部分是 k ~ k + n - m - 1，和为 (n - m) * (2 * k + n - m - 1) / 2。

代码

/**
 * @date 2025-03-26 0:13
 */
public class MinimumSum2829 {

    public int minimumSum(int n, int k) {
        int res = 0;
        int length = 0;
        int num = 1;
        Set<Integer> avoiding = new HashSet<>();
        while (length < n) {
            if (avoiding.contains(num)) {
                num++;
                continue;
            }
            if (num < k) {
                avoiding.add(k - num);
            }
            length++;
            res += num;
            num++;
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的 最小 可能长度。

同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。

示例 1：

输入：s = "abba"
输出：2
解释：
一个可能的字符串 t 为 "ba" 。

示例 2：

输入：s = "cdef"
输出：4
解释：
一个可能的字符串 t 为 "cdef" ，注意 t 可能等于 s 。

说明：

• 1 <= s.length <= 10^5
• s 只包含小写英文字母。

思路

字符串 s 由某个字符串 t 以及若干（可以为0） t 的同位字符串 连接 而成，返回字符串 t 最小的可能长度。同位字符串指构成字符串的字符分布完全相同，换句话说就是不同字符的种类与数量完全相同。

特别注意该题与字串的顺序有关，比如 aabb 并不能由 ab 拼接而来，它的同位字符串是 ab 和 ba，只能构成 abba abab baab baba。

注意到子串的长度 length 一定能够被 s.length 整除。将字符串截成 k 个长度为 length 的子字符串，通过计算这些子字符串的字母个数，判断是否是同位字符串，从小到大遍历因数 length，取最小的即可。

代码

/**
 * @date 2024-12-20 9:08
 */
public class MinAnagramLength3138 {

    public int minAnagramLength_v1(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        Map<Integer, int[]> possibleLength = new LinkedHashMap<>();
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            cnt[c]++;
            int length = i + 1;
            if (n % length == 0) {
                int[] composition = new int[26];
                System.arraycopy(cnt, 0, composition, 0, 26);
                possibleLength.put(length, composition);
            }
        }
        char[] chars = s.toCharArray();
        for (Map.Entry<Integer, int[]> entry : possibleLength.entrySet()) {
            int length = entry.getKey();
            if (length == n) {
                return n;
            }
            int[] composition = entry.getValue();
            int loop = n / length;
            boolean find = true;
            here:
            for (int i = 0; i < loop; i++) {
                int[] tmp = new int[26];
                System.arraycopy(composition, 0, tmp, 0, 26);
                for (int j = 0; j < length; j++) {
                    int c = chars[i * length + j] - 'a';
                    tmp[c]--;
                    if (tmp[c] < 0) {
                        find = false;
                        break here;
                    }
                }
            }
            if (find) {
                return length;
            }
        }
        return n;
    }

}

性能

目标

象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。

象棋骑士可能的移动方式如下图所示:

我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。

给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。

你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。

因为答案可能很大，所以输出答案模 10^9 + 7.

示例 1：

输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。

示例 2：

输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

示例 3：

输入：n = 3131
输出：136006598
解释：注意取模

说明：

• 1 <= n <= 5000

思路

有一个电话键盘，布局如下：

1  2  3
4  5  6
7  8  9
*  0  #

开始时，将一个骑士棋子放在数字键上，然后按照国际象棋骑士的走法（类似于中国象棋里的马）走 n - 1 步，问能够组成多少种长度为 n 的不同号码（不能走到 * 和 #）。

这道题与 688.骑士在棋盘上的概率 类似，只不过棋盘更小，状态转移是确定的。

定义 dp[k][i] 表示以 i 结尾长度为 k 的号码组合数。初始时，dp[1][i] 均为 1。状态转移方程，针对不同的数字有所不同，例如 dp[k][1] = dp[k - 1][8] + dp[k - 1][6]，dp[k][4] = dp[k - 1][3] + dp[k - 1][9] + dp[k - 1][0]等等。

1 - 6 - 7
|   |   |
8   0   2
|   |   |
3 - 4 - 9

仔细分析可以得到上面的状态转化图，1 3 7 9 的结果是完全相同的，同理 2 8 也可以认为是一个状态，4 6 是一个状态，0 是一个状态。定义以上 4 个状态为 a b c d，那么最终结果可以表示为 4 * dp[n][a] + 2 * dp[n][b] + 2 * dp[n][c] + dp[n][d]，状态转移方程为：

• dp[k][a] = dp[k - 1][b] + dp[k - 1][c]
• dp[k][b] = 2 * dp[k - 1][a]
• dp[k][c] = 2 * dp[k - 1][a] + dp[k - 1][d]
• dp[k][d] = 2 * dp[k - 1][c]

注意 k 的初值为 2，k == 1 是特殊情况，骑士可以在数字 5，但是无法继续移动。dp[2][a] = 2, dp[2][b] = 2, dp[2][c] = 3, dp[2][d] = 2

如果写成矩阵的形式 列向量 dp[k] 等于 A · dp[k - 1]，其中矩阵 A 为：

0 1 1 0
2 0 0 0
2 0 0 1
0 0 2 0

因此 dp[n] = A^(n - 1) · dp[1]，其中 dp[1] = [1, 1, 1, 1]。我们可以使用矩阵的快速幂求解。

代码

/**
 * @date 2024-12-10 9:39
 */
public class KnightDialer935 {

    public static int mod = 1000000007;

    public int knightDialer_v3(int n) {
        if (n == 1) {
            return 10;
        }
        long[][] A = new long[][]{
                {0, 1, 1, 0},
                {2, 0, 0, 0},
                {2, 0, 0, 1},
                {0, 0, 2, 0},
        };
        A = pow(A, n - 1);
        long[] res = new long[4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                res[i] += A[i][j];
            }
        }
        return (int) ((4 * res[0] + 2 * res[1] + 2 * res[2] + res[3]) % mod);
    }

    public long[][] pow(long[][] A, int exponent) {
        long[][] res = new long[][]{
                {1, 0, 0, 0},
                {0, 1, 0, 0},
                {0, 0, 1, 0},
                {0, 0, 0, 1},
        };
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                res = mul(A, res);
            }
            A = mul(A, A);
            exponent >>= 1;
        }
        return res;
    }

    public long[][] mul(long[][] A1, long[][] A2) {
        long[][] res = new long[4][4];
        for (int i = 0; i < 4; i++) {
            for (int k = 0; k < 4; k++) {
                if (A1[i][k] == 0) {
                    continue;
                }
                for (int j = 0; j < 4; j++) {
                    res[i][j] = (res[i][j] + A1[i][k] * A2[k][j]) % mod;
                }
            }
        }
        return res;
    }

    public static long[][] dp;
    public static int MAX = 5001;

    static {
        dp = new long[MAX][4];
        dp[2][0] = 2;
        dp[2][1] = 2;
        dp[2][2] = 3;
        dp[2][3] = 2;
        for (int k = 3; k < MAX; k++) {
            dp[k][0] = (dp[k - 1][1] + dp[k - 1][2]) % mod;
            dp[k][1] = (2 * dp[k - 1][0]) % mod;
            dp[k][2] = (2 * dp[k - 1][0] + dp[k - 1][3]) % mod;
            dp[k][3] = (2 * dp[k - 1][2]) % mod;
        }
    }

    public int knightDialer_v2(int n) {
        if (n == 1) {
            return 10;
        }
        return (int)((4 * dp[n][0] + 2 * dp[n][1] + 2 * dp[n][2] + dp[n][3]) % mod);
    }

    public int knightDialer_v1(int n) {
        long[][] dp = new long[n + 1][10];
        dp[1] = new long[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int MOD = 1000000007;
        int res = 0;
        for (int k = 2; k <= n; k++) {
            dp[k][0] = (dp[k - 1][4] + dp[k - 1][6]) % MOD;
            dp[k][1] = (dp[k - 1][6] + dp[k - 1][8]) % MOD;
            dp[k][2] = (dp[k - 1][7] + dp[k - 1][9]) % MOD;
            dp[k][3] = (dp[k - 1][4] + dp[k - 1][8]) % MOD;
            dp[k][4] = (dp[k - 1][3] + dp[k - 1][9] + dp[k - 1][0]) % MOD;
            dp[k][6] = (dp[k - 1][1] + dp[k - 1][7] + dp[k - 1][0]) % MOD;
            dp[k][7] = (dp[k - 1][2] + dp[k - 1][6]) % MOD;
            dp[k][8] = (dp[k - 1][1] + dp[k - 1][3]) % MOD;
            dp[k][9] = (dp[k - 1][2] + dp[k - 1][4]) % MOD;
        }
        for (int i = 0; i < 10; i++) {
            res = (int) (res + dp[n][i]) % MOD;
        }
        return res;
    }

}

性能