这是悦乐书的第319次更新，第340篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第188题（顺位题号是806）。我们要将给定字符串S的字母从左到右写成行。每行最大宽度为100个单位，如果写一个字母会导致该行的宽度超过100个单位，则会写入下一行。给出一个数组宽度，一个数组，其中widths[0]是'a'的宽度，widths[1]是'b'的宽度，widths[25]是'z'的宽度。
现在回答两个问题：S中至少有一个字符有多少行，最后一行使用的宽度是多少？将答案作为长度为2的整数数组返回。例如：
输入：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]
说明：所有字母都有相同的长度10.要写出所有26个字母，我们需要两条完整的线和一条60个宽度的线。
输入：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]
说明：除“a”之外的所有字母都具有10的相同长度，并且“bbbcccdddaa”将涵盖9 x 10 + 2 x 4 = 98个单位。对于最后一个'a'，它写在第二行，因为第一行只剩下2个单位。所以答案是2行，第二行加4个单位。
注意：
-
S的长度将在[1,1000]的范围内。
-
S只包含小写字母。
-
widths是一个长度为26的数组。
-
widths[i]将在[2,10]的范围内。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 解题
根据题目的说明和给出的示例，如果一行上字符长度超过100，就需要换行，并且需要去判断最后一次加的那个字符，是否正好让长度变成100换行，还是超过了100，需要去判断一次。
第一步，初始化。声明两个局部变量，count为行数，初始值为1，sum为最后一行使用的宽度。
第二步，循环。将S变为字符数组，遍历字符，对每个字符在widths中的宽度进行累加，赋值给sum。如果sum大于100，说明最后加的字符使整体宽度超过了100，此时需要换行了，count加1，sum重新赋值为当前字符的宽度。
第三步，返回结果。以count、sum作为数组（长度为2）元素返回。
public int[] numberOfLines(int[] widths, String S) {
int sum = 0, count = 1;
for (char ch : S.toCharArray()) {
sum += widths[ch-'a'];
if (sum > 100) {
sum = widths[ch-'a'];
count++;
}
}
return new int[]{count, sum};
}
03 小结
算法专题目前已日更超过五个月，算法题文章188+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论