leetcode weekly contes 362

T4 比较难的题目了，其余的前三题算是中规中距的题目，思考性还是挺不错的题目。

8029. 与车相交的点

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

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

示例 1：

输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

示例 2：

输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。

提示：

1 <= nums.length <= 100
nums[i].length == 2
1 <= starti <= endi <= 100

地址

https://leetcode.cn/contest/weekly-contest-362/problems/points-that-intersect-with-cars/

题意

排序 + 区间合并

思路

简单题目，可以直接暴力遍历即可，也可以排序后，再进行简单的区间合并。
复杂度分析：

时间复杂度：$O(n \ log n)$，其中 $n$ 为字符串的长度。
空间复杂度：$O(\log n)$。

代码

[sol1-C++]

class Solution {
public:
    int numberOfPoints(vector<vector<int>>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int start = 0, end = 0;
        for (auto v : nums) {
            if (v[0] > end) {
                ans += end - start;
                start = v[0];
                end = v[1] + 1;
            } else {
                end = max(end, v[1] + 1);
            }
        }
        ans += end - start;
        return ans;
    }
};

8049. 判断能否在给定时间到达单元格

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

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

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

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

示例 1：

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

示例 2：

输入：sx = 3, sy = 1, fx = 7, fy = 3, t = 3
输出：false
解释：从单元格 (3, 1) 开始出发，穿过上图标注的单元格，至少需要 4 秒后到达单元格 (7, 3) 。 因此，无法在 3 秒后到达单元格 (7, 3) 。

提示：

1 <= sx, sy, fx, fy <= 109
0 <= t <= 109

地址

https://leetcode.cn/contest/biweekly-contest-112/problems/check-if-strings-can-be-made-equal-with-operations-ii/

题意

数学问题

思路

由于每一步可以往 $8$ 个不同的方向走，因此题目就变得非常容易了，我们可以知道如下信息：
- 在 $x$ 轴方向至少需要走 $|sx - fx|$ 步；
- 在 $y$ 轴方向至少需要求 $|sy - fy|$ 步；
因此当如果 $t < |sx - fx|$ 或者 $t < |sy - fy|$ 时则一定不能满足题目要求，因此遇到这样情况直接返回。由于它可以向八个不同的方向行走，因此可以一直绕着外围转圈即可，特殊情况需要对待的时，当 $sx = fx, sy = fy$ 时，且当去 $t = 1$ 时，此时它向外走一步则无法返回远点，这种情况需要返回 $false$;
复杂度分析：

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int x = abs(sx - fx);
        int y = abs(sy - fy);
        if (x == 0 && y == 0) {
            return t != 1;
        }
        if (x > t || y > t) {
            return false;
        }
        return true;
    }
};

100030. 将石头分散到网格图的最少移动次数

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

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

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

示例 1：

输入：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 。

示例 2：

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

提示：

grid.length == grid[i].length == 3
0 <= grid[i][j] <= 9
grid 中元素之和为 9 。

地址

https://leetcode.cn/contest/weekly-contest-362/problems/minimum-moves-to-spread-stones-over-grid/

题意

状态压缩 + 动态规划

思路

设矩阵中每个格子多余出来的数目为 $n$ 个，即假设当前 $(i,j)$ 中有 $grid[i][j]$ 个石头，则多出来的石头数目为 $grid[i][j] - 1$ 个，则可以知道总共需要移动 $n$ 个石头，空的格子也为 $n$ 个，此时最小代价即可将这 $n$ 个石头移动到 $n$ 个空位的最小代价。此时设 $dp[i][j]$ 将表示将前 $i$ 个石头移动到分布状态为 $j$ 的最小代价，此时第 $i$ 个石头需要在分布为 $j$ 的格子中任意选择一个放下即可，

此时可以知道递推公式为:
$$
dp[i][j] = \min(dp[i][j], dp[i-1][j \oplus 2^k] + cost(i,k)
$$
其中 $cost(i,k)$ 表示第 $i$ 个石头与第 $k$ 个空格之间的曼哈顿距离。
复杂度分析：

时间复杂度：$O(n \times 2^n)$，其中 $n$ 表示空格子的总数目；
空间复杂度：$O(n \times 2^n)$，其中 $n$ 表示空格子的总数目；

代码

class Solution {
public:
    using pii = pair<int, int>;
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pii> arr1;
        vector<pii> arr2;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] == 0) {
                    arr1.emplace_back(i, j);
                }
                if (grid[i][j] > 1) {
                    for (int k = 1; k < grid[i][j]; k++) {
                        arr2.emplace_back(i, j);
                    }
                }
            }
        }

        auto cost = [](pii a, pii b) {
            return abs(a.first - b.first) + abs(a.second - b.second);
        };

        int n = arr1.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < (1 << n); i++) {
            int x = __builtin_popcount(i);
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    dp[i] = min(dp[i], dp[i ^ (1 << j)] + cost(arr2[x - 1], arr1[j]));
                }
            }
            
        }
        return dp[(1 << n) - 1];
    }
};

