Havel–Hakimi algorithm
Havel–Hakimi算法是用来测试一个用度表示的图的序列是否能成图的算法. 成图算法中这个比较常见, 但是这个算法只能判断Simple Graph 输入是一个数字序列, 里面的每个数字都是图中点的度 排序取最大的数x, 然后看剩余x的数是否全是0, 如果是, 则可构成简单图, 如果不是, x个数每个都-1, 再排序取最大数. 一直这么做. 如果不都是0, 则不能构图.
Havel–Hakimi算法是用来测试一个用度表示的图的序列是否能成图的算法. 成图算法中这个比较常见, 但是这个算法只能判断Simple Graph 输入是一个数字序列, 里面的每个数字都是图中点的度 排序取最大的数x, 然后看剩余x的数是否全是0, 如果是, 则可构成简单图, 如果不是, x个数每个都-1, 再排序取最大数. 一直这么做. 如果不都是0, 则不能构图.
给一个树和一个target node, 找早cloned里边的这个node. 这个题已知这个node一定存在, 并且唯一.
给一个2d矩阵, 和一个update, 一个getValue方法, 实现这两个方法,
给一个spare vector的类, 求dot product
给一个接口逆序打印.
给一个数组, 里边是哪里有水, 哪里是陆地, 求最大的height的地图, 满足每个格子之间最多差1. 这个题用单源bfs做, 会超时 感觉用了多源也卡的要死, 虽然过了,但是速度不是很快
给一个features数组, 和一个responses数组, 求responses出现每个feature的次数, 从大到小.
给一个数组, 问如何通过maxOperations个操作, 让数字中最大数字变得最小, 操作是把一个数分割成两个数字的和. 这个题上来肯定用优先队列来一个个找最大的数, 然后分, 但是这里有个问题是, 如何分才能在给出的maxOperations的操作下, 确保最小, 这个策略比较难定. 于是换个思路: 在maxOperations个操作下, 如果结果得到的数字中最大的数字是x, 那么x+1也可以, 所以可以用二分搜索找lower bound.
给一个数组, 里面是房子高度, 默认右侧是大海, 问那些房子能看到海. 这个题主要是问一个数后边有没有数字大于它. 直接从后往前扫即可.
给一个string, 里面是0和1, 给一个操作是移动一个1到相邻位置, cost为1, 求把所有1的位置挪到当前位置的cost. 就是两个循环算一下.