文章目录
一、找出数组中的所有 K 近邻下标
1、算法：二维枚举
用一个结果数组保存最后结果，数据量只有1000，所以直接上枚举，对于每个下标，去找所有等于
key的下标，如果找到则直接塞到结果数组中。时间复杂度
O ( n 2 ) O(n^2) O(n2)。
2、源码
classSolution{public:
vector<int>findKDistantIndices(vector<int>& nums,int key,int k){int i, j;
vector<int> ans;for(i =0; i < nums.size();++i){for(j =0; j < nums.size();++j){if(key != nums[j]){continue;}if(i < j && j-i <= k){
ans.push_back(i);break;}elseif(j <= i && i-j <= k){
ans.push_back(i);break;}}}return ans;}};
二、统计可以提取的工件
1、算法：二维哈希
直接用一个哈希表哈希出所有的格子，然后对于每个格子如果都被哈希了，则计数器加一。统计格子数量为
n n n，挖出来的数量为 m m m，时间复杂度 O ( n + m ) O(n+m) O(n+m)。
2、源码
int hashv[1010][1010];classSolution{public:intdigArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig){int i, j, k;int ans =0;bool flag;memset(hashv,0,sizeof(hashv));for(i =0; i < dig.size();++i){
hashv[ dig[i][0]][ dig[i][1]]=1;}for(i =0; i < artifacts.size();++i){
flag =true;for(j = artifacts[i][0]; j <= artifacts[i][2]; j++){for(k = artifacts[i][1]; k <= artifacts[i][3];++k){if(hashv[j][k]==0){
flag =false;}}}if(flag){++ans;}}return ans;}};
三、K 次操作后最大化顶端元素
1、算法：分情况讨论
讨论
k = 0 ， 1 ， 2 k = 0，1，2 k=0，1，2 的情况，再讨论 k k k 和 n n n 的大小关系。反正就是疯狂分情况讨论。 k = 0 k=0 k=0，直接返回第 0 个元素； k = 1 k=1 k=1，元素个数小于等于1，返回-1，否则直接返回第 1 个元素； k = 2 k=2 k=2，元素个数小于等于2，返回第0个元素，否则直接返回第 0 个元素 和 第 2 个元素中的大者； k > 3 且 n = 1 k>3 且 n=1 k>3且n=1 的时候， k − n k-n k−n 是奇数，则返回第0个元素，否则返回 -1； k > 3 且 n > 1 k > 3 且 n>1 k>3且n>1的时候，继续讨论： k < n k < n k<n 时，两种情况：1. 删除
k k k 个，然后 n u m s [ k ] nums[k] nums[k] 就是栈顶；2. 删除
k − 1 k-1 k−1 个，然后从 前 k − 1 k-1 k−1 个中，找最大值； k = n k = n k=n 时，取前 n − 1 n-1 n−1 个最大值； k > n k > n k>n 时，取前 n n n 个最大值；
2、源码
class Solution {
public:intmaximumTop(vector<int>& nums,int k){int n = nums.size();int maxv =0;// 边界条件if(k ==0){return nums[0];}elseif(k ==1){if(n <=1){return-1;}else{return nums[1];}}elseif(k ==2){if(n <=2){return nums[0];}else{returnmax(nums[0], nums[2]);}}else{if(n ==1){if((k-n)&1){return nums[0];}return-1;}}if(k < n){// 两种情况：// 1. 删除 k 个，然后 nums[k] 就是栈顶// 2. 删除 k-1 个，然后从 前 k-1 个中，找最大值
maxv = nums[k];for(int i =0; i < k-1;++i){
maxv =max(maxv, nums[i]);}}elseif(k == n){
maxv =0;for(int i =0; i < k-1;++i){
maxv =max(maxv, nums[i]);}}else{sort(nums.begin(), nums.end());
maxv = nums[ nums.size()-1];}return maxv;}};
四、得到要求路径的最小带权子图
1、算法：广度优先搜索
建立一个正图
A A A 和 反图 B B B， s r 1 [ i ] sr1[i] sr1[i] 代表正图 A A A 上从 s r c 1 src1 src1 到 i i i 的最短路； s r 2 [ i ] sr2[i] sr2[i] 代表正图 A A A 上从 s r c 2 src2 src2 到 i i i 的最短路； d e s t [ i ] dest[i] dest[i] 代表反图 B B B 上从 d e s t dest dest 到 i i i 的最短路；然后就是 s r 1 [ i ] + s r 2 [ i ] + d e s t [ i ] sr1[i] + sr2[i] + dest[i] sr1[i]+sr2[i]+dest[i] 取个最小值就可以了。最短路就用 Dijkstra + Heap 优化，或者 SPFA。
2、源码
class Solution {longlongminv(longlong a,longlong b){return a < b ? a : b;}struct edge {int v;longlong w;edge(){}edge(int _v,longlong _w){
v = _v;
w = _w;}};
vector<edge> eg[2][100010];
vector<longlong>bfs(int eid,int n,int start){
vector<longlong> dist;
priority_queue <int> q;int i;for(i =0; i < n;++i){
dist.push_back(-1);}
dist[start]=0;
q.push(start);while(!q.empty()){int u = q.top();
q.pop();for(int i = eg[eid][u].size()-1; i >=0;--i){int v = eg[eid][u][i].v;longlong w = eg[eid][u][i].w;if(dist[u]+ w < dist[v]|| dist[v]==-1){
dist[v]= dist[u]+ w;
q.push(v);}}}return dist;}
public:longlongminimumWeight(int n, vector<vector<int>>& edges,int src1,int src2,int dest){int i;longlong ret =1000000000;
ret *= ret;longlong x = ret;
vector<longlong> sr1, sr2, ds;for(i =0; i < n;++i){
eg[0][i].clear();
eg[1][i].clear();}for(i =0; i < edges.size();++i){int u = edges[i][1];int v = edges[i][0];int w = edges[i][2];
eg[0][v].push_back(edge(u, w));
eg[1][u].push_back(edge(v, w));}
sr1 =bfs(0, n, src1);for(i =0; i < n;++i){if(sr1[i]!=-1){break;}}if(i == n){return-1;}
sr2 =bfs(0, n, src2);for(i =0; i < n;++i){if(sr2[i]!=-1){break;}}if(i == n){return-1;}
ds =bfs(1, n, dest);for(i =0; i < n;++i){if(sr1[i]==-1|| sr2[i]==-1|| ds[i]==-1){continue;}
ret =minv(ret, sr1[i]+ sr2[i]+ ds[i]);}return ret == x ?-1: ret;}};
本文转载自: https://blog.csdn.net/WhereIsHeroFrom/article/details/123457150
版权归原作者 英雄哪里出来 所有， 如有侵权，请联系我们删除。
版权归原作者 英雄哪里出来 所有， 如有侵权，请联系我们删除。