LeetCode(微博搜索)-20240225-1

本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
LCA。前几天写过类似的。直接借助题目所给函数进行dfs，记返回值为是否找到p和q的公共祖先。有两种情况，没找到的话继续递归寻找，找到的话返回已经找到的公共祖先节点。递归终点是搜索到空节点(对应没找到返回NULL)，找到p或者q(对应找到返回相应根节点)。一般节点同理，子树返回值中不存在NULL，说明当前节点为最小公共祖先；两个都为NULL说明没找到；有一个为NULL，说明已经找到了最小公共祖先，继续向上返回结果。
国际站每日一题今日思路：
并查集问题。将每个数看成一个节点，每个数向其所有质因子引一条边，同时合并集合。若每个数对可以完成转化，说明所有数处在同一并查集中。质因子的计算可以使用埃氏筛预处理，并查集创建时可以将数组元素映射到前n位，后续的mx(mx为数组中最大元素)位于n位之后。最后判断前n位是否位于同一集合。
#每日一题# #LeetCode# #每天59秒拿下每日一题# 本条微博地址 檀多多的小玖儿
每周六晚上发疯时间到 为什么要那么难 一次比一次难 leetcode对我们这种半路出家的越来越不友好了