首页 > 分享一波机式题
头像
delicious-z
编辑于 2021-04-24 16:29
+ 关注

分享一波机式题

第一题

1-n表示1,2,3...n
现在有资源1-4,7 如果拿走3,则剩下资源为 1,2,4,7;你应该输出1-2,4,7
这题我的思路是对区间进行处理。以下是AC代码。

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        List<int[]> its = new ArrayList<>();
        for (String s : line.split(",")) {
            int[] it;
            String[] vs = s.split("-");
            if (vs.length == 1) it = new int[]{Integer.parseInt(s), Integer.parseInt(s)};
            else it = new int[]{Integer.parseInt(vs[0]), Integer.parseInt(vs[1])};
            its.add(it);
        }
        its.sort(Comparator.comparingInt(a -> a[0]));
//        its.forEach(a -> System.out.println(Arrays.toString(a)));
        int take = in.nextInt();
        List<int[]> res = new ArrayList<>();
        for (int[] it : its) {
            if (it[0] <= take && it[1] >= take) {
                if (it[0] == take || it[1] == take) {
                    if (it[0] == take) res.add(new int[]{it[0] + 1, it[1]});
                    else res.add(new int[]{it[0], it[1] - 1});
                } else {
                    res.add(new int[]{it[0], take - 1});
                    res.add(new int[]{take + 1, it[1]});
                }
            } else res.add(it);
        }

        res = res.stream().filter(it->it[0] <= it[1]).collect(Collectors.toList());
        for (int i = 0; i < res.size(); i++) {
            int[] it = res.get(i);
            if (it[0] > it[1]) continue;
            else if (it[0] == it[1]) System.out.print(it[0]);
            else System.out.print(it[0] + "-" + it[1]);
            if (i != res.size() - 1) System.out.print(",");
        }
    }

第二题

输入一行,包含若干个正整数,输出用由这些数中的3个组成的最小的数,如果不够三个数则用上所有的数。
输入: 12,31,10
输出: 101231
输入: 5,21
输出: 215
这题没有AC,没想到什么好的方法,用暴力试了一下仅仅通过了33%。

    public static void main(String[] args) {
        List<String> strings = Arrays.stream(new Scanner(System.in)
                .nextLine()
                .split(","))
                .collect(Collectors.toList());
        backtracking(strings, new LinkedList<>(), new HashSet<>());
        System.out.println(ans);
    }

    static int ans = Integer.MAX_VALUE;

    private static void backtracking(List<String> list, LinkedList<String> path, Set<Integer> seen) {

        if (path.size() == Math.min(3, list.size())) {
            StringBuilder builder = new StringBuilder();
            path.forEach(builder::append);
            ans = Math.min(ans, Integer.parseInt(builder.toString()));
        }
        for (int i = 0; i < list.size(); i++) {
            if (seen.contains(i)) continue;
            path.add(list.get(i));
            seen.add(i);
            backtracking(list, path, seen);
            path.removeLast();
            seen.remove(i);
        }
    }

第三题

输入一行,包含若干个正整数,2和5不能同时出现,6和9不能同时出现,所有数字在1-9范围内,否则输出-1。
2可以当作5用,5可以当作2用,6可以当作9用,9可以当作6用。
假设这些数最大的是N,这些数自由组合可以得到不同的数字,输出第N大的数,如果没有这么多数,输入最大的那个。

思路:这还有想,直接枚举。
这题也没有AC -- ,通过了80%。

    public static void main(String[] args) {

        List<String> collect = Arrays.stream(
                new Scanner(System.in).nextLine().split(",")
        ).collect(Collectors.toList());

        int max = 0;
        Set<Integer> set = new HashSet<>();
        for (String s : collect) {
            int x = Integer.parseInt(s);
            max = Math.max(max,x);
            if (set.contains(x)) {
                System.out.println(-1);
                return;
            }
            set.add(x);
        }

        if (
                (set.contains(2) && set.contains(5))
                        || (set.contains(6) && set.contains(9))
                        || set.stream().anyMatch(x -> x < 1 || x > 9)

        ) {
            System.out.println(-1);
            return;
        }

        if (set.contains(2)) collect.add("5");
        else if (set.contains(5)) collect.add("2");
        if (set.contains(6)) collect.add("9");
        else if (set.contains(9)) collect.add("6");

        String[] strings = collect.toArray(new String[0]);

        List<Integer> combinations = new ArrayList<>();
        backtracking(strings, combinations, new HashSet<>(), new LinkedList<>());
        combinations.sort(Comparator.comparingInt(Integer::intValue));
        int k = Math.min(
                combinations.size() - 1,
                max - 1
        );
//        System.out.println(combinations);
        System.out.println(combinations.get(k));
    }

    private static void backtracking(String[] strings, List<Integer> res, Set<Integer> seen, LinkedList<Integer> combination) {
        StringBuilder builder = new StringBuilder();
        for (int i : combination) {
            builder.append(strings[i]);
        }
        if (builder.length() != 0) res.add(Integer.parseInt(builder.toString()));
        for (int i = 0; i < strings.length; i++) {
            if (seen.contains(i)) continue;
            seen.add(i);
            combination.add(i);
            backtracking(strings, res, seen, combination);
            seen.remove(i);
            combination.removeLast();
        }
    }

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

热门推荐