复盘一下4.7华为实习笔试，并查集，拓扑排序，动态规划_华为暑期实习编程题动态规划

作者：羊村懒王 | 2024-05-05 23:15:56

踩

华为暑期实习编程题动态规划

复盘一下4.7华为实习笔试，并查集，拓扑排序，动态规划


public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> color = new HashMap<>();
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s1 = sc.next();
            String s2 = sc.next();
            color.put(s1, -1);
            color.put(s2, -1);
            if (!map.containsKey(s1)) {
                List<String> tmp = new ArrayList<>();
                tmp.add(s2);
                map.put(s1, tmp);
            } else {
                map.get(s1).add(s2);
            }
            if (map.containsKey(s2)) {
                map.get(s2).add(s1);
            } else {
                List<String> tmp = new ArrayList<>();
                tmp.add(s1);
                map.put(s2, tmp);
            }
        }
        int c = 0;
        for (String s : map.keySet()) {
            if (color.get(s) == -1) {
                dfs(s, map, color, c);
                c++;
            }
        }
        System.out.println(c);
    }

    public static void dfs(String start, Map<String, List<String>> map,  Map<String, Integer> color, int c) {
        if (color.get(start) == -1) {
            color.put(start, c);
            if (map.get(start) != null){
                for (String s : map.get(start)) {
                    dfs(s, map, color, c);
                }
            }

        }
    }

#include <bits/stdc++.h> 
using namespace std; int n, m, t;
int res = 7e6; bool vis[15][15]; int cost[15][15]; 
void dfs(int i, int j, int sum) { if (sum > t) return; if (i == n - 1 && j == m - 1) { int now = sum + cost[i][j]; if (now <= t) { if (abs(res - t) > abs(now - t)) { res = now; } } return; } int x, y; x = i; y = j + 1; if (x < n && y < m) { dfs(x, y, sum + cost[i][j]); } x = i + 1; y = j; if (x < n && y < m) { dfs(x, y, sum + cost[i][j]); } } int main() { memset(vis, 0, sizeof(vis)); cin >> n >> m >> t; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> cost[i][j]; } } dfs(0, 0, 0); if (res == 7e6) cout << -1; else { cout << res; } return 0; }

https://blog.csdn.net/qq_25414107/article/details/104572462

并查集：https://www.bilibili.com/video/BV13t411v7Fs?from=search&seid=3614961025874570832

1 ，并查集的构造

① 设定一个集合，叫并查集，即 Disjoint Set，功能是检查 图中 是否出现了 环

② 往集合里面添加边，怎么添加呢。取边的起点和终点，判断两点是否都在集合里面,

如果都在，则出现了环，如果不在，将两个点 放入集合中。

③ 继续添加下一条边，如果没有边了，还没有找到环，就是没有环了



 

二，数组以树的形式实现

上面所讲的就是基本的思想了，下面讲如何具体实现

① 由于集合操作并不方便，所以便设法使用数组实现

② 由于上面所说的添加边 可以看成是一组点的集合 连接 另外一组点的集合，所以我们只要随便让集合的某一点 连接 另外一个集合的任意一点 就行了，

这样就可以让所有点处于连通状态

③ 基于上述所讲，我们可以将点以树的形式连接，为什么是树呢？因为集合中没有环，所以最后画出来的图形就是树了。

④ 由于连接的随意性， 这种连接方式，并不能正确表示一张图，只是能表示所有点是连接在一起的，且这种图画出来是树的形式。

 

⑤ 所以，我们可以构造一个 parent 数组，什么意思呢 ？ 就是 parent[x]=y, 指 x 的父节点是 y ,

为什么要 定义一个父节点呢？ 定义父节点的意思是 你可以通过父节点找到这个集合的根 ，根就是 所有点 都由 这个点 出发得到的。

那么，为什么要找到这个根呢？ 即这样做的优点。

 

优点1，在添加边的时候，可以通过查找 边上两个点的根结点是否存在，是否相同，达到判断两个点是否在之前的集合中出现过的效果



 

如图：想要添加左边 2-3 这条边，首先要判断边的两个点是否都在右边出现过。

如 2 的 父节点为 0，3 的父节点为 -1，即没有，所以并没有都出现过，只有一点出现过，

所以还没有环出现，可以添加边了。

 

 

优点2，可以在 加边  时减少树的深度，之后查找 根节点时就可以减少步骤

 



 

先看右边 3-4 这条边，他想加入左边的集合，怎么加呢？

在实际的图中，3 是连接着 2 的，但如果让 3 的父节点为 2，就让树的深度直接加了两层，

但如果让 3 的父节点为 0 深度增加了一层，即parent[0]=3 ,[且这样并不会影响到第一个优点。(｡￫‿￩｡)

 

接下来就是看代码了

 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define VERTICES 6
int find_root(int x, int parent[])  // 找到根节点
{
    int x_root = x;
    while (parent[x_root] != -1)
    {
        x_root = parent[x_root];
    }
    return x_root;
}
int union_vertices(int x, int y, int parent[])  // 让两个集合合并
{
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root == y_root)
        return 0;
    else
    {
        parent[x_root] = y_root;
        return 1;
    }
}
int main(void)
{
    int parent[VERTICES] = { 0 };
    memset(parent, -1, sizeof(parent));   // 初始化
    int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} }; // 边集

    for (int i = 0; i < 6; i++)
    {
        int x = edges[i][0];
        int y = edges[i][1];
        if (union_vertices(x, y, parent) == 0)
        {
            printf("Cycle detected!\n");
            system("pause");
            exit(0);
        }
    }
    printf("No cycle found.\n");

    system("pause");
    return 0;
}
 

 

