卫生室可以做网站吗网站建设公司顺义

当前位置： 首页 > news >正文

卫生室可以做网站吗,网站建设公司顺义,棋牌游戏网站建设费用,成都设计专业的装修公司目录 有序三元组中的最大值 I有序三元组中的最大值 II无限数组的最短子数组 有序三元组中的最大值 I 给你一个下标从 0 开始的整数数组nums。 请你从所有满足 i j k 的下标三元组 (i, j, k) 中#xff0c;找出并返回下标三元组的最大值。如果所有满足条件的三元组的… 目录 有序三元组中的最大值 I有序三元组中的最大值 II无限数组的最短子数组 有序三元组中的最大值 I 给你一个下标从 0 开始的整数数组nums。 请你从所有满足 i j k 的下标三元组 (i, j, k) 中找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数则返回 0 。 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。 示例 1 输入nums [12,6,1,2,7] 输出77 解释下标三元组 (0, 2, 4) 的值是 (nums[0] -nums[2]) * nums[4] 77 。 可以证明不存在值大于 77 的有序下标三元组。 示例 2 输入nums [1,10,3,4,19] 输出133 解释下标三元组 (1, 2, 4) 的值是 (nums[1] -nums[2]) * nums[4] 133 。 可以证明不存在值大于 133 的有序下标三元组。 示例 3 输入nums [1,2,3] 输出0 解释唯一的下标三元组 (0, 1, 2) 的值是一个负数(nums[0] -nums[1]) * nums[2] -3 。因此答案是 0 。 提示 3 n u m s . l e n g t h 100 3 nums.length 100 3nums.length100 1 n u m s [ i ] 1 0 6 1 nums[i] 10^6 1nums[i]106 分析 根据数据范围可以发现 n u m s . l e n g t h nums.length nums.length最大也只是100因此可以直接按照题意暴力枚举满足题意的 i , j , k i,j,k i,j,k三个位置的数计算出 ( n u m s [ i ] − n u m s [ j ] ) ∗ n u m s k * numsk∗nums[k]的值用ans维护最大值即可。时间复杂度 O ( n 3 ) O(n^3) O(n3) 代码 class Solution { public:long long maximumTripletValue(vectorint nums) {int nnums.size();long long ans0;for(int i0;in;i){for(int ji1;jn;j){for(int kj1;kn;k){ansmax(ans,(long long)(nums[i]-nums[j])*nums[k]);}}}return ans;} };有序三元组中的最大值 II 给你一个下标从 0 开始的整数数组nums。 请你从所有满足 i j k 的下标三元组 (i, j, k) 中找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数则返回 0 。 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。 示例 1 输入nums [12,6,1,2,7] 输出77 解释下标三元组 (0, 2, 4) 的值是 (nums[0] -nums[2]) * nums[4] 77 。 可以证明不存在值大于 77 的有序下标三元组。 示例 2 输入nums [1,10,3,4,19] 输出133 解释下标三元组 (1, 2, 4) 的值是 (nums[1] -nums[2]) * nums[4] 133 。 可以证明不存在值大于 133 的有序下标三元组。 示例 3 输入nums [1,2,3] 输出0 解释唯一的下标三元组 (0, 1, 2) 的值是一个负数(nums[0] -nums[1]) * nums[2] -3 。因此答案是 0 。 提示 3 n u m s . l e n g t h 1 0 5 3 nums.length 10^5 3nums.length105 1 n u m s [ i ] 1 0 6 1 nums[i] 10^6 1nums[i]106 分析 此题为有序三元组中的最大值I的加强版即数据范围变大了不可以在使用暴力 O ( n 3 ) O(n^3) O(n3)的方法完成。我们只能在 O ( n ) O(n) O(n)的时间复杂度下完成此题。 不难发现要使得这个有序下标三元组最大对于 j j j位置的数来说 i i i和 k k k位置的数都是越大越好发现了这一点后续就好处理了。只需要维护每一个 j j j位置的前缀最大值 p r e [ j ] pre[j] pre[j]和后缀最大值 s u f [ j ] suf[j] suf[j]以当前 j j j位置作为下标三元组中间位置的最大值即为 ( p r e [ j ] − n u m s [ j ] ) ∗ s u f j *sufj∗suf[j]。即可在线性时间复杂度内完成该题目。 代码 class Solution { public:long long maximumTripletValue(vectorint nums) {//记录数组前面和后面的最大数int nnums.size();vectorintpre(n1),suf(n1);int ma0;for(int i0;in;i){pre[i]ma;mamax(ma,nums[i]);}ma0;for(int in-1;i0;i–){suf[i]ma;mamax(ma,nums[i]);}long long ans0;for(int i1;in-1;i){//枚举中间的那个数字ansmax((long long)(pre[i]-nums[i])*suf[i],ans);}return ans;} };无限数组的最短子数组 给你一个下标从 0 开始的数组 nums 和一个整数 target 。 下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。 请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组并返回该子数组的长度。如果不存在满足条件的子数组返回 -1 。 示例 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 是子数组的最短长度。 示例 2 输入nums [1,1,1,2,3], target 4 输出2 解释在这个例子中 infinite_nums [1,1,1,2,3,1,1,1,2,3,1,1,…]. 区间 [4,5] 内的子数组的元素和等于 target 4 且长度length 2 。 可以证明当元素和等于目标值 target 4 时2 是子数组的最短长度。 示例 3 输入nums [2,4,6,8], target 3 输出-1 解释在这个例子中 infinite_nums [2,4,6,8,2,4,6,8,…] 。 可以证明不存在元素和等于目标值 target 3 的子数组。 提示 1 n u m s . l e n g t h 1 0 5 1 nums.length 10^5 1nums.length105 1 n u m s [ i ] 1 0 5 1 nums[i] 10^5 1nums[i]105 1 t a r g e t 1 0 9 1 target 10^9 1target109 分析 题目需要计算一个 i n f i n i t e n u m s infinite_nums infiniten​ums数组中是否能够组成和为 t a r g e t target target的值我们可以想到如果 t a r g e t target target能够被构成则其是被 k k k个 n u n s nuns nuns数组的和 s u m sum sum以及一个余数 v v v构成即 t a r g e t k ∗ s u m v , k 0 , 0 v s u m targetk*sumv,k0,0vsum targetk∗sumv,k0,0vsum。 所以我们主要讨论的是 v v v这个数字能否被 i n f i n i t e n u m s infinite_nums infiniten​ums数组构造出来因为v是target除以sum的余数所以 v s u m vsum vsum因此如果v能够被构造出来其肯定是在两个nums数组中的一段数字且长度不超过n(只用考虑两个nums数组就可以考虑到从nums数组末加到nums数组开头)。 所以可以用双指针来对两个nums数组连接起来的数组进行构造在右指针移动的同时一旦当前和totalv则左指针移动最终维护一个构造出v值的最短子数组长度。 代码 class Solution { public:int minSizeSubarray(vectorint nums, int target) {int nnums.size();long long sum0;for(int i0;in;i)sumnums[i];int ptarget/sum;//至少需要这么多个完整的数组int vtarget%sum;//剩下的值需要从剩下的两个数组中组成int total0,minnn;for(int left0,right0;right2*n;right){totalnums[right%n];while(totalv)total-nums[left%n],left;if(totalv)minnmin(minn,right-left1);}if(minnn)return -1;return p*nminn;} };