【华为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-排列组合】一个套路速解排列组合题

双指针

回溯法可能会超时，所以推荐双指针法。

比如输入的数组是：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;
    }
}