力扣第450场周赛

Q1. 数位和等于下标的最小下标

给你一个整数数组 nums 。

返回满足 nums[i] 的数位和（每一位数字相加求和）等于 i 的最小下标 i 。

如果不存在满足要求的下标，返回 -1 。

示例 1：

输入：nums = [1,3,2]

输出：2

解释：

nums[2] = 2，其数位和等于 2 ，与其下标 i = 2 相等。因此，输出为 2 。
示例 2：

输入：nums = [1,10,11]

输出：1

解释：

nums[1] = 10，其数位和等于 1 + 0 = 1，与其下标 i = 1 相等。
nums[2] = 11，其数位和等于是 1 + 1 = 2，与其下标 i = 2 相等。
由于下标 1 是满足要求的最小下标，输出为 1 。
示例 3：

输入：nums = [1,2,3]

输出：-1

解释：

由于不存在满足要求的下标，输出为 -1 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

class Solution {
public:bool solve(int a,int b){int cnt=0;while(b>0){cnt+=b%10;b/=10;}return a==cnt;}int smallestIndex(vector<int>& nums) {for(int i=0;i<nums.size();i++){if(solve(i,nums[i])) return i;}return -1;}
};

Q2. 数位和排序需要的最小交换次数

给你一个由互不相同的正整数组成的数组 nums，需要根据每个数字的数位和（即每一位数字相加求和）按升序对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。

返回将 nums 排列为上述排序顺序所需的最小交换次数。

一次交换定义为交换数组中两个不同位置的值。

示例 1：

输入: nums = [37,100]

输出: 1

解释:

计算每个整数的数位和：[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]
根据数位和排序：[100, 37]。将 37 与 100 交换，得到排序后的数组。
因此，将 nums 排列为排序顺序所需的最小交换次数为 1。
示例 2：

输入: nums = [22,14,33,7]

输出: 0

解释:

计算每个整数的数位和：[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]
根据数位和排序：[22, 14, 33, 7]。数组已经是排序好的。
因此，将 nums 排列为排序顺序所需的最小交换次数为 0。
示例 3：

输入: nums = [18,43,34,16]

输出: 2

解释:

计算每个整数的数位和：[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]
根据数位和排序：[16, 34, 43, 18]。将 18 与 16 交换，再将 43 与 34 交换，得到排序后的数组。
因此，将 nums 排列为排序顺序所需的最小交换次数为 2。

提示:

1 <= nums.length <= 105
1 <= nums[i] <= 109
nums 由互不相同的正整数组成。

using pii=pair<int,int>;
class Solution {
public:int solve(int num){int ret=0;while(num>0){ret+=num%10;num/=10;}return ret;}int minSwaps(vector<int>& nums) {vector<pii> a;for(auto& x:nums){a.emplace_back(x,solve(x));}sort(a.begin(),a.end(),[&](auto x, auto y){if(x.second!=y.second) return x.second<y.second;else return x.first<y.first;});int n=nums.size();unordered_map<int,int> idx(n);for(int i=0;i<a.size();i++) idx[a[i].first]=i;vector<int> v(n);for(int i=0;i<n;i++){v[i]=idx[nums[i]];}vector<bool> vis(n);int c=0;for(int i=0;i<nums.size();i++){if(!vis[i]){c++;int j=i;while(!vis[j]){vis[j]=true;j=v[j];}}}return n-c;}
};// 1 2 3 4
// 4 3 2 1
// 1 3 2 4
// 1 2 3 4

Q3. 网格传送门旅游

给你一个大小为 m x n 的二维字符网格 matrix，用字符串数组表示，其中 matrix[i][j] 表示第 i 行和第 j 列处的单元格。每个单元格可以是以下几种字符之一：

'.' 表示一个空单元格。
'#' 表示一个障碍物。
一个大写字母（'A' 到 'Z'）表示一个传送门。
你从左上角单元格 (0, 0) 出发，目标是到达右下角单元格 (m - 1, n - 1)。你可以从当前位置移动到相邻的单元格（上、下、左、右），移动后的单元格必须在网格边界内且不是障碍物。

如果你踏入一个包含传送门字母的单元格，并且你之前没有使用过该传送门字母，你可以立即传送到网格中另一个具有相同字母的单元格。这次传送不计入移动次数，但每个字母对应的传送门在旅程中最多只能使用一次。

返回到达右下角单元格所需的最少移动次数。如果无法到达目的地，则返回 -1。