8020. 字符串转换

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

将 s 长度为 l （0 < l < n）的 后缀字符串 删除，并将它添加在 s 的开头。
比方说，s = 'abcd' ，那么一次操作中，你可以删除后缀 'cd' ，并将它添加到 s 的开头，得到 s = 'cdab' 。

给你一个整数 k ，请你返回恰好 k 次操作将 s 变为 t 的方案数。

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

示例 1：

输入：s = "abcd", t = "cdab", k = 2
输出：2
解释：
第一种方案：
第一次操作，选择 index = 3 开始的后缀，得到 s = "dabc" 。
第二次操作，选择 index = 3 开始的后缀，得到 s = "cdab" 。

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

示例 2：

输入：s = "ababab", t = "ababab", k = 1
输出：2
解释：
第一种方案：
选择 index = 2 开始的后缀，得到 s = "ababab" 。

第二种方案：
选择 index = 4 开始的后缀，得到 s = "ababab" 。

提示：

2 <= s.length <= 5 * 105
1 <= k <= 1015
s.length == t.length
s 和 t 都只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-362/problems/string-transformation/

题意

KMP + 矩阵快速幂乘法

思路

近期遇到最难的题目了，还是有不少狠人把题目做出来，感觉还是比赛学的算法太少了，需要强化算法学习题目，当然部分有技巧的算法学习起来确实难度太大，不是特别好学。有两点需要分析：
- 什么样的字符可以通过移动后缀后两个字符串相等，则此时 $s$ 一定是 $t$ 的循环同构字符串才可以，即此时一定满足：
  $$
  s[0 \cdots i] = t[n-i\cdots n-1], s[i + 1 \cdots n - 1] = t[0,\cdots n - i -1]
  $$
  此时我们需要判断 $s$ 与 $t$ 之间存在多少个同构循环字符串，此时我们只需要检测 $s + s$ 中的连续子字符串有多少等于 $t$, 这个检测方法可以使用 $KMP$ 或者 $Karp-Robin$ 算法来检测子字符串是否相等，这个需要一定的技巧，，不过 $KR$ 算法确实是个好算法。
- 第二步则是计算经过 $k$ 步移动后，有多少方案数，假设经过 $x$ 步移动后，此时字符串 $s$ 一定有两个状态：要么处于等于 $t$ ，要么不等于 $t$, 此时我们假设经过 $i$ 步操作后，等于 $t$ 的方案数为 $g[i]$, 不等于 $t$ 的方案数为 $f[i]$, 假设 $s$ 有 $cnt$ 个同构循环字符串与 $t$ 相等，由于每次移动后缀的长度 $l$ 的取值范围为 $0 < l < n$ ，则此时意味如下：
  - 假设当前字符串 $s = t$ 时，有 $cnt - 1$ 种移动方案使得 $s$ 继续等于 $t$, 有 $n - cnt$ 种移动方案使得当前的 $s \neq t$；
  - 假设当前字符串 $s \neq t$ 时，有 $cnt$ 种移动方案使得 $s$ 继续等于 $t$, 有 $n - cnt-1$ 种移动方案使得当前的 $s \neq t$；
  - 根据以上推理可以知道递推公式:
    $$
    g[i] = g[i-1] \times (cnt - 1) + f[i - 1] \times cnt \
    f[i] = g[i-1] \times (n - cnt) + f[i- 1] \times (n - cnt - 1)
    $$
    根据以上递推公式可以将其变换为矩阵乘法如下：
    $$
    \begin{bmatrix}
    f[i] & g[i]
    \end{bmatrix}
    \begin{bmatrix}
    f[i-1] & g[i-1]
    \end{bmatrix}
    \times
    \begin{bmatrix}
    n - cnt - 1 & cnt\
    n - cnt & cnt - 1
    \end{bmatrix}
    $$
- 根据以上推理可以知道如下：
  $$
  \begin{bmatrix}f[k] & g[k]\end{bmatrix}= \begin{bmatrix}f[0] & g[0]\end{bmatrix}\times\begin{bmatrix}n - cnt - 1 & cnt\n - cnt & cnt - 1\end{bmatrix} ^ k
  $$
  此时我们即可使用矩阵的快速幂来解决此问题，矩阵的快速幂问题就比较简单的解法了，力扣上类似的题目非常多，非常值得学习和思考的题目，不过kmp 算法确实有一些难度。
复杂度分析：

时间复杂度: $O(n + \log k)$, 其中 $n$ 表示字符串的长度。
空间复杂度：$O(n)$，其中 $n$ 表示字符串的长度。

代码

