100088. Maximum Value of an Ordered Triplet I
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
测试样例：
输入：nums = [12,6,1,2,7]
输出：77
解释：
下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。可以证明不存在值大于 77 的有序下标三元组。
解答：这个范围其实可以暴力，直接用了第二题的算法。具体解答也就放在第二题了。
class Solution {
public long maximumTripletValue(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
int max = 0;
for (int i = 0; i < len; ++i) {
if (i != 0) {
dp[i] = Math.max(dp[i - 1], max - nums[i]);
}
max = Math.max(max, nums[i]);
}
long res = 0;
for (int i = 2; i < len; ++i) {
long tmp = nums[i];
res = Math.max(dp[i - 1] * tmp, res);
}
return res;
}
}100086. Maximum Value of an Ordered Triplet II
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
测试样例：
输入：nums = [12,6,1,2,7]
输出：77
解释：
下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。可以证明不存在值大于 77 的有序下标三元组。
解答：这题简化一下，只要遍历两次数组。第一次遍历数组，寻找到当前位置，最大的(nums[i] - nums[j])之差，具体算法之遥记录max。第二次遍历，就是以当前数字为nums[k], 然后利用之间算出来的最大的(nums[i] - nums[j])之差获取结果。
class Solution {
public long maximumTripletValue(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
int max = 0;
for (int i = 0; i < len; ++i) {
if (i != 0) {
dp[i] = Math.max(dp[i - 1], max - nums[i]);
}
max = Math.max(max, nums[i]);
}
long res = 0;
for (int i = 2; i < len; ++i) {
long tmp = nums[i];
res = Math.max(dp[i - 1] * tmp, res);
}
return res;
}
}100076. Minimum Size Subarray in Infinite Array
给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。
测试样例：
输入：nums = [1,2,3], target = 5
输出：2
解释：
在这个例子中 infinite_nums = [1,2,3,1,2,3,1,2,...] 。区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。
解答：这道题目本质上是考了双指针。首先算出当前数组的和，然后计算出需要几次循环才能达到target。其次就是利用双指针来寻找数组中最短距离可以到达remain。注意有头尾相连的情况，所以双指针还需要额外计算一次。
class Solution {
public int minSizeSubarray(int[] nums, int target) {
long cycleSum = 0;
for (int n : nums) {
cycleSum += n;
}
int cycleCount = (int) (target / cycleSum), remain = (int) (target - cycleSum * cycleCount);
int res = Integer.MAX_VALUE;
long tmpSum = 0;
int st = 0, ed = 0;
while (ed < nums.length) {
tmpSum += nums[ed];
while (tmpSum > remain) {
tmpSum -= nums[st];
++st;
}
if (tmpSum == remain) {
res = Math.min(cycleCount * nums.length + ed - st + 1, res);
}
++ed;
}
st = 0; ed = 0;
tmpSum = cycleSum;
while (st < nums.length) {
tmpSum += nums[st];
while (tmpSum > remain && ed < nums.length) {
tmpSum -= nums[ed];
++ed;
}
if (tmpSum == remain) {
res = Math.min(cycleCount * nums.length + st + 1 + nums.length - ed, res);
}
++st;
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
100075. Count Visited Nodes in a Directed Graph
现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程：
- 你从节点 x 开始，通过边访问其他节点，直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。
测试样例
输入：edges = [1,2,0,0]
输出：[3,3,3,4]
解释：
从每个节点开始执行该过程，记录如下：
- 从节点 0 开始，访问节点 0 -> 1 -> 2 -> 0 。访问的不同节点数是 3 。
- 从节点 1 开始，访问节点 1 -> 2 -> 0 -> 1 。访问的不同节点数是 3 。
- 从节点 2 开始，访问节点 2 -> 0 -> 1 -> 2 。访问的不同节点数是 3 。
- 从节点 3 开始，访问节点 3 -> 0 -> 1 -> 2 -> 0 。访问的不同节点数是 4 。
解答：这周的题目不算难，这道题目主要需要细心。利用动态规划记录一下当前数组产生环的情况和遍历节点数。注意一种情况：1 -> 2 -> 3 -> 4 -> 3。这种情况1和2需要特殊考虑。
class Solution {
private int cyclePoint, maxDepth;
public int[] countVisitedNodes(List<Integer> _edges) {
int[] edges = new int[_edges.size()];
int offset = 0;
for (int n : _edges) {
edges[offset++] = n;
}
int[] dp = new int[offset];
for (int i = 0; i < offset; ++i) {
if (dp[i] == 0) {
cyclePoint = 0;
maxDepth = 0;
dfs(i, edges, dp, 0);
}
}
return dp;
}
private int dfs(int node, int[] edges, int[] dp, int count) {
if (dp[node] == 0) {
++count;
maxDepth = Math.max(maxDepth, count);
dp[node] = -count;
int tmp = dfs(edges[node], edges, dp, count);
if (cyclePoint == 0) {
int curDepth = maxDepth + dp[node] + 1;
dp[node] = curDepth + tmp;
} else {
if (-dp[node] >= cyclePoint) {
dp[node] = maxDepth - cyclePoint + 1;
} else {
dp[node] = maxDepth - cyclePoint + 1 + (dp[node] + cyclePoint);
}
}
return tmp;
} else {
if (dp[node] > 0) {
cyclePoint = 0;
return dp[node];
} else {
cyclePoint = -dp[node];
return 0;
}
}
}
}