using pii=pair<int,int>;
using ll=long long;
#define mx LLONG_MAX
struct Node{int x,y;ll d;bool operator<(const Node& o) const {return d>o.d;}
};
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
class Solution{
public:int minMoves(vector<string>& matrix) {int m=matrix.size(); int n=matrix[0].size();if(matrix[0][0]=='#'||matrix[m-1][n-1]=='#') return -1;vector<vector<pii>> o_p(26);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(matrix[i][j]>='A'&&matrix[i][j]<='Z'){o_p[matrix[i][j]-'A'].push_back({i,j});}}}vector<vector<ll>> d(m,vector<ll>(n,mx));d[0][0]=0;vector<bool> vis(26,false);priority_queue<Node> pq;pq.push({0,0,0});while(!pq.empty()){Node cur=pq.top();pq.pop();int x=cur.x,y=cur.y;ll c_d=cur.d;if(c_d>d[x][y]) continue;if(x==m-1&&y==n-1) return c_d;char c=matrix[x][y];if(c>='A'&&c<='Z'){int idx=c-'A';if(!vis[idx]){for(auto& p: o_p[idx]){int nx=p.first,ny=p.second;if(d[nx][ny]>c_d){d[nx][ny]=c_d;pq.push({nx,ny,c_d});}}vis[idx]=true;}}for(int k=0;k<4;k++){int nx=x+dx[k],ny=y+dy[k];if(nx<0||nx>=m||ny<0||ny>=n) continue;if(matrix[nx][ny]=='#') continue;if(d[nx][ny]>c_d+1){d[nx][ny]=c_d+1;pq.push({nx,ny,c_d+1});}}}return -1;}
};

Q4. 包含给定路径的最小带权子树 II

给你一个无向带权树，共有 n 个节点，编号从 0 到 n - 1。这棵树由一个二维整数数组 edges 表示，长度为 n - 1，其中 edges[i] = [ui, vi, wi] 表示存在一条连接节点 ui 和 vi 的边，权重为 wi。

此外，给你一个二维整数数组 queries，其中 queries[j] = [src1j, src2j, destj]。

返回一个长度等于 queries.length 的数组 answer，其中 answer[j] 表示一个子树的最小总权重，使用该子树的边可以从 src1j 和 src2j 到达 destj 。

这里的子树是指原树中任意节点和边组成的连通子集形成的一棵有效树。

using pii = pair<int, int>;
class LCA_solve {
public:vector<int> depth, to_root_minD;vector<vector<int>> pa;LCA_solve(vector<vector<int>>& edges) {int n = edges.size() + 1;int m = bit_width(edges.size() + 1); vector<vector<pii>> g(n);for (auto& e : edges) {int x = e[0], y = e[1], z = e[2];g[x].emplace_back(y, z);g[y].emplace_back(x, z);}depth.resize(n);to_root_minD.resize(n);pa.resize(n, vector<int>(m, -1));auto dfs = [&](this auto&& dfs, int x, int fa) -> void {pa[x][0] = fa;for (auto& [y, w] : g[x]) {if (y != fa) {depth[y] = depth[x] + 1;to_root_minD[y] = to_root_minD[x] + w;dfs(y, x);}}};dfs(0, -1);for (int i = 0; i < m - 1; i++) {for (int x = 0; x < n; x++) {if (int p = pa[x][i]; p != -1) {pa[x][i + 1] = pa[p][i];}}}}int get_kth_ancestor(int node, int k) {for (; k; k &= k - 1) {node = pa[node][countr_zero((unsigned)k)];}return node;}int get_lca(int x, int y) {if (depth[x] > depth[y]) {swap(x, y);}y = get_kth_ancestor(y, depth[y] - depth[x]);if (y == x) {return x;}for (int i = pa[x].size() - 1; i >= 0; i--) {int px = pa[x][i], py = pa[y][i];if (px != py) {x = px;y = py;}}return pa[x][0];}int twoPoits_dis(int x, int y) {return to_root_minD[x] + to_root_minD[y] - to_root_minD[get_lca(x, y)] * 2;}
};
class Solution {
public:vector<int> minimumWeight(vector<vector<int>>& edges, vector<vector<int>>& queries) {LCA_solve g(edges);int n = queries.size();vector<int> ans(n);for (int i = 0; i < n; i++) {vector<int> q = queries[i];int x = q[0], y = q[1], z = q[2];ans[i] = (g.twoPoits_dis(x, y) + g.twoPoits_dis(y, z) + g.twoPoits_dis(x, z)) / 2;}return ans;}
};