华为机试贪心算法 牛客真题实例Python可直接提交贪心核心思想每一步在当前局部选最优希望最终全局最优适用场景区间、分配、活动选择、跳跃、最小代价。华为机试贪心高频题型区间合并、区间选点、最多活动、分饼干、跳跃游戏。下面给2道最常考原题带完整AC代码。实例1区间合并牛客经典华为真题中等题目描述读取N个区间[start, end]合并所有重叠/相邻区间输出合并后的区间按起点升序。输入第一行区间数量n后面n行每行两个整数 start end输入样例4 1 3 2 6 8 10 15 18输出样例1 6 8 10 15 18贪心策略将所有区间按起点从小到大排序维护结果列表依次遍历当前区间和结果最后一个区间重叠/相接 → 合并更新右端点不重叠 → 直接加入结果完整可提交代码importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0])intervals[]foriinrange(1,n1):s,emap(int,lines[i].split())intervals.append([s,e])# 贪心第一步按区间起点升序排序intervals.sort(keylambdax:x[0])res[]forseginintervals:ifnotres:# 结果为空直接加入res.append(seg)else:last_s,last_eres[-1]cur_s,cur_esegifcur_slast_e:# 重叠合并右端取较大值new_seg[last_s,max(last_e,cur_e)]res[-1]new_segelse:# 不重叠直接追加res.append(seg)# 输出foriteminres:print(item[0],item[1])if__name____main__:main()考点排序贪心华为非常爱考区间类贪心。实例2活动选择最多参加多少活动简单贪心题目描述有n个活动每个活动有开始时间、结束时间。同一时间只能参加一个活动求最多可以参加多少活动。贪心策略优先选结束最早的活动留给后面更多时间经典活动选择贪心模板输入样例3 1 4 2 3 3 5输出2解释选 [2,3]再选[3,5]共2个完整AC代码importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0])acts[]foriinrange(1,n1):st,edmap(int,lines[i].split())acts.append([st,ed])# 贪心关键按【结束时间升序】排序acts.sort(keylambdax:x[1])count0last_end-1fors,einacts:ifslast_end:# 可以选这个活动count1last_endeprint(count)if__name____main__:main()贪心华为高频题型速记背这个题目类型贪心策略区间合并按区间起点排序最多活动选择按区间结束时间升序区间选点最少点覆盖区间按结束排序每次在区间末尾放一个点分发饼干孩子胃口、饼干都从小到大排序小饼干满足小胃口跳跃游戏遍历维护最远可到达位置贪心算法做题固定步骤机试直接套用排序绝大多数贪心第一步都是排序确定排序key最关键设置变量保存当前最优状态上一个区间终点 / 当前最大收益遍历局部做最优选择输出答案⚠️贪心坑点机试容易翻车贪心不能证明正确就不要用贪心只适用于局部最优可以推出全局最优不能凭感觉写比如背包问题不能贪心。排序key写错活动选择按起点排序就错必须按结束区间边界还是相邻区间是否算重叠仔细读题拓展跳跃游戏华为真题贪心题目数组每个数字代表最多可以跳几步判断能不能跳到最后。输入一行数组2 3 1 1 4输出Trueimportsysdefmain():numslist(map(int,sys.stdin.readline().split()))max_reach0nlen(nums)foriinrange(n):ifimax_reach:print(false)returnmax_reachmax(max_reach,inums[i])ifmax_reachn-1:print(true)returnprint(true)if__name____main__:main()要不要我给区间选点贪心真题华为机试同款或者贪心 vs DP对比题
华为机试贪心算法 牛客真题实例Python可直接提交贪心核心思想每一步在当前局部选最优希望最终全局最优适用场景区间、分配、活动选择、跳跃、最小代价。华为机试贪心高频题型区间合并、区间选点、最多活动、分饼干、跳跃游戏。下面给2道最常考原题带完整AC代码。实例1区间合并牛客经典华为真题中等题目描述读取N个区间[start, end]合并所有重叠/相邻区间输出合并后的区间按起点升序。输入第一行区间数量n后面n行每行两个整数 start end输入样例4 1 3 2 6 8 10 15 18输出样例1 6 8 10 15 18贪心策略将所有区间按起点从小到大排序维护结果列表依次遍历当前区间和结果最后一个区间重叠/相接 → 合并更新右端点不重叠 → 直接加入结果完整可提交代码importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0])intervals[]foriinrange(1,n1):s,emap(int,lines[i].split())intervals.append([s,e])# 贪心第一步按区间起点升序排序intervals.sort(keylambdax:x[0])res[]forseginintervals:ifnotres:# 结果为空直接加入res.append(seg)else:last_s,last_eres[-1]cur_s,cur_esegifcur_slast_e:# 重叠合并右端取较大值new_seg[last_s,max(last_e,cur_e)]res[-1]new_segelse:# 不重叠直接追加res.append(seg)# 输出foriteminres:print(item[0],item[1])if__name____main__:main()考点排序贪心华为非常爱考区间类贪心。实例2活动选择最多参加多少活动简单贪心题目描述有n个活动每个活动有开始时间、结束时间。同一时间只能参加一个活动求最多可以参加多少活动。贪心策略优先选结束最早的活动留给后面更多时间经典活动选择贪心模板输入样例3 1 4 2 3 3 5输出2解释选 [2,3]再选[3,5]共2个完整AC代码importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0])acts[]foriinrange(1,n1):st,edmap(int,lines[i].split())acts.append([st,ed])# 贪心关键按【结束时间升序】排序acts.sort(keylambdax:x[1])count0last_end-1fors,einacts:ifslast_end:# 可以选这个活动count1last_endeprint(count)if__name____main__:main()贪心华为高频题型速记背这个题目类型贪心策略区间合并按区间起点排序最多活动选择按区间结束时间升序区间选点最少点覆盖区间按结束排序每次在区间末尾放一个点分发饼干孩子胃口、饼干都从小到大排序小饼干满足小胃口跳跃游戏遍历维护最远可到达位置贪心算法做题固定步骤机试直接套用排序绝大多数贪心第一步都是排序确定排序key最关键设置变量保存当前最优状态上一个区间终点 / 当前最大收益遍历局部做最优选择输出答案⚠️贪心坑点机试容易翻车贪心不能证明正确就不要用贪心只适用于局部最优可以推出全局最优不能凭感觉写比如背包问题不能贪心。排序key写错活动选择按起点排序就错必须按结束区间边界还是相邻区间是否算重叠仔细读题拓展跳跃游戏华为真题贪心题目数组每个数字代表最多可以跳几步判断能不能跳到最后。输入一行数组2 3 1 1 4输出Trueimportsysdefmain():numslist(map(int,sys.stdin.readline().split()))max_reach0nlen(nums)foriinrange(n):ifimax_reach:print(false)returnmax_reachmax(max_reach,inums[i])ifmax_reachn-1:print(true)returnprint(true)if__name____main__:main()要不要我给区间选点贪心真题华为机试同款或者贪心 vs DP对比题
