做购物平台网站需要多少资金,微信公众号的字体和wordpress,淄博网站建设兼职,wordpress 文字背景目录 专栏导读一、题目描述二、输入描述三、输出描述备注用例1、输入2、输出3、说明 四、解题思路1、核心思路#xff1a;2、具体步骤 五、Java算法源码再重新读一遍题目#xff0c;看看能否优化一下~解题步骤也简化了很多。 六、效果展示1、输入2、输出3、说明 华为OD机试 2… 目录 专栏导读一、题目描述二、输入描述三、输出描述备注用例1、输入2、输出3、说明 四、解题思路1、核心思路2、具体步骤 五、Java算法源码再重新读一遍题目看看能否优化一下~解题步骤也简化了很多。 六、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
给定一组闭区间其中部分区间存在交集。
任意两个给定区间的交集称为公共区间(如:[1,2],[2,3]的公共区间为[2,2],[3,5],[3,6]的公共区间为[3,5])公共区间之间若存在交集则需要合并(如:[1,3],[3,5]区间存在交集[3,3],需合并为[1,5])。按升序排列输出合并后的区间列表。
二、输入描述
组区间列表
区间数为 N: ON1000。
区间元素为 X:-10000X10000。
三、输出描述
升序排列的合并区间列表
备注
区间元素均为数字不考虑字母、符号等异常输入。单个区间认定为无公共区间。
用例
1、输入
4 0 3 1 3 3 5 3 6
2、输出
[1,5]
3、说明
0 3和1 3的公共区间是1 30 3和3 5的公共区间是3 30 3和3 6的公共区间是3 31 3和3 5的公共区间是3 31 3和3 6的公共区间是3 33 5和3 6的公共区间是3 5两两组合求出公共区间去重变为[1,3][3,3][3,5]若公共区间存在交集合并为[1,5]
四、解题思路
第一反应是通过深度优先搜索dfs算法来解。
1、核心思路
两两组合求出公共区间左右分别相比谁小取谁删除重复的公共区间 [1,3][3,3][3,5]有交集就合并没交集就直接输出左边谁小取谁右边谁大取谁 [1,5]
2、具体步骤
第一行输入一个数字n表示公共区间的数量接下来的n行是具体的公共区间并添加到集合list中两两组合求出公共区间左右分别相比谁小取谁删除重复的公共区间 如果list就剩一个了就不用比了第一个数组 与 余下的数组进行两两比较比较过的直接移除遍历余下的数组 两个区间有交集取交集左取大右取小判断公共区间是否存在如果不存在加入到公共区间集合中 再取下一个第一个数组再与余下的数组进行两两比较循环往复 有交集就合并没交集就直接输出左边谁小取谁右边谁大取谁 如果list就剩一个了就不用比了第一个数组 与 余下的数组进行两两比较此时不能直接删除因为合并的才可以删除不能合并的直接输出即可遍历余下的数组当有交集时 左边谁小取谁右边谁大取谁删除有交集的区间将合并后的区间加入到list再进行比较合并可以合并重置mergeFlag为true表示list中的数组还可以继续合并 如果当前比较的第一个数组不能与余下的数组进行合并将其删除 能与余下的数组进行合并的区间可以合并表示list中的数组还可以继续合并重置合并表示为false 取第一个区间与余下的区间进行合并循环往复 按照左区间升序排序如果相等再按右区间升序排序将合并后的公共区间添加到builder中输出即可。
五、Java算法源码
public class OdTest07 {// 公共区间集合static Listint[] publicRangeList new ArrayList();public static void main(String[] args) {Scanner sc new Scanner(System.in);int n Integer.valueOf(sc.nextLine());Listint[] list new ArrayList();for (int i 0; i n; i) {int[] arr Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();list.add(arr);}// 两两组合求出公共区间左右分别相比谁小取谁删除重复的公共区间 [1,3][3,3][3,5]dfs(list);// 有交集就合并没交集就直接输出左边谁小取谁右边谁大取谁 [1,5]mergeDfs(publicRangeList);publicRangeList.addAll(unMergeList);// 按照左区间升序排序如果相等再按右区间升序排序publicRangeList.sort((a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]);StringBuilder builder new StringBuilder();for (int i 0; i publicRangeList.size(); i) {builder.append(publicRangeList.get(i)[0]).append( ).append(publicRangeList.get(i)[1]).append(\n);}System.out.println(builder.deleteCharAt(builder.length() - 1));}// 两两组合求出公共区间private static void dfs(Listint[] list) {// 如果list就剩一个了就不用比了if (list.size() 1) {return;}// 第一个数组 与 余下的数组进行两两比较int[] firstArr list.get(0);int left firstArr[0];int right firstArr[1];// 比较过的直接移除list.remove(0);// 余下的数组for (int i 0; i list.size(); i) {// 余下的数组int[] comareArr list.get(i);// 两个区间有交集if (right comareArr[0] comareArr[1] left) {// 取交集左取大右取小int compareLeft left comareArr[0] ? comareArr[0] : left;int compareRight right comareArr[1] ? right : comareArr[1];int[] range new int[]{compareLeft, compareRight};// 判断公共区间是否存在如果不存在加入到公共区间集合中if (!compareArr(range)) {publicRangeList.add(range);}}}// 再取下一个第一个数组再与余下的数组进行两两比较循环往复dfs(list);}// 判断公共区间是否存在private static boolean compareArr(int[] arr) {for (int i 0; i publicRangeList.size(); i) {int[] rangeArr publicRangeList.get(i);if (arr[0] rangeArr[0] arr[1] rangeArr[1]) {return true;}}return false;}// 是否可以合并static boolean mergeFlag false;// 不能合并的数组区间static Listint[] unMergeList new ArrayList();// 有交集就合并没交集就直接输出左边谁小取谁右边谁大取谁private static void mergeDfs(Listint[] list) {// 如果list就剩一个了就不用比了if (list.size() 1) {return;}// 第一个数组 与 余下的数组进行两两比较// [3,6][5,6][5,7][6,6][6,7][6,8][9,10]int[] firstArr list.get(0);int left firstArr[0];int right firstArr[1];// 此时不能直接删除因为合并的才可以删除不能合并的直接输出即可// 余下的数组for (int i 1; i list.size(); i) {int[] comareArr list.get(i);// [9,10][3,6][5,7][6,8]// 当有交集时if (right comareArr[0] comareArr[1] left) {// 左边谁小取谁右边谁大取谁int compareLeft left comareArr[0] ? left : comareArr[0];int compareRight right comareArr[1] ? comareArr[1] : right;int[] range new int[]{compareLeft, compareRight};// 删除有交集的区间list.remove(firstArr);list.remove(comareArr);// 将合并后的区间加入到list再进行比较合并list.add(range);// 可以合并表示list中的数组还可以继续合并mergeFlag true;break;}}// 如果当前比较的第一个数组不能与余下的数组进行合并将其删除if (!mergeFlag) {list.remove(firstArr);// 能与余下的数组进行合并的区间unMergeList.add(firstArr);} else {// 可以合并表示list中的数组还可以继续合并// 重置合并表示为falsemergeFlag false;}// 取第一个区间与余下的区间进行合并循环往复mergeDfs(list);}
}感觉这道题不至于这么复杂吧。
再重新读一遍题目看看能否优化一下~ 因为最近一直在刷dfs的算法题所以第一反应是采用dfs来解不过普通的for循环就可以解决了确实简单了很多找准方向才最重要~
核心思想没什么变化。
解题步骤也简化了很多。
第一行输入一个数字n表示公共区间的数量接下来的n行是具体的公共区间并添加到集合list中按照左区间升序排序如果相等再按右区间升序排序定义公共区间集合publicRangeList遍历list每一个数组与后面的数组分别比较取交集 两个区间有交集左右分别相比取交集左取大右取小 按照左区间升序排序如果相等再按右区间升序排序定义合并后的区间数组builder获取第一个有效的合并区间mergeArr遍历公共区间集合publicRangeList 有交集取右区间的最大值没有交集拼接到合并的区间数组builder中重置有效的合并区间为下一个区间 输出合并后的区间数组即可。
public class OdTest07 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n Integer.valueOf(sc.nextLine());Listint[] list new ArrayList();for (int i 0; i n; i) {int[] arr Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();list.add(arr);}// 按照左区间升序排序如果相等再按右区间升序排序list.sort((a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]);// 公共区间集合Listint[] publicRangeList new ArrayList();// 遍历list每一个数组与后面的数组分别比较取交集for (int i 0; i list.size(); i) {int[] arr list.get(i);for (int j i 1; j list.size(); j) {int[] nextArr list.get(j);// 两个区间有交集if (arr[1] nextArr[0]) {// 左右分别相比取交集左取大右取小publicRangeList.add(new int[]{Math.max(arr[0], nextArr[0]), Math.min(arr[1], nextArr[1])});}}}// [3,6][5,6][6,6][5,7][6,8][6,7][9,10]if (publicRangeList.size() 0) {System.out.println(None);return;}// [3,6][5,6][5,7][6,6][6,7][6,8][9,10]publicRangeList.sort((a, b) - a[0] ! b[0] ? a[0] - b[0] : a[1] - b[1]);// 合并后的区间数组StringBuilder builder new StringBuilder();// 有效的合并区间int[] mergeArr publicRangeList.get(0);for (int i 1; i publicRangeList.size(); i) {int[] nextArr publicRangeList.get(i);// 有交集取右区间的最大值if (mergeArr[1] nextArr[0]) {mergeArr[1] Math.max(mergeArr[1], nextArr[1]);} else {// 没有交集拼接到合并的区间数组builder中builder.append(mergeArr[0]).append( ).append(mergeArr[1]).append(\n);// 重置有效的合并区间为下一个区间mergeArr nextArr;}}builder.append(mergeArr[0]).append( ).append(mergeArr[1]).append(\n);// 输出合并后的区间数组System.out.println(builder.deleteCharAt(builder.length() - 1));}
}六、效果展示
1、输入
5 9 10 5 7 6 11 3 8 3 6
2、输出
3 8 9 10
3、说明
3 6和3 8的公共区间是3 63 6和5 7的公共区间是5 63 6和6 11的公共区间是6 63 6和9 10的公共区间是无3 8和5 7的公共区间是5 73 8和6 11的公共区间是6 83 8和9 10的公共区间是无5 7和6 11的公共区间是6 75 7和9 10的公共区间是无6 11和9 10的公共区间是9 10两两组合求出公共区间[3,6][5,6][6,6][5,7][6,8][6,7][9,10]有交集就合并没交集就直接输出[3,8][9,10] 下一篇华为OD机试 - 最长的顺子 - 感谢禁止你发言提供的更简便算法Java 2023 B卷 200分
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