class Solution {
public:
    constexpr static long long Mod = 1e9 + 7;
    constexpr static long long Base1 = 31;
    constexpr static long long Base2 = 97;
    using LL = long long;
    int numberOfWays(string s, string t, long long k) {
        int n = s.size();
        srand(time(NULL));

        /* Karp-Robin 字符串匹配算法 */
        long long h1 = 1LL, h2 = 1LL;
        long long g1 = 0, g2 = 0;
        long long c1 = 0, c2 = 0;
        for (int i = 0; i < n; i++) {
            int x = t[i] - 'a';
            int y = s[i] - 'a';
            h1 = (h1 * Base1) % Mod;
            h2 = (h2 * Base2) % Mod;
            g1 = (g1 * Base1 + x) % Mod;
            g2 = (g2 * Base2 + x) % Mod;
            c1 = (c1 * Base1 + y) % Mod;
            c2 = (c2 * Base2 + y) % Mod;
        }
        vector<int> valid(n, 0);
        for (int i = 0; i < n; i++) {
            int x = s[i] - 'a';
            if (c1 == g1 && c2 == g2) {
                valid[i] = 1;
            }
            c1 = (c1 * Base1 + x) % Mod;
            c2 = (c2 * Base2 + x) % Mod;
            c1 = (c1 - (h1 * x) % Mod + Mod) % Mod;
            c2 = (c2 - (h2 * x) % Mod + Mod) % Mod;
        }

        int tot = accumulate(valid.begin(), valid.end(), 0);
        vector<vector<LL>> mat(2, vector<LL>(2));
        mat[0][0] = n - tot - 1;
        mat[0][1] = tot;
        mat[1][0] = n - tot;
        mat[1][1] = tot - 1;
        auto res = matrixPow(mat, k);
        if (t == s) {
            return res[0][0];
        } else {
            return res[0][1];
        }
    }

    vector<vector<LL>> multiply(vector<vector<LL>> &a, vector<vector<LL>> &b) {
        int n = a.size();
        int m = a[0].size();
        int q = b[0].size();
        vector<vector<LL>> res(n, vector<LL>(q));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < q; j++) {
                for (int k = 0; k < m; k++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % Mod;
                }
            }
        }
        return res;
    };

    vector<vector<LL>> matrixPow(vector<vector<LL>> &a, long long k) {
        int n = a.size();
        vector<vector<LL>> res(n, vector<LL>(n, 0));
        for (int i = 0; i < n; i++) res[i][i] = 1LL;
        for (; k != 0; k >>= 1) {
            if (k & 1) {
                res = multiply(res, a);
            }
            a = multiply(a, a);
        }
        return res;
    };
};

class Solution {
public:
    constexpr static long long Mod = 1e9 + 7;
    constexpr static long long Base1 = 31;
    constexpr static long long Base2 = 97;
    using LL = long long;

    int numberOfWays(string s, string t, long long k) {
        int n = s.size();
        vector<int> pat = find_pattern(t, s + s.substr(0, n - 1));
        int tot = pat.size();
        vector<vector<LL>> mat(2, vector<LL>(2));
        mat[0][0] = n - tot - 1;
        mat[0][1] = tot;
        mat[1][0] = n - tot;
        mat[1][1] = tot - 1;
        auto res = matrixPow(mat, k);
        if (t == s) {
            return res[1][1] ;
        } else {
            return res[0][1];
        }
    }

    vector<vector<LL>> multiply(vector<vector<LL>> &a, vector<vector<LL>> &b) {
        int n = a.size();
        int m = a[0].size();
        int q = b[0].size();
        vector<vector<LL>> res(n, vector<LL>(q));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < q; j++) {
                for (int k = 0; k < m; k++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % Mod;
                }
            }
        }
        return res;
    }

    vector<vector<LL>> matrixPow(vector<vector<LL>> &a, long long k) {
        int n = a.size();
        vector<vector<LL>> res(n, vector<LL>(n, 0));
        for (int i = 0; i < n; i++) res[i][i] = 1LL;
        for (; k != 0; k >>= 1) {
            if (k & 1) {
                res = multiply(res, a);
            }
            a = multiply(a, a);
        }
        return res;
    }

    vector<int> find_pattern(const string& pattern, const string& text) {
        int n = pattern.size();
        int m = text.size();
        string t = pattern + "$" + text;
        vector<int> result;
        vector<int> prefix(m + n + 1, 0);
        
        int j = 0;
        for (int i = 1; i < t.size(); i++) {
            while (j > 0 && t[j] != t[i]) {
                j = prefix[j - 1];
            }
            if (t[i] == t[j]) {
                j++;
            } else {
                j = 0;
            }
            prefix[i] = j;
            if (i > n && prefix[i] == n) {
                result.push_back(i - 2 * n);
            }
        }
        return result;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcodeweekly contes 361 leetcode biweekly contes 112 →

扫描二维码，分享此文章