自己做网站免费,怎样做化妆品网站,建设部2018年工作要点网站,梨树做网站题目 跳房子#xff0c;也叫跳飞机#xff0c;是—种世界性的儿童游戏#xff0c;游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后—格。跳房子的过程中#xff0c;可以向前跳#xff0c;也可以向后跳。 假设房子的总格数是count#xff0c;小红每回合可能连续跳…题目 跳房子也叫跳飞机是—种世界性的儿童游戏游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后—格。跳房子的过程中可以向前跳也可以向后跳。 假设房子的总格数是count小红每回合可能连续跳的步教都放在数组steps中请问数组中是否有一种步数的组合可以让小红两个回合跳到最后—格?如果有请输出索引和最小的步数组合。 注意: 数组中的步数可以重复但数组中的元素不能重复使用。提供的数据保证存在满足题目要求的组合且索引和最小的步数组合是唯一的 输入描述 第一行输入为房子总格数count它是int整数类型。 第二行输入为每回合可能连续跳的步数它是int整数数组类型。 输出描述 返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序 备注 count ≤ 1000 0 ≤ steps.length ≤ 5000 -100000000 steps ≤ 100000000 示例1: 输入 7 [1,4,5,2,2] 输出 [5, 2] 示例2: 输入 9 [-1,2,4,9,6] 输出 [-1,9] 说明 此样例有多种组合满足两回合跳到最后譬如: [-1,9][2,6]其中[-1,9]的索引和为033[2,6]的索和为145所以索引和最小的步数组合[-1,9] 思路
同leetcode1. 两数之和
双指针 和本系列 跳房子2 思路一样不赘述 哈希表 除了用对象记录值和索引的关系还可以用map。 遍历数组看target - nums[i]是否存在map中 如果存在说明当前值(target - nums[i])等于target那么记录此时的(target - nums[i])和nums[i]并通过map计算当前组合的索引和。 如果不存在以当前值为key当前值的索引为val存到map中 最后返回索引和最小的组合 题解
1. 双指针
package hwod;import java.util.*;public class JumpHouse1 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();sc.nextLine();String secondLines sc.nextLine();int[] nums Arrays.stream(secondLines.substring(1, secondLines.length() - 1).split(,)).mapToInt(Integer::parseInt).toArray();int[] res jumpHouse1(nums, n);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.toString());}private static int[] jumpHouse1(int[] nums, int target) {int[] res new int[2];ListHouse1 list new ArrayList();for (int i 0; i nums.length; i) {list.add(new House1(i, nums[i]));}Collections.sort(list);int i 0, j list.size() - 1;int minIdxSum Integer.MAX_VALUE;while (i j) {int sum list.get(i).getVal() list.get(j).getVal();if (sum target) {while (i j list.get(i).getVal() list.get(i).getVal()) ;} else if (sum target) {while (i j list.get(j).getVal() list.get(--j).getVal()) ;} else {int idxSum list.get(i).getIdx() list.get(j).getIdx();if (idxSum minIdxSum) {minIdxSum idxSum;ListHouse1 resHouses Arrays.asList(list.get(i), list.get(j));resHouses.sort(Comparator.comparingInt(House1::getIdx));res new int[]{resHouses.get(0).getVal(), resHouses.get(1).getVal()};}while (i j list.get(i).getVal() list.get(i).getVal()) ;while (i j list.get(j).getVal() list.get(--j).getVal()) ;}}return res;}
}class House1 implements ComparableHouse1 {private int idx;private int val;public int getIdx() {return idx;}public void setIdx(int idx) {this.idx idx;}public int getVal() {return val;}public void setVal(int val) {this.val val;}public House1(int idx, int val) {this.idx idx;this.val val;}Overridepublic int compareTo(House1 o) {if (this.val ! o.val) return this.val - o.val;return this.idx - o.idx;}
}2. 哈希表
package hwod;import org.omg.PortableInterceptor.INACTIVE;import java.util.*;public class JumpHouse1 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();sc.nextLine();String secondLines sc.nextLine();int[] nums Arrays.stream(secondLines.substring(1, secondLines.length() - 1).split(,)).mapToInt(Integer::parseInt).toArray();int[] res jumpHouse1(nums, n);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.toString());}private static int[] jumpHouse1(int[] nums, int target) {MapInteger, Integer map new HashMap();int[] res new int[2];int minIdxSum Integer.MAX_VALUE;for (int i 0; i nums.length; i) {if (map.containsKey(target - nums[i])) {int idxSum i map.get(target - nums[i]);if (idxSum minIdxSum) {minIdxSum idxSum;resnew int[]{target - nums[i], nums[i]};}}map.put(nums[i], i);}return res;}
}补充用例
再提供一组示例验证 输入 9 [4,1,3,6,5] 输出 [4,5]
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
