leetcode 第 083 场算法比赛

零、背景

Leetcode 以往比赛也有不少质量不错的题目。

所以准备把题解补充一下。

四道题代码地址: https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/0/083

一、较大分组的位置

题意：给一个字符串，问连续字符区间中，长度大于等于3的区间列表，按下标升序返回。

思路：扫描计算出所有连续字符的区间，大于等于3放入答案即可。

二、隐藏个人信息

题意：给一个字符串，可能是电话号码，也可能是电子邮箱地址，要求对字符串进行加密。

电子邮件地址加密规则：
1）所有大写字母转换成小写字母。
2）名字出第一个字母和最后一个字母，中间字母必须用5 个星号。

电话号码加密规则：
1）最低位10位是本地号码，其他高位是国家代码。
2）本地号码加密为 ***-***-XXXX，其中 XXXX为最后4位本地号码。
3) 如果国家代码为1位，前缀增加 +*-
4) 如果国家代码为2位，前缀增加 +**-
5) 如果国家代码为3位，前缀增加 +***-

思路：模拟题，按题意模拟即可。

三、连续整数求和

题意：给一个数字 n，问有多少个连续正整数之和等于n。

思路：枚举。

连续整数的长度不可能大于 sqrt(n)，枚举长度，计算是否有答案，有了答案加1。

推导公式如下：

a, a+1, a+2, a+(k-1)
(a + a+k-1) * k /2 = n
a = (2n/k - k + 1)/2

四、统计子串中的唯一字符

题意：给一个字符串，求所有子串的唯一字符个数之和。
唯一字符个数定义：字符串中字符只出现一次的个数。

思路：枚举。

枚举每个位置是多少个子串的唯一字符。
子串可以分为前缀和后缀，显然，前缀和后缀都不能包含这个字符。
所以找到上个字符出现的位置，最长前缀就是位置向后的一位开始。
同理，找到下个字符出现的位置，最长后缀就是位置向前的一位开始。
答案为前缀的个数乘以后缀的个数。

五、最后

总结下这次比赛。
1）签到题，循环一遍即可。
2）模拟题。
3）枚举，公式题。
4）枚举，统计题。

《完》

-EOF-

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