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;}
};

總結：難度還好吧，看榜單上AK的人挺多的....

1. 簡單模擬

2. 找規律

3.?Dijkstra+優先隊列優化

4. 找最近公共祖先

感謝大家的點贊和關注，你們的支持是我創作的動力！(其他細節，有時間再補充...)