LeetCode(微博搜索)-20240406-1

本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
倍增思想。算法类似快速幂，若要想计算一个节点的第101(二进制)的祖先，可以通过两步得到；找到第001(二进制)的祖先置为当前节点，接着找当前节点的第100(二进制)的祖先。题目输入限制了不超过65536，即不超过2的16次方，所以初始化时最多倍增16次。每次倍增有p[i][j+1]=p[p[i][j]][j]，注意防止下标越界。搜索时类似快速幂，分解k，若k的二进制位1，进行跳跃。
国际站每日一题今日思路：
括号题。首先剔除右括号。访问到右括号时，若不存在左括号删除当前右括号；遍历完后右括号处理完毕，但是可能出现左括号未匹配的情况，再从右到左遍历剔除多余左括号；方法同上。剔除时可以标记为一个特殊字符，最后一并剔除，省去拷贝的时间。
#每日一题# #LeetCode# #每天59秒拿下每日一题#