第 362 场 LeetCode 周赛题解

这篇具有很好参考价值的文章主要介绍了第 362 场 LeetCode 周赛题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

A 与车相交的点

第 362 场 LeetCode 周赛题解,LeetCode,leetcode,算法,C++,排列,字符串哈希,动态规划,快速幂

数据范围小直接暴力枚举

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 判断能否在给定时间到达单元格

第 362 场 LeetCode 周赛题解,LeetCode,leetcode,算法,C++,排列,字符串哈希,动态规划,快速幂

设起点和终点的横坐标之差的绝对值为 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 tmn 即可, 起点终点重合需要 t ≥ 2 t \ge 2 t2 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 将石头分散到网格图的最少移动次数

第 362 场 LeetCode 周赛题解,LeetCode,leetcode,算法,C++,排列,字符串哈希,动态规划,快速幂
第 362 场 LeetCode 周赛题解,LeetCode,leetcode,算法,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 字符串转换

第 362 场 LeetCode 周赛题解,LeetCode,leetcode,算法,C++,排列,字符串哈希,动态规划,快速幂

动态规划 + 字符串哈希 + 矩阵快速幂:设 c n t cnt cnt 为满足“将 s s s 的长为 l ( 0 ≤ l < n ) l(0\le l<n) l(0l<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]=[cnt1ncntcntncnt1][pk1qk1]
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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 周赛 343(2023/04/30)结合「下一个排列」的贪心构造问题

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天是五一假期的第二天,打周赛的人数比前一天的双周赛多了,难道大家都只玩一天吗?这场周赛是 LeetCode 第 343 场单周赛,如果不考虑第一题摆烂的翻译,整体题目质量还是

    2024年02月02日
    浏览(39)
  • 第 122 场 LeetCode 双周赛题解

    A 将数组分成最小总代价的子数组 I 枚举:枚举后两个子数组的起始下标 B 判断一个数组是否可以变为有序 模拟:模拟冒泡排序的过程,若相邻元素大小关系需要交换位置,但其二进制下数位为 1 的数目不同,则返回false,若完成排序返回true C 通过操作使数组长度最小 脑筋急

    2024年01月22日
    浏览(40)
  • LeetCode 第385场周赛个人题解

    目录 100212. 统计前后缀下标对 I 原题链接 题目描述 接口描述 思路分析 代码详解 100229. 最长公共前缀的长度 原题链接 题目描述 接口描述 思路分析 代码详解 100217. 出现频率最高的素数 原题链接 题目描述 接口描述 思路分析 代码详解 100212. 统计前后缀下标对 II 原题链接 题目

    2024年02月19日
    浏览(60)
  • LeetCode 第 388 场周赛个人题解

    目录 100233. 重新分装苹果 原题链接 思路分析 AC代码 100247. 幸福值最大化的选择方案 原题链接 思路分析 AC代码 100251. 数组中的最短非公共子字符串 原题链接 思路分析 AC代码 100216. K 个不相交子数组的最大能量值 原题链接 思路分析 AC代码 100233. 重新分装苹果 直接模拟 降序排

    2024年03月15日
    浏览(59)
  • LeetCode 第384 场周赛题解(JavaScript版)

    废话不多说,我们来直接看题目!没参与本次周赛的小伙伴也可以先点进去自己试试看!第 384 场周赛 - 力扣(LeetCode) 好的家人们,这个第一题,我们也是必须拿下的好吧,一道非常简单的模拟送分题,它的意思是, 让我们把矩阵中,值为-1的数,变为它所在这一列最大的

    2024年02月22日
    浏览(38)
  • C++ | Leetcode C++题解之第46题全排列

    题目: 题解:

    2024年04月24日
    浏览(40)
  • Golang | Leetcode Golang题解之第31题下一个排列

    题目: 题解:

    2024年04月17日
    浏览(40)
  • leetcode 567. 字符串的排列(滑动窗口-java)

    难度 -中等 leetcode567. 字符串的排列 给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。 换句话说,s1 的排列之一是 s2 的 子串 。 示例 1: 输入:s1 = “ab” s2 = “eidbaooo” 输出:true 解释:s2 包含 s1 的排列之一 (“ba”

    2024年02月10日
    浏览(45)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面 不能有重复元素 。 示例: 输入:s = “abc” 输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 : 1 = s 的长度 = 8 💡思路:回溯 可以直接 暴力穷举 ,但

    2024年02月12日
    浏览(50)
  • Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划)

    Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划) 题目 给你一个二进制字符串 s ,你需要将字符串分割成一个或者多个 子字符串 ,使每个子字符串都是 美丽 的。 如果一个字符串满足以下条件,我们称它是 美丽 的: 它不包含前导 0 。 它是

    2024年02月15日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包