华为校招机试 - 相似图片分类（20240410）

叁歲伎倆 2024-04-21 08:26 60阅读 0赞

#### 在线OJ测试 ####

[题目详情 - 相似图片分类 - HydroOJ][- _ - HydroOJ]

#### 题目描述 ####

小明想要处理一批图片，将相似的图片分类。

他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类：

1.  相似度 > 0 表示两张图片相似
2.  如果 A 和 B 相似，B 和 C 相似，但 A 和 C 不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度
3.  如果 A 和所有其他图片都不相似，则 A 自己归为一类，相似度为0。

给定一个大小为 N × N 的矩阵 M，存储任意两张图片的相似度：

> M\[i\]\[j\] 即为第 i 个图片和第 j 个图片的相似度

请按照 “从大到小” 的顺序返回每个相似类中所有图片的相似度之和。

#### 输入描述 ####

第一行一个数 N，代表矩阵 M 中有 N 个图片，

下面跟着 N 行，每行有 N 列数据，空格分隔（为了显示整弃，空格可能为多个）代表 N 个图片之间的相似度。

约束：

*  0 < N ≤ 900
 *  0 ≤ M\[i\]\[j\] ≤ 100
 *  输入保证 M\[i\]\[i\] =0，M\[i\]\[j\]=M\[j\]\[i\]

#### 输出描述 ####

每个相似类的相似度之和。

格式为：一行数字，分隔符为1个空格。

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">5<br> 0 0 50 0 0<br> 0 0 0 25 0<br> 50 0 0 0 15<br> 0 25 0 0 0<br> 0 0 15 0 0</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">65 25</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>把1~5看成A,B,C,D,E，矩阵显示，</p> 
    <ul> 
     <li>A和C相似度为50，</li> 
     <li>C和E的相似度为15，</li> 
     <li>B和D相似度为25。</li> 
    </ul><p>划分出2个相似类，分别为</p> 
    <ul> 
     <li>{A,C,E}，相似度之和为65</li> 
     <li>{B,D}，相似度之和25</li> 
    </ul><p>排序输出相似度之和，结果为：65&nbsp;25</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

题目用例图示：

![3531360b8eb64d64806a761ce4b5fe37.png][]

本题的图片相似归类可以使用并查集实现，关于并查集知识可以看下：

