【笔试记录】华为 | 20230823 | cpp

获取连通的相邻节点列表

题目描述

在网元内，存在了 N 个转发节点，每个转发节点有自己唯一的标识 TB 且每个节点有 M 个端口，节点间通过端口进行报文通讯。出于业务隔离的需求，服务器内的端口被划分为多个通讯平面(用 VLAN 隔离，每个 VLAN 都有一个 VLAN ID作为标识)

  1. 如果两个端口的VLAN ID相同，则说明这两个端口处于同个 VLAN，且处于连通状态;
  2. 如果两个端口的VLAN ID不同，则说明这两个端口处于不同 VLAN，彼此不连通;

现给出节点 A 的端口数及其各端口所属的 VLAN ID，以及节点 A 相邻的其他节点和端口信息。 要求获取与节点 A 处于连通状态的所有相邻节点的 TB 列表（按 TB 从小到大顺序输出）

输入描述
第 1 行: M VLAN_ID_1…VLAN_ID_m 数据间有空格隔开，分别表示: 节点 A 有 M 个端口，各个端口所属的 VLAN_ID，即后面 VLAN_ID_m 表示第 m 个端口的 VLAN ID。

其中，网元内节点的端口数量 M 的取值范围为[1,4]; 端口划分 VLAN ID 的取值范围为[1,4];

第 2 行: N 表示与节点 A 相邻的其他节点有 N 个，N 的取值范围为[0,4000)

第 3 行开始，将有 N 行数据，分别描述与节点 A 相邻的节点的 TB 和端口信息

输入格式为: TBx Mx VLAN_ID_xx…VLAN_ID_xm 数据间有空格隔开，

分别表示: 节点 x 的 TBx，有 Mx 个端口，各个端口所属的 VLAN_ID，即后面 VLAN_ID_xm 表示第 m 个端口的 VLAN ID。 其中，网元内节点 TB 的取值范围为(0,4294967295);

输出描述
第 1 行: N

表示与节点 A 连通的相邻节点个数，如 N 为 0，则无需在输出其他信息

第 2 行: TB_1…TB_n

数据间有空格隔开，分别表示：与节点 A 连通的相邻节点的 TB，个数为 N，按从小到大的顺序输出。

输入示例

1 1
3
1024 2 1 2
1023 1 1
1025 3 2 2 3

输出示例

2
1023 1024

提示信息
节点 A 有 1 个端口，VLAN ID 为 1。

相邻的 3 个节点中：

节点 1024 有 2 个端口，其中一个端口的 VLAN ID 为 1，与节点 A 连通。

节点 1023 有 1 个端口，VLAN ID 为 1，与节点 A 连通。

节点 1025 的端口 VLAN ID 分别为 2, 2, 3，没有与节点 A 相同的 VLAN ID，不连通。

最终输出连通的 2 个相邻节点 1023 和 1024，按 TB 从小到大排序。

cpp代码

真的是读题半小时，做题五分钟。。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAX 4000
int M;  // 节点A端口数量
int A_VLAN[4];  // 节点A的VLAN ID
int N;  // 节点A相邻节点数量
int N_VLAN[MAX][6];  // 相邻节点的信息
vector<int> result;
 
int main() {
    // 读取节点A的端口数量和VLAN ID
    cin >> M;
    for(int i = 0; i < M; i++) {
        cin >> A_VLAN[i];
    }
     
    // 读取相邻节点的数量
    cin >> N;
     
    // 读取每个相邻节点的TB、端口数量和VLAN ID
    for(int i = 0; i < N; i++) {
        cin >> N_VLAN[i][0] >> N_VLAN[i][1];  // TB和Mx
        bool isConnected = false;  // 标志是否连通
         
        for(int j = 0; j < N_VLAN[i][1]; j++) {
            cin >> N_VLAN[i][j + 2];  // 读取VLAN ID
             
            if(!isConnected){
                // 检查是否有相同的VLAN ID
                for(int k = 0; k < M; k++) {
                    if(N_VLAN[i][j + 2] == A_VLAN[k]) {
                        isConnected = true;
                        break;
                    }
                }
            }
        }
        // 如果连通，将TB添加到结果中
        if(isConnected) {
            result.push_back(N_VLAN[i][0]);
        }
    }
     
    // 对结果进行排序
    sort(result.begin(), result.end());
     
    // 输出结果
    cout << result.size() << endl;
    for(int i = 0; i < result.size(); i++) {
        cout << result[i];
        if(i != result.size() - 1) cout << " ";
    }
     
    return 0;
}

