A 与车相交的点
数据范围小直接暴力枚举
class Solution {
public:
int numberOfPoints(vector <vector<int>> &nums) {
unordered_set<int> vis;
for (auto &p: nums)
for (int i = p[0]; i <= p[1]; i++)
vis.insert(i);
return vis.size();
}
};
B 判断能否在给定时间到达单元格
设起点和终点的横坐标之差的绝对值为 d x dx dx , 纵坐标之差的绝对值为 d y dy dy ,则最少需要的时间 m n mn mn 为 m a x ( d x , d y ) max(dx, dy) max(dx,dy),当起点终点不重合时只需要 t ≥ m n t\ge mn t≥mn 即可, 起点终点重合需要 t ≥ 2 t \ge 2 t≥2 或 t = 0 t = 0 t=0。
class Solution {
public:
bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
int dx = abs(sx - fx), dy = abs(sy - fy);
int mn = min(dx, dy) + max(dx, dy) - min(dx, dy);
if (mn != 0)
return t >= mn;
return t >= 2|| t == 0;
}
};
C 将石头分散到网格图的最少移动次数
枚举排列:将待移动的石子的坐标加入数组 s t a r t start start ,将没有石子的坐标加入数组 t a r g e t target target ,枚举 s t a r t start start 可能的排列,一种排列和 t a r g e t target target 对应一种移动方案。
class Solution {
public:
int minimumMoves(vector<vector<int>> &grid) {
vector<pair<int, int>> start, target;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i][j] >= 1) {
for (int k = 0; k < grid[i][j] - 1; k++)
start.emplace_back(i, j);
} else if (grid[i][j] == 0)
target.emplace_back(i, j);
sort(start.begin(), start.end());
int res = INT32_MAX;
do {
int t = 0;
for (int i = 0; i < start.size(); i++) {
t += abs(start[i].first - target[i].first) + abs(start[i].second - target[i].second);
if (t >= res)
break;
}
res = min(res, t);
} while (next_permutation(start.begin(), start.end()));
return res;
}
};
D 字符串转换
文章来源:https://www.toymoban.com/news/detail-706144.html
动态规划 + 字符串哈希 + 矩阵快速幂:设 c n t cnt cnt 为满足“将 s s s 的长为 l ( 0 ≤ l < n ) l(0\le l<n) l(0≤l<n) 的后缀移动到 s s s 的开头后 s = = t s==t s==t ” 的 l l l 的个数。设 p k p_k pk 为:恰好 k k k 次操作后 s s s 变为 t t t 的方案数,设 q k q_k qk 为:恰好 k k k 次操作后 s s s 不能变为 t t t 的方案数,因为题目要求操作的后缀长度 0 < l < n 0<l<n 0<l<n , 所以有矩阵形式的转移方程: [ p k q k ] = [ c n t − 1 c n t n − c n t n − c n t − 1 ] [ p k − 1 q k − 1 ] \begin{bmatrix} p_k\\ q_k \end{bmatrix}=\begin{bmatrix} cnt -1 & cnt\\ n-cnt & n-cnt-1 \end{bmatrix} \begin{bmatrix} p_{k-1}\\ q_{k-1} \end{bmatrix} [pkqk]=[cnt−1n−cntcntn−cnt−1][pk−1qk−1]
若 s = = t s==t s==t 则 [ p 0 , q 0 ] T = [ 1 , 0 ] T [p_0,q_0]^T=[1,0]^T [p0,q0]T=[1,0]T ,否则 [ p 0 , q 0 ] T = [ 0 , 1 ] T [p_0,q_0]^T=[0,1]^T [p0,q0]T=[0,1]T,设转移方程中的方阵为 A A A ,则有 [ p k , q k ] T = A k [ p 0 , q 0 ] T [p_k,q_k]^T=A^k[p_0,q_0]^T [pk,qk]T=Ak[p0,q0]T ,通过矩阵快速幂求 A k A^k Ak 。文章来源地址https://www.toymoban.com/news/detail-706144.html
class Solution {
public:
using ll = long long;
using type_mat = vector<vector<ll>>;
ll mod = 1e9 + 7;
type_mat pow_mat(type_mat &mat, ll n) {//矩阵快速幂
type_mat res = mat;//mat^n=mat*mat^(n-1)
n--;
for (type_mat e = mat; n; e = mat_product(e, e), n >>= 1)
if (n & 1)
res = mat_product(res, e);
return res;
}
vector<vector<ll>> mat_product(type_mat &a, type_mat &b) {//矩阵乘法
int m = a.size(), n = b[0].size(), mid = a[0].size();
type_mat res(m, vector<ll>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < mid; k++)
res[i][j] = (res[i][j] + a[i][k] * b[k][j] % mod) % mod;
return res;
}
int numberOfWays(string s, string t, long long k) {
int n = s.size();
shash h1(s, 2333, 1e9 + 9), h2(t, 2333, 1e9 + 9);
int cnt = 0;
bool flag = false;//s是否等于t
if (h1(0, n - 1) == h2(0, n - 1)) {
cnt++;
flag = true;
}
for (int i = 1; i < n; i++)//判断将s长为i的后缀移至s的开头后s是否等于t
if (h1(n - i, n - 1) == h2(0, i - 1) && h1(0, n - i - 1) == h2(i, n - 1))
cnt++;
vector<vector<ll>> A{{cnt - 1, cnt},
{n - cnt, n - cnt - 1}};
type_mat res = pow_mat(A, k);
return flag ? (res[0][0] + mod) % mod : (res[0][1] + mod) % mod;
}
class shash {//字符串哈希模板
public:
vector<ll> pres;
vector<ll> epow;
ll e, p;
shash(string &s, ll e, ll p) {
int n = s.size();
this->e = e;
this->p = p;
pres = vector<ll>(n + 1);
epow = vector<ll>(n + 1);
epow[0] = 1;
for (int i = 0; i < n; i++) {
pres[i + 1] = (pres[i] * e + s[i]) % p;
epow[i + 1] = (epow[i] * e) % p;
}
}
ll operator()(int l, int r) {//返回s[l,r]对应的哈希值
ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;
return (res + p) % p;
}
};
};
到了这里,关于第 362 场 LeetCode 周赛题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!