【华为面试题】贪心算法（一）

深藏阁楼爱情的钟 2024-03-23 22:15 137阅读 0赞

### 题目描述： ###

给定M个端口组，其中1 <= M <= 10。每个端口组是一个包含N个整数的数组，其中1 <= N <= 100。如果两个端口组中有至少2个相同的端口，则可以将它们合并。请实现合并逻辑，并返回合并后的端口组。

输入：  
第一行：端口组的数量M。  
接下来的M行：每行表示一个端口组，由逗号分隔的整数构成。  
输出：

合并后的端口组列表，以二维数组形式表示。  
注意：

在合并的端口组中，相同的端口只保留一个，并且按升序排序。  
合并的端口组之间的顺序应与输入中的原始顺序相同。

示例：

输入：

4  
4  
2,3,2  
1,2  
5

输出：

\[\[4\],\[2,3\],\[1,2\],\[5\]\]

### 代码 ###

function mergePorts(m, groups) {
        
    
        merge(groups);
    
        // 去重并排序每个组
        for (let i = 0; i < groups.length; i++) {
        
            groups[i] = [...new Set(groups[i])].sort((a, b) => a - b);
        }
    
        console.log(groups);
    
        // 尝试合并端口组
        function merge(groups) {
        
            for (let i = groups.length - 1; i >= 0; i--) {
        
                // 从当前元素的前一个元素开始到数组头部
                for (let j = i - 1; j >= 0; j--) {
        
                    let set1 = new Set(groups[i]);
                    let set2 = new Set(groups[j]);
                    // 检查两个端口组是否有共同的端口
                    if (check(set1, set2)) {
        
                        // 如果可以合并，则合并两个组
                        groups[j] = groups[j].concat(groups[i]);
                        // 移除已经合并的组
                        groups.splice(i, 1);
                        // 递归调用自身，继续检查是否还有可以合并的组
                        merge(groups);
                        return;
                    }
                }
            }
        }
    
        // 检查两个端口组是否有至少2个共同的端口
        function check(set1, set2) {
        
            let count = 0;
            for (let num of set1) {
        
                if (set2.has(num)) {
        
                    count++;
                }
                if (count >= 2) {
        
                    return true;
                }
            }
            return false;
        }
    }
    
    mergePorts(4, [
        [4],
        [2, 3, 2],
        [1, 2],
        [5]
    ]);

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 python算法面试题(一)

![在这里插入图片描述][642029a9a3fd460ea77e9e095acbe7fc.jpeg_pic_center] -------------------- 1

Bertha 。/ 2024年04月05日 07:34/ 0 赞/ 99 阅读

相关【华为面试题】贪心算法（二）

题目一个商人有一个有限的仓库空间，他需要在指定的天数内通过买卖商品来最大化其利润。每种商品都有其特定的价格和仓库存储上限。你的任务是计算商人在给定的天数内可以获得的最大

谁借莪１个温暖的怀抱￠/ 2024年03月23日 22:17/ 0 赞/ 68 阅读

相关【华为面试题】贪心算法（一）

题目描述：给定M个端口组，其中1 <= M <= 10。每个端口组是一个包含N个整数的数组，其中1 <= N <= 100。如果两个端口组中有至少2个相同的端口，则可以

深藏阁楼爱情的钟/ 2024年03月23日 22:15/ 0 赞/ 138 阅读

相关 2023华为OD机试真题【端口合并/贪心算法】

题目描述 > 有 M(1<=M<=10) 个端口组 > 每个端口组是长度为N(1<=N<=100)的整数数组，如果端口组间存在2个及以上不同端口相同，则认为这2个端口

我会带着你远行/ 2024年03月23日 14:02/ 0 赞/ 99 阅读

相关【华为面试题】深度优先搜索（一）

题目 Jungle居住在蓝鲸城，一个拥有规则街道的城市。然而，街道每天的封闭情况都是不同的。为了测试Jungle的导航技巧，我们设置了以下挑战： Jungle必须从他的

- 日理万妓/ 2023年10月14日 18:42/ 0 赞/ 108 阅读

相关贪心算法（一）

文章目录贪心算法简介 LeetCode 45跳跃游戏 LeetCode 55跳跃游戏 || 记录一些自己学到的知识，同时希望能帮

谁借莪１个温暖的怀抱￠/ 2023年09月30日 11:45/ 0 赞/ 42 阅读

相关 2023华为OD机试真题【连接器/贪心算法】

题目描述 > 有一组区间\[a0，b0\]，\[a1，b1\]，…（a，b表示起点，终点），区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间； > 给定一组连接

川长思鸟来/ 2023年09月27日 17:35/ 0 赞/ 120 阅读

相关贪心算法刷题

1.递增数组题目链接：[递增数组][Link 1] 题目介绍： > 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这

快来打我*/ 2023年07月16日 09:59/ 0 赞/ 60 阅读

相关贪心算法 leetcode编程题

1. [452. 用最少数量的箭引爆气球][452.] 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐

ゝ一世哀愁。/ 2022年12月23日 09:55/ 0 赞/ 257 阅读

相关面试算法大全-贪心算法总结

11、贪心 11.1 贪心算法总结贪心算法是指在每个阶段做选择的时候都做出当前阶段（或状态）最好的选择，并且期望这样做到的结果是全局最优解（但未必是全局最优

喜欢ヅ旅行/ 2022年10月17日 13:51/ 0 赞/ 219 阅读