7.21华为笔试

# 前两题是贪心问题
首先,问题我就不贴了(因为不能传播,学习思路就好了,题目千变万化,华为本就没有原题),供大家参考思路。

# 1 最少的汽车数量
这个题很有意思,眼看着是活动安排问题,当时没绕不出来。不妨这么想
1. 假定你知道活动安排问题。
2. 活动安排问题是指,一个共享会议室,安排了k个活动,每个活动都有起始时间startTime和结束时间endTime。当然这k个活动有重叠,没有重叠就能安排k个活动,求最大安排的活动数量?
3. 把这个思想放在这里,假如这k个APP请求,最多相容安排数量为ans,换句话说,这ans个请求只需要1辆车。
4. 将步骤3中的APP请求剔除,再一次执行最多相容安排问题,又需要1辆车
5. 直到ans为0,轮询的次数就是答案。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int start, upID, downID;
        for (int i = 0; i < k; ++i) {
            cin >> start >> upID >> downID;
            int temp = abs(upID - downID);
            nums[i].push_back(start);
            nums[i].push_back(start + min(temp, n - temp) * 5);
        }

        /**<按照结束时间升序排序 */
        sort(nums.begin(), nums.end(), [](const vector<int>& a, vector<int>& b){
           return a[1] < b[1];
        });

        vector<int> vis(k, 0);          /**<标记是否移除该任务 */
        int remain = k;
        int lastBegin = 0;              /**<相容任务剔除后,下一个起点在不断前进 */

        /**<1. 求解最大相容任务数量 使用一辆车 */
        /**<2. 剔除上次任务再求最大相容任务数量 使用一辆车 */
        /**<3. 重复2,直到任务为0 */
        int minCar = 0;
        while (remain > 0) {
            int i = lastBegin;
            while (vis[i] != 0)   ++i;        /**<找到第一个未移除的结点 */
            lastBegin = i;

            int endTime = nums[i][1];
            vis[i] = 1;
            int ans = 1;                      /**<活动至少安排一个 */
            for (++i; i < k; ++i) {
                if (vis[i]==0 && nums[i][0]>=endTime) {
                    endTime = nums[i][1];
                    ++ans;
                    vis[i] = 1;
                }
            }
            remain -= ans;                      /**<剔除当前相容的任务 */
            ++minCar;
        }
        cout << minCar << '\n';
    }

    return 0;
}




#if 0
50 3
0 0 5
10 10 11
25 20 40
output: 2

10 3
0 0 1
5 0 9
10 0 1
output: 1

15 8
0 6 12
5 0 3
15 5 7
15 8 13
20 12 15
25 7 11
30 0 11
40 5 8
output: 4

#endif
注意:一共有三组测试数据,第三组是我自己想的,有问题可以留言

备注: 这题是一个改编题

253. 会议室 II



网友提出了一个很经典的解法,官方也提出了优先队列的解答方式

借用这种解法,可以把时间复杂度降低到O(nlogn)
int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int start, upID, downID;
        for (int i = 0; i < k; ++i) {
            cin >> start >> upID >> downID;
            int temp = abs(upID - downID);
            nums[i].push_back(start);
            nums[i].push_back(start + min(temp, n - temp) * 5);
        }
        
        vector<pair<int,int>> info;
        for (const auto& e : nums) {
            info.push_back({e[0], 1});
            info.push_back({e[1], -1});
        }
        sort(info.begin(), info.end());

        int minCar = 0;
        int number = 0;
        for (const auto& e : info) {
            number += e.second;
            minCar = max(minCar, number);
        }
        cout << minCar << '\n';
    }

    return 0;
}


