leetcode 第 381 场算法比赛，排名45

零、背景

leetcode 是越来越聪明了，现在只出两道题，相同题目，一道数据范围小，一道数据范围大。

A+C: 贪心，出现次数最多的字母放在最前面。
B+D: 构造，分环前、环中、环后三种情况统计步长的个数，区间求和。

PS：这次比赛的时候，电脑开机失败，折腾了好久，比赛开始十几分钟才开机成功。

一、输入单词需要的最少按键次数 I

题目：以前的老式手机是物理按键，按键上有多个字母，根据字母的位置，通过按多次可以按出字母。
问如何重新排列字母，从而使得输入一个字符串按键次数最少。

思路：贪心。

统计每个字母出现的次数，显然次数越多的字母需要尽量排在最前面。

2到9共8个按键。
频次最高的8个字母分别排在第一位。
频次排名处于9到16的字母，分别排在第二位。
依次递推即可。

二、按距离统计房屋对数目 I

题目：街道上有一排房屋，相邻的房屋之间有条街道。
现在某两个房屋之间建了一个街道，某两个房屋的最少街道个数称为距离。
问距离为1~n的房屋对分别有多少个。

思路：构造体。

可以发现，某个点出发，到达非环上点的距离是连续递增的，环上的点有两条路，也是依次递增的。

只看一个直线，直线上随意一点可以分别向两端走，距离分别是 1 到尽头。
只看一个环，环上任意一点可以朝两个方向走，距离也是从1到相遇，所以环上的距离是环大小除2，奇数有一个多走一步。

这些距离可以使用区间加一的数据结构来维护，例如树状数组或者线段树。
当然，由于不需要求区间和，更简单的做法是维护一个加一减一标记。

由此，我们可以枚举每个顶点为起点，分环前、环中、环后三种情况统计，求区间分别加一即可。

三、输入单词需要的最少按键次数 II

与第一题一样。

四、按距离统计房屋对数目 II

与第二题一样。

五、最后

这次比赛只有两道题，由于比赛电脑开机失败，浪费十几分钟，不然有可能进入前10名的。

《完》

-EOF-

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