leetcode_day59

今日内容：

• 寻宝
• 将石头分散到网格的最少移动次数 medium

寻宝

题目

在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。

不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。

给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

输入描述

第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。

接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

输出描述

输出联通所有岛屿的最小路径总距离。

思路

Prim和Kruskal都是求最小生成树的算法。

Prim算法

Prim是每次往树中加节点，第一个节点随便选，然后：

1. 获取其他点距离树的最短距离
2. 选取距离树最近的点加入树中
3. 更新其他点距离树的最近距离

使用used数组判断点是否加入，只需选取 \(n-1\) 次点即可构成最小生成树。

Kruskal算法

Kruskal是每次往树中加边，只要不是树内的边，都可以往里加，从小到大：

1. 获取图内最短边
2. 若该边不在树内，则加入树内，否则跳过

具体代码实现要注意，不能像Prim那样直接使用used数组判断是否将所有点加入树，Kruskal中途是不连通的，需要使用并查集来判断是否连通，否则会缺边。

代码

Prim

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int V, E;
    cin >> V >> E;
    vector<vector<pair<int, int>>> grid(V + 1, vector<pair<int, int>>());
    for(int i = 0;i < E;i++) {
        int x, y, wt;
        cin >> x >> y >> wt;
        grid[x].emplace_back(pair<int, int>(y, wt));
        grid[y].emplace_back(pair<int, int>(x, wt));
    }
    vector<int> minDist(V + 1, INT_MAX / 2);
    vector<bool> visited(V + 1, false);
    visited[0] = true;
    minDist[1] = 0;
    for(int i = 1;i < V;i++){
        //更新minDist
        int minVal = INT_MAX;
        int cur = 0;
        for(int j = 1;j <= V;j++) {
            if(!visited[j] && minDist[j] < minVal) {
                cur = j;
                minVal = minDist[j];
            }
        }
         
        visited[cur] = true;
         
        for(int j = 1;j <= V;j++) {
            if(!visited[j]) {
                for(auto & [y, wt] : grid[cur]) {
                    if(y == j && minDist[j] > wt) minDist[j] = wt;
                }
            }
        }
    }
    int result = 0;
    for (int i = 2; i <= V; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
        result += minDist[i];
    }
    cout << result << endl;
    return 0;
}

Kruskal

#include <bits/stdc++.h>
  
using namespace std;
 
class UnionFind{
public:
    vector<int> f;
    UnionFind(int n) {
        f.resize(n);
        for(int i = 0;i < n;i++) f[i] = i;
    }
    int find(int u) {
        if(u != f[u]) {
            f[u] = find(f[u]);
        }
        return f[u];
    }
    void join(int u, int v) {
        f[find(u)] = find(v);
    }
    bool isSame(int u, int v) {
        return find(u) == find(v);
    }
};
 
int main() {
    int V, E;
    cin >> V >> E;
    vector<vector<int>> grid(E, vector<int>(3, 0));
    for(int i = 0;i < E;i++) {
        for(int j = 0; j < 3;j++)
        cin >> grid[i][j];
    }
    auto cmp = [&](vector<int> & a, vector<int> & b) -> bool {
        return a[2] < b[2];
    };
    sort(grid.begin(), grid.end(), cmp);
    UnionFind uf(V + 1);
    int result = 0;
    for(int i = 1;i <= V;i++) {
        //find the shortest and not in the tree
        for(vector<int> & e : grid) {
            if(uf.isSame(e[0], e[1])) continue;
            result += e[2];
            uf.join(e[0], e[1]);
        }
    }
    cout << result;
    return 0;
}

将石头分散到网格的最少移动次数

题比较少，所以记录一下每日一题，半小时纯自主AC🎉

题目

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

示例 1：

img

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

思路

1不用动，只需知道0的位置和大于1的位置。之后不能简单地为每个0寻找最近的大于1，或者为每个最近的大于1寻找0。可轻易地举出反例，比如：

img

若先遍历到了居中的0，那么[0, 1]位的2会被分给居中0，左下2就会分给右上0。局部最优不能得到整体最优。可抽象为：

第一个大于1到所有0的距离为：[1, 1]

第二个大于1到所有0的距离为：[2, 4]

要从[[1,1], [2,4]]中每个数组取一个数字，且每个数组取的地方不能相同，最后总和最小。

这就变成了全排列问题，可制定流程为：

1. 获得全部0和大于1的位置，注意大于1的位置需要多次加入保证总数
2. 计算上述矩阵，即每个多余的1到0的距离
3. 枚举所有排列，取最小总和

流程没错，代码有点慢。只能击败不到10%...，也许是暴力回溯比不上next_permutation的缘故，读者可以帮忙测试一下👍

官方题解

代码

#define dis(x, y, i, j) (abs(x - i) + abs(y - j))
//曼哈顿距离
class Solution {
public:
    int res = INT_MAX;
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>> zero;
        vector<pair<int, int>> more;
        for(int i = 0;i < 3;i++) {
            for(int j = 0;j < 3;j++) {
                if(grid[i][j] > 1) {
                    for(int k = 2;k <= grid[i][j];k++) more.emplace_back(pair<int, int>(i, j));
                }
                else if(grid[i][j] < 1) zero.emplace_back(pair<int, int>(i, j));
            }
        }
        vector<vector<int>> dist(more.size(), vector<int>(zero.size(), 0));
        for(int i = 0;i < more.size();i++) {
            for(int j = 0;j < zero.size();j++) {
                dist[i][j] = dis(more[i].first, more[i].second, zero[j].first, zero[j].second);
            }
        }
        
        vector<bool> used(dist.size(), false);
        backtrack(used, dist, 0, 0);
        return res;
    }
    void backtrack(vector<bool> & used, vector<vector<int>> & dist, int sum, int step) {
        if(step == dist.size()) res = min(res, sum);
        for(int i = 0;i < dist.size();i++) {
            if(used[i]) continue;
            sum += dist[step][i];
            used[i] = true;
            backtrack(used, dist, sum, step + 1);
            sum -= dist[step][i];
            used[i] = false;
        }
    }
};