【华为OD题库-037】跳房子2-java
题目
跳房子，也叫跳飞机，是一种世界性的儿童游戏游戏。参与者需要分多个回合按顺序跳到第1格直到房子的最后一格，然后获得一次选房子的机会，直到所有房子被选完，房子最多的人获胜。
跳房子的过程中，如果有踩线等违规行为会结束当前回合，甚至可能倒退几步.假设房子的总格数是count，小红每回合可能连续跳的步数都放在数组steps中，请问数组中是否有一种步数的组合，可以让小红三个回合跳到最后一格?如果有，请输出索引和最小的步数组合(数据保证索引和最小的步数组合是唯一的)。
注意:数组中的步数可以重复，但数组中的元素不能重复使用
输入描述:
第一行输入为房子总格数count，它是int整数类型
第二行输入为每回合可能连续跳的步数，它是int整数数组类型
输出描述
返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序)
补充说明:
count<=10000，3<=steps.length<=10000，-100000<=steps[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]
它的下角标之和为:0+1+7=8 ；
[1,4,10]
它的下角标之和为:0+2+4=6
因为6<8，故输出[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固定为-4，j固定位-1时，需要找的目标数字是5（加起来和才为0），回溯的过程，对于k来说，是依次遍历-1,0，1，2,5，找到最后才出现5，因为数组是按照从小到大排序的，所以可以考虑，最开始k就从最后一位开始找：
如果最后一位都小于5，那么其前面的数字不可能比5还大，也就不必再找-4，-1，？的组合了。
如果最后一位大于5，那么i，j，k这三个数加起来肯定大于0，此时需要将k左移可以使三个数的和相对小一点。
上面的优化过程就是双指针的思想。
双指针
根据上面的分析，回溯法可能会超时，所以推荐双指针法。
比如输入的数组是：1,4,5,2,0,2，目标数字是9
先将nums按照升序排序：0 1 2 2 4 5
外层遍历k，范围为0，len-2;
内层设置两个变量，i指向k+1位置，j指向最后一个位置，如下：
现在计算这三个数的和，0+1+5=6，小于9，将i右移动到下一个不同的值（比如此时nums[2]、nums[3]均为2，如果i=2满足要求，那么i=3时也满足要求，题目要求索引和的最小值，所以要尽可能选则索引小的值，这里就需要保证前面的2的索引是小于后面的2的索引的）
此时和为7，还是小于9，继续将i右移动到下一个不同的值
此时和为9满足条件，将此时的i,j,k存下来
依次类推，再考虑k=2,i=3,j=len-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 List<Integer> res = new ArrayList<>();
private static int minestIndex = Integer.MAX_VALUE;
private static int[] jumpHouse(int[] nums, int count) {
LinkedList<Integer> path = new LinkedList<>();
dfs(nums, 0, path, count, 0);
return res.stream().mapToInt(i -> i).toArray();
}
private static void dfs(int[] nums, int start, LinkedList<Integer> 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();
List<House> 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(List<House> 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(k>0&&houses.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 (i<j&&houses.get(i).getVal()==houses.get(++i).getVal());
} else if (sum > count) {
while (i<j&&houses.get(j).getVal()==houses.get(--j).getVal());
} else {
int idxSum=houses.get(k).getId() + houses.get(i).getId() + houses.get(j).getId();
if (idxSum < minIdxSum) {
minIdxSum = idxSum;
List<House> 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 (i<j&&houses.get(i).getVal()==houses.get(++i).getVal());
while (i<j&&houses.get(j).getVal()==houses.get(--j).getVal());
}
}
}
return res;
}
}
class House implements Comparable<House> {
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
*/
@Override
public int compareTo(House o) {
if(o.val==this.val) return this.getId() - o.getId();
return this.val - o.val;
}
}
推荐
如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。