复盘|第73场双周赛
数组中紧跟 key 之后出现最频繁的数字
【哈希表】遍历数组中的nums[i] = key,找到nums[i + 1] = target就在哈希表里加一。
将杂乱无章的数字排序
【自定义排序】线转换为数位列表,然后根据给定映射规则进行映射
【调库】需要将原数字进行映射,Python maketrans() 方法用于创建字符映射的转换表。自定义比较函数,(num2map, idx),从到大排序,python稳定排序,排序后相同元素的相对位置和原来相同。
有向无环图中一个节点的所有祖先
【拓扑排序】通过拓扑排序的顺序遍历每个节点并计算祖先节点集合,如果所有父节点的祖先节点集合都已计算完成,直接堆这些集合加上父节点本身取并集。代码中,anc存每个节点的祖先节点集合,e邻接表存出边,indeg存入度,用BFS求解拓扑排序。
得到回文串的最少操作次数
【贪心】每次固定字符串最左边的字母 a不变,找出距离字符串右侧最近的 a,把它交换到字符串最右边。这样字符串的头尾字母就相等了。把字符串的头尾去掉,就变成了子问题。把所有子问题的答案加起来就是最少交换次数。