[《算法训练营》进阶篇 01 并查集\_哔哩哔哩\_bilibili《算法训练营集训》进阶篇全套视频100集在这里： https://www.bilibili.com/cheese/play/ss6658 加QQ群281607840下载所有源码。《算法训练营》是一套没有编程经验的小白也能看懂的算法书，海量图解，实例丰富，图文并茂，全面系统搭建数据结构与算法知识体系，模块化逐一拆解算法问题。300道竞赛试题展示算法设计与实现的详细过程，培养算法思维，感受算法之美。, 视频播放量 17090、弹幕量 20、点赞数 428、投硬币枚数 265、收藏人数 588、转发人数 68, 视频作者 算法训练营, 作者简介 小玉老师，高级程序员，大数据分析师，课程咨询qq155170962，著作《算法训练营》(入门篇、进阶篇)《趣学算法》《趣学数据结构》，相关视频：全网最清晰的并查集讲解，算法讲解056【必备】并查集-上，图论——并查集(详细版)，《算法训练营》进阶篇 04 最近公共祖先，\[PTA\] 朋友圈 并查集，【算法】并查集（Disjoint Set）\[共3讲\]，算法动画秒懂并查集，《算法训练营》进阶篇 02 优先队列，并查集，并查集 画图详解+代码书写![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://www.bilibili.com/video/BV1VM4y1K7FV/?spm\_id\_from=333.337.search-card.all.click][01 _bilibili_100_ https_www.bilibili.com_cheese_play_ss6658 _QQ_281607840_300_ _ 17090_ 20_ 428_ 265_ 588_ 68_ _ _ _ _qq155170962_056_-_ 04 _PTA_ _ _Disjoint Set_3_ 02 _ _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.bilibili.com_video_BV1VM4y1K7FV_spm_id_from_333.337.search-card.all.click]

以及练手题目：

[LeetCode - 547 省份数量\_return (this.fa\[x\]=this.find(this.fa\[x\]));-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://fcqian.blog.csdn.net/article/details/127605092][LeetCode - 547 _return _this.fa_x_this.find_this.fa_x_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_fcqian.blog.csdn.net_article_details_127605092][LeetCode - 200 岛屿数量\_leetcode200岛屿数量-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://fcqian.blog.csdn.net/article/details/127606569][LeetCode - 200 _leetcode200_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_fcqian.blog.csdn.net_article_details_127606569]

本题难点并不在实现并查集，以及完成节点关联。

而是在节点关联完成后，如何统计每个连通图中所有图片的相似度之和？

如果是暴力求解的话，我们需要将连通图中图片两两判断，累加相似度之和。这种做法并不好。

更优的策略是，在我们遍历M矩阵时，如果M\[i\]\[j\] > 0，则说明 i, j 图片相似，相似度为M\[i\]\[j\]。

此时，我们需要做两个操作：

*  完成 i，j 节点的关联，即并查集的union操作
 *  将此时的相似度 M\[i\]\[j\] 记录到 i, j 关联后的新连通图的根上

另外，需要注意的是，在完成 i，j 关联之前

*  fa\[i\] 节点记录 i 所在连通图中所有图片的相似度之和
 *  fa\[j\] 节点记录 j 所在连通图中所有图片的相似度之和

当完成关联后，i，j处于一个连通图中，假设fa\[j\] = fa\[i\]，即将 j 所在子树并入了 i 所在子树，此时新连通图的根为fa\[i\]。

此时我们需要注意，由于我们期望将连通图中所有图片的相似度之和累计到根上，因此此时

*  fa\[i\] += fa\[j\]
 *  fa\[j\] = 0

#### JS算法源码 ####

#### Java算法源码 ####

import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            int n = sc.nextInt();
    
            UnionFindSet ufs = new UnionFindSet(n);
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int similar = sc.nextInt();
    
                    // 避免重复ufs.union操作
                    if (j <= i) continue;
    
                    if (similar > 0) {
                        // 合并两个子连通图为一个，将所有相似度之和（包括本次similar）全部转移到新连通图的根节点上
                        ufs.union(i, j, similar);
                    }
                }
            }
    
            ArrayList<Integer> ans = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                // 找根节点
                if (ufs.find(i) == i) {
                    // 相似类是一个连通子图，连通子图中所有图片的相似度之和记录在根上
                    ans.add(ufs.sum[i]);
                }
            }
    
            // 按照 “从大到小” 的顺序返回每个相似类中所有图片的相似度之和
            ans.sort((a, b) -> b - a);
            ans.forEach(a -> System.out.print(a + " "));
        }
    }
    
    // 并查集实现
    class UnionFindSet {
        int[] fa;
        // sum[i]表示以i为根的相似类中所有图片的相似度之和
        int[] sum;
    
        public UnionFindSet(int n) {
            this.fa = new int[n];
            for (int i = 0; i < n; i++) fa[i] = i;
    
            this.sum = new int[n];
        }
    
        public int find(int x) {
            if (x != this.fa[x]) {
                this.fa[x] = this.find(this.fa[x]);
                return this.fa[x];
            }
            return x;
        }
    
        public void union(int x, int y, int val) {
            int x_fa = this.find(x);
            int y_fa = this.find(y);
    
            // 本次新增的相似度，归到x_fa根或者y_fa根都可以
            this.sum[x_fa] += val;
    
            if (x_fa != y_fa) {
                // 让Y_fa指向x_fa, 即x_fa成为新根
                this.fa[y_fa] = x_fa;
    
                // 此时y_fa上的相似度之和累计到新根x_fa上
                this.sum[x_fa] += this.sum[y_fa];
                // 累计完后，y_fa不在记录相似度
                this.sum[y_fa] = 0;
            }
        }
    }

