leetcode 第 319 场算法比赛

零、背景

上篇文章提到，我拉了一个算法群，用于分享 leetcode 每日一题的题解以及算法咨询讨论。

上周七天的每日一题，有两道题有点难度。
2022-11-10 第 864 题，是状态压缩与搜索的综合应用，理解起来稍微难一点。
2022-11-12 第 790 题，是求形状填充矩阵方案数的动态规划题，也比较经典。

对算法感兴趣的朋友可以扫描下面的群二维码，或者关注公众号，在对话框里回复 “算法群” 获得进群方法。

一、温度转换

题意：给一个摄氏温度，求分别转换为开氏温度和华氏温度。

思路：有点侮辱人。

开始以为是需要自己写四舍五入，即有精度问题，最后发现直接复制题目中的公式就行了。

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

题意：给一个数组，求所有最小公倍数为 k 的子数组个数。

思路：数据范围不大，求所有子数组的最小公倍数即可。

小技巧1：求子数组的最小公倍数时，可以复用前一个子数组的答案。
小技巧2：如果某个子数组最小公倍数大于K，则这个子数组为前缀的所有子数组都不可能是答案。

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

题意：给一个二叉树，问对每层的值进行交换排序，至少需要多少次交换才能让所有层都有序。

思路：每一层互相独立，分别转化为数组进行计算。
这样问题就转化为了，给一个数组，至少交换排序几次，才能得到有序数组。

很容易才想到，贪心每次选择最值来交换，这样最多交换 N 次即可得到有序数组。
那该怎么证明贪心的正确性呢？

仔细分析贪心交换的序列，会发现数组按照最终位置和原始位置，可以划分为几个环。

例如 3 2 1 5 6 4， 3 和 1 组成一个环，2 自身一个环， 5 6 4组成一个环。

没错，这个就是大学里离散数学里学的群论知识。
可以证明，最优答案的交换只会在环内，如果在环之间，答案只会更差。

对于环内的序列，交换次数是环的大小减一。
所以这道题的算法也就出来了。

方法1：计算出所有循环节，数组大小减去循环节个数就是答案。
复杂度：O(n)

方法2：贪心模拟交换。
暴力寻找最小值，复杂度 O(n)
map 或 堆 维护最小值，复杂度 O(n log(n))

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

题意：给一个字符串，求最多可以拆分多少个不重叠的不小于 k 的回文子字符串。

思路：典型的动态规划题。

状态定义: dp(i) 前 i 个字符的最优答案。
状态转移： dp(i)= max(dp(i-1), dp[L[i]-1] + 1);

L[i]：每个位置为结尾的满足要求的最短的回文串位置，可以预处理计算出所有回文串得到。

预处理复杂度：O(n^2)
状态转移复杂度：O(n)
综合复杂度：O(n^2)

小技巧1：枚举每个位置为中心，相两边扩散，即可预处理出所有回文串。
小技巧2：计算回文串时可以利用动态规划来加速，不过这道题没必要这样做。

五、最后

这次比赛最后两道题有点难度，不过也没那么难。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code