高频算法和数据结构（二）

高频算法和数据结构（二）

题目一

给定数组hard和money，长度都为N

hard[i]表示i号的难度， money[i]表示i号工作的收入

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

每一号工作，都可以提供无数的岗位，难度和收入都一样

但是人的能力必须>=这份工作的难度，才能上班

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

解题：

 先按难度进行分组，同一个组只留下报酬最高的；

再把每个组的组长进行排序，难度大的报酬反而小的去掉

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> {@Overridepublic 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 = job[i];map.put(pre.hard, );}}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 ? (key) : 0;}return ans;}

题目二

贩卖机只支持硬币支付，且收退都只支持10 ，50，100三种面额

一次购买只能出一瓶可乐，且投钱和找零都遵循优先使用大钱的原则

需要购买的可乐数量是m，

其中手头拥有的10、50、100的数量分别为a、b、c

可乐的价格是x(x是10的倍数)

请计算出需要投入硬币次数？

解题：

模拟过程，主要考coding能力。

算好历史遗留钱数 

// 要买的可乐数量，m// 100元有a张// 50元有b张// 10元有c张// 可乐单价xpublic static int putTimes(int m, int a, int b, int c, int x) {//              0    1   2int[] qian = { 100, 50, 10 };int[] zhang = { c,  b,  a };// 总共需要多少次投币int puts = 0;// 之前面值的钱还剩下多少总钱数int preQianRest = 0;// 之前面值的钱还剩下多少总张数int preQianZhang = 0;for (int i = 0; i < 3 && m != 0; i++) {// 要用之前剩下的钱、当前面值的钱，共同买第一瓶可乐// 之前的面值剩下多少钱，是preQianRest// 之前的面值剩下多少张，是preQianZhang// 之所以之前的面值会剩下来，一定是剩下的钱，一直攒不出一瓶可乐的单价// 当前的面值付出一些钱+之前剩下的钱，此时有可能凑出一瓶可乐来// 那么当前面值参与搞定第一瓶可乐，需要掏出多少张呢？就是curQianFirstBuyZhangint curQianFirstBuyZhang = (x - preQianRest + qian[i] - 1) / qian[i];if (zhang[i] >= curQianFirstBuyZhang) { // 如果之前的钱和当前面值的钱，能凑出第一瓶可乐// 凑出来了一瓶可乐也可能存在找钱的情况，giveRest(qian, zhang, i + 1, (preQianRest + qian[i] * curQianFirstBuyZhang) - x, 1);puts += curQianFirstBuyZhang + preQianZhang;zhang[i] -= curQianFirstBuyZhang;m--;} else { // 如果之前的钱和当前面值的钱，不能凑出第一瓶可乐preQianRest += qian[i] * zhang[i];preQianZhang += zhang[i];continue;}// 凑出第一瓶可乐之后，当前的面值有可能能继续买更多的可乐// 以下过程就是后续的可乐怎么用当前面值的钱来买// 用当前面值的钱，买一瓶可乐需要几张int curQianBuyOneColaZhang = (x + qian[i] - 1) / qian[i];// 用当前面值的钱，一共可以搞定几瓶可乐int curQianBuyColas = Math.min(zhang[i] / curQianBuyOneColaZhang, m);// 用当前面值的钱，每搞定一瓶可乐，收货机会吐出多少零钱int oneTimeRest = qian[i] * curQianBuyOneColaZhang - x;// 每次买一瓶可乐，吐出的找零总钱数是oneTimeRest// 一共买的可乐数是curQianBuyColas，所以把零钱去提升后面几种面值的硬币数，// 就是giveRest的含义giveRest(qian, zhang, i + 1, oneTimeRest, curQianBuyColas);// 当前面值去搞定可乐这件事，一共投了几次币puts += curQianBuyOneColaZhang * curQianBuyColas;// 还剩下多少瓶可乐需要去搞定，继续用后面的面值搞定去吧m -= curQianBuyColas;// 当前面值可能剩下若干张，要参与到后续买可乐的过程中去，// 所以要更新preQianRest和preQianZhangzhang[i] -= curQianBuyOneColaZhang * curQianBuyColas;preQianRest = qian[i] * zhang[i];preQianZhang = zhang[i];}return m == 0 ? puts : -1;}public static void giveRest(int[] qian, int[] zhang, int i, int oneTimeRest, int times) {for (; i < 3; i++) {zhang[i] += (oneTimeRest / qian[i]) * times;oneTimeRest %= qian[i];}}

题目三

已知一个消息流会不断地吐出整数 1~N，

但不一定按照顺序依次吐出

如果上次打印的序号为i， 那么当i+1出现时

请打印 i+1 及其之后接收过的并且连续的所有数

直到1~N全部接收并打印完

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

解题：

 使用两个hash表分别保存，头部位和尾部位

然后使用一个waitPoint触发打印动作

