力扣390周赛
力扣第390场周赛
每个字符最多出现两次的最长子字符串
模拟
class Solution {
public:
int maximumLengthSubstring(string s) {
int ans = 0 , n = s.size();
for(int i = 0 ; i < n ; i ++){
for(int j = i ; j < n ; j ++){
vector<int>a(30);
bool f = true;
for(int k = i ; k <= j ; k ++){
a[s[k] - 'a'] ++;
if(a[s[k] - 'a'] > 2)f = false;
}
if(f)ans = max(ans , j - i + 1);
}
}
return ans;
}
};
执行操作使数据元素之和大于等于 K
贪心,一定是先加1后乘,枚举加几次1
class Solution {
public:
int minOperations(int k) {
int ans = 1e9;
for(int i = 0 ; i < k; i ++){
int cur = 1 + i;
int s = k / cur;
if(k % cur == 0)s --;
ans = min(ans , i + s);
}
return ans;
}
};
最高频率的 ID
考验STL排序的用法
class Solution {
public:
struct Cmp {
bool operator()(const std::pair<int,int> &s1, const std::pair<int,int> &s2) const {
if(s1.second == s2.second)return s1.first < s2.first;
return s1.second > s2.second;
}
};
vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
vector<long long> ans;
int n = nums.size();
multiset<pair<int,long long> , Cmp> s;
map<int ,long long> mi;
for(int i = 0 ; i < n ; i ++){
auto t = mi[nums[i]];
s.erase({nums[i] , t});
t += freq[i];
s.insert({nums[i] , t});
mi[nums[i]] = t;
auto firstPair = *s.begin();
ans.push_back(firstPair.second);
}
return ans;
}
};
最长公共后缀查询
字典树,每次遇到长度更小的时候更新
const int N = 5e5 + 10;
int sz, key[N], val[N], ch[N][26];
void init(){
memset(ch[0], 0, sizeof(ch[0]));
key[0] = -1;
sz = 1;
}
void add(string &s, int x){
int len = s.length();
int u = 0, c;
if(key[0] == -1 || val[0] > len){
key[0] = x;
val[0] = len;
}
for(int i=len-1; i>=0; --i){
c =s[i] - 'a';
if(!ch[u][c]){
memset(ch[sz], 0, sizeof(ch[sz]));
key[sz] = -1;
ch[u][c] = sz++;
}
u = ch[u][c];
if(key[u] == -1 || val[u] > len){
key[u] = x;
val[u] = len;
}
}
}
class Solution {
public:
vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
init();
for(int i=0; i<wordsContainer.size(); ++i){
add(wordsContainer[i], i);
}
int n = wordsQuery.size();
vector<int> ret(n);
for(int i=0; i<wordsQuery.size(); ++i){
int u = 0, c = 0;
int len = wordsQuery[i].length();
for(int j=len-1; j>=0; --j){
c = wordsQuery[i][j] - 'a';
if(!ch[u][c]) break;
u = ch[u][c];
}
ret[i] = key[u];
}
return ret;
}
};
–
原文地址:https://blog.csdn.net/qq_60755751/article/details/136996743
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!