LeetCode 第390场周赛个人题解

2024-03-25 15:44
文章标签 leetcode 周赛 个人 题解 390

本文主要是介绍LeetCode 第390场周赛个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

100245. 每个字符最多出现两次的最长子字符串

原题链接

思路分析

AC代码

100228. 执行操作使数据元素之和大于等于 K

原题链接

思路分析

AC代码

100258. 最高频率的 ID

原题链接

思路分析

AC代码

100268. 最长公共后缀查询

原题链接

思路分析

AC代码

100245. 每个字符最多出现两次的最长子字符串

原题链接

每个字符最多出现两次的最长子字符串 - 力扣 (LeetCode) 竞赛

思路分析

枚举

直接遍历每一个子串，然后统计那些最大字符频率小于2的就行了

时间复杂度O(n^2)

AC代码

class Solution {
public:int maximumLengthSubstring(string s) {int n = s.size(), ret = 1;for(int len = 1; len <= n; len++){for(int i = 0; i <= n - len; i++){int cnt[26]{0};bool f = 0;for(int j = i; j < i + len; j++)f = f || (++cnt[s[j] - 'a'] > 2);if(f) continue;ret = max(ret, len);break;}}return ret;}
};

100228. 执行操作使数据元素之和大于等于 K

原题链接

执行操作使数据元素之和大于等于 K - 力扣 (LeetCode) 竞赛

思路分析

贪心

最优解一定是自增若干次，然后再复制若干次

证明：如果存在自增、复制交替出现，或者先复制若干次再自增若干次，我们将自增的操作全都放在前面，复制的操作都放在后面，得到的元素和会变大，因为最终的元素数目一样，而这样最大化了每个元素，故得证

那么我们只需要枚举最终每个元素的值就行了，从1枚举到k

时间复杂度：O(k)

AC代码

class Solution {
public:int minOperations(int k) {int ret = k;for(int i = 1; i <= k; i++)ret = min(ret, (i - 1) + (int)ceil(1.0 * k / i) - 1);return ret;}
};

100258. 最高频率的 ID

原题链接

最高频率的 ID - 力扣 (LeetCode) 竞赛

思路分析

线段树

每次对区间内某个数的频率进行修改，然后求修改后区间内的最大频率

这就完美对应了线段树的单点修改和区间最值，我们只需要写一下线段树的递归建树和单点修改的函数即可，码量巨小

时间复杂度O(mlogn)，m为操作次数，n为区间大小

AC代码

struct node{int l, r;long long s;
}tr[400010];
#define lc p << 1
#define rc p << 1 | 1
void build(int p, int l, int r){tr[p] = {l, r, 0};if(l == r) return;int m = (l + r) >> 1;build(lc, l, m), build(rc, m + 1, r);
}
void update(int p, int x, int k){if(tr[p].l == x && tr[p].r == x){tr[p].s += k; return;}int m = (tr[p].l + tr[p].r) >> 1;if(x > m) update(rc, x, k);else update(lc, x, k);tr[p].s = max(tr[lc].s, tr[rc].s);
}
class Solution {
public:vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {build(1, 1, *max_element(nums.begin(), nums.end()));vector<long long> ret;for(int i = 0, n = nums.size(); i < n; i++){update(1, nums[i], freq[i]);ret.emplace_back(tr[1].s);}return ret;}
};

100268. 最长公共后缀查询

原题链接

最长公共后缀查询 - 力扣 (LeetCode) 竞赛

思路分析

字典树

考虑要能快速的求出查询字符串和字符串集合中的最长公共后缀，我们提前将字符串集合中的字符串倒序插入字典树，然后边插入边统计路径上的最短字符串的下标，这个值是存在路径上节点中的

然后对于每个查询去在字典树上沿着路径往下走就行了，走不动就退出

然后答案就是当前节点存的那个下标

时间复杂度O(Σlen(wordsContainer[i]) + Σlen(wordsQuery[i]))

AC代码

struct node{unordered_map<char, node*> ch;int idx = -1;
}*root, *cur;
class Solution {
public:vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {root = new node;vector<int> ret;int n = wordsContainer.size(), mi = 0;for(int i = 0; i < n; i++){cur = root;if(wordsContainer[i].size() < wordsContainer[mi].size()) mi = i;for(int j = (int)wordsContainer[i].size() - 1; j >= 0; j--){char x = wordsContainer[i][j];if(!cur->ch.count(x)) cur->ch[x] = new node;cur = cur->ch[x];if(cur->idx == -1) cur->idx = i;else if(wordsContainer[cur->idx].size() > wordsContainer[i].size()) cur->idx = i;}}n = wordsQuery.size();for(int i = 0; i < n; i++){cur = root;for(int j = wordsQuery[i].size() - 1; j >= 0; j--){char x = wordsQuery[i][j];if(cur->ch.count(x)) cur = cur->ch[x];else break;}if(cur != root)ret.emplace_back(cur->idx);elseret.emplace_back(mi);}return ret;}
};

这篇关于LeetCode 第390场周赛个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/845471。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
HomeBank：开源免费的个人财务管理软件

HomeBank：开源免费的个人财务管理软件

在个人财务管理领域，找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目，它不仅提供了强大的功能，还拥有一个活跃的社区，不断推动其发展和完善。 开源免费：HomeBank 是一个完全开源的项目，用户可以自由地使用、修改和分发。用户友好的界面：提供直观的图形用户界面，使得非技术用户也能轻松上手。数据导入支持：支持从 Quicken、Microsoft Money
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
分布式系统的个人理解小结

分布式系统的个人理解小结

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2