做商城网站一般用什么,佛山推广seo排名,官方网站建设调研报告,做网站的哪家比较好Leetcode Test
1334 阈值距离内邻居最少的城市(11.14)
有 n 个城市#xff0c;按从 0 到 n-1 编号。给你一个边数组 edges#xff0c;其中 edges[i] [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边#xff0c;距离阈值是一个整数 distanceThreshold。…Leetcode Test
1334 阈值距离内邻居最少的城市(11.14)
有 n 个城市按从 0 到 n-1 编号。给你一个边数组 edges其中 edges[i] [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市则返回编号最大的城市。
注意连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
提示
2 n 1001 edges.length n * (n - 1) / 2edges[i].length 30 fromi toi n1 weighti, distanceThreshold 10^4所有 (fromi, toi) 都是不同的。
【Floyd】
int findTheCity(int n, int** edges, int edgesSize, int* edgesColSize, int distanceThreshold) {int ans[2] {INT_MAX 1, -1};//初始化mp矩阵int mp[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {mp[i][j] INT_MAX 1;}}//赋值mp矩阵for (int i 0; i edgesSize; i) {int from edges[i][0], to edges[i][1], weight edges[i][2];mp[from][to] mp[to][from] weight;}//计算Floydfor (int k 0; k n; k) {//对角线k到k的距离是0mp[k][k] 0;for (int i 0; i n; i) {for (int j 0; j n; j) {//更新Floyd距离mp[i][j] fmin(mp[i][j], mp[i][k] mp[k][j]);}}}//统计距离阈值内的城市数目for (int i 0; i n; i) {int cnt 0;//计算以i为起点在距离阈值内的j城市数目for (int j 0; j n; j) {if (mp[i][j] distanceThreshold) {cnt;//实际上这里计算了m[k][k]但是由于每一个城市都多计算了一个所以没有影响}}//如果cnt的城市数目更少更新ans0为计数ans1为编号if (cnt ans[0]) {ans[0] cnt;ans[1] i;}}//返回城市编号return ans[1];
}2656 K个元素的最大和(11.15)
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次最大化你的得分
从 nums 中选择一个元素 m 。将选中的元素 m 从数组中删除。将新元素 m 1 添加到数组中。你的得分增加 m 。
请你返回执行以上操作恰好 k 次后的最大得分。
提示
1 nums.length 1001 nums[i] 1001 k 100
【贪心】
int maximizeSum(int* nums, int numsSize, int k){int max0;for(int i0;inumsSize;i){maxfmax(max,nums[i]);//O(n)找到nums的最大值}//max , max1, ...,maxk-1高斯求和即可return max*k(k-1)*k/2;
}2760 最长奇偶子数组(11.16)
给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。
请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 l r nums.length) 且满足以下条件的 最长子数组
nums[l] % 2 0对于范围 [l, r - 1] 内的所有下标 i nums[i] % 2 ! nums[i 1] % 2对于范围 [l, r] 内的所有下标 i nums[i] threshold
以整数形式返回满足题目要求的最长子数组的长度。
注意子数组 是数组中的一个连续非空元素序列。
提示
1 nums.length 100 1 nums[i] 100 1 threshold 100
int longestAlternatingSubarray(int* nums, int numsSize, int threshold){int cnt0,nnumsSize,left0;while(leftn){if(nums[left]threshold || nums[left]%21){left;continue;}int startleft;left;while(leftn nums[left]threshold nums[left]%2!nums[left-1]%2){left;}cntfmax(cnt,left-start);}return cnt;
}
//时间复杂度O(n)一次遍历left只增不减2736 最大和查询(11.17)
给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 另给你一个下标从 1 开始的二维数组 queries 其中 queries[i] [xi, yi] 。
对于第 i 个查询在所有满足 nums1[j] xi 且 nums2[j] yi 的下标 j (0 j n) 中找出 nums1[j] nums2[j] 的 最大值 如果不存在满足条件的 j 则返回 -1 。
返回数组 answer **其中 answer[i] 是第 i 个查询的答案。
提示
nums1.length nums2.lengthn nums1.length 1 n 1051 nums1[i], nums2[i] 109 1 queries.length 105queries[i].length 2xi queries[i][1]yi queries[i][2]1 xi, yi 109
【单调栈 二分】
class Solution {
public:vectorint maximumSumQueries(vectorint nums1, vectorint nums2, vectorvectorint queries) {vectorpairint, int sortedNums;vectortupleint, int, int sortedQueries;for (int i 0; i nums1.size(); i) {sortedNums.emplace_back(nums1[i], nums2[i]);}sort(sortedNums.begin(), sortedNums.end(), greaterpairint, int());for (int i 0; i queries.size(); i) {sortedQueries.emplace_back(i, queries[i][0], queries[i][1]);}sort(sortedQueries.begin(), sortedQueries.end(), [](tupleint, int, int a, tupleint, int, int b) {return get1(a) get1(b);});vectorpairint, int stk;vectorint answer(queries.size(), -1);int j 0;for (auto [i, x, y] : sortedQueries) {while (j sortedNums.size() sortedNums[j].first x) {auto [num1, num2] sortedNums[j];while (!stk.empty() stk.back().second num1 num2) {stk.pop_back();}if (stk.empty() || stk.back().first num2) {stk.emplace_back(num2, num1 num2);}j;}int k lower_bound(stk.begin(), stk.end(), make_pair(y, 0)) - stk.begin();if (k stk.size()) {answer[i] stk[k].second;}} return answer;}
};2342 数位和相等数对的最大和(11.18)
给你一个下标从 0 开始的数组 nums 数组中的元素都是 正 整数。请你选出两个下标 i 和 ji ! j且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j 找出并返回 nums[i] nums[j] 可以得到的 最大值 。
提示
1 nums.length 1051 nums[i] 109
【hash】
int maximumSum(int* nums, int numsSize) {int hash[82];for(int i0;i82;i){hash[i]0;}int ret-1;for(int i0;inumsSize;i){int sum0,tempnums[i];while(temp0){sumtemp%10;temp/10;}if(hash[sum]0){retfmax(ret,hash[sum]nums[i]);}hash[sum]fmax(hash[sum],nums[i]);}return ret;
}689 三个无重叠子数组的最大和(11.19)
给你一个整数数组 nums 和一个整数 k 找出三个长度为 k 、互不重叠、且全部数字和3 * k 项最大的子数组并返回这三个子数组。
以下标的数组形式返回结果数组中的每一项分别指示每个子数组的起始位置下标从 0 开始。如果有多个结果返回字典序最小的一个。
提示
1 nums.length 2 * 1041 nums[i] 2161 k floor(nums.length / 3)
【滑动窗口】
class Solution {
public:vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {vectorint ans;int sum10,maxsum10,maxsum1id0;int sum20,maxsum120,maxsum12id10,maxsum12id20;int sum30,maxsum30;//初始化for(int ik*2;inums.size();i){//以第三个窗口为基准进行判定sum1nums[i-k*2];sum2nums[i-k];sum3nums[i];//求出当前三个窗口的元素和也就是初始的划分if(ik*3-1){//如果第三个窗口已经遍历完成if(sum1maxsum1){//如果新的sum1大于原来的则更新maxsum1maxsum1sum1;maxsum1idi-k*31;//同时更新maxsum1的id}if(maxsum1sum2maxsum12){//如果新的sum12大于原来的则更新maxsum12maxsum12maxsum1sum2;maxsum12id1maxsum1id;maxsum12id2i-k*21;}if(maxsum12sum3maxsum3){//如果新的sum123大于原来的则更新maxsum3maxsum3maxsum12sum3;ans{maxsum12id1,maxsum12id2,i-k1};}sum1-nums[i-k*31];sum2-nums[i-k*21];sum3-nums[i-k1];//已经向右滑动了去掉首位值}}return ans;}
};
/*使用3个大小为k的滑动窗口sum1是第一个的元素和【0k-1】sum2是第二个的元素和【k2k-1】sum3是第三个的元素和【2k3k-1】同时向右滑动三个窗口维护maxsum12和对应的位置仅当元素和超过最大元素和时才修改最大元素和
*/53 最大子数组和(11.20)
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
提示
1 nums.length 105-104 nums[i] 104
【动态规划】
int maxSubArray(int* nums, int numsSize){int f0,maxnums[0];for (int i0;inumsSize;i){ffmax(fnums[i],nums[i]); //最大前缀和维护f(i)f(i-1)nums[i] or f(i)nums[i]maxfmax(max,f); //最大值维护旧值or最大前缀和当前nums[i]}return max;
}
//f(i) 代表以第 i 个数结尾的「连续子数组的最大和」
//求出每个位置的 f(i)然后返回 f 数组中的最大值即可
