有哪些关于校园内网站建设的法律,防做网站,乐清上班族网论坛,asp网站建设 iis配置目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介绍 …
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 可整合数组定义如果数组排序后相邻元素之间差值为1的话则该数组为可整合数组 给定一个数组arr求arr中最长的可整合子数组。 如5532643 返回53264长度为5
解决方案
原问题 首先有个定律相邻元素差值为1的话该数组的最大值和最小值差值1就应该是数组的长度 根据该定律遍历数组的所有子数组每一轮检测数组最大值和最小值差值是否是当前数组长度求出最长长度即可。
代码编写
java语言版本
原问题
/*** 二轮测试求代码可整合子数组的最长长度* 可整合数组定义对数组排序后数组中每相邻两个数之间的差值为1* param arr* return*/public static Record getLILCp1(int[] arr) {if (arr null || arr.length 0) {return null;}Record record new Record();int min;int max;// 用来判重SetInteger set new HashSet();// 遍历每一个子数组for (int i 0; i arr.length; i) {// 每一轮需要清空最值min arr[0];max arr[0];set.clear();for (int j i; j arr.length; j) {// 子数组为[i...j],先计算最值// 更新当前子数组的最大值或最小值max Math.max(max, arr[j]);min Math.min(min, arr[j]);// 计算当前子数组是否是可整合数组if (set.contains(arr[j])) {// 从j开始存在重复的,直接下一轮break;}else if (max - min 1 j - i 1) {// 值域 长度if (j - i 1 record.len) {record.setLen(j - i 1);record.setArr(Arrays.copyOfRange(arr, i, j1));}set.add(arr[j]);}}}return record;}/*** 存储最长子数组长度和对应子数组的实体类*/static class Record {private int len;private int[] arr;public int getLen() {return len;}public void setLen(int len) {this.len len;}public int[] getArr() {return arr;}public void setArr(int[] arr) {this.arr arr;}Overridepublic String toString() {return Record{ len len , arr Arrays.toString(arr) };}}public static void main(String[] args) {System.out.println(getLILCp1(new int[]{5,5,3,2,6,4,3}));}
c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
这道题给我两个启发 首先求符合要求的子数组类型的问题一定能够通过暴力解决 符合要求的子数组可以通过暴力算法遍历每一个子数组这道题我一开始往最优解上想的时候根本没有考虑过使用暴力遍历每一个子数组虽然可能大多数题目都不会这么写但是不代表所有的题最优解不会遍历所有子数组。 其次长度和最值差值之间的关系需要记牢 相差1可以用长度等于最值差值这个定律在我刚开始接触算法的时候可能没有想到过但是数组计数算法也有相似的启发有时候我们可以多想想数组的index和实际的值有时候是否存在微妙的关联是很重要的。
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
