LeetCode Contest 362

8029. Points That Intersect With Cars

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

测试样例：

输入：nums = [[3,6],[1,5],[4,7]]

输出：7

解释：
从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

解答：搜索范围很小，没必要用困难写法。暴力计算。

class Solution {
    public int numberOfPoints(List<List<Integer>> nums) {
        boolean[] mem = new boolean[101];

        int res = 0;
        for (List<Integer> num : nums) {
            int st = num.get(0), ed = num.get(1);
            for (int i = st; i <= ed; ++i) {
                if (!mem[i]) {
                    mem[i] = true;
                    ++res;
                }
            }
        }
        return res;
    }
}

8049. Determine if a Cell Is Reachable at a Given Time

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。

在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你 必须 移动到任一与之前所处单元格相邻的单元格中。

如果你能在 恰好 t 秒 后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。

单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。

测试样例：

输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6

输出：true

解释：
从单元格 (2, 4) 开始出发，穿过上图标注的单元格，可以在恰好 6 秒后到达单元格 (7, 7) 。

解答：如果最短距离，t秒也无法到达，则返回false。否则特殊情况只有起始点和结束点一致的情况，如果这个时候t=1，则返回false。其他情况一律true。

class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int xdiff = Math.abs(fx - sx), ydiff = Math.abs(fy - sy);
        int max = Math.max(xdiff, ydiff);
        if (t < max) {
            return false;
        }
        if (xdiff == 0 && ydiff == 0) {
            return t != 1;
        } else {
            return true;
        }
    }
}

100030. Minimum Moves to Spread Stones Over Grid

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

测试样例

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]

输出：3

解释：
让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

解答：这道题目搜索范围相当小，直接暴力枚举9个石子放在9个格子的总移动次数，选择移动次数最少的选项。

class Solution {
    public int minimumMoves(int[][] grid) {
        int[] mem = new int[512];
        boolean isInitial = true;
        Arrays.fill(mem, Integer.MAX_VALUE);
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid.length; ++j) {
                while (grid[i][j] > 0) {
                    grid[i][j] -= 1;
                    if (isInitial) {
                        isInitial = false;
                        for (int k = 0; k < 9; ++k) {
                            mem[1 << k] = Math.abs((k / 3) - i) + Math.abs((k % 3) - j);
                        }
                    } else {
                        int[] nextMem = new int[512];
                        Arrays.fill(nextMem, Integer.MAX_VALUE);
                        for (int t = 0; t < 512; ++t) {
                            if (mem[t] != Integer.MAX_VALUE) {
                                for (int k = 0; k < 9; ++k) {
                                    int m = (t >> k) & 1;
                                    if (m == 0) {
                                        nextMem[t + (1 << k)] = Math.min(nextMem[t + (1 << k)]
                                                , mem[t] + Math.abs((k / 3) - i) + Math.abs((k % 3) - j));
                                    }
                                }
                            }
                        }
                        mem = nextMem;
                    }
                }
            }
        }
        return mem[511];
    }
}

8020. 字符串转换

给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作：

将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
比方说，s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。
给你一个整数 k ，请你返回 恰好 k 次操作将 s 变为 t 的方案数。

由于答案可能很大，返回答案对 10^9 + 7 取余 后的结果。

测试样例

输入：s = "abcd", t = "cdab", k = 2

输出：2

解释：
第一种方案：

• 第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。
• 第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。

第二种方案：

• 第一次操作，选择 index = 1 开始的后缀，得到 s = "bcda" 。
• 第二次操作，选择 index = 1 开始的后缀，得到 s = "cdab" 。

解答：这道题目分值8分，其实没想象中这么难。没注意到k的范围居然是10^15次方，一开始准备暴力算一下可能性，最后发现超时，然后实现折半搜索的时候时间来不及了。。。

这道题目需要思考到的第一问题是，当前字符串的长度为n，那么假设k是无限大的，那么总共可以转移到的可能性就是n种。第二个，当前字符串除了自己没办法变化，其他n-1种可能都可以变化到，一个例子：

• 输入abcde，那么所有的可能是abcde,bcdea,cedab,deabc,eabcde。当前abcde，除了abcde无法通过一步变化到，其他字符串都可以。

这个能想明白，那么题目就简化为当前等于target的字符串数和不等于target的字符串数。然后利用RollingHash判断一下，所有可能中的字符串有多少个等于target。那么假设等于target的是equMul个，不等于的就是n - equMul个。那么每次移动，可以产生

• 等于：nonEquCount equMul + equCount (equMul - 1)) % mod
• 不等于：(nonEquCount nonEquMul + equCount (nonEquMul + 1)) % mod;

由于k非常大，还需要利用一下折半搜索来快速找到k次结果。

