随笔记录

笔试题-田忌赛马

2022-5-13 diaba 笔试题

package com.jiucaiyuan.net.algrithm.audition;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class MrTianHorseRacing {
    /**
     * <pre>
     * 田忌赛马
     * 两个数组没有重复元素，第一个数组固定按照从小道大出场比赛，数组较大的获胜
     * 给出第二个数组可以获得胜利的一个排列
     * 不存在获胜可能返回空数组
     *
     * 2 4 6
     * 1 3 5
     *
     * 按照默认顺序是0:3失败
     * 调整为3 5 1 之后是2:1获胜
     * </pre>
     *
     * @param arr1 团队1，顺序递增
     * @param arr2 团队2，顺序不定
     * @return 返回团队2可以胜利的其中一种排列次序
     */
    public static int[] win(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null || arr1.length != arr2.length) {
            return null;
        }
        //大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        for (int e : arr2) {
            queue.add(e);
        }

        List<Integer> result = new ArrayList<>();
        process(arr1, queue, result, arr1.length - 1);

        if (result.size() > arr1.length / 2) {
            int[] res = new int[arr1.length];
            int i = 0;
            for (Integer e : result) {
                res[i++] = e;
            }
            while (!queue.isEmpty()) {
                res[i++] = queue.poll();
            }
            return res;
        }

        return null;
    }

    public static void process(int[] arr, PriorityQueue<Integer> queue, List<Integer> result, int index) {
        if (queue.isEmpty() || result.size() > arr.length / 2) {
            return;
        }
        int e = queue.poll();
        for (int i = index; i >= 0; i--) {
            if (e > arr[i]) {
                result.add(e);
                process(arr, queue, result, i - 1);
                return;
            }
        }
    }

    public static void main(String[] args) {
        // Scanner input=new Scanner(System.in);
        // String str=input.next();
        int[] arr1 = {1, 2, 5, 6};
        int[] arr2 = {4, 3, 5, 1};
        print(win(arr1, arr2));
        int[] arr11 = {1, 4, 3, 5};
        int[] arr22 = {1, 2, 5, 6};
        print(win(arr11, arr22));
    }

    private static void print(int[] win) {
        if (win == null) {
            System.out.println("null");
            return;
        }
        for (int i : win) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}