# 2 一批任务需要多长时间?
这题也是贪心,比较简单,
1. 按照题目的优先级对数组排序
2. 由于机器数量n有限制,如果没有限制,那么最长时间就是最长的那个任务
3. 那么问题来了,机器少任务多,怎么办?
4. 用一个数组cost存下前n个任务,因为只有n个机器
5. 之后,遍历的每个时长加在cost数组的最小值上
6. 结果就是数组cost的最大值
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) 
{
    int n, k;
    while (cin >> n >> k) {
        vector<vector<int>> nums(k);
        int t, p;
        for (int i = 0; i < k; ++i) {
            cin >> t >> p;
            nums[i].push_back(t);
            nums[i].push_back(p);
        }
        
        /**<按照第二列升序排序,相同按照第一列降序 */
        sort(nums.begin(), nums.end(), [](const vector<int>& a, vector<int>& b) {
            return a[1]!=b[1] ? a[1]<b[1] : a[0]>b[0];
        });

        /**<机器足够多 */
        if (n >= k) {
            int ans = 0;
            for (int i = 0; i < k; ++i)
                ans = max(ans, nums[i][0]);
            cout << ans << '\n';
        }

        /**<初始化n台机器 */
        vector<int> cost(n, 0);
        int i = 0;
        while (i < n) {
            cost[i] = nums[i][0];
            ++i;
        }
        /**<给最小值加上当前值-贪心 */
        while (i < k) {
            *min_element(cost.begin(), cost.end()) += nums[i++][0];
        }
        cout << *max_element(cost.begin(), cost.end()) << '\n';
    }

    return 0;
}


#if 0
3 7
1 1
4 1
5 3
4 2
2 1
3 3
2 1
output: 8


#endif

# 3  图中最长路径
这题不难,输入是真难顶
1. 解析输入
[[1,2,5],[1,3,5],[2,5,5],[3,7,10],[3,4,10],[4,2,10],[4,7,5],[5,6,5],[6,7,5]]
有两个基本问题?
(1)图的边集未知?
(2)图的点数未知?
我没有采用传统的切割方式,我换了一种方式
(1)把", [ ]"替换成空格
(2)将新的字符串存入istringstream
(3)每次读取三个整数即可

求解图中最大的路径长度
(1)首先,图中有没有环?我的代码没有考虑环,当然dfs可以解决环,只是最长路径有环的话可以多绕几圈,,,就没有最大值了
(2)之后对每一个结点dfs找出最大路径和,就暴力搜索
(3)这里存储图有技巧,因为实际上图的存储常用邻接表,它是链表,考试中没有那么多时间写出来;如果用邻接矩阵的话,三维,可能超时。
问题:把邻接表存入矩阵中?
struct Node {
    int to, weight;
};
const int MAXSIZE = 210;
vector<Node> G[MAXSIZE];
1. 起点其实是数组的下标,把终点和权重存入Node即可
2. 上面的G后面是中括号,它其实是二维矩阵,和
G(MAXSIZE)
有区别。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int to, weight;
};
const int MAXSIZE = 210;
vector<Node> G[MAXSIZE];

int dfs(int u) {
    int ans = 0;
    for (const auto&e : G[u]) {
        ans = max(ans, dfs(e.to) + e.weight);
    }
    return ans;
}

int main(int argc, char *argv[]) 
{
    string str;
    while (cin >> str) {
        for (auto& e : str) {
            if (e==',' || e=='[' || e==']')
                e = ' ';
        }
        istringstream iss(str);
        int a, b, c;
        int points = 0;                             /**<图中节点数 */
        while (iss >> a >> b >> c) {
            points = max(points, max(a, b));
            G[a].push_back({b, c});
        }

        int ans = 0;
        for (int i = 1; i <= points; ++i) {
            ans = max(ans, dfs(i));
        }
        cout << ans << '\n';
    }

    return 0;
}


#if 0
[[1,2,5],[1,3,5],[2,5,5],[3,7,10],[3,4,10],[4,2,10],[4,7,5],[5,6,5],[6,7,5]]
output: 40

#endif

华为没有使用牛客答题了,用的实习知,不少人踩坑,考试过程在不能退出页面,考前个人信息填写任何一步出问题,都可能导致无法开启摄像头--判为作弊,所以要提前练习下模拟考试。


最后,若有侵权,我立即删帖。


#华为笔试##笔经##华为#
全部评论
你好,第一题我是帮我同学做的,只过了20%,请问这题的边界条件在哪?我考虑的最近的站点,就是超过一半的站点数就用总站点数减去当前的站点数
1 回复
分享
发布于 2021-07-24 14:54
我第一题使用的模拟,第二题使用的倒是贪心
1 回复
分享
发布于 2021-07-30 21:57
百信银行
校招火热招聘中
官网直投
您好,问一下笔试时长多少?
点赞 回复
分享
发布于 2021-08-02 16:56

相关推荐

头像
不愿透露姓名的神秘牛友
03-10 02:21
投票
华为无线 单板硬件 13a 硕士985
点赞 评论 收藏
转发
4 36 评论
分享
牛客网
牛客企业服务