leetcode - 365周赛

一，2873.有序三元组中的最大值 I

​

 该题的数据范围小，直接遍历：

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long ans = 0;for(int i=0; i<n-2; i++){for(int j=i+1; j<n-1; j++){for(int k=j+1; k<n; k++){ans = Math.max(ans,(long)(nums[i]-nums[j])*nums[k]);}}}return ans;}
}

 二，2874.有序三元组中的最大值 II

题目与上一题一样，只不过数据范围变大了，不能使用暴力，会超出时间限制。

按照 j 来遍历数组：

        先定义一个数组，从后向前遍历，得到数组后缀最大值，在定义一个数组，从前向后遍历，得到数组前缀最大值，最后按照 j 从前往后遍历。

class Solution {public long maximumTripletValue(int[] nums) {int n = nums.length;long ans = 0;int[] suf_max = new int[n];suf_max[n-1] = nums[n-1];for(int i=n-2; i>=0; i--){suf_max[i] = Math.max(suf_max[i+1],nums[i]);}int[] pre_max = new int[n];pre_max[0] = nums[0];for(int i=1; i<n; i++){pre_max[i] = Math.max(pre_max[i-1],nums[i]);}for(int j=1; j<n-1; j++){ans = Math.max(ans, (long)(pre_max[j-1]-nums[j])*suf_max[j+1]);}return ans;}
}

//解法二
class Solution {public long maximumTripletValue(int[] nums) {long ans = 0;int pre_max = 0;//前缀最大值 - nums[i]int max_diff = 0;//(nums[i]-nums[j])最大值for(int x : nums){//x = nums[k]ans = Math.max(ans,(long)max_diff*x);//x = nums[j]max_diff = Math.max(max_diff,pre_max-x);//x = nums[i]pre_max = Math.max(pre_max,x);}return ans;}
}

 三，2875.无限数组的最短子数组

 该题是一个滑动窗口题：我们实际上是计算环形数组中，是否有子数组和为 target % sum(nums)，如果有就返回 子数组长度 + target / sum * len(nums)，没有就返回 -1.

class Solution {public int minSizeSubarray(int[] nums, int target) {int sum = 0;int total = 0;int ans = Integer.MAX_VALUE;int n = nums.length;for(int x : nums) total += x;for(int l=0,r=0; l<n; r++){sum += nums[r%n];while(sum > target%total){sum -= nums[l%n];l++;}if(sum == target%total)ans = Math.min(ans,r-l+1);}return ans==Integer.MAX_VALUE?-1:ans+target/total*n;}
}

 四，2876.有向图访问计数

class Solution {public int[] countVisitedNodes(List<Integer> edges) {int n = edges.size();List<Integer>[] rg = new ArrayList[n];int[] deg = new int[n];for(int i=0; i<n; i++)rg[i] = new ArrayList<>();for(int i=0; i<n; i++){int y = edges.get(i);//i -> yrg[y].add(i);//统计指向y的节点deg[y]++;//统计指向y的节点个数}//拓扑排序Queue<Integer> queue = new LinkedList<>();for(int i=0; i<n; i++){if(deg[i] == 0)//叶子节点queue.add(i);}while(!queue.isEmpty()){int x = queue.poll();int y = edges.get(x);//x -> yif(--deg[y] == 0)//删除树枝和叶子，保留环queue.add(y);}int[] ans = new int[n];for(int i=0; i<n; i++){if(deg[i] <= 0) continue;List<Integer> ring = new ArrayList<>();for(int x = i; ; x = edges.get(x)){deg[x] = -1;//防止重复ring.add(x);if(edges.get(x) == i)break;}for(int x : ring)rdfs(x,ring.size(),rg,deg,ans);}return ans;}//得到深度void rdfs(int x, int depth, List<Integer>[] rg, int[] deg, int[] ans){ans[x] = depth;for(int y : rg[x]){if(deg[y] == 0)rdfs(y,depth+1,rg,deg,ans);}}
}