第一次双周赛~总结-进步:

T1：从2个数字组 中生成最小的数字

给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。

解：

1.关键：

(1)预处理:
set1用于存放已经访问过的数字
min1--用于记录数组nums1中的最小数字,min2 --nums2中最小数字
min_common:记录2者共有的最小的数字，初始化为10
（2）分别从下标为1开始遍历,分是否为common元素讨论
//(2)分是否有 共有元素 ，否则 分别取最小的元素 ,返回得到最终的结果

2.代码：

class Solution {
public:int minNumber(vector<int>& nums1, vector<int>& nums2) {//直接贪心就完事了//(1)预处理://set1用于存放已经访问过的数字//min1--用于记录数组nums1中的最小数字,min2 --nums2中最小数字//min_common:记录2者共有的最小的数字，初始化为10unordered_set<int> set1;int min1 = nums1[0],min2 = nums2[0],min_common=10;int size1 = nums1.size(),size2 = nums2.size();set1.insert(nums1[0]); set1.insert(nums2[0]);if(nums1[0] == nums2[0]){min_common = nums1[0];}//（2）分别从下标为1开始遍历,分是否为common元素讨论for(int i=1;i<size1;i++){if(set1.count(nums1[i])){//common元素if(min_common > nums1[i]){min_common = nums1[i];}}//不是common元素:set1.insert(nums1[i]); //加入set容器if(nums1[i] < min1){min1 = nums1[i];}}//--for(int i=1;i<size2;i++){if(set1.count(nums2[i])){//common元素if(min_common > nums2[i]){min_common = nums2[i];}}set1.insert(nums2[i]);if(nums2[i] < min2){min2= nums2[i];}}//(2)分是否有 共有元素 ，否则 分别取最小的元素//case1:if(min_common != 10){return min_common;}//case2:int left = min(min1,min2);int right = max(min1,min2);return left*10+right;}
};

T2:找到最大开销的子字符串

给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。

子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。

字符的价值 定义如下：

• 如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
  • 比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
• 否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。

请你返回字符串 s 的所有子字符串中的最大开销。

解：

1.关键：

（1）首先，建立一个映射 map <26个字母，开销值>
(2)为了得到最大开销，
dp[i]--表示以s[i]结束的连续子串的最大开销
初值 dp[0] = max(0,map1[s[0]])
递推关系:dp[i] = max(dp[i-1]+map1[s[i]],map1[s[i]]) -最后，带擂台返回 一个max即可

2.代码：

class Solution {
public:int maximumCostSubstring(string s, string chars, vector<int>& vals) {int ans = 0;int n = s.size();vector<int> dp(n,0);//(1)建立一个映射mapunordered_map<char,int> map0;int size_chars = chars.size();for(int i=0;i<size_chars;i++){map0[chars[i]] = i+1; //记录 对应字母在 vals中的 下标位置+1}unordered_map<char,int> map1;for(char ch = 'a';ch<='z';ch++){if(map0.count(ch) != 0){map1[ch] = vals[map0[ch]-1];}else{map1[ch] = ch-'a'+1;}}//(2)动态规划 中的 初值 和 递推关系:dp[0] = max(0,map1[s[0]]);ans = max(dp[0],ans);//--递推，for(int i=1;i<n;i++){dp[i] = max(dp[i-1]+map1[s[i]],map1[s[i]]) ;ans = max(ans, dp[i]);}return ans;}
};

T3 -之前的预备知识：（Bezout定理 + 最小操作次数 使数组元素相等）

--先完成 leetcode 462. 最小操作次数使数组元素相等 II。 

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solutions/1504085/by-fuxuemingzhu-13z3/?orderBy=most_votes

具体为什么要选择 “中位数” 作为target数值 ，见 负雪明烛 的这个解析，非常清晰

解：

1.关键：

（1）通过对数组进行排序，选择 向下取整的中位数 ，作为target

（2）遍历计算差值diff[i],然后求和，不能直接求和，因为。。。自己去想一下就好了

2.代码：

class Solution {
public:int minMoves2(vector<int>& nums) {//(1)排序:sort(nums.begin() , nums.end());//(2）找到targetint n = nums.size();int target = nums[n/2];//(3)计算diff[i]，并且求和int ans=0;for(int i=0;i<n;i++){ans+= abs(nums[i] - target);}return ans;}
};

好了，言归正传:

T3：使得所有大小为k的连续子数组和 相等

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

• 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

解：

1.关键：

//借鉴 灵茶山的 思路:

 (1)铺垫：让一个数组中的所有元素都相等的最小操作数--中位数作为目标

(2)由于是循环数组，所以需要考虑 i + xn + yk == i 下标位置的元素

其实，由于 bezout定理，n和k的所有线性组合的结果都有公因子gcd(n,k)

而且，有gcd(n,k)的元素都可以 用n和k线性组合出来

总的来说，+ 或 - n：相当于 向前或者向后跳跃所有元素

