C语言/数据结构区间合并题解：暴雨梨花针——最少无重复连续段分割次数-北京尧图网络

问题描述小明是唐门年轻一代的暗器高手他正在练习唐门绝技“暴雨梨花针”。每次发射可以覆盖一排连续的敌人但每次发射都会消耗一枚银针。敌人排成一行每个敌人都有一个特定的编号可能重复。小明发现除了一个编号的敌人需要被单独针对外其他编号的敌人都是成对出现的即每个编号恰好有两个敌人。为了节省银针小明希望用最少的发射次数消灭所有敌人每次发射可以消灭任意连续的一段敌人但要求这段中不能包含两个相同编号的敌人即同一编号的两个敌人不能被同一发银针消灭。注意每次发射后被消灭的敌人将不再存在后续发射只能针对剩余的敌人。你的任务是帮助小明计算最少需要多少次发射才能消灭所有敌人。要求设计一个算法计算最少发射次数。时间复杂度应为 O(n)其中 n 是敌人的数量。测试样例样例1输入enemies [1, 2, 1, 3, 2]输出2解释编号1和2的敌人都成对出现。第一次发射消灭前两个敌人[1,2]此时剩余敌人为[1,3,2]。第二次发射消灭剩余所有敌人[1,3,2]注意这次发射中没有重复编号。不能一次发射消灭所有敌人因为第一个和第三个敌人编号相同1不能在同一发中消灭。样例2输入enemies [5, 5, 3, 3, 4]输出3解释编号5和3的敌人都成对出现编号4的敌人单独出现。第一次发射消灭第一个敌人[5]此时剩余敌人为[5,3,3,4]。第二次发射消灭第二个和第三个敌人[5,3]此时剩余敌人为[3,4]。第三次发射消灭最后两个敌人[3,4]。每次发射中都没有重复编号。样例3输入enemies [1, 2, 3, 2, 1, 3, 4]输出2解释编号1、2、3的敌人都成对出现编号4的敌人单独出现。第一次发射消灭前四个敌人[1,2,3,2]注意这段中没有重复编号编号2虽然出现两次但位置不同且编号2的两次出现不在同一发射段。剩余敌人为[1,3,4]。第二次发射消灭剩余所有敌人[1,3,4]没有重复编号。约束条件1 ≤ enemies.length ≤ 1000001 ≤ enemies[i] ≤ 100000敌人数量为奇数除了一个编号的敌人出现一次外其余每个编号的敌人都恰好出现两次程序代码#include stdio.h#include string.hint minShots(int* enemies, int enemiesSize) {int first[100001], second[100001];memset(first, -1, sizeof(first));memset(second, -1, sizeof(second));for (int i 0; i enemiesSize; i) {int id enemies[i];if (first[id] -1) {first[id] i;} else {second[id] i;}}// 收集区间 [first, second]int intervals[50000][2];int cnt 0;for (int id 1; id 100000; id) {if (first[id] ! -1 second[id] ! -1) {intervals[cnt][0] first[id];intervals[cnt][1] second[id];cnt;}}// 如果没有成对的区间只有独特元素需要1次发射if (cnt 0) {return 1;}// 按左端点排序冒泡排序因为cnt最多50000但实际数据规模不大for (int i 0; i cnt - 1; i) {for (int j i 1; j cnt; j) {if (intervals[i][0] intervals[j][0]) {int tmp0 intervals[i][0], tmp1 intervals[i][1];intervals[i][0] intervals[j][0];intervals[i][1] intervals[j][1];intervals[j][0] tmp0;intervals[j][1] tmp1;}}}// 合并重叠区间int mergedCnt 0;for (int i 0; i cnt; i) {int l intervals[i][0];int r intervals[i][1];if (mergedCnt 0) {intervals[mergedCnt][0] l;intervals[mergedCnt][1] r;mergedCnt;} else if (l intervals[mergedCnt - 1][1]) {// 重叠合并if (r intervals[mergedCnt - 1][1]) {intervals[mergedCnt - 1][1] r;}} else {// 不重叠新区间intervals[mergedCnt][0] l;intervals[mergedCnt][1] r;mergedCnt;}}// 最少发射次数合并区间数 1return mergedCnt 1;}int main() {int enemies1[] {1, 2, 1, 3, 2};int enemies2[] {5, 5, 3, 3, 4};int enemies3[] {1, 2, 3, 2, 1, 3, 4};printf(%d\n, minShots(enemies1, 5)); // 2printf(%d\n, minShots(enemies2, 5)); // 3printf(%d\n, minShots(enemies3, 7)); // 2return 0;}#include stdio.h #include string.h int minShots(int* enemies, int enemiesSize) { int first[100001], second[100001]; memset(first, -1, sizeof(first)); memset(second, -1, sizeof(second)); for (int i 0; i enemiesSize; i) { int id enemies[i]; if (first[id] -1) { first[id] i; } else { second[id] i; } } // 收集区间 [first, second] int intervals[50000][2]; int cnt 0; for (int id 1; id 100000; id) { if (first[id] ! -1 second[id] ! -1) { intervals[cnt][0] first[id]; intervals[cnt][1] second[id]; cnt; } } // 如果没有成对的区间只有独特元素需要1次发射 if (cnt 0) { return 1; } // 按左端点排序冒泡排序因为cnt最多50000但实际数据规模不大 for (int i 0; i cnt - 1; i) { for (int j i 1; j cnt; j) { if (intervals[i][0] intervals[j][0]) { int tmp0 intervals[i][0], tmp1 intervals[i][1]; intervals[i][0] intervals[j][0]; intervals[i][1] intervals[j][1]; intervals[j][0] tmp0; intervals[j][1] tmp1; } } } // 合并重叠区间 int mergedCnt 0; for (int i 0; i cnt; i) { int l intervals[i][0]; int r intervals[i][1]; if (mergedCnt 0) { intervals[mergedCnt][0] l; intervals[mergedCnt][1] r; mergedCnt; } else if (l intervals[mergedCnt - 1][1]) { // 重叠合并 if (r intervals[mergedCnt - 1][1]) { intervals[mergedCnt - 1][1] r; } } else { // 不重叠新区间 intervals[mergedCnt][0] l; intervals[mergedCnt][1] r; mergedCnt; } } // 最少发射次数合并区间数 1 return mergedCnt 1; } int main() { int enemies1[] {1, 2, 1, 3, 2}; int enemies2[] {5, 5, 3, 3, 4}; int enemies3[] {1, 2, 3, 2, 1, 3, 4}; printf(%d\n, minShots(enemies1, 5)); // 2 printf(%d\n, minShots(enemies2, 5)); // 3 printf(%d\n, minShots(enemies3, 7)); // 2 return 0; }运行结果

C语言/数据结构区间合并题解：暴雨梨花针——最少无重复连续段分割次数

相关推荐

现在靠谱的AI写作辅助网站有哪些品牌？学生党亲测反馈

深圳 GEO 优化服务商选型笔记：五家厂商优劣势梳理

类DNF微变版本服务端技术拆解与本地部署指南

更多资讯

武强电工证实操考试心里没底怕挂科？官方报名入口和备考攻略全在这

临高办电工证怎么转异地？真实经历告诉你怎么复审延期

年审电工证材料证全国通用吗

如何考电工证在哪考好值不值得考

紫云考电工证考前押题攻略：怕考不过白交培训费？别慌，看完就懂

天津低压电工证学习值不值得考？实操考试心里没底怕挂科怎么办？

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？