文章目录
题目
标题和出处
标题：写字符串需要的行数
难度
3 级
题目描述
要求
给你由小写英语字母组成的字符串 s \texttt{s} s 和一个表示每个小写英语字母的宽度的像素数的数组 widths \texttt{widths} widths。特别地， widths[0] \texttt{widths[0]} widths[0] 表示 ‘a’ \texttt{`a'} ‘a’ 的宽度， widths[1] \texttt{widths[1]} widths[1] 表示 ‘b’ \texttt{`b'} ‘b’ 的宽度，以此类推。
你要将 s \texttt{s} s 写在若干行中，每一行的最大长度不超过 100 \texttt{100} 100 像素。从 s \texttt{s} s 的第一个字符开始，在第一行写尽可能多的字母使得总宽度不超过 100 \texttt{100} 100 像素。然后在第二行继续写尽可能多的 s \texttt{s} s 中的字符。该过程持续到 s \texttt{s} s 的全部字符都写完。
返回长度为 2 \texttt{2} 2 的数组 result \texttt{result} result：
- result[0] \texttt{result[0]} result[0] 是总行数；
- result[1] \texttt{result[1]} result[1] 是最后一行的宽度的像素数。
示例
示例 1：
输入：
widths
=
[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
s
=
"abcdefghijklmnopqrstuvwxyz"
\texttt{widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz"}
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz"
输出：
[3,60]
\texttt{[3,60]}
[3,60]
解释：你可以按如下方法写
s
\texttt{s}
s：
abcdefghij
//
100
像素
\texttt{abcdefghij // 100 像素}
abcdefghij // 100 像素
klmnopqrst
//
100
像素
\texttt{klmnopqrst // 100 像素}
klmnopqrst // 100 像素
uvwxyz
//
60
像素
\texttt{uvwxyz ~~~~// 60 像素}
uvwxyz // 60 像素
一共有
3
\texttt{3}
3 行，最后一行的宽度是
60
\texttt{60}
60 像素。
示例 2：
输入：
widths
=
[4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
s
=
"bbbcccdddaaa"
\texttt{widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "bbbcccdddaaa"}
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "bbbcccdddaaa"
输出：
[2,4]
\texttt{[2,4]}
[2,4]
解释：你可以按如下方法写
s
\texttt{s}
s：
bbbcccdddaa
//
98
像素
\texttt{bbbcccdddaa // 98 像素}
bbbcccdddaa // 98 像素
a
//
4
像素
\texttt{a ~~~~~~~~~~// 4 像素}
a // 4 像素
一共有
2
\texttt{2}
2 行，最后一行的宽度是
4
\texttt{4}
4 像素。
数据范围
- widths.length = 26 \texttt{widths.length} = \texttt{26} widths.length=26
- 2 ≤ widths[i] ≤ 10 \texttt{2} \le \texttt{widths[i]} \le \texttt{10} 2≤widths[i]≤10
- 1 ≤ s.length ≤ 1000 \texttt{1} \le \texttt{s.length} \le \texttt{1000} 1≤s.length≤1000
- s \texttt{s} s 只包含小写英语字母
解法
思路和算法
这道题只需要模拟写字符串的过程，并计算使用的行数和当前行的宽度即可。
由于字符串 s s s 的长度大于 0 0 0，因此至少需要 1 1 1 行。
用 linesCount \textit{linesCount} linesCount 表示行数， curWidth \textit{curWidth} curWidth 表示当前行的宽度。初始化 linesCount = 1 \textit{linesCount}=1 linesCount=1 和 curWidth = 0 \textit{curWidth} = 0 curWidth=0。
从左到右遍历字符串 s s s，对于每个字符，获得该字符的宽度 width \textit{width} width，进行如下操作：
-
如果 curWidth + width ≤ 100 \textit{curWidth} + \textit{width} \le 100 curWidth+width≤100，则该字符可以写入当前行，因此 linesCount \textit{linesCount} linesCount 的值不变，将 curWidth \textit{curWidth} curWidth 的值增加 width \textit{width} width；
-
如果 curWidth + width > 100 \textit{curWidth} + \textit{width} > 100 curWidth+width>100，则该字符不可以写入当前行，否则当前行的总宽度超过 100 100 100 像素，因此该字符必须写在新的一行，将 linesCount \textit{linesCount} linesCount 的值加 1 1 1，将 curWidth \textit{curWidth} curWidth 的值设置为 width \textit{width} width。
遍历结束之后，即有 result [ 0 ] = linesCount , result [ 1 ] = curWidth \textit{result}[0]=\textit{linesCount},\textit{result}[1]=\textit{curWidth} result[0]=linesCount,result[1]=curWidth。
上面的内容是解题过程。具体实现时，有一些细节问题需要考虑。
-
对于字符 c c c，其取值范围是 ‘a’ \text{`a'} ‘a’ 到 ‘z’ \text{`z'} ‘z’， c − ‘a’ c - \text{`a'} c−‘a’ 的取值范围是 0 0 0 到 25 25 25，和 widths \textit{widths} widths 的下标对应。因此，字符 c c c 的宽度为 widths [ c − ‘a’ ] \textit{widths}[c - \text{`a'}] widths[c−‘a’]。
-
题目中明确说明了每一行最多 100 100 100 像素，因此可以在代码中使用数字 100 100 100 表示每一行的最大宽度。更好的做法是声明常量 MAX_WIDTH \textit{MAX\_WIDTH} MAX_WIDTH，将该常量的值设为 100 100 100，然后用该常量表示每一行的最大宽度。使用常量的好处是常量名称可以体现含义，增加代码的可读性，而且更有利于程序的可扩展性。
代码
class Solution {
public int[] numberOfLines(int[] widths, String s) {
final int MAX_WIDTH = 100;
int linesCount = 1, curWidth = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int width = widths[c - 'a'];
if (curWidth + width <= MAX_WIDTH) {
curWidth += width;
} else {
linesCount++;
curWidth = width;
}
}
return new int[]{linesCount, curWidth};
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。需要遍历字符串 s s s 一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。