枚举中间位置高级篇
参考资料来源灵神在力扣所发的题单，仅供分享学习笔记和记录，无商业用途。
核心思路：参考枚举中间位置基础篇-CSDN博客
力扣题单练习(灵神题单中摘取题目)
447. 回旋镖的数量
核心思路：
因给出的点都不相同，所以不会出现枚举到当前点的次数会>=2的情况，枚举每一个点对当前点的距离，从而得出有多少个点到当前点距离一致。
若有 m 个点到点 i 的距离都相同，那么能够组成的回旋镖数量就是 m * (m - 1)。这是因为从 m 个点里选 2 个点进行排列，排列数为 A(m, 2) = m * (m - 1)。
计算从m个点中选2个点进行排列动态(边统计数量)计算：ret+=map[buff]++*2;
class Solution {
public:int numberOfBoomerangs(vector<vector<int>>& points) {//核心思路：因给出的点都不相同，所以不会出现枚举到当前点的次数会>=2的情况，枚举每一个点对当前点的距离，从而得出有多少个点到当前点距离一致。//若有 m 个点到点 i 的距离都相同，那么能够组成的回旋镖数量就是 m * (m - 1)。这是因为从 m 个点里选 2 个点进行排列，排列数为 A(m, 2) = m * (m - 1)。int ret=0;unordered_map<int,int> map;for(auto& x:points){int buff=0;for(auto& y:points){buff=(x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1]);//采用的是动态计算的方式，在每次发现新点时，就把新增的组合数量累加到 ret 中。这样一来，当统计完所有点之后，ret 中存储的就是最终的结果。ret+=map[buff]++*2;}map.clear();}return ret;}
};456. 132 模式
核心思路：
枚举中间位置 j，寻找左侧最小值与右侧次小值。采用自底向上单调递减栈维护右侧，保证满足栈顶大于左侧最小值的同时并且尝试满足小于当前元素
class Solution {
public:bool find132pattern(vector<int>& nums) {//核心思路：枚举中间位置 j，寻找左侧最小值与右侧次小值。采用自底向上单调递减栈维护右侧，保证满足栈顶大于左侧最小值的同时并且尝试满足小于当前元素int n=nums.size();if(n<3) return false;vector<int> left_min(n);left_min[0]=INT_MAX;//维护当前下标前面区间的最小值for(int i=1;i<n;i++) left_min[i]=min(left_min[i-1],nums[i-1]);stack<int> s; //存放可能满足条件的nums[k],维护自底向上递减栈，j实际上就是a[k]左侧第一个严格大于a[k]的元素下标for(int i=n-1;i>=1;i--){int current=nums[i]; //当前元素int buff=left_min[i]; //左侧区间最小值if(buff>=current) continue; //当前位置元素不合法while(!s.empty() && s.top()<=buff) s.pop(); //保证nums[k]>nums[i]if(!s.empty() && s.top()<current) return true; //栈顶元素为可能满足条件的最小元素，如果存在栈顶元素<nums[j]则存在132模式s.push(current);}return false;}
};3067. 在带权树网络中统计可连接服务器对数目
题意：
给定一个双向路径带权节点数组，要求找到一个节点有至少2条不同的路径并且到路径上的节点的权重可以被signalSpeed整除，统计有多少对满足条件的服务器对组合。
核心思路：
根据给定数组构建路径图，枚举每一个节点，保证有至少两条不同路径。深搜找满足条件的数量，然后进行局部计算组合数量最终得到全部满足条件的组合数量
乘法原理：累加使用过的节点数*当前新统计节点，然后更新使用过的节点数
class Solution {
public://深搜：查找根元素到当前元素的权重可以被signalSpeed整除的节点数量int dfs(vector<vector<pair<int,int>>>& f, int x, int i, int sum, int signalSpeed){int cnt=sum%signalSpeed==0;for(auto &[y,w]:f[x]){if(y!=i) cnt+=dfs(f,y,x,sum+w,signalSpeed);}return cnt;}vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {//题意：给定一个双向路径带权节点数组，要求找到一个节点有至少2条不同的路径并且到路径上的节点的权重可以被signalSpeed整除，统计有多少对满足条件的服务器对组合。//核心思路：根据给定数组构建路径图，枚举每一个节点，保证有至少两条不同路径。深搜找满足条件的数量，然后进行局部计算组合数量最终得到全部满足条件的组合数量int n=edges.size()+1;vector<vector<pair<int,int>>> f(n+1);//建立路径图for(auto &k:edges){int x=k[0],y=k[1],w=k[2];f[x].push_back({y,w});f[y].push_back({x,w});}vector<int> ret(n);for(int i=0;i<=n;i++){if(f[i].size()<=1) continue;int cnt=0;for(auto &[x,w]:f[i]){int buff=dfs(f,x,i,w,signalSpeed);ret[i]+=buff*cnt; //用前面统计过局部答案的节点数*新满足条件的节点数获得当前局部答案。保证了最后能算出总组合数cnt+=buff; //前面统计过组合的节点数} }return ret;}
};灵神枚举中间题单2000分以下题目以完成，后续会更新2000+题目的题解