leetcode 第 322 场算法比赛

零、背景

之前提到，我拉了一个算法群，用于分享 leetcode 每日一题的题解以及算法咨询讨论。
对算法感兴趣的朋友可以关注公众号，在对话框里回复 “算法群” 获得进群方法。

最近七天（11-27~12-03) 4 道题涉及到经典算法或者比较有意思。

2022-11-28 第 813 题，经典的动态规划，拆分子数组，求某种最值。
2022-11-30 第 895 题，设计最大频率栈，按频率最高的出栈，很有意思。
2022-12-02 第 1769 题，所有位置的最优值，经典算法，算出上一个位置答案，可以快速算出下个位置答案。
2022-12-03 第 1796 题，求第 K 大数字，使用一个固定大小的堆即可。

PS：这次比赛第四题有点意思。

一、回环句

题意：给一个句子，问相邻单词中，前一个单词尾字母与后一个单词首字母是否相等。

思路：单词由一个空格分隔，找到所有分隔，判断前后的字符是否相等即可。

注意事项：句子收尾字母可以单独判断。

二、划分技能点相等的团

题意：给一个大小为 2*n 的数组，问是否可以分 n 组，所有组的和都相等。
如果可以，所有组内成员乘积后的累计和。

思路：分组和是固定的，综合除以 n 就可以计算出来。
如果不能整除，直接没答案。

分组和确定后，每个元素和哪个另外的元素匹配也就确定了。
所以，如果可以分组，则答案是固定的。

map 统计所有元素，遍历 map, 每次在统计信息中去掉一组成员。
如果最终可以全部分组，则计算出答案。

三、两个城市间路径的最小分数

题意：给一个图，不保证是不是连通图，问固定两个节点之间形成的路径中最小权重边。
要求：路径允许有重复边。

思路：题目保证两个节点直接有通路，且允许有重复边，则路径可以遍历整个连通图，答案就是连通图的最小边。

PS：一开始看错题了，看成求最短路。
看数据范围是 10^5，就写了一个 Dijkstra，浪费不少时间。

四、将节点分成尽可能多的组

题意：给一个图，可能非连通。
问是否可以将图中顶点分为 m 个有编号的组，使得所有边对应顶点的分组编号相差为1.

思路：分析可以发现，如果有答案，具有下面几个特征。

特征1：如果存在环，环的大小肯定是偶数，根据平行四边形法则，平行四边形可以压缩为一个直线。

特征2：连通图第一个分组一定可以只有一个顶点。
如果有多个顶点，任意选择一个，其他的对称的方式反转到下一层即可。

辅助：想象节点有重量但无体积，拉起第一个分组的顶点，其他的就会像串珠子一样，压缩为一个直线。

特征3：选择任意一个顶点为第一组的顶点，都可以正常分组，只是答案不一定最优。

根据上面的三个特征，解决方案也就出来了：枚举第一分组的顶点。
第一组的顶点确定了，下一组的顶点也就确定了，由此可以计算出是否有答案，以及答案是多少。

是否有答案：假设当前分组为 x 分组，x 分组中所有顶点的边集合里，另一个顶点要么已经分配分组是 x-1，要么是新分配分组 x+1。
其他情况都是没有答案。

注意事项：非连通图也允许存在答案，比如两个孤立顶点，任意分组都满足题意。

PS：看错题了，认为非连通图必然不存在答案，后来又修改代码求连通分支，浪费不少调试时间。

五、最后

这次比赛题目最后一题有点难想，你哪道题卡住了吗？卡在哪里了？

加油，算法人。

《完》

-EOF-

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