LeetCode 第385场周赛个人题解

2024-02-19 16:12
文章标签 leetcode 周赛 个人 题解 385

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

目录

100212. 统计前后缀下标对 I

原题链接

题目描述

接口描述

思路分析

代码详解

100229. 最长公共前缀的长度

原题链接

题目描述

接口描述

思路分析

代码详解

100217. 出现频率最高的素数

原题链接

题目描述

接口描述

思路分析

代码详解

100212. 统计前后缀下标对 II

原题链接

题目描述

接口描述

思路分析

代码详解

100212. 统计前后缀下标对 I

原题链接

100212. 统计前后缀下标对 I

题目描述

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

  • 当 str1 同时是 str2 的前缀（

    prefix

    ）和后缀（

    suffix

    ）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

示例 1：

输入：words = ["a","aba","ababa","aa"]
输出：4
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("a", "aba") 为 true 。
i = 0 且 j = 2 ，因为 isPrefixAndSuffix("a", "ababa") 为 true 。
i = 0 且 j = 3 ，因为 isPrefixAndSuffix("a", "aa") 为 true 。
i = 1 且 j = 2 ，因为 isPrefixAndSuffix("aba", "ababa") 为 true 。
因此，答案是 4 。

示例 2：

输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。

示例 3：

输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。

接口描述

class Solution {
public:int countPrefixSuffixPairs(vector<string>& words) {}
};

思路分析

前后缀问题很容易想到字符串哈希和字典树

这里使用字典树解法

  1. 遍历字符串数组，用kmp的next数组推导方式计算出所有公共前后缀，并插入到哈希表中
  2. 倒序遍历，在字典树上匹配，如果匹配长度在哈希表中存在，我们就加上这个字典树节点处的权值
  3. 结束后倒序插入当前字符串

时间复杂度O(Σlen(s))

代码详解

class Solution
{
public:struct node{int cnt = 0;unordered_map<char, node *> ch;} *root, *t;bool isloop(const string &s){int l = 0, r = (int)s.size() - 2;while (l < r)if (s[l] != s[r])return false;elsel++, r--;return true;}long long countPrefixSuffixPairs(vector<string> &words){long long ret = 0;root = new node;for (auto &s : words){int n = s.size();vector<int> nxt(n + 1, -1);s.push_back('#');int j = 0, k = -1;unordered_set<int> mp;while (j < n){if (k == -1 || s[j] == s[k]){k++, j++;nxt[j] = k;}elsek = nxt[k];}while (j)mp.insert(nxt[j]), j = nxt[j];mp.insert(n);t = root;for (int i = n - 1; i >= 0; i--){if (!t->ch.count(s[i]))break;t = t->ch[s[i]];if (mp.count(n - i))ret += t->cnt;}t = root;for (int i = n - 1; i >= 0; i--){if (!t->ch.count(s[i]))t->ch[s[i]] = new node;t = t->ch[s[i]];}t->cnt++;}return ret;}
};

100229. 最长公共前缀的长度

　　

原题链接

　　100229. 最长公共前缀的长度

题目描述

　　

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

接口描述

　　

class Solution {
public:int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {}
};

思路分析

　　还是字典树

  1. 把arr1中所有数字转化为字符串插入到字典树中
  2. 遍历arr2，在字典树上进行匹配，维护最长前缀长度

代码详解

class Solution
{
public:struct node{unordered_map<char, node *> ch;} *root;int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2){root = new node;int ret = 0;for (auto v : arr1){node *t = root;for (auto x : to_string(v)){if (!t->ch.count(x))t->ch[x] = new node;t = t->ch[x];}}for (auto &v : arr2){node *t = root;int s = 0;for (auto x : to_string(v)){if (!t->ch.count(x))break;t = t->ch[x];s++;}ret = max(ret, s);}return ret;}
};

　

100217. 出现频率最高的素数

　　

原题链接

　　100217. 出现频率最高的素数

题目描述

　　

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

  • 最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
  • 选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
  • 注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的

素数

；如果不存在这样的素数，则返回  -1  。如果存在多个出现频率最高的素数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

接口描述

　　

class Solution {
public:int mostFrequentPrime(vector<vector<int>>& mat) {}
};

思路分析

　　素数筛+暴力模拟

预处理素数筛，遍历每个网格的八个方向维护出现的大于10的素数的次数即可

代码详解

const int maxn = 1e7 + 10;
bitset<maxn + 1> prime; // 0为素数 1为合数
int primes[maxn + 1], cnt;
bool f = 0;
inline void calcprime(int x)
{prime[2] = 0;for (int i = 2; i <= x; i++){if (!prime[i])primes[cnt++] = i;for (int j = 0; j < cnt && primes[j] * i <= x; j++){prime[primes[j] * i] = 1;if (i % primes[j] == 0)break;}}
}
class Solution
{
public:Solution(){if (!f)calcprime(1e7), f = 1;;}static constexpr int dir[9] = {1, 0, -1, 0, 1, 1, -1, -1, 1};int mostFrequentPrime(vector<vector<int>> &mat){int m = mat.size(), n = mat[0].size(), ret = -1, ma = 0;int cnt[10000005]{0};for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){for (int k = 0, x, y; k < 8; k++){int s = 0;x = i, y = j;while (x >= 0 && x < m && y >= 0 && y < n){s = (s << 3) + (s << 1) + mat[x][y];if (s > 10 && !prime[s]){++cnt[s];if (cnt[s] > ma)ma = cnt[s], ret = s;else if (cnt[s] == ma)ret = max(ret, s);}x += dir[k], y += dir[k + 1];}}}}return ret;}
};

　

100212. 统计前后缀下标对 II

　　

原题链接

　　100208. 统计前后缀下标对 II

题目描述

　　

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

  • 当 str1 同时是 str2 的前缀（

    prefix

    ）和后缀（

    suffix

    ）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

接口描述

　　

class Solution {
public:long long countPrefixSuffixPairs(vector<string>& words) {}
};

思路分析

　　思路同第一题

代码详解

class Solution
{
public:struct node{int cnt = 0;unordered_map<char, node *> ch;} *root, *t;bool isloop(const string &s){int l = 0, r = (int)s.size() - 2;while (l < r)if (s[l] != s[r])return false;elsel++, r--;return true;}long long countPrefixSuffixPairs(vector<string> &words){long long ret = 0;root = new node;for (auto &s : words){int n = s.size();vector<int> nxt(n + 1, -1);s.push_back('#');int j = 0, k = -1;unordered_set<int> mp;while (j < n){if (k == -1 || s[j] == s[k]){k++, j++;nxt[j] = k;}elsek = nxt[k];}while (j)mp.insert(nxt[j]), j = nxt[j];mp.insert(n);t = root;for (int i = n - 1; i >= 0; i--){if (!t->ch.count(s[i]))break;t = t->ch[s[i]];if (mp.count(n - i))ret += t->cnt;}t = root;for (int i = n - 1; i >= 0; i--){if (!t->ch.count(s[i]))t->ch[s[i]] = new node;t = t->ch[s[i]];}t->cnt++;}return ret;}
};

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


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

相关文章

哈希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