力扣第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 由 互不相同 的正整数组成。

class Solution {
public:int minSwaps(vector<int>& nums) {int n = nums.size();vector<pair<pair<int,int>, int>> a;for (int i = 0; i < n; i++) {int x = nums[i], p = 0;while (x) { p += x % 10; x /= 10; }a.push_back({{p, nums[i]}, i});}sort(a.begin(), a.end(), [](auto& x, auto& y) {if (x.first.first != y.first.first) return x.first.first < y.first.first;return x.first.second < y.first.second;});vector<bool> vis(n);int cnt = 0;for (int i = 0; i < n; i++) {if (vis[i] || a[i].second == i) continue;int k = 0, j = i;while (!vis[j]) {vis[j] = true;j = a[j].second;k++;}if (k > 0) cnt += k - 1;}return cnt;}
};
// 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;}
};

总结：难度还好吧，看榜单上AK的人挺多的....

1. 简单模拟

2. 找规律

3. Dijkstra+优先队列优化

4. 找最近公共祖先

感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)