ublic 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~numheadMap.put(num, cur);tailMap.put(num, cur);// 建立了num~num这个连续区间的头和尾// 查询有没有某个连续区间以num-1结尾if (ainsKey(num - 1)) {(num - 1).next = ve(num - 1);ve(num);}// 查询有没有某个连续区间以num+1开头的if (ainsKey(num + 1)) { = (num + 1);ve(num);ve(num + 1);}if (num == waitPoint) {print();}}private void print() {Node node = (waitPoint);ve(waitPoint);while (node != null) {System.out.print(node.info + " ");node = ;waitPoint++;}ve(waitPoint-1);System.out.println();}}

题目四

 现有司机N*2人，调度中心会将所有司机平分给A、B两个区域

第 i 个司机去A可得收入为income[i][0]，

第 i 个司机去B可得收入为income[i][1]，

返回所有调度方案中能使所有司机总收入最高的方案，是多少钱

 解题：

动态规划：返回把司机，分配完，并且最终A和B区域同样多的情况下&#这些司机，整体收入最大是多少！

   //暴力递归
// income -> N * 2 的矩阵 N是偶数！// 0 [9, 13]// 1 [45,60]public static int maxMoney1(int[][] income) {if (income == null || income.length < 2 || (income.length & 1) != 0) {return 0;}int N = income.length; // 司机数量一定是偶数，所以才能平分，A N /2 B N/2int M = N >> 1; // M = N / 2 要去A区域的人return process1(income, 0, M);}// 所有的司机，往A和B区域分配！// A区域还有rest个名额!// 返回把司机，分配完，并且最终A和B区域同样多的情况下&#这些司机，整体收入最大是多少！public static int process1(int[][] income, int index, int rest) {if (index == income.length) {return 0;}// 还剩下司机！if (income.length - index == rest) {return income[index][0] + process1(income, index + 1, rest - 1);}if (rest == 0) {return income[index][1] + process1(income, index + 1, rest);}// 当前司机，可以去A，或者去Bint p1 = income[index][0] + process1(income, index + 1, rest - 1);int p2 = income[index][1] + process1(income, index + 1, rest);return Math.max(p1, p2);}

    //在暴力递归基础上，通过傻缓存法，该成严格位置依赖的动态规划版本// 严格位置依赖的动态规划版本public static int maxMoney2(int[][] income) {int N = income.length;int M = N >> 1;int[][] dp = new int[N + 1][M + 1];for (int i = N - 1; i >= 0; i--) {for (int j = 0; j <= M; j++) {if (N - i == j) {dp[i][j] = income[i][0] + dp[i + 1][j - 1];} else if (j == 0) {dp[i][j] = income[i][1] + dp[i + 1][j];} else {int p1 = income[i][0] + dp[i + 1][j - 1];int p2 = income[i][1] + dp[i + 1][j];dp[i][j] = Math.max(p1, p2);}}}return dp[0][M];}

// 这题有贪心策略 :// 假设一共有10个司机，思路是先让所有司机去A，得到一个总收益// 然后看看哪5个司机改换门庭(去B)，可以获得最大的额外收益// 这道题有贪心策略，打了我的脸public static int maxMoney3(int[][] income) {int N = income.length;int[] arr = new int[N];int sum = 0;for (int i = 0; i < N; i++) {arr[i] = income[i][1] - income[i][0];sum += income[i][0];}Arrays.sort(arr);int M = N >> 1;for (int i = N - 1; i >= M; i--) {sum += arr[i];}return sum;}

题目五

设计有setAll功能的哈希表

put、get、setAll方法，时间复杂度O(1)

 解题：

为每个存储的元素增加版本号

为setAll动作增加一个全局的版本号

取数据时判断元素版本号与setAll全局版本号的大小

public static class MyValue<V> {public V value;public long time;public MyValue(V v, long t) {value = v;time = t;}}public static class MyHashMap<K, V> {private HashMap<K, MyValue<V>> map;private long time;private MyValue<V> setAll;public MyHashMap() {map = new HashMap<>();time = 0;setAll = new MyValue<V>(null, -1);}public void put(K key, V value) {map.put(key, new MyValue<V>(value, time++));}public void setAll(V value) {setAll = new MyValue<V>(value, time++);}public V get(K key) {if (!ainsKey(key)) {return null;}if ((key).time > setAll.time) {(key).value;} else {return setAll.value;}}}

题目六

/

给定一个数组arr，只能对arr中的一个子数组排序，

但是想让arr整体都有序

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

解题：

从左往右遍历，左边最大大于当前数标记违规，最后记录最右违规位置

从右往左遍历，右边最小小于当前数的标记违规，记录最左违规位置

两个违规位置，就是答案 

public static int findUnsortedSubarray(int[] nums) {if (nums == null || nums.length < 2) {return 0;}int N = nums.length;int right = -1;int max = Integer.MIN_VALUE;for (int i = 0; i < N; i++) {if (max > nums[i]) {right = i;}max = Math.max(max, nums[i]);}int min = Integer.MAX_VALUE;int left = N;for (int i = N - 1; i >= 0; i--) {if (min < nums[i]) {left = i;}min = Math.min(min, nums[i]);}return Math.max(0, right - left + 1);}