Menu Sidebar
Menu

Leetcode

Construct the Lexicographically Largest Valid Sequence

给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组. 这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.

Minimize Hamming Distance After Swap Operations

给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数. 这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.

Average Waiting Time

给一个已经排序好的二维数组. 第一个数字表示顾客到达的时间, 第二个表示准备顾客order的时长, 求平均服务顾客的时间. 这个题就是分类讨论, 通过看例子, 知道如果前后两个人在同一时间到达, 那么后一个人的服务时间是要把给前边人准备的时间也算进去的. 然后再按照当前时间进行分类, 还是第二个例子, 能看出如果两个人不是同一时间到达, 但是两个人的准备时间不重叠, 那么只需要分别算服务时间, 如果重叠, 需要先找到上一个顾客的完成时间, 然后计算出当前顾客的服务时间, 所以还需要一个变量记录上一个顾客的完成时间.

Newer Posts
Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.