消息传输

题目描述

在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中，分布着一些信号塔，用于区域间通信。

每个单元格可以有以下三种状态：

  • 值 0 代表空地，无法传递信号；
  • 值 1 代表信号塔 A，在收到消息后，信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔；
  • 值 2 代表信号塔 B，在收到消息后，信号塔 B 可以在 2ms 后将信号发送给上下左右四个方向的信号塔。

给定一个坐标 (j, k)，输入保证坐标 (j, k) 位置一定有信号塔。在坐标 (j, k) 位置的信号塔触发一个信号。

要求返回网格地图中所有信号塔收到信号的最短时间，单位为 ms。如果有信号塔无法收到信号，则返回 -1。

输入描述
第一行：网格的列数 n。

第二行：网格的行数 m。

第三行：触发信号的信号塔坐标 (j, k)。

接下来的 m 行：每行包含 n 个整数，表示该行网格中每个位置的信号塔安装信息（通过空格间隔每个状态值）。

输出描述
输出返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。

输入示例

3
3
1 0
0 1 2
1 2 1
0 1 2

输出示例

4

初始答案

感觉这题和京东的皇后移动的最小步数，所以我首要考虑了BFS。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N 1004
#define pi pair<int, int>
int m, n;   // 网格行数，列数
int j, k;   // 触发信号的信号塔(j, k)
int grid[N][N];
int dx[4] = { -1, 1, 0, 0 }; // 上下左右
int dy[4] = { 0, 0, -1, 1 }; // 上下左右
 