#### Python算法源码 ####

import re
    
    
    # 并查集实现
    class UnionFindSet:
        def __init__(self, n):
            self.fa = [i for i in range(n)]
            # sum[i]表示以i为根的相似类中所有图片的相似度之和
            self.sum = [0 for i in range(n)]
    
        def find(self, x):
            if x != self.fa[x]:
                self.fa[x] = self.find(self.fa[x])
                return self.fa[x]
            return x
    
        def union(self, x, y, val):
            x_fa = self.find(x)
            y_fa = self.find(y)
    
            # 本次新增的相似度，归到x_fa根或者y_fa根都可以
            self.sum[x_fa] += val
    
            if x_fa != y_fa:
                # 让Y_fa指向x_fa, 即x_fa成为新根
                self.fa[y_fa] = x_fa
    
                # 此时y_fa上的相似度之和累计到新根x_fa上
                self.sum[x_fa] += self.sum[y_fa]
                # 累计完后，y_fa不在记录相似度
                self.sum[y_fa] = 0
    
    
    # 算法入口
    def solution():
        n = int(input())
    
        matrix = []
        for _ in range(n):
            # 每行有 N 列数据，空格分隔（为了显示整弃，空格可能为多个）
            matrix.append(list(map(int, re.split(r"\s+", input()))))
    
        ufs = UnionFindSet(n)
    
        for i in range(n):
            for j in range(i + 1, n):
                similar = matrix[i][j]
    
                if similar > 0:
                    # 合并两个子连通图为一个，将所有相似度之和（包括本次similar）全部转移到新连通图的根节点上
                    ufs.union(i, j, similar)
    
        ans = []
    
        for i in range(n):
            # 找根节点
            if ufs.find(i) == i:
                # 相似类是一个连通子图，连通子图中所有图片的相似度之和记录在根上
                ans.append(ufs.sum[i])
    
        # 按照 “从大到小” 的顺序返回每个相似类中所有图片的相似度之和
        ans.sort(reverse=True)
    
        return " ".join(map(str, ans))
    
    
    # 算法调用
    print(solution())

#### C算法源码 ####

#include <stdio.h>
    #include <stdlib.h>
    
    /** 并查集定义 **/
    typedef struct {
        int *fa;
        // sum[i]表示以i为根的相似类中所有图片的相似度之和
        int *sum;
    } UFS;
    
    UFS *new_UFS(int n) {
        UFS *ufs = (UFS *) malloc(sizeof(UFS));
    
        ufs->fa = (int *) malloc(sizeof(int) * n);
        ufs->sum = (int *) malloc(sizeof(int) * n);
        for (int i = 0; i < n; i++) {
            ufs->fa[i] = i;
            ufs->sum[i] = 0;
        }
    
        return ufs;
    }
    
    int find_UFS(UFS *ufs, int x) {
        if (x != ufs->fa[x]) {
            ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
            return ufs->fa[x];
        }
        return x;
    }
    
    void union_UFS(UFS *ufs, int x, int y, int val) {
        int x_fa = find_UFS(ufs, x);
        int y_fa = find_UFS(ufs, y);
    
        // 本次新增的相似度，归到x_fa根或者y_fa根都可以
        ufs->sum[x_fa] += val;
    
        if (x_fa != y_fa) {
            // 让Y_fa指向x_fa, 即x_fa成为新根
            ufs->fa[y_fa] = x_fa;
    
            // 此时y_fa上的相似度之和累计到新根x_fa上
            ufs->sum[x_fa] += ufs->sum[y_fa];
            // 累计完后，y_fa不在记录相似度
            ufs->sum[y_fa] = 0;
        }
    }
    
    int cmp(const void *a, const void *b) {
        return *((int *) b) - *((int *) a);
    }
    
    int main() {
        int n;
        scanf("%d", &n);
    
        UFS *ufs = new_UFS(n);
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int similar;
                scanf("%d", &similar);
    
                if (j <= i) continue;
    
                if (similar > 0) {
                    // 合并两个子连通图为一个，将所有相似度之和（包括本次similar）全部转移到新连通图的根节点上
                    union_UFS(ufs, i, j, similar);
                }
            }
        }
    
        int res[n];
        int res_size = 0;
    
        for (int i = 0; i < n; i++) {
            // 找根节点
            if (find_UFS(ufs, i) == i) {
                // 相似类是一个连通子图，连通子图中所有图片的相似度之和记录在根上
                res[res_size++] = ufs->sum[i];
            }
        }
    
        // 按照 “从大到小” 的顺序返回每个相似类中所有图片的相似度之和
        qsort(res, res_size, sizeof(int), cmp);
    
        for (int i = 0; i < res_size; i++) {
            printf("%d ", res[i]);
        }
    
        return 0;
    }

