[左神面试指南] 其他题目[下]篇

CD79 一种消息接收并打印的结构设计

public class CD79_1
{
    public static class Node
    {
        public int num;
        public Node next;

        public Node(int num)
        {
            this.num = num;
        }
    }

    public static class MessageBox
    {
        private HashMap<Integer, Node> headMap;
        private HashMap<Integer, Node> tailMap;
        private int lastPrint;

        public MessageBox()
        {
            headMap = new HashMap<Integer, Node>();
            tailMap = new HashMap<Integer, Node>();
            lastPrint = 0;
        }

        public void receive(int num)
        {
            if (num < 1) return;
            Node cur = new Node(num);
            headMap.put(num, cur);
            tailMap.put(num, cur);
            if (tailMap.containsKey(num - 1))
            {
                tailMap.get(num - 1).next = cur;
                tailMap.remove(num - 1);
                headMap.remove(num);
            }
            if (headMap.containsKey(num + 1))
            {
                cur.next = headMap.get(num + 1);
                tailMap.remove(num);
                headMap.remove(num + 1);
            }
            if (headMap.containsKey(lastPrint + 1))
                print(num);
        }

        private void print(int num)
        {
            Node node = headMap.get(++lastPrint);
            headMap.remove(lastPrint);
            while (node != null)
            {
                System.out.println(node.num + " " + num);
                node = node.next;
                lastPrint++;
            }
            tailMap.remove(--lastPrint);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        MessageBox messageBox = new MessageBox();
        int n = in.nextInt();
        for (int i = 0; i < n; i++)
            messageBox.receive(in.nextInt());
    }
}

CD80 随时找到数据流的中位数

public class CD80_1
{
    public static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    public static PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    public static int count = 0;

    public static void Insert(Integer num)
    {
        count++;
        if (count % 2 != 0)
        {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        }
        else
        {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }

    public static Double GetMedian()
    {
        if (minHeap.size() == maxHeap.size())
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        else
            return maxHeap.peek() * 1.0;
    }
}

CD81 在两个长度相等的排序数组中找到上中位数❓

/*❓*/
public class CD81_1
{
    public static int solution(int[] arr1, int[] arr2)
    {
        if (arr1 == null || arr2 == null || arr1.length != arr2.length)
        {
            throw new RuntimeException("Your arr is invalid!");
        }
        int start1 = 0;
        int end1 = arr1.length - 1;
        int start2 = 0;
        int end2 = arr2.length - 1;
        int mid1 = 0;
        int mid2 = 0;
        int offset = 0;
        while (start1 < end1)
        {
            mid1 = (start1 + end1) / 2;
            mid2 = (start2 + end2) / 2;
            // 元素个数为奇数，则 offset 为 0；
            // 元素个数为偶数，则 offset 为 1
            offset = ((end1 - start1 + 1) & 1) ^ 1;
            if (arr1[mid1] > arr2[mid2])
            {
                end1 = mid1;
                start2 = mid2 + offset;
            }
            else if (arr1[mid1] < arr2[mid2])
            {
                start1 = mid1 + offset;
                end2 = mid2;
            }
            else
                return arr1[mid1];
        }
        return Math.min(arr1[start1], arr2[start2]);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++)
            arr1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            arr2[i] = in.nextInt();
        System.out.println(solution(arr1, arr2));
    }
}

CD82 在两个排序数组中找到第 k 小的数❓

/*❓*/
public class CD82_1
{
    public static int solution(int[] arr1, int[] arr2, int kth)
    {
        if (arr1 == null || arr2 == null)
            throw new RuntimeException("Your arr is invalid!");
        if (kth < 1 || kth > arr1.length + arr2.length)
            throw new RuntimeException("K is invalid!");
        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
        int l = longs.length;
        int s = shorts.length;
        if (kth <= s)
            return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
        if (kth > l)
        {
            if (shorts[kth - l - 1] >= longs[l - 1])
                return shorts[kth - l - 1];
            if (longs[kth - s - 1] >= shorts[s - 1])
                return longs[kth - s - 1];
            return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
        }
        if (longs[kth - s - 1] >= shorts[s - 1])
            return longs[kth - s - 1];
        return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
    }