int main() {
    cin >> n >> m;
    cin >> j >> k;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
        }
    }
 
    // 特殊情况：只有一行
    if (m <= 1){
        for(int i = 0; i < n; i++){
            if(i < k && i < n-1 && grid[0][i] != 0 && grid[0][i+1] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > k && i >= 1 && grid[0][i] != 0 && grid[0][i-1] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
         
    // 特殊情况：只有一列
    if (n <= 1){
        for(int i = 0; i < m; i++){
            if(i < j && i < m-1 && grid[i][0] != 0 && grid[i+1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
                 
            if(i > j && i >= 1 && grid[i][0] != 0 && grid[i-1][0] == 0){
                cout << -1 << endl; 
                return 0;
            }
        }
    }
 
 
    vector<vector<int>> ttime(m, vector<int>(n, -1));
    int max_time = -1;
    vector<vector<int>> visited(m, vector<int>(n, 0));
    queue<pi> q;  // 队列存放当前信号塔发射信号能够收到的信号塔index
    q.push(pi(j, k));
    visited[j][k] = 1;  // 因为是从(j, k)开始的，所以要设置已访问 
    ttime[j][k] = 0;
    while (!q.empty()) {
        pi cur = q.front();
        q.pop();
        int cur_x = cur.first;
        int cur_y = cur.second;
        // cout << "cur: " << cur_x << ", " << cur_y << "\n";
        // 上下左右四种情况分别看看 
        for (int i = 0; i < 4; i++) {
            int q_x = cur_x + dx[i];
            int q_y = cur_y + dy[i];
            // cout << "ques: " << q_x << ", " << q_y << " ";
            // 如果此处没有信号塔，或被访问过，或索引超出范围，就continue 
            if (q_x < 0 || q_x >= m || q_y < 0 || q_y >= n || grid[q_x][q_y] == 0 || visited[q_x][q_y] == 1) {
                // cout << "continue" << endl;
                continue;
            }
            // 将(q_x, q_y)处标记为已访问
            visited[q_x][q_y] = 1;
            // 计算从(cur_x, cur_y)发送信号到(q_x, q_y)的时间（并加上之前的时间） 
            ttime[q_x][q_y] = ttime[cur_x][cur_y] + grid[cur_x][cur_y];
            max_time = max(max_time, ttime[q_x][q_y]);
            // cout << "time: " << time[q_x][q_y] << " max_time: " << max_time << endl;
            q.push(pi(q_x, q_y));
        }
    }
 
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0 && ttime[r][c] == -1) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << max_time << endl;
    return 0;
}

但是这个代码在运行下面这个案例时出现了wrong answer：

运行时间：
85ms
消耗内存：
6780kb
========[test2.in]=========
21
5
3 14
2 1 1 1 2 2 0 2 1 1 0 0 1 1 1 2 2 1 1 1 1
2 1 2 1 1 2 0 2 2 2 2 1 1 2 2 1 2 1 1 1 1
0 1 1 0 2 1 2 1 2 0 1 1 1 2 1 1 0 0 0 2 1
2 1 2 1 1 1 1 0 1 1 1 1 0 2 2 1 2 2 1 2 1
0 2 1 1 2 2 1 0 2 1 2 2 0 1 2 2 1 0 1 2 2

========[test2.out]=========
Expected						      |	Yours
24							      |	30

后续改进

实在想不出来哪里错了，于是问了chatgpt，有了以下回答：

分析你的代码，发现问题出现在传递时间的计算上。你在计算时间时总是直接加上信号塔的时间，而不是根据不同信号塔的不同传递时间来更新时间。因此，存在多次更新时间的情况，导致最终的时间计算错误。

为了修复这个问题，我们需要改进时间的计算方式，并确保每个信号塔只在更短时间内收到信号时才会被更新。

以下是修正后的代码：

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

#define N 1004
#define pi pair<int, int>
#define ti tuple<int, int, int> // (time, x, y)

int m, n;   // 网格行数，列数
int j, k;   // 触发信号的信号塔(j, k)
int grid[N][N];
int dx[4] = { -1, 1, 0, 0 }; // 上下左右
int dy[4] = { 0, 0, -1, 1 }; // 上下左右

int main() {
    cin >> n >> m;
    cin >> j >> k;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
        }
    }

    vector<vector<int>> ttime(m, vector<int>(n, INT_MAX));
    int max_time = -1;
    vector<vector<int>> visited(m, vector<int>(n, 0));
    priority_queue<ti, vector<ti>, greater<ti>> pq; // 优先队列 (time, x, y)
    pq.push({0, j, k});
    ttime[j][k] = 0;

    while (!pq.empty()) {
        auto [cur_time, cur_x, cur_y] = pq.top();
        pq.pop();

        if (visited[cur_x][cur_y]) continue;
        visited[cur_x][cur_y] = 1;

        for (int i = 0; i < 4; i++) {
            int q_x = cur_x + dx[i];
            int q_y = cur_y + dy[i];

            if (q_x < 0 || q_x >= m || q_y < 0 || q_y >= n || grid[q_x][q_y] == 0) {
                continue;
            }

            int new_time = cur_time + (grid[cur_x][cur_y] == 1 ? 1 : 2);
            if (new_time < ttime[q_x][q_y]) {
                ttime[q_x][q_y] = new_time;
                pq.push({new_time, q_x, q_y});
                max_time = max(max_time, new_time);
            }
        }
    }

    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0 && ttime[r][c] == INT_MAX) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    cout << max_time << endl;
    return 0;
}

直接提交试试，发现居然是正确的。。。[大拇指]

主要改动：

  1. 引入优先队列：优先队列用于确保总是处理当前最短时间的信号传递。
  2. 优化时间更新逻辑：只有当新的时间更短时，才会更新信号塔的时间，并将其加入优先队列。确实，我的初始代码更新时间时没有考虑这个，可能会导致原本是更短的时间被更长的时间更新。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/761415.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Visual Studio 设置回车代码补全

Visual Studio 设置回车代码补全

工具 -> 选项 -> 文本编辑器 -> C/C -> 高级 -> 主动提交成员列表 设置为TRUE
阅读更多...
萨科微slkor金航标kinghelm的品牌海外布局

萨科微slkor金航标kinghelm的品牌海外布局

