阿三做网站,上海高端网站制作公司,广东百度推广的代理商,网站建设实训个人总结3000Leetcode 第 365 场周赛题解 Leetcode 第 365 场周赛题解题目1#xff1a;2873. 有序三元组中的最大值 I思路代码复杂度分析 题目2#xff1a;2874. 有序三元组中的最大值 II思路代码复杂度分析思路2 题目3#xff1a;2875. 无限数组的最短子数组思路代码复杂度分析 题目42873. 有序三元组中的最大值 I思路代码复杂度分析 题目22874. 有序三元组中的最大值 II思路代码复杂度分析思路2 题目32875. 无限数组的最短子数组思路代码复杂度分析 题目42876. 有向图访问计数 Leetcode 第 365 场周赛题解
题目12873. 有序三元组中的最大值 I
思路
暴力。
代码
/** lc appleetcode.cn id2873 langcpp** [2873] 有序三元组中的最大值 I*/// lc codestart
class Solution
{
public:long long maximumTripletValue(vectorint nums){int n nums.size();long long ans INT_MIN;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 max(ans, (long long)(nums[i] - nums[j]) * nums[k]);return ans 0 ? ans : 0;}
};
// lc codeend复杂度分析
时间复杂度O(n3)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
题目22874. 有序三元组中的最大值 II
思路
枚举 k我们需要知道 k 左边 nums[i]−nums[j] 的最大值。
使用 pre_max 维护 k 之前的 nums[i] 的最大值使用 max_diff 维护 nums[i]−nums[j] 的最大值。
每次遍历一个 nums[i]都更新 anspre_maxmax_diff
ans max(ans, (long long)max_diff * nums[i])max_diff max(max_diff, pre_max - nums[i])pre_max max(pre_max, nums[i])
最后 return ans 0 ? ans : 0 即为答案。
代码
/** lc appleetcode.cn id2874 langcpp** [2874] 有序三元组中的最大值 II*/// lc codestart
class Solution
{
public:long long maximumTripletValue(vectorint nums){int n nums.size();long long ans INT_MIN;int max_diff 0, pre_max 0;for (int i 0; i n; i){ans max(ans, (long long)max_diff * nums[i]);max_diff max(max_diff, pre_max - nums[i]);pre_max max(pre_max, nums[i]);}return ans 0 ? ans : 0;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(1)。
思路2
枚举 j
pre_max 数组维护 nums[i] 的最大值。
max_suffix 数组维护 nums[k] 的最大值。
更新 ans max(ans, (long long)(pre_max[j - 1] - nums[j]) * max_suffix[j 1])。
最后 return ans 0 ? ans : 0 即为答案。
class Solution
{
public:long long maximumTripletValue(vectorint nums){int n nums.size();long long ans INT_MIN;vectorint pre_max(n, 0);pre_max[0] nums[0];for (int i 1; i n; i)pre_max[i] max(pre_max[i - 1], nums[i]);vectorint max_suffix(n, 0);max_suffix[n - 1] nums[n - 1];for (int i n - 2; i 0; i--)max_suffix[i] max(max_suffix[i 1], nums[i]);for (int j 1; j n - 1; j)ans max(ans, (long long)(pre_max[j - 1] - nums[j]) * max_suffix[j 1]);return ans 0 ? ans : 0;}
};题目32875. 无限数组的最短子数组
思路
滑动窗口。
设数组 nums 的总和为 total长度为 n。
已知数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
假设有下面这种情况 去掉中间一整段完整的 nums 数组新的目标值为 target % total。
问题转化为在 nums nums[1,…,n-1] 这个长度为 2 * n - 1 的数组上求满足元素和 等于 target % total 的最短子数组设这个长度为 len。
加上 target / total 个完整数组的长度最终的长度为 len target / total * n。
代码
/** lc appleetcode.cn id2875 langcpp** [2875] 无限数组的最短子数组*/// lc codestart// 滑动窗口class Solution
{
public:int minSizeSubarray(vectorint nums, int target){int n nums.size();long long total accumulate(nums.begin(), nums.end(), 0LL);for (int i 0; i n - 1; i)nums.push_back(nums[i]);long long sum 0;int left 0, len INT_MAX;for (int right 0; right 2 * n - 1; right){sum nums[right];while (sum target % total){sum - nums[left];left;}int cur_len right - left 1;if (sum target % total)len min(len, cur_len);}return len INT_MAX ? -1 : len target / total * n;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 为 nums 数组的长度。
空间复杂度O(n)延长了 nums 数组。
题目42876. 有向图访问计数
超出能力范围。
题解【模板】内向基环树