三，压缩路径

且看我上面优点 2 这一句 “但如果让 3 的父节点为 0 深度增加了一层” ，其实如果但如果让 0 的父节点为 3 深度就没有增加了

之前的代码中，我们这一步那个时那个的父节点我们并没有对此做一个判断，来判断哪一个成为 父节点 树的深度会更少。

这样子就有一个问题，如果一直是

0-1 1-2 2-3 3-4 这样子就会让树的深度一直增加，这样就会让 find_root 函数时间复杂度在最坏的情况下达到 o(n) ,即每个点都要查找。

 

所以，我们使用 rank 数组来记录 树的深度，如 rank[x]=y 表示 以 x 点为根结点的话，树的深度为 y

如图：现在有两颗树（并查集以树的形式）



 

 

 要在添加一条边 x-y,

其中，x 的根节点为 Rx,y 的根节点为 Ry, 他们的根节点并不相同，所以没有环，可以加边，

那么我们就可以通过比较 rank[Rx] 与 rank[Ry] 来决定谁是谁的父节点。

 

优化后的代码实现：

复制代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define VERTICES 6
int find_root(int x, int parent[])  // 找到根节点
{
    int x_root = x;
    while (parent[x_root] != -1)
    {
        x_root = parent[x_root];
    }
    return x_root;
}
int union_vertices(int x, int y, int parent[],int rank[])  // 让两个集合合并
{
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root == y_root)
        return 0;
    else
    {
        if (rank[x_root] > rank[y_root])  // 让 少的指向多 的
        {
            parent[y_root] = x_root;
        }
        else if (rank[x_root] < rank[y_root])
            parent[x_root] = y_root;
        else
        {
            parent[x_root] = y_root;   // 这个随便可以
            rank[y_root]++;
        }
        return 1;
    }
}
int main(void)
{
    int parent[VERTICES] = { 0 };
    int rank[VERTICES] = { 0 };
    memset(rank, 0, sizeof(rank));
    memset(parent, -1, sizeof(parent));
    int edges[6][2] = { {0,1},{1,2},{1,3},{2,4},{3,4},{2,5} };

    for (int i = 0; i < 6; i++)
    {
        int x = edges[i][0];
        int y = edges[i][1];
        if (union_vertices(x, y, parent,rank) == 0)
        {
            printf("Cycle detected!\n");
            system("pause");
            exit(0);
        }
    }
    printf("No cycle found.\n");

    system("pause");
    return 0;
}
 



 

从图可以看出以下几点

① 当你添加的边中，有一点已经在集合中出现过了，根节点不会变，树的深度也是不会变，

② 你添加的第一条边父节点的出现是

由  第三个else  ,决定的

　　else
        {
            parent[x_root] = y_root;   
            rank[y_root]++;
        }

 ③，树所构成的图，与原来的图点的连接顺序基本不一样，

他只是保证了连通点是与原来一样的

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line1 = sc.nextLine();
        String[] missions = line1.split(",");
        int n = missions.length;
        int[] missionTime = new int[n];
        Deque<Integer> dq = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            missionTime[i] = Integer.parseInt(missions[i]);
            dq.offer(i);
        }

        String line2 = sc.nextLine();
        String[] depends;
        if (line2.length() == 0) depends = new String[0];
        else depends = line2.split(",");
        int[] time = new int[n];

        Map<Integer, Integer> dependMap = new HashMap<>();
        for (String depend : depends) {
            String[] tmp = depend.split("->");
            int key = Integer.parseInt(tmp[0]);
            if (dependMap.containsKey(key)) {
                dependMap.put(key, Math.max(dependMap.get(key), Integer.parseInt(tmp[1])));
            } else dependMap.put(key, Integer.parseInt(tmp[1]));
        }
        Map<Integer, List<Integer>> reverse = new HashMap<>();
        for (Integer integer : dependMap.keySet()) {
            int revKey = dependMap.get(integer);
            if (reverse.containsKey(revKey)) {
                reverse.get(revKey).add(integer);
            } else {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(integer);
                reverse.put(revKey, tmp);
            }
        }

        int exeTime = 0;
        Set<Integer> trigger = new HashSet<>();
        for (Integer key : dependMap.keySet()) {
            trigger.add(dependMap.get(key));
        }
        while (!dq.isEmpty()) {
            int poll = dq.poll();
            if (dependMap.containsKey(poll)) {
                dq.offer(poll);
            } else {
                if (trigger.contains(poll)) {
                    List<Integer> list = reverse.get(poll);
                    for (Integer integer : list) {
                        dependMap.remove(integer);
                    }
                }
                time[poll] = missionTime[poll] + exeTime;
                exeTime += missionTime[poll];
            }
        }
        for (int i = 0; i < time.length; i++) {
            if (i == time.length - 1) {
                System.out.print(time[i] + "\n");
            }
            else System.out.print(time[i] + ",");
        }

题目来源：https://www.nowcoder.com/discuss/634336

https://www.nowcoder.com/discuss/634345

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/541299