萨科微slkor&#xff08;www.slkormicro.com&#xff09;金航标kinghelm宋仕强在介绍品牌的海外布局时说&#xff0c; 萨科微目前在土耳其、印度、新加坡均有代理商&#xff0c;海外代理商还在不断的发展和筛选中&#xff01;欢迎公司有资质&#xff0c;在当地有一定客户关系的…
阅读更多...
Axure 中继器 实现选取表格行、列交互

Axure 中继器 实现选取表格行、列交互

Axure 中继器 实现选取表格行、列交互 引言 在办公软件或富文本编辑器中插入表格的时候我们经常可以通过在表格上移动鼠标&#xff0c;可以选取想要插入的表格行、列数。 本文分享如何通过 Axure 实现这个交互。 放入中继器 这个交互的用到了中继器&#xff0c;所以首先在…
阅读更多...
WPF/C#：BusinessLayerValidation

WPF/C#：BusinessLayerValidation

BusinessLayerValidation介绍 BusinessLayerValidation&#xff0c;即业务层验证&#xff0c;是指在软件应用程序的业务逻辑层&#xff08;Business Layer&#xff09;中执行的验证过程。业务逻辑层是应用程序架构中的一个关键部分&#xff0c;负责处理与业务规则和逻辑相关的…
阅读更多...
【C++】继承(详解)

【C++】继承(详解)

前言&#xff1a;今天我们正式的步入C进阶内容的学习了&#xff0c;当然了既然是进阶意味着学习难度的不断提升&#xff0c;各位一起努力呐。 &#x1f496; 博主CSDN主页:卫卫卫的个人主页 &#x1f49e; &#x1f449; 专栏分类:高质量&#xff23;学习 &#x1f448; &#…
阅读更多...
2065. 最大化一张图中的路径价值 Hard

2065. 最大化一张图中的路径价值 Hard

给你一张 无向 图&#xff0c;图中有 n 个节点&#xff0c;节点编号从 0 到 n - 1 &#xff08;都包括&#xff09;。同时给你一个下标从 0 开始的整数数组 values &#xff0c;其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges &#xf…
阅读更多...
电子技术基础（模电部分）笔记

电子技术基础（模电部分）笔记

终于整理出来了&#xff0c;可以安心复习大物线代了&#xff01;&#xff01; 数电部分预计7.10出
阅读更多...
007-GeoGebra基础篇-构建等边三角形

007-GeoGebra基础篇-构建等边三角形

今天继续来一篇尺规作图&#xff0c;可以跟着操作一波&#xff0c;刚开始我写的比较细一点&#xff0c;每步都有截图&#xff0c;后续内容逐渐复杂后我就只放置算式咯。 目录 一、先看看一下最终效果二、本次涉及的内容三、开始尺规画图1. 绘制定点A和B2. 绘制线段AB3. 以点A为…
阅读更多...
【日记】度过了一个堕落的周末……（184 字）

【日记】度过了一个堕落的周末……（184 字）

正文 昨天睡了一天觉&#xff0c;今天看了一天《三体》电视剧。真是堕落到没边了呢&#xff08;笑。本来想写代码完成年度计划&#xff0c;或者多写几篇文章&#xff0c;但实在不想写&#xff0c;也不想动笔。 感觉这个周末什么都没做呢&#xff0c;休息倒是休息好了。 今天 30…
阅读更多...
基于x86/ARM+FPGA+AI工业相机的智能工艺缺陷检测，可以检测点状，线状，面状的缺陷

基于x86/ARM+FPGA+AI工业相机的智能工艺缺陷检测，可以检测点状，线状，面状的缺陷

应用场景 缺陷检测 在产品的制造生产环节中发挥着极其重要作用。智能工业缺陷检测能够替代传统的人工检测&#xff0c;降低人为判断漏失&#xff0c;使得产品质量大幅提升的同时降低了工厂的人力成本。智能工艺缺陷检测技术可以检测点状&#xff0c;线状&#xff0c;面状的缺陷…
阅读更多...
UnityUGUI之四 Mask

UnityUGUI之四 Mask

会将上级物体遮盖 注&#xff1a; 尽量不使用Mask&#xff0c;因为其会过度消耗运行资源&#xff0c;可以使用Rect 2DMask&#xff0c;但容易造成bug&#xff0c;因此最好实现遮罩效果的方式为自己写一个mask物体
阅读更多...
用易查分下发《致家长一封信》，支持在线手写签名，一键导出PDF！

