社群网站建设,微信小程序支付功能开发,东道设计一个logo多少钱,wordpress get_posts category目录 3090. 每个字符最多出现两次的最长子字符串 简单3091. 执行操作使数据元素之和大于等于 K 中等3092. 最高频率的 ID 中等3093. 最长公共后缀查询 困难 3090. 每个字符最多出现两次的最长子字符串 简单
3090. 每个字符最多出现两次的最长子字符串
分析#xff1a; 数据量… 目录 3090. 每个字符最多出现两次的最长子字符串 简单3091. 执行操作使数据元素之和大于等于 K 中等3092. 最高频率的 ID 中等3093. 最长公共后缀查询 困难 3090. 每个字符最多出现两次的最长子字符串 简单
3090. 每个字符最多出现两次的最长子字符串
分析 数据量按照题意模拟即可。 这里我是用了 前缀和 记录了 0~i 的所有字母出现的次数。
代码
C
class Solution {
public:int maximumLengthSubstring(string s) {int ns.length();vectorvectorint cnt(n1,vectorint(26,0));for(int i0;in;i){cnt[i1][s[i]-a];for(int j0;j26;j) cnt[i1][j]cnt[i][j];}for(int in;i1;i--){for(int j0;jin;j){int k0;for(;k26;k){if(cnt[ji][k]-cnt[j][k]2) break;}if(k26) return i;}}return 1;}
};python
class Solution:def maximumLengthSubstring(self, s: str) - int:cnt [[0] * 216 for i in range(len(s)1)]for i in range(len(s)):cnt[i1][ord(s[i]) - ord(a)]1for j in range(26):cnt[i1][j] cnt[i][j]for i in range(len(s),1,-1):for j in range(0,len(s)-i1):flag Truefor k in range(26):if cnt[ij][k] - cnt[j][k]2:flagFalsebreakif flag:return ireturn 13091. 执行操作使数据元素之和大于等于 K 中等
3091. 执行操作使数据元素之和大于等于 K
分析
法一 贪心找规律 在固定的操作次数 l l l 下先进行 ⌊ l / 2 ⌋ \lfloor l/2 \rfloor ⌊l/2⌋ 次操作一再进行 l − ⌊ l / 2 ⌋ l - \lfloor l/2 \rfloor l−⌊l/2⌋ 操作二即可得到最大的元素之和。 规律如下
操作次数 l最大元素之和 1 1 1 1 ∗ 2 2 1 * 2 2 1∗22 2 2 2 2 ∗ 2 4 2 * 2 4 2∗24 3 3 3 2 ∗ 3 6 2 * 3 6 2∗36 4 4 4 3 ∗ 3 9 3 * 3 9 3∗39 5 5 5 3 ∗ 4 12 3 * 4 12 3∗412 6 6 6 4 ∗ 4 16 4 * 4 16 4∗416……
最终依照此规律寻找最小的大于 k 的操作次数。
法二 贪心枚举 先加后复制得到的数更大。 最多进行 k-1 次加法此时是操作次数最大的情况枚举 1~k-1 次加法再计算后续还需要多少次复制维护最小操作数即可。
代码
法一 C
class Solution {
public:int minOperations(int k) {if(k0||k1) return 0;int cnt1,a1,b2;while(a*bk){if(ab) a;else b;cnt;}return cnt;}
};python
class Solution:def minOperations(self, k: int) - int:if k1 or k0:return 0cnt,a,b1,1,2while a*bk:if ab:a1else:b1cnt1return cnt法二法二
3092. 最高频率的 ID 中等
3092. 最高频率的 ID
分析 寻找每次操作后出现频率最高的数即可。 题目难点在于在每次操作之后怎么寻找当前出现频率最高的数。
遍历的话数据量大一定超时。利用语言自带的工具 哈希表 可重复的有序集合c中的 multiset python中的 SortedList哈希表 优先队列 懒删除堆 懒删除堆因为优先队列不能查找因此对于并非队首或队尾的元素我们无法操作。可以使用 哈希表 维护当前的ID出现的次数并将修改后的ID即其出现次数放入优先队列。同时对比优先队列队首的ID出现次数与当前不符就弹出。 代码
哈希表 可重复的有序集合 C
class Solution {
public:vectorlong long mostFrequentIDs(vectorint nums, vectorint freq) {unordered_mapint ,long long m;multisetlong long s;vectorlong long ans;m[nums[0]]1LL*freq[0];s.emplace(1LL*freq[0]);ans.push_back(1LL*freq[0]);for(int i1;inums.size();i){long long t m[nums[i]];m[nums[i]]1LL*freq[i];auto it s.find(t);if(it ! s.end()){s.erase(it); // 删除集合中的一个 t}s.insert(m[nums[i]]);ans.push_back(*s.rbegin()); // 有序集合s.rbegin() 即为最大的出现次数}return ans;}
};python
from sortedcontainers import SortedList
class Solution:def mostFrequentIDs(self, nums: List[int], freq: List[int]) - List[int]:cnt Counter()s SortedList()ans []for x,f in zip(nums, freq):t cnt[x]s.discard(t)cnt[x]fs.add(cnt[x])ans.append(s[-1])return ans哈希表 优先队列 懒删除堆 C
class Solution {
public:vectorlong long mostFrequentIDs(vectorint nums, vectorint freq) {unordered_mapint ,long long m;priority_queuepairlong long, int q;vectorlong long ans;m[nums[0]]1LL*freq[0];q.emplace(m[nums[0]], nums[0]);ans.push_back(1LL*freq[0]);for(int i1;inums.size();i){long long t m[nums[i]];m[nums[i]]1LL*freq[i];q.emplace(m[nums[i]], nums[i]); // 不断的将修改后的 ID 及其 对应的出现次数 加入优先队列// 如下循环 实现 懒删除堆while(m[q.top().second] ! q.top().first) q.pop(); // 与当前 ID 的出现次数不符合弹出优先队列ans.push_back(q.top().first);}return ans;}
};python
class Solution:def mostFrequentIDs(self, nums: List[int], freq: List[int]) - List[int]:cnt Counter()h []ans []for x,f in zip(nums, freq):cnt[x]fheapq.heappush(h, (-cnt[x], x))while -h[0][0] ! cnt[h[0][1]]:heapq.heappop(h)ans.append(-h[0][0])return ans3093. 最长公共后缀查询 困难
3093. 最长公共后缀查询
分析 构建基于字符串后缀的字典树并且不断维护对应下标后续不断在字典树上查找即可。 注意数组的使用容易内存超限。 同时注意当没有后缀与其匹配是需要填入最短字符串的下标、 构建字典树模板CPP 构建字典树模板Python 代码
C
class Node{
public:int index-1;Node* next[26]{};
};class Solution {
public:vectorint stringIndices(vectorstring wordsContainer, vectorstring wordsQuery) {int nwordsContainer.size(),mwordsQuery.size(),d1e45,dindex-1;vectorint ans;Node* root new Node();for(int i0;in;i){int lwordsContainer[i].length();if(dl) dl,dindexi;Node* node root;for(int jl-1;j0;j--){int k wordsContainer[i][j]-a;if(!node-next[k]) node-next[k] new Node();node node-next[k];if(node-index-1) node-indexi;else{if(wordsContainer[node-index].length()l) node-indexi;}}}for(int i0;im;i){Node* node root;int lwordsQuery[i].length();int index-1;for(int jl-1;j0;j--){int k wordsQuery[i][j]-a;if(!node-next[k])break;nodenode-next[k];indexnode-index;}ans.push_back(index!-1?index:dindex);}return ans;}
};python
class Node:def __init__(self) - None:self.children [None] * 26self.index -1class Solution:def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) - List[int]:n,m len(wordsContainer), len(wordsQuery)d,d_index len(wordsContainer[0]),0ans []def build_trie() - Node: # 构建字典树nonlocal wordsContainer,d,d_indexroot Node()for i in range(n):llen(wordsContainer[i])if dl:dld_indexinode rootfor j in range(l-1, -1, -1):k ord(wordsContainer[i][j]) - ord(a) # 字母转换成下标if node.children[k] None:node.children[k] Node()node node.children[k]if node.index -1: # 更新更优下标node.index ielse:node.index i if len(wordsContainer[node.index]) l else node.indexreturn rootroot build_trie()def find_word(s: str):nonlocal rootnode rootindex -1for i in range(len(s)-1,-1,-1):k ord(s[i]) - ord(a)if node.children[k]None:breaknode node.children[k]index node.indexreturn indexfor i in range(m):t find_word(wordsQuery[i])ans.append(t if t!-1 else d_index)return ans
