华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接

华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接,第1张

华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接,请添加图片描述,第2张

文章目录

  • 前言
  • 思路
  • 主要思路
  • 关于f函数的剖析
  • Code
    • 就到这,铁子们下期见!!!!

前言

铁子们好啊!今天阿辉又给大家来更新新一道好题,下面链接是23年9月27的华为笔试原题,LeetCode上面的

hard

难题,阿辉带大伙来拿下它!!!
你可以安排的最多任务数目

思路

二分和单调队列以及一丢丢贪心

主要思路

  • 先按照任务难度和工人能力排序

  • 二分的范围是

    [l,r)

    左闭右开,

    l = 0

    ,

    r = n+1

    ,最多完成

    n

    个任务,

    n

    取任务数与工人数的较小值,因为左闭右开,所以

    r

    n+1

    ,最少完成

    0

    个任务,所以

    l

    0

  • 然后就是如何判断

    l

    r

    的中点

    m

    是否是能够完成的任务数

    • 排序的重要就在这里体现了,我们取任务难度最小的

      m

      个与能力最强的

      m

      个工人如果能够完成,那就能完成,如果不能就完成不了

主逻辑代码:

// 主函数,用于找出可以分配的最大任务数量。 int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { int n = min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个,因为任务数不能超过工人数。 int l = 0; // 二分查找的左边界 int r = n+1; // 二分查找的右边界 sort(tasks.begin(), tasks.end()); // 将任务按难度排序 sort(workers.begin(), workers.end()); // 将工人按能力排序 // 二分查找,确定最大可分配任务数 while (l < r) { int m = l + (r - l) / 2; // 中间点 //f函数用于判断是否可以完成m个任务 if (f(tasks, workers, pills, strength, m)) { l = m + 1; // 如果能完成m个任务,则尝试增加任务数 } else { r = m; // 如果不能完成m个任务,则减少任务数 } } return l - 1; // 返回最终的任务数(因为在二分查找结束时,l指向的是第一个不能完成的任务数) }

关于f函数的剖析

f

函数的空间复杂度是 O ( M ) O(M) O(M),因为

i

j

都只前进不回退,也就是只遍历

2

m

长度的数组

N

为任务数组与工人数组的较大值
然后主函数排序两个数组是 O ( N l o g N ) O(NlogN) O(NlogN),二分加上f函数最多也不超过 O ( N l o g N ) O(NlogN) O(NlogN)
所以时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)
空间复杂度低于 O ( N ) O(N) O(N),队列长度取决于完成任务的数量

int deque[50001]; // 一个双端队列,用于存储可能通过使用或不使用药丸完成的任务。 // 辅助函数,用于判断是否能在当前条件下完成m个任务。 bool f(vector<int>& ts, vector<int>& ws, int p, int s, int m) { int h = 0, t = 0; // 双端队列的头部和尾部指针 //i指向最容易完成的第一个任务,j指向能力第m强的工人 //遍历m个最容易完成的任务以及能力最强的m个工人 for (int i = 0, j = ws.size() - m; j < ws.size(); ++j) { // 遍历每一个工人,并尝试分配任务 while (i < m && ts[i] <= ws[j]) { // 如果当前任务可以由工人直接完成,则将其加入队列 deque[t++] = ts[i++]; } //经过上面的if如果队列里面没东西,说明该试试药了 //如果队列里面有东西,可能是前一个工人嗑药留下的 if (h == t || ws[j] < deque[h]) { // 如果队列为空,或当前工人无法完成队列头部的任务,则尝试使用药丸 --p; // 使用一颗药丸 while (i < m && ts[i] <= ws[j] + s) { // 将可以通过使用药丸完成的任务加入队列 deque[t++] = ts[i++]; } if (h == t || p < 0 || ws[j] + s < deque[h]) { // 如果队列依然为空,或药丸用完,或即使使用药丸也无法完成队列头部的任务,则返回false return false; } --t; // 上面没返回说明嗑药有用,完成最难的任务,一点子贪心各位肯定能懂,队列尾部指针前移 } else {//否则 ++h; // 工人直接完成了队列头部的任务,队列头部指针后移 } } //能走到这就说明能完成 return true;

Code

class Solution { public: // 主函数,用于找出可以分配的最大任务数量。 int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { int n = min(tasks.size(), workers.size()); // 取任务数和工人数中较小的一个,因为任务数不能超过工人数。 int l = 0; // 二分查找的左边界 int r = n+1; // 二分查找的右边界 sort(tasks.begin(), tasks.end()); // 将任务按难度排序 sort(workers.begin(), workers.end()); // 将工人按能力排序 // 二分查找,确定最大可分配任务数 while (l < r) { int m = l + (r - l) / 2; // 中间点 if (f(tasks, workers, pills, strength, m)) { l = m + 1; // 如果能完成m个任务,则尝试增加任务数 } else { r = m; // 如果不能完成m个任务,则减少任务数 } } return l - 1; // 返回最终的任务数(因为在二分查找结束时,l指向的是第一个不能完成的任务数) } int deque[50001]; // 一个双端队列,用于存储可能通过使用或不使用药丸完成的任务。 // 辅助函数,用于判断是否能在当前条件下完成m个任务。 bool f(vector<int>& ts, vector<int>& ws, int p, int s, int m) { int h = 0, t = 0; // 双端队列的头部和尾部指针 for (int i = 0, j = ws.size() - m; j < ws.size(); ++j) { // 遍历每一个工人,并尝试分配任务 while (i < m && ts[i] <= ws[j]) { // 如果当前任务可以由工人直接完成,则将其加入队列 deque[t++] = ts[i++]; } if (h == t || ws[j] < deque[h]) { // 如果队列为空,或当前工人无法完成队列头部的任务,则尝试使用药丸 --p; // 使用一颗药丸 while (i < m && ts[i] <= ws[j] + s) { // 将可以通过使用药丸完成的任务加入队列 deque[t++] = ts[i++]; } if (h == t || p < 0 || ws[j] + s < deque[h]) { // 如果队列依然为空,或药丸用完,或即使使用药丸也无法完成队列头部的任务,则返回false return false; } --t; // 完成一个任务,队列尾部指针前移 } else { ++h; // 工人直接完成了队列头部的任务,队列头部指针后移 } } return true; // 如果所有工人都成功分配了任务,则返回true } };

就到这,铁子们下期见!!!!

华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接,请添加图片描述,第3张

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/13518697.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2024-02-18
下一篇 2024-02-25

发表评论

登录后才能评论

评论列表(0条)

保存