用易查分下发《致家长一封信》，支持在线手写签名，一键导出PDF！

暑假来临之际&#xff0c;学校通常需要下发致家长信&#xff0c;以正式、书面的形式向家长传达重要的通知或建议。传统的发放方式如家长签字后学生将回执单上交&#xff0c;容易存在丢失、遗忘的问题。 那么如何更高效、便捷、安全地将致家长一封信送达给每位家长呢&#xff1f…
阅读更多...
项目方案：社会视频资源整合接入汇聚系统解决方案(八)---视频监控汇聚应用案例

项目方案：社会视频资源整合接入汇聚系统解决方案(八)---视频监控汇聚应用案例

目录 一、概述 1.1 应用背景 1.2 总体目标 1.3 设计原则 1.4 设计依据 1.5 术语解释 二、需求分析 2.1 政策分析 2.2 业务分析 2.3 系统需求 三、系统总体设计 3.1设计思路 3.2总体架构 3.3联网技术要求 四、视频整合及汇聚接入 4.1设计概述 4.2社会视频资源分…
阅读更多...
多片体育场地建球馆，就选气膜球馆—轻空间

多片体育场地建球馆，就选气膜球馆—轻空间

随着现代社会对健康生活的追求日益增加&#xff0c;体育场地的需求也在不断增长。尤其是羽毛球作为一项受欢迎的全民运动&#xff0c;其场地需求量更是与日俱增。在众多的球馆建设方案中&#xff0c;气膜球馆因其独特的优势&#xff0c;正逐渐成为多片体育场地建设的最佳选择。…
阅读更多...
微尺度气象数值模拟—大涡模拟技术

微尺度气象数值模拟—大涡模拟技术

原文链接&#xff1a;微尺度气象数值模拟—大涡模拟技术https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247607904&idx4&snc02e7b7b104c500626cc7456c819112a&chksmfa826787cdf5ee91860e66b4f45532b995760edc1780cdde52bb8b36349b9b997392d21aed18&…
阅读更多...
为什么安装了SSL证书还是不能HTTPS访问？

为什么安装了SSL证书还是不能HTTPS访问？

即便是正确安装了SSL证书&#xff0c;有时网站仍然无法通过HTTPS正常访问&#xff0c;这背后可能隐藏着多种原因。以下是一些常见的问题及解决方案&#xff0c;帮助您排查并解决这一困扰。 PC点此申请&#xff1a;SSL证书申请_https证书下载-极速签发 注册填写注册码230918&a…
阅读更多...
mysql-5.6.26-winx64免安装版本

mysql-5.6.26-winx64免安装版本

mysql为什么要使用免安装 MySQL 提供免安装版本主要有以下几个原因和优势&#xff1a; 便捷性&#xff1a;用户无需经历安装过程&#xff0c;直接解压即可使用。这对于需要快速部署环境或者在不支持安装权限的系统上使用MySQL非常有用。灵活性&#xff1a;免安装版允许用户将…
阅读更多...
基于SSM的挂号系统（简单）

基于SSM的挂号系统（简单）

设计技术&#xff1a; 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SSMJSP 工具&#xff1a;IDEA、Maven、Navicat 主要功能&#xff1a; 首页 登录 查看医生信息 挂号 挂号记录查看 个人信息查看 需要可加V分享源码 package com.hg.controller;impor…
阅读更多...
idk17配置

idk17配置

只需要把zip包解压&#xff0c;然后配置环境变量&#xff1a; bin目录路径粘到path里面就好了 然后打开cmd窗口分别输入 java javac java -version 验证
阅读更多...
IT专业入门，高考假期预习指南

IT专业入门，高考假期预习指南

文章目录 一、了解IT专业的基本概念二、选择适合的编程语言入门三、掌握基本的编程工具和环境四、学习基础的数据结构和算法五、实践项目和动手实验六、利用在线资源进行学习七、参加编程竞赛和社区活动总结 高考结束后&#xff0c;许多同学将迎来大学生活&#xff0c;而对于选…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站