温度转换

【模拟】按题意模拟。

最小公倍数为 K 的子数组数目

【暴力枚举】数据范围小，n^2枚举（加上求lcm的logk，一共n^2 + nlogk），固定起点，枚举终点，增量式求lcm，如lcm(a,b,c) = lcm(lcm(a, b), c)。因为lcm越算越大，所以如果LCM > k（或k % LCM > 0）直接break。

还可以优化下，用LCM 的性质。

逐层排序二叉树所需的最少操作数目

【BFS + 置换环 + 离散化】置换环，环与环之间交换会使得环变大，所以只要环内交换就行了（拆环图，最终拆成n个自环）。找环——从第一个数开始，把这个数字当成下标去访问，不断循环知道回到这个数本身，计算每个环内需要几次交换，对于每个环，交换次数为环大小-1（离散化是有序数组变成0~n，离散化的方式除了二分还可以map）

此题也可以用并查集。

不重叠回文子字符串的最大数目

【DP】枚举每个可能的回文中心，用两个指针分别向左右两边扩展，当两个指针指向元素相同就拓展，否则停止拓展。回文长度为奇数，回文中心是一个字符，偶数是两个字符，但可以用一个循环搞定。长度为n的字符串会生成2n-1组回文中心[l_i, r_i]。 l_i = ⌊i/2⌋，r_i = l_i + (i mod 2)，从0~2n - 2遍历i，就能得到所有可能的回文中心，统一了奇偶两种情况。

此题也可以用马拉车，空间O(n)但时间会快。