        // + 或 - k： 相当于 向前 或者 向后跳跃k个元素

（3）所以直接把 数组arr按照 mod(gcd(n,k))进行分组，

        //然后 每一组 先sort，然后向中位数位置靠拢即可

2.代码：

class Solution {
public:long long makeSubKSumEqual(vector<int>& arr, int k) {//借鉴 灵茶山的 思路://(1)铺垫：让一个数组中的所有元素都相等的最小操作数--中位数作为目标//(2)由于是循环数组，所以需要考虑 i + xn + yk == i 下标位置的元素//其实，由于 bezout定理，n和k的所有线性组合的结果都有公因子gcd(n,k)//而且，有gcd(n,k)的元素都可以 用n和k线性组合出来//总的来说，+ 或 - n：相当于 向前或者向后跳跃所有元素// + 或 - k： 相当于 向前 或者 向后跳跃k个元素//（3）所以直接把 数组arr按照 mod(gcd(n,k))进行分组，//然后 每一组 先sort，然后向中位数位置靠拢即可int n= arr.size();int mod_num = gcd(n,k);//遍历arr,进行分组存到一个二维数组中vector<vector<int>> vec(mod_num);for(int i = 0 ;i < n ;i++){vec[i%mod_num].push_back(arr[i]);}//一边sort ， 一边 向中位数靠拢long long  ans = 0;for(int i=0;i<mod_num;i++){sort(vec[i].begin(),vec[i].end());int size = vec[i].size();long mid = vec[i][size/2];//直接和 vec[i][size/2]这个元素进行 差值运算for(long item: vec[i]){ans+= abs(item - mid);}}return ans;}
};

T4:图中的最短环

现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。

返回图中 最短 环的长度。如果不存在环，则返回 -1 。

环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。

解：

1.关键：

（1）通用的操作-通过edges边集数组 --建图--为了方便得到一个节点x的所有 相邻节点 y，一般使用一个二维数组graph ， graph[x] 中的所有元素都是 x的 相邻节点的下标值

(2)以其中某一个下标start作为起点，然后，返回这种情况下的 最短的 环的 长度，返回一个int类型的值，写一个bfs函数

<1>数据结构 ，一个大小为n，初始值全为-1的 一维数组dis[n],ans初始为INT_MAX,queue<pair<int,int>> q一个队列，每个元素都是<此节点下标，该路径下到达此节点的 上一个节点>,

<2>初始条件:pair<start,-1> 入队，dis[start] =0;

<3>开始while（！q.empty()) 的while循环，每次从q从取出 队首元素，然后 ，除了上一个访问的节点，其它相邻的节点都要访问，不过如果是第一次访问--dis【】 == -1，那么就可以入队，并且更新dis，如果不是，那么环就产生了

2.代码:

class Solution {
public:int findShortestCycle(int n, vector<vector<int>>& edges) {//首先需要判断出这是一个环，然后还要记录环的长度//(1)建图：利用二维数组构建一个邻接表vector<vector<int>> graph(n);for(auto e:edges){int x = e[0]; int y = e[1];graph[x].push_back(y);graph[y].push_back(x);}//(2)分n个不同的起点调用 bfs，搜索 取所有环中的最短环的长度//(3)...打擂台int ans = INT_MAX; //先等于一个最大的整数for(int i = 0;i< n ;i++){ans = min( ans , bfs(n,i,graph));}return ans == INT_MAX ? -1 : ans;}//写一下这个 bfs函数int bfs(int n,int start,vector<vector<int>>& g){//从下标为start作为不同起点开始，每次找到其中的最小环既可以了，//返回一个int型的最小环的长度int dis[n]; //设置一个记录 从起点 到达各个下标点的 长度数组int ans = INT_MAX; //返回 最小环长度的 结果memset(dis,-1,sizeof(dis)); //将dis数组中到达所有的节点设置为-1--表示没有访问过dis[start] = 0; //到达起点的长度为0queue<pair<int,int>> q; //防止访问前一个节点，<此节点，该路径下到达此节点的上一个节点>q.emplace(start,-1); //让第一个节点入队，开始广搜bfs//--开始bfs 广度优先搜索while(!q.empty()){auto [x,fa] = q.front(); //出队，得到第一个出队节点q.pop(); //记得出队for(int y:g[x]) //除了上一个节点，其它相邻的节点都要去考虑{//x相邻的节点if(dis[y] < 0) {//第一次遇到dis[y] = dis[x]+1;q.emplace(y,x);//记录y的上一个节点}else if(y != fa){//第二次遇到:ans =min(ans,dis[x]+dis[y]+1);}}}return ans;}
};