#### C++算法源码 ####

#include <bits/stdc++.h>
    using namespace std;
    
    // 并查集实现
    class UnionFindSet {
    public:
        int *fa;
        // sum[i]表示以i为根的相似类中所有图片的相似度之和
        int *sum;
    
        explicit UnionFindSet(int n) {
            fa = new int[n];
            sum = new int[n];
    
            for (int i = 0; i < n; i++) {
                fa[i] = i;
                sum[i] = 0;
            }
        };
    
        int find(int x) {
            if (x != fa[x]) {
                fa[x] = find(fa[x]);
                return fa[x];
            }
            return x;
        };
    
        void merge(int x, int y, int val) {
            int x_fa = find(x);
            int y_fa = find(y);
    
            // 本次新增的相似度，归到x_fa根或者y_fa根都可以
            sum[x_fa] += val;
    
            if (x_fa != y_fa) {
                // 让Y_fa指向x_fa, 即x_fa成为新根
                fa[y_fa] = x_fa;
    
                // 此时y_fa上的相似度之和累计到新根x_fa上
                sum[x_fa] += sum[y_fa];
                // 累计完后，y_fa不在记录相似度
                sum[y_fa] = 0;
            }
        };
    };
    
    int main() {
        int n;
        cin >> n;
    
        UnionFindSet ufs(n);
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int similar;
                cin >> similar;
    
                if (j <= i) continue;
    
                if (similar > 0) {
                    // 合并两个子连通图为一个，将所有相似度之和（包括本次similar）全部转移到新连通图的根节点上
                    ufs.merge(i, j, similar);
                }
    
            }
        }
    
        vector<int> res;
    
        for (int i = 0; i < n; i++) {
            // 找根节点
            if (ufs.find(i) == i) {
                // 相似类是一个连通子图，连通子图中所有图片的相似度之和记录在根上
                res.emplace_back(ufs.sum[i]);
            }
        }
    
        // 按照 “从大到小” 的顺序返回每个相似类中所有图片的相似度之和
        sort(res.begin(), res.end(), [](int a, int b) {
            return a > b;
        });
    
        for (const auto &item: res) {
            cout << item << " ";
        }
    
        return 0;
    }

[- _ - HydroOJ]: https://hydro.ac/d/HWOCR/p/OCR030
[3531360b8eb64d64806a761ce4b5fe37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/9602572878f14074a9d349e0692cd14b.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[01 _bilibili_100_ https_www.bilibili.com_cheese_play_ss6658 _QQ_281607840_300_ _ 17090_ 20_ 428_ 265_ 588_ 68_ _ _ _ _qq155170962_056_-_ 04 _PTA_ _ _Disjoint Set_3_ 02 _ _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.bilibili.com_video_BV1VM4y1K7FV_spm_id_from_333.337.search-card.all.click]: https://www.bilibili.com/video/BV1VM4y1K7FV/?spm_id_from=333.337.search-card.all.click
[LeetCode - 547 _return _this.fa_x_this.find_this.fa_x_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_fcqian.blog.csdn.net_article_details_127605092]: https://fcqian.blog.csdn.net/article/details/127605092
[LeetCode - 200 _leetcode200_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_fcqian.blog.csdn.net_article_details_127606569]: https://fcqian.blog.csdn.net/article/details/127606569