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 4Q3. 网格传送门旅游
给你一个大小为 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. 找最近公共祖先
感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)