文章目录
题目
标题和出处
标题：重新格式化电话号码
难度
3 级
题目描述
要求
给你一个字符串形式的电话号码 number \texttt{number} number。 number \texttt{number} number 由数字、空格 ‘ ’ \texttt{` '} ‘ ’ 和破折号 ‘-’ \texttt{`-'} ‘-’ 组成。
请你按下述方式重新格式化电话号码。首先，删除所有的空格和破折号。其次，将数字从左到右每 3 \texttt{3} 3 个一组分块，直到剩下 4 \texttt{4} 4 个或更少数字。剩下的数字将按下述规定再分块：
- 2 \texttt{2} 2 个数字：单个含 2 \texttt{2} 2 个数字的块。
- 3 \texttt{3} 3 个数字：单个含 3 \texttt{3} 3 个数字的块。
- 4 \texttt{4} 4 个数字：两个分别含 2 \texttt{2} 2 个数字的块。
最后用破折号将这些块连接起来。注意，重新格式化过程中不应该生成仅含 1 \texttt{1} 1 个数字的块，并且最多生成两个含 2 \texttt{2} 2 个数字的块。
返回格式化后的电话号码。
示例
示例 1：
输入：
number
=
"1-23-45
6"
\texttt{number = "1-23-45 6"}
number = "1-23-45 6"
输出：
"123-456"
\texttt{"123-456"}
"123-456"
解释：数字是
"123456"
\texttt{"123456"}
"123456"。
步骤
1
\texttt{1}
1：共有超过
4
\texttt{4}
4 个数字，所以先取
3
\texttt{3}
3 个数字分为一组。第
1
\texttt{1}
1 个块是
"123"
\texttt{"123"}
"123"。
步骤
2
\texttt{2}
2：剩下
3
\texttt{3}
3 个数字，将它们放入单个含
3
\texttt{3}
3 个数字的块。第
2
\texttt{2}
2 个块是
"456"
\texttt{"456"}
"456"。
连接这些块后得到
"123-456"
\texttt{"123-456"}
"123-456"。
示例 2：
输入：
number
=
"123
4-567"
\texttt{number = "123 4-567"}
number = "123 4-567"
输出：
"123-45-67"
\texttt{"123-45-67"}
"123-45-67"
解释：数字是
"1234567"
\texttt{"1234567"}
"1234567"。
步骤
1
\texttt{1}
1：共有超过
4
\texttt{4}
4 个数字，所以先取
3
\texttt{3}
3 个数字分为一组。第
1
\texttt{1}
1 个块是
"123"
\texttt{"123"}
"123"。
步骤
2
\texttt{2}
2：剩下
4
\texttt{4}
4 个数字，所以将它们分成两个含
2
\texttt{2}
2 个数字的块。这
2
\texttt{2}
2 块分别是
"45"
\texttt{"45"}
"45" 和
"67"
\texttt{"67"}
"67"。
连接这些块后得到
"123-45-67"
\texttt{"123-45-67"}
"123-45-67"。
示例 3：
输入：
number
=
"123
4-5678"
\texttt{number = "123 4-5678"}
number = "123 4-5678"
输出：
"123-456-78"
\texttt{"123-456-78"}
"123-456-78"
解释：数字是
"12345678"
\texttt{"12345678"}
"12345678"。
步骤
1
\texttt{1}
1：第
1
\texttt{1}
1 个块是
"123"
\texttt{"123"}
"123"。
步骤
2
\texttt{2}
2：第
2
\texttt{2}
2 个块是
"456"
\texttt{"456"}
"456"。
步骤
3
\texttt{3}
3：剩下
2
\texttt{2}
2 个数字，将它们放入单个含
2
\texttt{2}
2 个数字的块。第
3
\texttt{3}
3 个块是
"78"
\texttt{"78"}
"78"。
连接这些块后得到
"123-456-78"
\texttt{"123-456-78"}
"123-456-78"。
示例 4：
输入：
number
=
"12"
\texttt{number = "12"}
number = "12"
输出：
"12"
\texttt{"12"}
"12"
示例 5：
输入：
number
=
"--17-5
229
35-39475
"
\texttt{number = "--17-5 229 35-39475 "}
number = "--17-5 229 35-39475 "
输出：
"175-229-353-94-75"
\texttt{"175-229-353-94-75"}
"175-229-353-94-75"
数据范围
- 2 ≤ number.length ≤ 100 \texttt{2} \le \texttt{number.length} \le \texttt{100} 2≤number.length≤100
- number \texttt{number} number 由数字和字符 ‘-’ \texttt{`-'} ‘-’ 及 ‘ ’ \texttt{` '} ‘ ’ 组成
- number \texttt{number} number 中至少含 2 \texttt{2} 2 个数字
解法
思路和算法
由于在格式化电话号码时，只考虑电话号码中的数字，因此只需要知道电话号码中的数字有多少个，即可知道应该如何格式化。遍历原始电话号码 number \textit{number} number，统计数字的个数。
得到数字的个数之后，即可按照如下步骤生成格式化的电话号码。
-
当剩余的数字大于 4 4 4 个时，总是将数字按照每 3 3 3 个一组分块，因此遍历电话号码并生成含 3 3 3 个数字的块，得到一个含 3 3 3 个数字的块之后，则添加一个破折号。由于该操作是在剩余的数字大于 4 4 4 个时进行的，因此每次添加破折号之后，一定还有剩余的数字，即格式化的电话号码不会以破折号结尾。
-
当剩余的数字不超过 4 4 4 个时，剩余的数字可能是 4 4 4 个、 3 3 3 个或 2 2 2 个。当剩余 4 4 4 个数字时，可以生成 2 2 2 个块，当剩余 3 3 3 个或 2 2 2 个数字时，只可以生成 1 1 1 个块。因此当剩余 4 4 4 个数字时，继续遍历电话号码，再处理出一个含 2 2 2 个数字的块，然后添加一个破折号，则剩下 2 2 2 个数字。
-
当剩余的数字为 3 3 3 个或 2 2 2 个时，剩余的数字只能生成 1 1 1 个块，因此遍历电话号码的剩余部分直到结束，将剩余的数字全部添加到最后一个块即可。
如果电话号码中的数字大于 4 4 4 个，步骤 1 必定会执行，然后执行步骤 2 和步骤 3，或者只执行步骤 3。具体为，当电话号码中的数字个数除以 3 3 3 的余数为 1 1 1 时，会执行步骤 2 和步骤 3，当电话号码中的数字个数除以 3 3 3 的余数不为 1 1 1 时，只会执行步骤 3。
如果电话号码中的数字等于 4 4 4 个，则只会执行步骤 2 和步骤 3。
如果电话号码中的数字等于 3 3 3 个或 2 2 2 个，则只会执行步骤 3。
代码
class Solution {
public String reformatNumber(String number) {
final int BLOCK_SIZE = 3, SMALL_BLOCK_SIZE = 2;
int digits = 0;
int length = number.length();
for (int i = 0; i < length; i++) {
char c = number.charAt(i);
if (Character.isDigit(c)) {
digits++;
}
}
StringBuffer sb = new StringBuffer();
int index = 0;
while (digits > 4) {
int curBlockSize = BLOCK_SIZE;
while (curBlockSize > 0) {
char c = number.charAt(index);
if (Character.isDigit(c)) {
sb.append(c);
curBlockSize--;
}
index++;
}
digits -= BLOCK_SIZE;
sb.append('-');
}
if (digits == 4) {
int curBlockSize = SMALL_BLOCK_SIZE;
while (curBlockSize > 0) {
char c = number.charAt(index);
if (Character.isDigit(c)) {
sb.append(c);
curBlockSize--;
}
index++;
}
digits -= SMALL_BLOCK_SIZE;
sb.append('-');
}
while (index < length) {
char c = number.charAt(index);
if (Character.isDigit(c)) {
sb.append(c);
}
index++;
}
return sb.toString();
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 number \textit{number} number 的长度。需要遍历字符串 number \textit{number} number 两次。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 number \textit{number} number 的长度。需要额外创建一个长度为 O ( n ) O(n) O(n) 的 StringBuffer \texttt{StringBuffer} StringBuffer 或 StringBuilder \texttt{StringBuilder} StringBuilder 类型的对象用于存储格式化后的电话号码。由于 Java 中的 String \texttt{String} String 类型的对象不可变，因此空间复杂度至少为 O ( n ) O(n) O(n)。