阿源的知识库# 大厂刷题班2
02 第二节
1. ChooseWork（贪心 有序表）
给定数组hard和money，长度都为N
hard[i]表示i号的难度，money[i]表示i号 工作的收入
给定数组ability,长度都为M，ability[j]表示j号 人的能力
每一号工作，都可以提供无数的岗位，难度和收入都一样
但是人的能力必须>=这份工作的难度，才能上班
返回一个长度为M的数组ans，ans[j]表示j号 人能获得的最好收入
根据难度排序 难度一样收入大的放前面
只需要同难度中收入最高的，然后难度的收入要按升序排列
二分去查询java
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. Cola （携程 ）
* 买饮料 时间限制： 3000MS 内存限制： 589824KB 题目描述：
* 游游今年就要毕业了，和同学们在携程上定制了日本毕业旅行。愉快的一天行程结束后大家回到了酒店房间，这时候同学们都很口渴，
* 石头剪刀布选出游游去楼下的自动贩卖机给大家买可乐。 贩卖机只支持硬币支付，且收退都只支持10 ，50，100
* 三种面额。一次购买行为只能出一瓶可乐，且每次购买后总是找零最小枚数的硬币。（例如投入100圆，可乐30圆，则找零50圆一枚，10圆两枚）
* 游游需要购买的可乐数量是 m，其中手头拥有的 10,50,100 面额硬币的枚数分别是 a,b,c，可乐的价格是x(x是10的倍数)。
* 如果游游优先使用大面额购买且钱是够的情况下,请计算出需要投入硬币次数？ 输入描述 依次输入， 需要可乐的数量为 m 10元的张数为 a 50元的张数为 b
* 100元的张树为 c 1瓶可乐的价格为 x 输出描述 输出当前金额下需要投入硬币的次数
* 例如需要购买2瓶可乐，每瓶可乐250圆，手里有100圆3枚，50圆4枚，10圆1枚。 购买第1瓶投递100圆3枚，找50圆 购买第2瓶投递50圆5枚
* 所以是总共需要操作8次金额投递操作 样例输入 2 1 4 3 250 样例输出 83.ReceiveAndPrintOrderLine（数据结构设计）
java
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();
}
}6. MinLengthForSort
// 本题测试链接 : https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
给定一个数组arr，只能对arr中的一个子数组排序,
但是想让arr整体都有序
返回满足这一设定的子数组中，最短的是多长
int[] arr = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };左边max
若左边Max > 当前数 错
若左边Max <=当前数 对
关注最后一个叉，说明后边都是对，叉后面顺序都不用动
右边Min
右边min < 当前数 错
同理,前面一部分的数是不用动的java
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--) {
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++) {
if (arr[i] < max) {
noMaxIndex = i;
} else {
max = Math.max(max, arr[i]);
}
}
return noMaxIndex - noMinIndex + 1;
}