Menu Sidebar
Menu

Interview Question

Havel–Hakimi algorithm

Havel–Hakimi算法是用来测试一个用度表示的图的序列是否能成图的算法. 成图算法中这个比较常见, 但是这个算法只能判断Simple Graph 输入是一个数字序列, 里面的每个数字都是图中点的度 排序取最大的数x, 然后看剩余x的数是否全是0, 如果是, 则可构成简单图, 如果不是, x个数每个都-1, 再排序取最大数. 一直这么做. 如果不都是0, 则不能构图.

Map of Highest Peak

给一个数组, 里边是哪里有水, 哪里是陆地, 求最大的height的地图, 满足每个格子之间最多差1. 这个题用单源bfs做, 会超时 感觉用了多源也卡的要死, 虽然过了,但是速度不是很快

Minimum Limit of Balls in a Bag

给一个数组, 问如何通过maxOperations个操作, 让数字中最大数字变得最小, 操作是把一个数分割成两个数字的和. 这个题上来肯定用优先队列来一个个找最大的数, 然后分, 但是这里有个问题是, 如何分才能在给出的maxOperations的操作下, 确保最小, 这个策略比较难定. 于是换个思路: 在maxOperations个操作下, 如果结果得到的数字中最大的数字是x, 那么x+1也可以, 所以可以用二分搜索找lower bound.

Older Posts

书脊

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

March 2021
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031