思路:
使用哈希表计数一下,然后找到最大的。
代码:
class Solution {
public:
int mostFrequentEven(vector<int>& nums) {
map<int,int> a;
int mx=-1;
for(auto&x:nums){
if(x%2==0){
a[x]++;
mx=max(mx,a[x]);
}
}
for(auto&[l,r]:a){
if(r==mx){
return l;
}
}
return -1;
}
};
思路:
遍历一次,如果发现当前字符是出现过的,就清空哈希表,答案加一。
代码:
class Solution {
public:
int partitionString(string s) {
int n=s.size();
map<char,int> a;
int ans=0;
for(int i=0;i<n;i++){
if(a.count(s[i])) {
ans++;
a.clear();
}
a[s[i]]++;
}
if(a.size()) ans++;
return ans;
}
};
思路:
根据题目意思,只需要找到同一个位置重叠的次数最大是多少就是答案。
同时就是数据又比较小,可以使用差分来对一个区间同事加一个数。
代码:
class Solution {
public:
int minGroups(vector<vector<int>>& in) {
sort(in.begin(),in.end());
int n=in.size();
vector<int> a(1000000+2,0);
for(int i=0;i<n;i++){
int x=in[i][0],y=in[i][1];
a[x]+=1;
a[y+1]-=1;
}
for(int i=1;i<=1000000;i++){
a[i]+=a[i-1];
}
return *max_element(a.begin(),a.end());
}
};
思路:
首先,这个题目如果数据量比较小是可以DP做的,时间复杂度 O ( n 2 ) O(n^2) O(n2)
f[i][j]
表示从前i
个数当中选择以j
结尾的最长序列长度。
f
[
i
]
[
j
]
=
m
a
x
(
f
[
i
−
1
]
[
j
−
k
]
到
f
[
i
−
1
]
[
j
]
)
+
1
f[i][j]=max(f[i-1][j-k]到f[i-1][j])+1
f[i][j]=max(f[i−1][j−k]到f[i−1][j])+1
然后因为第i层知会由i-1层推导而来,所以可以优化成一维数组。
要从一段区间中求出最大值,且要满足动态更新,所以可以使用线段树或者树状数组来维护最大值。
线段树代码量大,采用树状数组。
代码:
const int N=100010;
int n,m,a[N],c[N];
int lowbit(int x){ return x & (-x);}
void update(int x){
int lx = x;
while(x < N) {
c[x] = max(c[x], a[lx]);
x += lowbit(x);
}
}
int query(int x, int y){
int ans = 0;
while(y >= x){
ans = max(a[y], ans);
for(y --; y-lowbit(y) >= x; y -= lowbit(y)){
ans=max(c[y], ans);
}
}
return ans;
}
class Solution {
public:
int lengthOfLIS(vector<int>& nums, int k) {
memset(c,0,sizeof c);
memset(a,0,sizeof a);
n=nums.size();
int ans=0;
for(int i=0;i<n;i++){
int x=nums[i];
int max_k=query(max(1,x-k),x-1);
a[x]=max(a[x],max_k+1);
ans=max(ans,a[x]);
update(x);
}
return ans;
}
};