链接:LeetCode
[Leetcode]2873. 有序三元组中的最大值 I
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
暴力即可,\(O(N^3)\)
class Solution {
public long maximumTripletValue(int[] nums) {
int n = nums.length;
long res = 0;
for(int i=0;i<n;++i) {
for(int j=i+1;j<n;++j) {
for(int k=j+1;k<n;++k) {
res = Math.max(res, (nums[i]-nums[j]) * 1L * nums[k]);
}
}
}
return res;
}
}
[Leetcode]2874. 有序三元组中的最大值 II
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
贪心。
首先,输出的数值最小为 0,同时数组中每个元素均为正数,因此,我们要让 (nums[i] - nums[j]) * nums[k] 最大,只需要对于固定的 k 找到其前面 nums[i] - nums[j] 的最大值。
为了使得 nums[i] - nums[j] 尽可能大,我们需要对于固定的 j 找到其前面最大的 nums[i] 再将两者相减。因此我们只需要维护三个东西:到当前位置的最大值,到当前位置为止最大的 nums[i] - nums[j],到当前位置为止最大的 (nums[i] - nums[j]) * nums[k]. 而从上面的分析可以看出,这些都可以遍历过程中实现。
因此时间复杂度是\(\mathcal{O}(n)\) 的。
class Solution {
public long maximumTripletValue(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
long res = 0, maxDiff = 0;
long max = nums[0], min = nums[0];
for(int i=0;i<nums.length-1;++i) {
if(nums[i] > max) {
max = nums[i];
min = nums[i];
} else if(nums[i] < min) {
min = nums[i];
}
maxDiff = Math.max(maxDiff, max-min);
res = Math.max(res, maxDiff * nums[i+1]);
}
return res;
}
}
[Leetcode]2875. 无限数组的最短子数组
给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组,并返回该子数组的长度。如果不存在满足条件的子数组,返回 -1 。
因为是无限循环的,所以结果可能是 任意 k 个完整的数组加上循环数组中的一部分。
提前求出有几个完整的,然后用滑动窗口计算最小的窗口。
class Solution {
public int minSizeSubarray(int[] nums, int target) {
int sum = getSum(nums);
int n = nums.length;
int[] doubleNums = new int[2*n];
for(int i=0;i<n;++i) doubleNums[i] = nums[i];
for(int i=n;i<2*n;++i) doubleNums[i] = nums[i-n];
int res = getMinSizeSubarray(doubleNums, target % sum);
return res == Integer.MAX_VALUE ? -1 : res + target / sum * n;
}
private int getMinSizeSubarray(int[] nums, int target) {
if(target == 0) return 0;
int res = Integer.MAX_VALUE;
int start = 0;
int sum = 0;
for(int i=0;i<nums.length;++i) {
sum += nums[i];
while(sum > target) {
sum -= nums[start];
start ++;
}
if(sum == target) res = Math.min(res, i-start+1);
}
return res;
}
private int getSum(int[] nums) {
int res = 0;
for(int num:nums) res += num;
return res;
}
}
[Leetcode]2876. 有向图访问计数
现有一个有向图,其中包含 n 个节点,节点编号从 0 到 n - 1 。此外,该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程:
- 你从节点 x 开始,通过边访问其他节点,直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案,其中 answer[i] 表示如果从节点 i 开始执行该过程,你可以访问到的不同节点数。
这是一个经典的类型的图——基环树,每个点都只有一条出去的边。其有特点:所有的点要么在环上,要么有一条路径走向环。环上的点不会有往外的边(因为该点的边指向环中其他的点)。
先找到所有的环,环上所有点能到达的点都是环上的点。接下来从环上的点出发往外走,每个点能到达的新的点可以进行访问点数的更新。如果原节点能到达 k 个,则往外走一步的新节点能到达 k+1 个点。
找环我们可以使用拓扑排序来做,即不断找入度为 0 的点放入栈中,删去其出边,再放入新产生的入度为 0 的点,最后剩下的图只有环,最后环里的所有点可以通过 DFS 等方式得到。
时间复杂度为 \(\mathcal{O}(n)\).
class Solution {
public int[] countVisitedNodes(List<Integer> edges) {
int n = edges.size();
List<List<Integer>> rev = new ArrayList<>();
int[] indegree = new int[n];
for(int i=0;i<n;++i) {
rev.add(new ArrayList<>());
}
for(int i=0;i<n;++i) {
int v = edges.get(i);
indegree[v] += 1;
rev.get(v).add(i);
}
// 拓扑排序
Deque<Integer> stack = new ArrayDeque<>();
for(int i=0;i<n;++i) {
if(indegree[i] == 0) stack.push(i);
}
while(!stack.isEmpty()) {
int u = stack.pop();
int v = edges.get(u);
indegree[v] --;
if (indegree[v] == 0) {
stack.push(v);
}
}
// 找环里的点
int[] res = new int[n];
for(int i=0;i<n;++i) {
if(indegree[i] > 0) {
LinkedList<Integer> elements = new LinkedList<>(List.of(i));
while(edges.get(elements.getLast()) != i) {
elements.add(edges.get(elements.getLast()));
}
for(int element:elements) {
res[element] = elements.size();
indegree[element] = 0;
}
}
}
// 更新环外的点
for(int i=0;i<n;++i) {
if(res[i] == 0) continue;
Deque<Integer> temp = new ArrayDeque<>(List.of(i));
while(!temp.isEmpty()) {
int u = temp.pop();
for(int v: rev.get(u)) {
if(res[v] == 0) {
res[v] = res[u] + 1;
temp.push(v);
}
}
}
}
return res;
}
}
参考:LeetCode
- Leetcode Contest Weekly 365leetcode contest weekly 365 leetcode contest weekly 361 leetcode contest weekly 355 leetcode contest weekly 367 leetcode contest weekly 350 leetcode contest weekly 368 leetcode contest weekly 351 leetcode contest weekly 339 leetcode contest weekly 364 leetcode contest weekly 359