Menu Sidebar
Menu

February 2021

Map of Highest Peak

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

Kirchhoff’s theorem

这个算法又叫matrix tree theorem. 是一种计算一个无向图上生成树的个数的矩阵运算方法. 给一个图G, 这个图可连续也可不连续, 啥样子都可以. 设G的拉普拉斯矩阵(又名: 调和矩阵)为Q. 则我们可以通过计算Q11(删除第一行和第一列)的行列式, 得知G的生成树个数.

Minimum Limit of Balls in a Bag

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

Older Posts

书脊

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