class Solution {
    private class RollingHash61 {
        static final long mod = (1L << 61) - 1;
        public long M;
        public long[] pows;
        public long[] hs;
        public int hp;

        public RollingHash61(long M, int n) {
            assert M > 0;
            assert n > 0;
            this.M = M;
            this.pows = makePows(M, n);
            this.hs = new long[n + 1];
            this.hp = 0;
        }

        private long mul(long a, long b) {
            long al = a & (1L << 31) - 1, ah = a >>> 31;
            long bl = b & (1L << 31) - 1, bh = b >>> 31;
            long low = al * bl; // <2^62
            long mid = al * bh + bl * ah; // < 2^62
            long high = ah * bh + (mid >>> 31); // < 2^60 + 2^31 < 2^61
            // high*2^62 = high*2 (mod 2^61-1)
            long ret = mod(mod(2 * high + low) + ((mid & (1L << 31) - 1) << 31));
            return ret;
        }

        private long mod(long a) {
            while (a >= mod) a -= mod;
            while (a < 0) a += mod;
            return a;
        }

        private long[] makePows(long M, int n) {
            long[] ret = new long[n + 1];
            ret[0] = 1;
            for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], M);
            return ret;
        }

        public void add(long x) {
            hs[hp + 1] = mul(hs[hp], M) + x;
            if (hs[hp + 1] >= mod) hs[hp + 1] -= mod;
            hp++;
        }

        public long h(int l, int r) {
            assert l <= r;
            return mod(hs[r] - mul(hs[l], pows[r - l]));
        }
    }

    private static final int mod = 1_000_000_007;
    private HashMap<Long, long[]> equMap, nonEquMap;

    public int numberOfWays(String s, String t, long k) {
        int len = s.length();
        RollingHash61 h1 = new RollingHash61(mod, len), h2 = new RollingHash61(mod, len);
        equMap = new HashMap<>();
        nonEquMap = new HashMap<>();

        for (int i = 0; i < len; ++i) {
            h1.add(s.charAt(i));
            h2.add(t.charAt(i));
        }

        int equ = 0;
        for (int i = 0; i < len; ++i) {
            if (h1.h(0, i + 1) == h2.h(len - i - 1, len) && h1.h(i + 1, len) == h2.h(0, len - i - 1)) {
                ++equ;
            }
        }

        boolean isStartEqu = s.equals(t);

        long equCount = isStartEqu ? 1 : 0, nonEquCount = isStartEqu ? 0 : 1;
        int nonEquMul = len - 1 - equ;
        return (int) (cacheBinarySearch(equCount, nonEquCount, k, equ, nonEquMul)[0]);
    }

    private long[] cacheBinarySearch(long equCount, long nonEquCount, long k, int equMul, int nonEquMul) {
        if (equCount == 1) {
            if (!equMap.containsKey(k)) {
                equMap.put(k, binarySearch(equCount, nonEquCount, k, equMul, nonEquMul));
            }
            return equMap.get(k);
        } else {
            if (!nonEquMap.containsKey(k)) {
                nonEquMap.put(k, binarySearch(equCount, nonEquCount, k, equMul, nonEquMul));
            }
            return nonEquMap.get(k);
        }
    }

    private long[] binarySearch(long equCount, long nonEquCount, long k, int equMul, int nonEquMul) {
        if (k == 0) {
            return new long[]{equCount, nonEquCount};
        }

        long[] equMulArr = cacheBinarySearch(1, 0, k / 2, equMul, nonEquMul);
        long[] nonEquMulArr = cacheBinarySearch(0, 1, k / 2, equMul, nonEquMul);
        long[] res = {0,0};
        if (equCount == 1) {
            res[0] = (equMulArr[0] * equMulArr[0] + equMulArr[1] * nonEquMulArr[0]) % mod;
            res[1] = (equMulArr[0] * equMulArr[1] + equMulArr[1] * nonEquMulArr[1]) % mod;
        } else {
            res[0] = (nonEquMulArr[0] * equMulArr[0] + nonEquMulArr[1] * nonEquMulArr[0]) % mod;
            res[1] = (nonEquMulArr[0] * equMulArr[1] + nonEquMulArr[1] * nonEquMulArr[1]) % mod;
        }

        if (k % 2 == 1) {
            return new long[]{findNextEqu(res[0], res[1], equMul, nonEquMul), findNextNonEqu(res[0], res[1], equMul, nonEquMul)};
        } else {
            return res;
        }
    }

    private long findNextEqu(long equCount, long nonEquCount, int equMul, int nonEquMul) {
        return (nonEquCount * equMul + equCount * (equMul - 1)) % mod;
    }

    private long findNextNonEqu(long equCount, long nonEquCount, int equMul, int nonEquMul) {
        return (nonEquCount * nonEquMul + equCount * (nonEquMul + 1)) % mod;
    }
}