    public static int getUpMedian(int[] a1, int s1, int e1, int[] a2, int s2, int e2)
    {
        int mid1 = 0;
        int mid2 = 0;
        int offset = 0;
        while (s1 < e1)
        {
            mid1 = (s1 + e1) / 2;
            mid2 = (s2 + e2) / 2;
            offset = ((e1 - s1 + 1) & 1) ^ 1;
            if (a1[mid1] > a2[mid2])
            {
                e1 = mid1;
                s2 = mid2 + offset;
            }
            else if (a1[mid1] < a2[mid2])
            {
                s1 = mid1 + offset;
                e2 = mid2;
            }
            else
                return a1[mid1];
        }
        return Math.min(a1[s1], a2[s2]);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[m];
        for (int i = 0; i < n; i++)
            arr1[i] = in.nextInt();
        for (int i = 0; i < m; i++)
            arr2[i] = in.nextInt();
        System.out.println(solution(arr1, arr2, k));
    }
}

CD83 两个有序数组间相加和的 Top k 问题

public class CD83_1
{
    public static class Node implements Comparable<Node>
    {
        public int index1;
        public int index2;
        public int val;

        public Node(int index1, int index2, int val)
        {
            this.index1 = index1;
            this.index2 = index2;
            this.val = val;
        }

        @Override
        public int compareTo(Node o)
        {
            return o.val - this.val;
        }
    }

    public static int[] solution(int[] arr1, int[] arr2, int k)
    {
        PriorityQueue<Node> que = new PriorityQueue<>();
        HashSet<String> set = new HashSet<>();
        int res[] = new int[k];
        int len1 = arr1.length - 1, len2 = arr2.length - 1, index = -1;
        que.add(new Node(len1, len2, arr1[len1] + arr2[len2]));
        while (++index < k)
        {
            Node pollNode = que.poll();
            int curIdx1 = pollNode.index1, curIdx2 = pollNode.index2;
            res[index] = pollNode.val;
            if (!set.contains(curIdx1 + "_" + (curIdx2 - 1)))
            {
                set.add(curIdx1 + "_" + (curIdx2 - 1));
                que.add(new Node(curIdx1, curIdx2 - 1, arr1[curIdx1] + arr2[curIdx2 - 1]));
            }
            if (!set.contains((curIdx1 - 1) + "_" + curIdx2))
            {
                set.add((curIdx1 - 1) + "_" + curIdx2);
                que.add(new Node(curIdx1 - 1, curIdx2, arr1[curIdx1 - 1] + arr2[curIdx2]));
            }
        }
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        for (int i = 0; i < n; i++)
            arr1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            arr2[i] = in.nextInt();
        int[] res = solution(arr1, arr2, k);
        System.out.println(Arrays.stream(res).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CD84 出现次数的 Top k 问题

public class CD84_1
{
    public static class Node implements Comparable<Node>
    {
        public String str;
        public int times;

        public Node(String s, int t)
        {
            str = s;
            times = t;
        }

        @Override
        public int compareTo(Node o)
        {
            if (this.times != o.times)
                return o.times - this.times;
            else
                return this.str.compareTo(o.str);
        }
    }

    public static void solution(String[] arr, int topK)
    {
        HashMap<String, Integer> map = new HashMap<>();
        PriorityQueue<Node> que = new PriorityQueue<>();
        for (String word : arr)
        {
            if (!map.containsKey(word))
                map.put(word, 1);
            else
                map.put(word, map.get(word) + 1);
        }
        for (String word : map.keySet())
            que.add(new Node(word, map.get(word)));
        while (topK-- > 0)
        {
            Node pollNode = que.poll();
            System.out.println(pollNode.str + " " + pollNode.times);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        in.nextLine();
        String[] arr = new String[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextLine();
        solution(arr, k);
    }
}

CD85 Manacher 算法✍

CD86 Manacher 算法（进阶）✍

CD87 KMP 算法✍

CD88 丢棋子问题✍

CD89 画匠问题✍

CD90 邮局选址问题✍