leetcode 第 341 场算法比赛

零、背景

这次比赛比较简单，拼手速的时候到了。

一、一最多的行

题意：给一个矩阵，问矩阵的哪一行之和最大，有多个时输出第一个。

思路：循环计算，比大小即可。

小技巧：accumulate函数可以快速计算一行的和。

二、找出可整除性得分最大的整数

题意：给一批分母和分子，问分母和分子组合里面，能被分母整除最多的分子的值，如果有多个，输出最小的分子。

思路：数据范围不大，两层循环判断、比较。

三、构造有效字符串的最少插入数

题意：给一个只包含abc 三个字符的字符串，问至少多少个字符，才能使得字符串保持为(abc)+的格式。

思路：贪心。

上一个字母是固定的，当前字母是固定的，中间插入的最少字母也是固定的。

组合分 9 中情况。

1) 3 种前后字母相同，aa，bb，cc，需要插入两个字符。
2) 前后字母正序相邻，ab，bc，ca，不需要插入字符。
3) 其他情况，ac，ba，cb，需要插入一个字符。

按照这个规则循环计算答案即可。

小技巧：可以把 9 中规则做成 map 映射表，循环相加即可。

四、最小化旅行的价格总和

题意：给一个树代表城市之间到道路，给若干路径代表城市之间的旅行计划，每个城市有过路费。
问现在可以对一批不相邻的节点集合的过路费打5折，问怎么选择这个集合，才能使得旅行的总过路费最小。

思路：典型的树形DP，之前分享无数次了。

不过这道题需要先进行数据建模，即将原始问题转化为树形DP问题。

不打折的情况下，旅行的过路费是固定的，即所有旅行的过路费的和。

问题稍微转化一下，答案就变成了所有城市收取的过路费之和。
即旅行次数问题，转化为城市收费次数问题。

第一步可以通过求所有的 LCA，预处理所有旅行，计算出每个城市被经过的次数。

第二步即可使用树形DP来做这道题了。

对于每个节点子树，可以计算当前打折与不打折两种情况的最小费用。
对于一个父节点，选择了，子节点就不能选择；没选择，则子节点任意选择，最终取最小费用。

五、最后

思考题1：第二题原题分子和分母的数据范围是 1000，修改为 10万该如何做呢？
思考题2：第三题是求一个字符串的串联，如果修改为可选的 n 个字符串的串联，怎么做呢？

《完》

-EOF-

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