免费企业建站cms,建站记录查询,东营市住房和城乡建设局官网,凤岗本地网站题目列表
2855. 使数组成为递增数组的最少右移次数
2856. 删除数对后的最小数组长度
2857. 统计距离为 k 的点对
2858. 可以到达每一个节点的最少边反转次数
一、使数组成为递增数组的最少右移次数 这题可以直接暴力求解#xff0c;枚举出每种右移后的数组#xff0c;将…题目列表
2855. 使数组成为递增数组的最少右移次数
2856. 删除数对后的最小数组长度
2857. 统计距离为 k 的点对
2858. 可以到达每一个节点的最少边反转次数
一、使数组成为递增数组的最少右移次数 这题可以直接暴力求解枚举出每种右移后的数组将它和排完序后的数组比较时间复杂度为O(n^2)
代码如下
class Solution {
public:int minimumRightShifts(vectorint nums) {vectorint vnums;sort(v.begin(),v.end());for(int i0;inums.size();i){if(vnums) return i;nums.insert(nums.begin(),nums.back());nums.pop_back();}return -1;}
};
这个能过但是有没有更快的算法我们观察一下这个数组如果它要是能右移成递增数组那么它必然是由两个递增数组构成的且前一个数组的最小值一定大于后一个数组的最大值答案就是第二个数组的长度所以我们只要试着将数组拆分成两个递增数组就行(边界条件挺多一定要细节)时间复杂度为O(n)
代码如下
class Solution {
public:int minimumRightShifts(vectorint nums) {int end10,nnums.size();while(end11nnums[end1]nums[end11])end1;if(end1n-1) return 0;int end2end11;while(end21nnums[end2]nums[end21])end2;if(end2!n-1||nums[0]nums[n-1]) return -1;else return n-end1-1;}
};
二、删除数对后的最小数组长度 这题还是比较难想到的比较绕。我们需要多枚举几个例子然后就会发现当某个数的个数cnt大于等于数组长度n的一半时最优的方案就是将它前后的数都与它相互抵消(因为如果还让其他数相互抵消那么剩余的和该数相抵消的元素个数就会变小从而该元素剩下的个数就会变多)所以答案就是cnt-(n-cnt)2*cnt-n那么如果没有一个数的个数大于数组长度的一半呢
首先从最特殊的数组中数字都是唯一的情况开始讨论那么显然当数组长度为偶数时答案为0当数组长度为奇数时答案为1那么是不是所有的情况都符合这个规律呢答案是确实都符合这个规律因为所有的数的个数都n/2那么我们就可以通过抵消将数的个数全部化成1
代码如下
class Solution {
public:int minLengthAfterRemovals(vectorint nums) {unordered_mapint,intcnt;int nnums.size(),ansn1;//n1奇数为1偶数为0for(auto x:nums)cnt[x];for(auto [x,y]:cnt)if(yn/2)ansmax(ans,2*y-n);return ans;}
};
当然这题如果想不到这么深那么也可以用最基本的贪心每次拿出出现次数最大的两个元素相抵消直到剩下零个数或剩下一个数为止。代码如下
class Solution {
public:int minLengthAfterRemovals(vectorint nums) {unordered_mapint,intcnt;int nnums.size(),ansn1;for(auto x:nums)cnt[x];priority_queueintq;for(auto [x,y]:cnt)q.push(y);while(q.size()1){int xq.top();q.pop();int yq.top();q.pop();x--,y--;if(x)q.push(x);if(y)q.push(y);}return q.empty()?0:q.top();}
};
三、统计距离为k的点对 看到两个数的和k以及k的数据范围我们就要想到这题能用暴力枚举点来做然后通过枚举到的点求出与之相对应的点的坐标答案加上之前出现的该点个数(用哈希表统计)代码如下
class Solution {
public:int countPairs(vectorvectorint coordinates, int k) {int ncoordinates.size();unordered_maplong long,intcnt;int ans0;for(auto e:coordinates){int xe[0],ye[1];for(int i0;ik;i){auto itcnt.find((x^i)*1000000LL(y^(k-i)));if(it!cnt.end())ansit-second;}cnt[x*1000000LLy];}return ans;}
}; 四、可以到达每一个节点的最小边反转次数 这题是换根dp即通过根节点的最小边反转次数来得到它孩子结点的最小边反转次数因为它的孩子结点的反转边的个数就和它父节点的最小边反转次数相差一个它俩之间的边是否需要翻转其它的都一样。
代码如下
class Solution {
public:vectorint minEdgeReversals(int n, vectorvectorint edges) {//建图vectorvectorpairint,intg(n);for(auto e:edges){int xe[0],ye[1];g[x].push_back({y,1});//顺便记录一下边的方向1为正-1为逆g[y].push_back({x,-1});}vectorintans(n);//计算根节点的最少边反转次数functionvoid(int,int)dfs[](int x,int fa){for(auto [y,dir]:g[x]){if(y!fa){ans[0](dir0);//方向反的需要反转dfs(y,x);}}};dfs(0,-1);//换根dpfunctionvoid(int,int)reroot[](int x,int fa){for(auto [y,dir]:g[x]){if(y!fa){ans[y]ans[x]dir;reroot(y,x);}}};reroot(0,-1);return ans;}
};
