第 319 场周赛
复习：
- 求两个数的最大公因数
1
2
3
| int gcd(int a,int b){
return b==0 ? a:gcd(b,a%b);
}
|
- 区间调度问题，无重复区间
思路：先按照end排序，寻找下一个start要大于等于这个end
例题：无重叠区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)-> a[1]-b[1]);
int count=1;
int end=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>=end){
count++;
end=intervals[i][1];
}
}
return intervals.length-count;
}
}
|
第四题不重叠回文子字符串的最大数目
我的思路是：找出所有的回文串，然后使用无重叠区间，但一些样例过不了，比如字符串全是同一个字符。
如果暴力的话，找到长度>=k的回文串即可，而且无需存储回文串，因为这样会超内存空间，只需要存储回文串的位置即可
先O(n^2)暴力枚举把所有最短的长度>=k的回文子串【长度为k和k+1】，然后把回文子串看成区间，求最大的不交叉的区间
枚举的时候，只要记录长度为k和长度为k+1的回文串，因为要使回文串的数目最大，如果k+2长度为回文串，我必然会选择长度为k的作为回文串即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
public int maxPalindromes(String s, int k) {
List<Loc> list=new ArrayList<Loc>();
for(int i=0;i+k<=s.length();i++){
if(check(s,i,i+k)){
list.add(new Loc(i,i+k));
}
if(i+k+1<=s.length() && check(s,i,i+k+1)){
list.add(new Loc(i,i+k+1));
}
}
if(list.size()==0){
return 0;
}
list.sort((a,b)->a.end-b.end);
int count=1;
int temp=list.get(0).end;
for(int i=1;i<list.size();i++){
if(list.get(i).start>=temp){
count++;
temp=list.get(i).end;
}
}
return count;
}
boolean check(String s,int i,int j){
int left=i;
int right=j-1;
while(left<=right){
if(s.charAt(left)!=s.charAt(right)){
return false;
}
left++;right--;
}
return true;
}
static class Loc{
int start;
int end;
public Loc(int start,int end){
this.start=start;
this.end=end;
}
}
}
|
第二题2470. 最小公倍数为 K 的子数组数目
后判不正确
确实不对
我判断子数组的最小公倍数是不是为k,方式是：是不是含有k且是不是k的因子
这样不对，例如【2，3】 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int subarrayLCM(int[] nums, int k) {
int n=nums.length;
int ans=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
if(i==j && nums[i]==k){
ans++;
}else{
if(check(nums,i,j,k)){
ans++;
}
}
}
}
return ans;
}
boolean check(int nums[],int i,int j,int k){
int t=nums[i];
for(int x=i+1;x<=j;x++){
int temp=gcd(t,nums[x]);
t=t*nums[x]/temp;
}
return t==k;
}
int gcd(int a,int b){
return b==0 ? a:gcd(b,a%b);
}
}
|
时间复杂度O(n^3) 超时
思路：二重循环，如果子数组的最大公倍数超过k,break;等于k,ans++;
