Leetcode 第 420 场周赛题解

Leetcode 第 420 场周赛题解

  • Leetcode 第 420 场周赛题解
    • 题目1:3324. 出现在屏幕上的字符串序列
      • 思路
      • 代码
      • 复杂度分析
    • 题目2:3325. 字符至少出现 K 次的子字符串 I
      • 思路
      • 代码
      • 复杂度分析
    • 题目3:3326. 使数组非递减的最少除法操作次数
      • 思路
      • 代码
      • 复杂度分析
    • 题目4:3327. 判断 DFS 字符串是否是回文串
      • 思路
      • 代码
      • 复杂度分析

Leetcode 第 420 场周赛题解

题目1:3324. 出现在屏幕上的字符串序列

思路

模拟整个过程。

初始化字符串 s 为空。

对于每一个 target[i],先在字符串 s 的末尾插入一个 ‘a’,然后模拟 s[i] 从 ‘a’ 到 target[i] 的过程,每更新一次 s,就将 s 插入到答案数组中。

代码

/** @lc app=leetcode.cn id=3324 lang=cpp** [3324] 出现在屏幕上的字符串序列*/// @lc code=start
class Solution
{
public:vector<string> stringSequence(string target){if (target.empty())return {};string s;vector<string> ans;for (int i = 0; i < target.length(); i++){s.push_back('a');for (char c = 'a'; c <= target[i]; c++){s.back() = c;ans.push_back(s);}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度:O(n2 * ∣Σ∣),其中 n 是字符串 target 的长度,∣Σ∣=26 是字符集合的大小。

空间复杂度:O(n),其中 n 是字符串 target 的长度。

题目2:3325. 字符至少出现 K 次的子字符串 I

思路

暴力会超时:

/** @lc app=leetcode.cn id=3325 lang=cpp** [3325] 字符至少出现 K 次的子字符串 I*/// @lc code=start
class Solution
{
public:int numberOfSubstrings(string s, int k){int n = s.length();if (k > n)return 0;int count = 0;for (int i = 0; i < n; i++)for (int len = 1; i + len <= n; len++){string temp = s.substr(i, len);if (check(temp, k))count++;}return count;}// 辅函数bool check(string &s, int k){unordered_map<int, int> hashMap;for (char &c : s)hashMap[c]++;for (auto &[c, cnt] : hashMap)if (cnt >= k)return true;return false;}
};
// @lc code=end

在这里插入图片描述

我们可以用滑动窗口求解。

从小到大枚举子串右端点 right,如果子串符合要求,则右移左端点 left。

滑动窗口的内层循环结束时,右端点固定在 right,左端点在 0、1、2、⋯、left−1 的所有子串都是合法的,这一共有 left 个,加入答案。

代码

/** @lc app=leetcode.cn id=3325 lang=cpp** [3325] 字符至少出现 K 次的子字符串 I*/// @lc code=start
class Solution
{
public:int numberOfSubstrings(string s, int k){int n = s.length();if (k > n)return 0;vector<int> cnt(26, 0);int left = 0; // 滑动窗口的左端点int count = 0;for (int right = 0; right < n; right++){cnt[s[right] - 'a']++;while (cnt[s[right] - 'a'] >= k){cnt[s[left] - 'a']--;left++;}count += left;}return count;}
};
// @lc code=end

复杂度分析

时间复杂度:O(n+∣Σ∣),其中 n 是字符串 s 的长度,∣Σ∣=26 是字符集合的大小。

空间复杂度:O(∣Σ∣),∣Σ∣=26 是字符集合的大小。

题目3:3326. 使数组非递减的最少除法操作次数

思路

定义 LPF(x) 为 x 的最小质因子。规定 LPF(1)=1。

  • 如果 LPF(x)=x,说明 x 是 1 或者质数,无法变小。
  • 如果 LPF(x)<x,说明 x 是合数,可以变小。由于题目规定只能除以最大真因数,我们可以把 x 除以 x / LPF(x),得到 LPF(x)。

贪心,最后一个数肯定无需减少,所以我们从 i=n−2 开始倒着遍历 nums:

如果 nums[i]>nums[i+1],那么把 nums[i] 更新为 LPF(nums[i]),操作次数加一。注意更新后 nums[i] 一定是质数或 1,无法再变小。

更新后,如果 nums[i]>nums[i+1] 仍然成立,说明无法把 nums 变成非降的,返回 −1。

代码

/** @lc app=leetcode.cn id=3326 lang=cpp** [3326] 使数组非递减的最少除法操作次数*/// @lc code=start// 预处理
const int MX = 1e6 + 1;
int LPF[MX];auto init = []
{for (int i = 2; i < MX; i++)if (LPF[i] == 0)for (int j = i; j < MX; j += i)if (LPF[j] == 0)LPF[j] = i;return 0;
}();class Solution
{
public:int minOperations(vector<int> &nums){int ans = 0;for (int i = nums.size() - 2; i >= 0; i--){if (nums[i] > nums[i + 1]){nums[i] = LPF[nums[i]];if (nums[i] > nums[i + 1])return -1;ans++;}}return ans;}
};
// @lc code=end

复杂度分析

预处理的时间复杂度为 O(UloglogU),其中 U=106

时间复杂度:O(n),其中 n 是数组 nums 的长度。

空间复杂度:O(1)。

题目4:3327. 判断 DFS 字符串是否是回文串

思路

题解:https://leetcode.cn/problems/check-if-dfs-strings-are-palindromes/solutions/2957704/mo-ban-dfs-shi-jian-chuo-manacher-suan-f-ttu6/

构造 dfsStr 的过程是后序遍历。

子树的后序遍历字符串,是整棵树的后序遍历字符串的子串。

后序遍历的同时,计算每个节点 i 在后序遍历中的开始时间戳和结束时间戳,这也是子树 i 的后序遍历字符串在 dfsStr 上的开始下标和结束下标(代码用的左闭右开区间)。

在 dfsStr 上跑 Manacher 算法,这样就可以 O(1) 判断任意子串是否回文了。

代码

/** @lc app=leetcode.cn id=3327 lang=cpp** [3327] 判断 DFS 字符串是否是回文串*/// @lc code=start
class Solution
{
public:vector<bool> findAnswer(vector<int> &parent, string s){int n = parent.size();vector<vector<int>> g(n);for (int i = 1; i < n; i++){int p = parent[i];// 由于 i 是递增的,所以 g[p] 必然是有序的,下面无需排序g[p].push_back(i);}// dfsStr 是后序遍历整棵树得到的字符串string dfsStr(n, 0);// nodes[i] 表示子树 i 的后序遍历的开始时间戳和结束时间戳+1(左闭右开区间)vector<pair<int, int>> nodes(n);int time = 0;auto dfs = [&](auto &&dfs, int x) -> void{nodes[x].first = time;for (int y : g[x])dfs(dfs, y);dfsStr[time++] = s[x]; // 后序遍历nodes[x].second = time;};dfs(dfs, 0);// Manacher 模板// 将 dfsStr 改造为 t,这样就不需要讨论 n 的奇偶性,因为新串 t 的每个回文子串都是奇回文串(都有回文中心)// dfsStr 和 t 的下标转换关系:// (dfsStr_i+1)*2 = ti// ti/2-1 = dfsStr_i// ti 为偶数,对应奇回文串(从 2 开始)// ti 为奇数,对应偶回文串(从 3 开始)string t = "^";for (char c : dfsStr){t += '#';t += c;}t += "#$";// 定义一个奇回文串的回文半径=(长度+1)/2,即保留回文中心,去掉一侧后的剩余字符串的长度// halfLen[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子串的回文半径// 即 [i-halfLen[i]+1,i+halfLen[i]-1] 是 t 上的一个回文子串vector<int> halfLen(t.length() - 2);halfLen[1] = 1;// boxR 表示当前右边界下标最大的回文子串的右边界下标+1// boxM 为该回文子串的中心位置,二者的关系为 r=mid+halfLen[mid]int boxM = 0, boxR = 0;for (int i = 2; i < halfLen.size(); i++){ // 循环的起止位置对应着原串的首尾字符int hl = 1;if (i < boxR){// 记 i 关于 boxM 的对称位置 i'=boxM*2-i// 若以 i' 为中心的最长回文子串范围超出了以 boxM 为中心的回文串的范围(即 i+halfLen[i'] >= boxR)// 则 halfLen[i] 应先初始化为已知的回文半径 boxR-i,然后再继续暴力匹配// 否则 halfLen[i] 与 halfLen[i'] 相等hl = min(halfLen[boxM * 2 - i], boxR - i);}// 暴力扩展// 算法的复杂度取决于这部分执行的次数// 由于扩展之后 boxR 必然会更新(右移),且扩展的的次数就是 boxR 右移的次数// 因此算法的复杂度 = O(len(t)) = O(n)while (t[i - hl] == t[i + hl]){hl++;boxM = i;boxR = i + hl;}halfLen[i] = hl;}// t 中回文子串的长度为 hl*2-1// 由于其中 # 的数量总是比字母的数量多 1// 因此其在 dfsStr 中对应的回文子串的长度为 hl-1// 这一结论可用在 isPalindrome 中// 判断左闭右开区间 [l,r) 是否为回文串  0<=l<r<=n// 根据下标转换关系得到 dfsStr 的 [l,r) 子串在 t 中对应的回文中心下标为 l+r+1// 需要满足 halfLen[l + r + 1] - 1 >= r - l,即 halfLen[l + r + 1] > r - lauto isPalindrome = [&](int l, int r) -> bool{return halfLen[l + r + 1] > r - l;};vector<bool> ans(n);for (int i = 0; i < n; i++){ans[i] = isPalindrome(nodes[i].first, nodes[i].second);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度:O(n),其中 n 是字符串 s 的长度。

空间复杂度:O(n),其中 n 是字符串 s 的长度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/460152.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity3D学习FPS游戏(3)玩家第一人称视角转动和移动

前言&#xff1a;上一篇实现了角色简单的移动控制&#xff0c;但是实际游戏中玩家的视角是可以转动的&#xff0c;并根据转动后视角调整移动正前方。本篇实现玩家第一人称视角转动和移动&#xff0c;觉得有帮助的话可以点赞收藏支持一下&#xff01; 玩家第一人称视角 修复小问…

代码随想录算法训练营第十二天(补) 二叉树| 二叉树理论知识、深度优先遍历、广度优先遍历

目录 一、二叉树理论基础 &#xff08;一&#xff09;二叉树的种类 二叉搜索树 平衡二叉搜索树 &#xff08;二&#xff09;二叉树的存储 &#xff08;三&#xff09;二叉树的遍历 &#xff08;四&#xff09;二叉树的定义 二、二叉树的递归遍历 三、二叉树的层序遍历 …

在线教育系统源码开发详解:网校培训平台搭建的核心技术

本篇文章&#xff0c;笔者将详细介绍在线教育系统源码的开发过程&#xff0c;重点聚焦网校培训平台搭建的核心技术&#xff0c;以期为有意从事在线教育行业的开发者提供实用的参考。 一、在线教育系统的构成 前端负责用户的交互体验&#xff0c;后端处理业务逻辑&#xff0c;…

利士策分享,赚大钱与赚小钱的哲学,选大还是小?

利士策分享&#xff0c;赚大钱与赚小钱的哲学&#xff0c;选大还是小&#xff1f; 在商海浮沉的浪潮中&#xff0c;时常能听到一些业界大佬发表关于财富积累的独到见解。 其中&#xff0c;有一种观点颇为引人注目&#xff0c;那便是“赚大钱比赚小钱容易”。 此言一出&#xf…

【vue】14.插槽:构建可复用组件的关键

今天看代码的时候碰到了插槽&#xff0c;有些看不懂&#xff0c;所以写下这篇文章&#xff0c;系统地梳理一下关于插槽的内容&#xff0c;也希望给大家带来一些帮助。 // 我碰到的插槽长这样 <template #default"scope">... </template> 一.什么是插槽…

Java项目实战II基于Spring Boot的美食烹饪互动平台的设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在当今美食…

ssm基于ssm框架的滁艺咖啡在线销售系统+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码请私聊我 需要定制请私聊 目 录 第1章 绪论 1 1.1选题动因 1 1.2目的和意义 1 1.3论文结构安排 2 第2章 开发环境与技术 3 2.1 MYSQ…

echarts实现 水库高程模拟图表

需求背景解决思路解决效果index.vue 需求背景 需要做一个水库高程模拟的图表&#xff0c;x轴是水平距离&#xff0c;y轴是高程&#xff0c;需要模拟改水库的形状 echarts 图表集链接 解决思路 配合ui切图&#xff0c;模拟水库形状 解决效果 index.vue <!--/*** author:…

引入RFID技术,焕新消防应急物资管理方式

智能化应急消防管理系统在现代消防工作中扮演着至关重要的角色&#xff0c;引入射频识别&#xff08;RFID&#xff09;技术&#xff0c;并根据消防设备管理的具体状况及需求&#xff0c;广州一芯未来研发了一套RFID消防设备管理系统。 一、射频识别技术RFID简述 射频识别技术RF…

软件压力测试有多重要?北京软件测试公司有哪些?

软件压力测试是一种基本的质量保证行为&#xff0c;它是每个重要软件测试工作的一部分。压力测试是给软件不断加压&#xff0c;强制其在极限的情况下运行&#xff0c;观察它可以运行到何种程度&#xff0c;从而发现性能缺陷。 在数字化时代&#xff0c;用户对软件性能的要求越…

正式入驻!上海斯歌BPM PaaS管理软件等产品入选华为云联营商品

近日&#xff0c;上海斯歌旗下BPM PaaS管理软件&#xff08;NBS&#xff09;等多款产品入选华为云云商店联营商品&#xff0c;上海斯歌正式成为华为云联营商品合作伙伴。用户登录华为云云商店即可采购上海斯歌的BPM PaaS产品及配套服务。通过联营模式&#xff0c;双方合作能够深…

「Mac畅玩鸿蒙与硬件7」鸿蒙开发环境配置篇7 - 使用命令行工具和本地模拟器管理项目

本篇将讲解在 macOS 上配置 HarmonyOS 开发环境的流程&#xff0c;聚焦 hvigorw 命令行工具的使用。我们将以创建 HelloWorld 项目为例&#xff0c;演示使用 hvigorw 进行项目构建、清理操作&#xff0c;并通过 DevEco Studio 的本地模拟器进行预览&#xff0c;帮助提升项目开发…

ECharts饼图,配置标注示例

const color ["#00FFB4", "#5498FD", "#6F54FD", "#FD5454", "#FDA354",]const datas [{ value: 100, name: "一年级" },{ value: 70, name: "二年级" },{ value: 184, name: "三年级" },{…

基于卷积神经网络的苹果病害识别与防治系统,resnet50,mobilenet模型【pytorch框架+python源码】

更多目标检测和图像分类识别项目可看我主页其他文章 功能演示&#xff1a; 苹果病害识别与防治系统&#xff0c;卷积神经网络&#xff0c;resnet50&#xff0c;mobilenet【pytorch框架&#xff0c;python源码】_哔哩哔哩_bilibili &#xff08;一&#xff09;简介 基于卷积…

YOLO即插即用模块---CAA

oly Kernel Inception Network for Remote Sensing Detection 论文地址&#xff1a;2403.06258https://arxiv.org/pdf/2403.06258 主要问题&#xff1a; 目标尺度变化大&#xff1a; 遥感图像中目标尺度范围广泛&#xff0c;从大型物体&#xff08;如足球场&#xff09;到小型…

【网络面试篇】TCP与UDP类

目录 一、综述 1. TCP与UDP的概念 2. 特点 3. 区别 4. 对应的使用场景 二、补充 1. 基础概念 &#xff08;1&#xff09;面向连接 &#xff08;2&#xff09;可靠的 &#xff08;3&#xff09;字节流 2. 相关问题 &#xff08;1&#xff09;TCP 和 UDP 可以同时绑定…

【C++】类和对象(六):运算符重载1

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解C的运算符重载&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 (A) 引入(B) 运算符重载 (A) 引入 写一个Date日期类&#xff0c;问&#xff1a;如果我…

C语言(一维数组)

如果对你有帮助&#xff0c;请点个免费的赞吧&#xff0c;谢谢汪。&#xff08;点个关注也可以&#xff01;&#xff09;\n\n如果以下内容需要补充和修改&#xff0c;请大家在评论区交流~ 思维导图 1.数组 由一个或多个相同的数据类型组成的集合 特点&#xff1a; 数据类型相…

Mount Image Pro,在取证安全的环境中挂载和访问镜像文件内容

天津鸿萌科贸发展有限公司从事数据安全服务二十余年&#xff0c;致力于为各领域客户提供专业的数据恢复、数据备份解决方案与服务&#xff0c;并针对企业面临的数据安全风险&#xff0c;提供专业的相关数据安全培训。 天津鸿萌科贸发展有限公司是 GetData 公司数据恢复与取证工…

上市公司企业数字金融认知数据集(2001-2023年)

一、测算方式&#xff1a;参考C刊《经济学家》王诗卉&#xff08;2021&#xff09;老师的做法&#xff0c;数字金融认知使用每万字年报描述中包含的对数字金融相关关键词的提及次数&#xff0c;关键词为&#xff1a;互联网、数字化、智能、大数据、电子银行、金融科技、科技金融…