leetcode周赛352
1. 最长奇偶子数组
思路分析
- 这是一道变形的双指针题目我们可以使用相关算法模板基础上来书写
- 左边界：偶数，且小于值threshold;所以我们需要寻找符合要求的左边界
- 判断是否奇偶相间：只有 奇数+偶数=奇数
class Solution {static int[] arr;static int thre;public int longestAlternatingSubarray(int[] nums, int threshold) {int maxlen=0;//用来记录答案arr=nums;thre=threshold;int j=0;j=getl(j);//维持一个[]的区间for(int i=j;i<arr.length;i++){//枚举右边界//特判i为0的情况if(i==j && nums[i]<=thre){maxlen=Math.max(maxlen,i-j+1);}else if(i!=j && (nums[i]+nums[i-1])%2!=0 && nums[i]<=thre){maxlen=Math.max(maxlen,i-j+1);}else if(nums[i]>thre || (nums[i]+nums[i-1])%2==0){//不符合条件，j重置j=getl(i);//重置左边界 }}return maxlen;}//从当前位置开始符合左边界条件的下一个坐标public static int getl(int j){int len=arr.length;while(j<len && (arr[j]%2!=0 || arr[j]>thre))j++;return j;}
2.和等于目标的质数对
思路分析
- 这里我们只需要遍历一遍数组即可
- 且只需要遍历一半
- 质数判断：试除法
class Solution {public List<List<Integer>> findPrimePairs(int n) {List<List<Integer>> ans=new ArrayList<>();if(n<=2)return ans;int num=11;for(int i=2;i<=n/2;i++){List<Integer> t=new ArrayList<>();if(check(i)&&check(n-i)){t.add(i);t.add(n-i);ans.add(t);}}return ans;}//试除法，判断一个数是不是质数public static boolean check(int num){//1,2进行判if(num<3)return true;for(int i=2;i*i<=num;i++){if(num%i==0)return false;}return true;}
}
3.不间断的子数组
思路分析
- 对于计数问题，我们最重要的就是及进行分类，可以不重不漏的进行统计
- 我们以子数组的右边界进行分类，每一类的数目为 right-left+1
- 接下来我们就需要找出所有符合条件的数组，我们可以使用滑动窗口算法
- 我们需要维护的有，最大值，最小值，窗口各值得数目
- 所以我们使用TreeMap
class Solution {public long continuousSubarrays(int[] nums) {long res=0;TreeMap<Integer,Integer> map=new TreeMap<>();int j=0;//左边界for(int i=0;i<nums.length;i++){map.merge(nums[i],1,Integer::sum);while(j<nums.length && Math.abs(map.lastKey()-map.firstKey())>2){int y=nums[j];j++;if(map.get(y)==1)map.remove(y);else map.merge(y,-1,Integer::sum);}res+=i-j+1;}return res;}
}
