解题记录

Leetcode 857 Minimum cost to hire K workers

N个工人，每人有质量和最低工资期望两个值，先要雇佣K个工人，满足：

每个人的工资数目和质量成正比，且高于最低工资期望

想法：对于最后找出的几个工人，有等式wage[i]/wage[j] == quality[i]/quality[j]

​ 可得wage[i]/quality[i] == wage[j]/quality[j]

​ 所以一个直观的想法是把所有工人按照工资比质量排序，如果要满足条件，最后的K个人中

这个比值总是大于等于这K个人中的第一个人的值的，这样可以保证每个人拿到的工资都比自己的最低期望高。

（第一个人是工资比质量比最小的，也就是说期望工资相同的情况下质量更高，而最后的钱是按照质量之比发的所以这样可以保证所有人都能拿够钱。最后的比例是由最后一个人定的（期望工资相同的情况下质量较低））

接下来就是如何找出这样符合要求的长度为K的子序列

开始想的是使用双指针，像sliding window那样解决问题。

但其实因为原数据是排过序的，所以有一个更直接的想法：

遍历一遍所有worker，维护一个优先队列，这个优先队列按质量排序（质量越高，要给的工资越高）

对于每一个worker,记录一个sum(当前质量和)， 将当前worker的质量加入队列

（一个小技巧，取负加入队列可以直接获取当前最大值，不需要写compare）

如果当前优先队列长度大于K，则抛弃质量最高的人(队列首部) sum+= q.poll() （负数值直接加）

长度等于K，取min(res, 当前质量和乘以这个人的工资质量比)

其实看下来，这也相当于是一直在维护一个长度为K的窗口，只是不同于一般的sliding window

问题是记录这个window中某种数据的数量，这个相当于是在记录区间最大值，然后每次移动的时候更新

LeetCode 855 Extra Room

一个房间，有N个座位，编号为0到N-1。

当一个人进入时，他们要坐的尽量比别人远，如果有多个这样的位子，则选择一个编号小的。

这个问题有如下几种操作，进入房间，离开房间。

思路：记录一个list, 其中有每个人的座位编号

离开房间没什么好说的，remove完事

对于进入房间，可以分如下几种情况讨论：

没有人：坐在0

有一个人：坐在0或者9，看离哪个远

其它：将list排序，找其中两个距离最大的，然后坐在他们中间。

非常直观的题，但是交了两次都有点没过去

不太明白咋回事

后来看discussion里面有一个人他的思路是这样的。

没有人：坐在0

然后另距离等于第一个人和最后一个人的距离差（注意他没有sort)

然后也是找距离最大值

这里有一个特判，如果现在list里面第一个人的座位编号就是最大距离

那么应该把这个人放在第零位。这算是一个没想到的edge case了。

然后这个人再过一遍队列，找到第一个最大距离并将数据插入到这两个座位中间。

如果没找到该最大值（只有长度为1的时候满足)

返回最大值。

为啥没sort也可以呢？因为插入点就是从小到大找最大距离插入的，数据本身就是有序的。。

因为可能没有考虑到之前的哪个edge case所以有时候出来的结果顺序是不对的

找edge case还是需要一些方法。

比如这个题，就想，除了最开始，什么时候要加到0， 什么时候要加到最后一位。

其实0严格上来说不能算edge case, 因为相当于是队头插入，而我的遍历查找

是没有包括队头和队尾插入的情况的（找的是两个之间的距离），所以都要额外考虑。

这就是个找队列插入位置的问题（队列维护）

这样想就很自然了。

抽象问题的技巧还要多练练。

LeetCode 863 All Nodes Distance K in Binary Tree

有一颗树。我们知道一个树中的一个target节点，现在要找树中所有距离这个节点K的节点。

思路：先分一下类

• 比现在节点深K的节点，

• 深度浅K的节点

• 不在一个子树内的节点（弯曲路径）

  dfs自然是首选项

  先找到target，然后向下找距离target K的点（另写一个dfs）

  对于其它的节点，我得先知道target是否在它的左子树或右子树中

  还要知道它关于target的高度

  注意一个特判：

  如果我知道这个点在root的左子树或者右子树中，如果这个root刚好比target高K

  则找到一个解

  另外的general情况是在这个点的另一个子树中存在符合要求的节点

  （弯曲路径）

  就相当于是相对root来说距离为（K-height）的点

  所以也可用另写的dfs搜索

  所以我们的主dfs要返回什么？

  当然是相对高度

  -1 表示这个target不在左子树或右子树中

  1 表示这个节点就是target (注意这是给上一层节点返回的深度，所以自然是从1开始)

  其它情况，记录left_height和right_height, 返回其值加一

  所以有以下简易伪代码

  dfs1
  root == null || K < 0 -> return
  K == 0 add to list
  dfs1(left, K - 1), dfs1(right, K - 1)
    
  dfs list, root, target, K
  root == null || K < 0 -> return null
  root == target -> dfs1(left, K - 1), dfs1(right, K - 1), return 1
  left_height = dfs(left)
  left_height != -1 => left_height == K -> add to list
  			else -> dfs1(right, K - left_height - 1);
  return left_height + 1
    
  Same thing for right.