大厂算法与数据结构刷题(二)

题目1

给定数组hard和money,长度都为N 数组hard[i]表示i号工作的的难度，money[i]表示i号工作的收入

给定数组ability,长度都为M, ability[j]表示j号人的能力

每一号工作，都可以提供无数的岗位，难度和收入都一样. 但是人的能力必须>=这份工作的难度，才能上班

返回一个长度为M的数组ans，ans[j]表示j号人能获得的最好收入

思路：贪心

image-20210607084320556

第一步：先根据难度从小到大排序，难度相同，工资从大到小排序

image-20210607084702559 image-20210607084908330

贪心删选难度增大，收入没有提高的工作

image-20210607085334254

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;

public class Code01_ChooseWork {

    public static class Job {
        public int money;
        public int hard;

        public Job(int m, int h) {
            money = m;
            hard = h;
        }
    }

    public static class JobComparator implements Comparator<Job> {
        @Override
        public int compare(Job o1, Job o2) {
            return o1.hard != o2.hard ? (o1.hard - o2.hard) : (o2.money - o1.money);
        }
    }

    public static int[] getMoneys(Job[] job, int[] ability) {
        Arrays.sort(job, new JobComparator());
        // key : 难度   value：报酬
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(job[0].hard, job[0].money);
        // pre : 上一份进入map的工作
        Job pre = job[0];
        for (int i = 1; i < job.length; i++) {
            if (job[i].hard != pre.hard && job[i].money > pre.money) {
                pre = job[i];
                map.put(pre.hard, pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            // ability[i] 当前人的能力 <= ability[i]  且离它最近的
            Integer key = map.floorKey(ability[i]);
            ans[i] = key != null ? map.get(key) : 0;
        }
        return ans;
    }

}

---

题目2

给定一个数组arr，只能对arr中的一个子数组排序,但是想让arr整体都有序

返回满足这一设定的子数组中，最短的是多长。

image-20210610212851281 image-20210610213319044 image-20210610213339842 image-20210610213518181 image-20210610213641840

public class MinLengthForSort {

   public static int getMinLength(int[] arr) {
      if (arr == null || arr.length < 2) {
         return 0;
      }
      int min = arr[arr.length - 1];
      int noMinIndex = -1;
      for (int i = arr.length - 2; i != -1; i--) {//从右往左遍历，找到当前index位置，从右往左的最小值，比最小值大的， noMinIndex = i;
         if (arr[i] > min) {
            noMinIndex = i;
         } else {
            min = Math.min(min, arr[i]);
         }
      }
      if (noMinIndex == -1) {
         return 0;
      }
      int max = arr[0];
      int noMaxIndex = -1;
      for (int i = 1; i != arr.length; i++) {//从左往右遍历，找到左边部分的最大值，小于最大值， noMaxIndex = i;
         if (arr[i] < max) {
            noMaxIndex = i;
         } else {
            max = Math.max(max, arr[i]);
         }
      }
      return noMaxIndex - noMinIndex + 1;
   }

   public static void main(String[] args) {
      int[] arr = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };
      System.out.println(getMinLength(arr));

   }

}

题目3

已知一个消息流会不断地吐出整数1~N, 但不一定按照顺序依次吐出

如果上次打印的序号为i，那么当i+1出现时 请打印i+1及其之后接收过的并且连续的所有数直到1~N全部接收并打印完

请设计这种接收并打印的结构.

public class Code03_ReceiveAndPrintOrderLine {

   public static class Node {
      public String info;
      public Node next;

      public Node(String str) {
         info = str;
      }
   }

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

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

      // 消息的编号，info消息的内容, 消息一定从1开始
      public void receive(int num, String info) {
         if (num < 1) {
            return;
         }
         Node cur = new Node(info);
         // num~num
         headMap.put(num, cur);
         tailMap.put(num, cur);
         // 建立了num~num这个连续区间的头和尾
         // 查询有没有某个连续区间以num-1结尾
         if (tailMap.containsKey(num - 1)) {
            tailMap.get(num - 1).next = cur;
            tailMap.remove(num - 1);
            headMap.remove(num);
         }
         // 查询有没有某个连续区间以num+1开头的
         if (headMap.containsKey(num + 1)) {
            cur.next = headMap.get(num + 1);
            tailMap.remove(num);
            headMap.remove(num + 1);
         }
         if (num == waitPoint) {
            print();
         }
      }

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

   }

   public static void main(String[] args) {
      // MessageBox only receive 1~N
      MessageBox box = new MessageBox();
      // 1....
      box.receive(2,"B"); // - 2"
      box.receive(1,"A"); // 1 2 -> print, trigger is 1
      box.receive(4,"D"); // - 4
      box.receive(5,"E"); // - 4 5
      box.receive(7,"G"); // - 4 5 - 7
      box.receive(8,"H"); // - 4 5 - 7 8
      box.receive(6,"F"); // - 4 5 6 7 8
      box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3
      box.receive(9,"I"); // 9 -> print, trigger is 9
      box.receive(10,"J"); // 10 -> print, trigger is 10
      box.receive(12,"L"); // - 12
      box.receive(13,"M"); // - 12 13
      box.receive(11,"K"); // 11 12 13 -> print, trigger is 11

   }
}