网站制作开发,重庆市建设工程信息网资质系统,wordpress注册插件,微信小程序怎么删除题目 跳房子#xff0c;也叫跳飞机#xff0c;是一种世界性的儿童游戏游戏。参与者需要分多个回合按顺序跳到第1格直到房子的最后一格#xff0c;然后获得一次选房子的机会#xff0c;直到所有房子被选完#xff0c;房子最多的人获胜。 跳房子的过程中#xff0c;如果有踩…题目 跳房子也叫跳飞机是一种世界性的儿童游戏游戏。参与者需要分多个回合按顺序跳到第1格直到房子的最后一格然后获得一次选房子的机会直到所有房子被选完房子最多的人获胜。 跳房子的过程中如果有踩线等违规行为会结束当前回合甚至可能倒退几步.假设房子的总格数是count小红每回合可能连续跳的步数都放在数组steps中请问数组中是否有一种步数的组合可以让小红三个回合跳到最后一格?如果有请输出索引和最小的步数组合(数据保证索引和最小的步数组合是唯一的)。 注意:数组中的步数可以重复但数组中的元素不能重复使用 输入描述: 第一行输入为房子总格数count它是int整数类型 第二行输入为每回合可能连续跳的步数它是int整数数组类型 输出描述 返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序) 补充说明: count100003steps.length10000-100000steps[i]100000 示例1 输入: 9 [1,4,5,2,0,2] 输出: [4,5,0] 示例2 输入: 9 [1,5,2,0,2,4] 输出: [5,2,2] 示例3 输入: 12 [-1,2,4,9] 输出: [-1,4,9] 示例4: 输入 15 [1,9,4,25,10,8,7,5] 输出 [1,4,10] 说明 符合条件的步数集合有 [1,9,5] 它的下角标之和为:0178 [1,4,10] 它的下角标之和为:0246 因为68故输出[1,4,10]。 思路
两种思路
回溯法双指针
回溯法
列举所有的组合找到符合条件的组合排列组合思路详见【JAVA-排列组合】一个套路速解排列组合题 先只考虑三数之和等于目标值比如对于-4 -1 -1 0 1 2 5目标和为0 回溯遍历过程 -4 -1 -1 -4 -1 0 -4 -1 1 -4 -1 2 -4 -1 5 -1 -1 0 -1 -1 1 -1 -1 2 -1 -1 5 0 1 2 0 1 5 1 2 5 设第一二三位分别为i,j,k当i固定为-4j固定位-1时需要找的目标数字是5加起来和才为0回溯的过程对于k来说是依次遍历-1,012,5找到最后才出现5因为数组是按照从小到大排序的所以可以考虑最开始k就从最后一位开始找 如果最后一位都小于5那么其前面的数字不可能比5还大也就不必再找-4-1的组合了。 如果最后一位大于5那么ijk这三个数加起来肯定大于0此时需要将k左移可以使三个数的和相对小一点。 上面的优化过程就是双指针的思想。 双指针
根据上面的分析回溯法可能会超时所以推荐双指针法。 比如输入的数组是1,4,5,2,0,2目标数字是9 先将nums按照升序排序0 1 2 2 4 5 外层遍历k范围为0len-2; 内层设置两个变量i指向k1位置j指向最后一个位置如下 现在计算这三个数的和0156小于9将i右移动到下一个不同的值比如此时nums[2]、nums[3]均为2如果i2满足要求那么i3时也满足要求题目要求索引和的最小值所以要尽可能选则索引小的值这里就需要保证前面的2的索引是小于后面的2的索引的 此时和为7还是小于9继续将i右移动到下一个不同的值 此时和为9满足条件将此时的i,j,k存下来 依次类推再考虑k2,i3,jlen-1的情况。 以上思路基本能够找到三个不同的数让它们的和等于给定的数和题目在以下方面还有出入 题目要求输出索引和最小的组合输出的顺序需要于输入的顺序一致 要解决上面两个问题只需要新建一个对象House有两个属性值和索引。如果我们把输入的nums转为List House houses因为需要将nums按照值的升序排序所以house可以实现Comparable接口它按照值的升序排序当值相等时应该按照索引的升序排序当出现两个相同的数保证前面值的索引小于后面值的索引houses中存放了索引信息可以供后续比较得到最小的索引和而针对“输出的顺序需要于输入的顺序一致”当我们找到满足条件的组合时我们再按照对象中存放的索引重新按照从小到大排序即可。 题解
回溯法
package hwod;import java.util.*;public class JumpHouse {public static void main(String[] args) {Scanner sc new Scanner(System.in);int count sc.nextInt();sc.nextLine();String str sc.nextLine();int[] nums Arrays.stream(str.substring(1, str.length() - 1).split(,)).mapToInt(Integer::parseInt).toArray();int[] res jumpHouse(nums, count);StringBuilder sb new StringBuilder([);for (int i 0; i res.length; i) {if (i ! 0) sb.append(,);sb.append(res[i]);}sb.append(]);System.out.println(sb);}private static ListInteger res new ArrayList();private static int minestIndex Integer.MAX_VALUE;private static int[] jumpHouse(int[] nums, int count) {LinkedListInteger path new LinkedList();dfs(nums, 0, path, count, 0);return res.stream().mapToInt(i - i).toArray();}private static void dfs(int[] nums, int start, LinkedListInteger path, int target, int indexSum) {if (path.size() 3) {if (target 0 indexSum minestIndex) {minestIndex indexSum;res new ArrayList(path);}return;}for (int i start; i nums.length; i) {path.addLast(nums[i]);dfs(nums, i 1, path, target - nums[i], indexSum i);path.removeLast();}}
}
双指针
package hwod;import java.util.*;public class JumpHouse2 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int count sc.nextInt();sc.nextLine();String str sc.nextLine();int[] nums Arrays.stream(str.substring(1, str.length() - 1).split(,)).mapToInt(Integer::parseInt).toArray();ListHouse houses new ArrayList();for (int i 0; i nums.length; i) {houses.add(new House(i, nums[i]));}int[] res jumpHouse(houses, count);StringBuilder sb new StringBuilder([);for (int i 0; i res.length; i) {if (i ! 0) sb.append(,);sb.append(res[i]);}sb.append(]);System.out.println(sb);}private static int[] jumpHouse(ListHouse houses, int count) {Collections.sort(houses);int[] res new int[3];int minIdxSum Integer.MAX_VALUE;for (int k 0; k houses.size()-2; k) {if(houses.get(k).getVal()count) break;if(k0houses.get(k).getVal()houses.get(k-1).getVal()) continue;int i k 1, j houses.size() - 1;while (i j) {int sum houses.get(k).getVal() houses.get(i).getVal() houses.get(j).getVal();if (sum count) {while (ijhouses.get(i).getVal()houses.get(i).getVal());} else if (sum count) {while (ijhouses.get(j).getVal()houses.get(--j).getVal());} else {int idxSumhouses.get(k).getId() houses.get(i).getId() houses.get(j).getId();if (idxSum minIdxSum) {minIdxSum idxSum;ListHouse houseAns Arrays.asList(houses.get(k), houses.get(i), houses.get(j));houseAns.sort(Comparator.comparingInt(House::getId));res new int[]{houseAns.get(0).getVal(), houseAns.get(1).getVal(), houseAns.get(2).getVal()};}while (ijhouses.get(i).getVal()houses.get(i).getVal());while (ijhouses.get(j).getVal()houses.get(--j).getVal());}}}return res;}}class House implements ComparableHouse {private int id;private int val;public House(int id, int val) {this.id id;this.val val;}public int getId() {return id;}public void setId(int id) {this.id id;}public int getVal() {return val;}public void setVal(int val) {this.val val;}/*** 自定义排序按照val倒序索引升序排列,保证去重时始终选的较小值的索引* param o the object to be compared.* return*/Overridepublic int compareTo(House o) {if(o.valthis.val) return this.getId() - o.getId();return this.val - o.val;}
}推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
