跳至主要內容

806. 写字符串需要的行数

806. 写字符串需要的行数

🟢   🔖  数组 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a string s of lowercase English letters and an array widths denoting how many pixels wide each lowercase English letter is. Specifically, widths[0] is the width of 'a', widths[1] is the width of 'b', and so on.

You are trying to write s across several lines, where each line is no longer than100pixels. Starting at the beginning of s, write as many letters on the first line such that the total width does not exceed 100 pixels. Then, from where you stopped in s, continue writing as many letters as you can on the second line. Continue this process until you have written all of s.

Return an arrayresult of length 2 where:

  • result[0]is the total number of lines.
  • result[1]is the width of the last line in pixels.

Example 1:

Input: 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"

Output: [3,60]

Explanation: You can write s as follows:

abcdefghij // 100 pixels wide
klmnopqrst // 100 pixels wide
uvwxyz // 60 pixels wide

There are a total of 3 lines, and the last line is 60 pixels wide.

Example 2:

Input: 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"

Output: [2,4]

Explanation: You can write s as follows:

bbbcccdddaa // 98 pixels wide
a // 4 pixels wide

There are a total of 2 lines, and the last line is 4 pixels wide.

Constraints:

  • widths.length == 26
  • 2 <= widths[i] <= 10
  • 1 <= s.length <= 1000
  • s contains only lowercase English letters.

题目大意

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为 100 个单位，如果我们在写某个字母的时候会使这行超过了 100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为 2 的整数列表返回。

示例 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"

输出: [3, 60]

解释: 所有的字符拥有相同的占用单位 10。所以书写所有的 26 个字母，

我们需要 2 个整行和占用 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"

输出: [2, 4]

解释: 除去字母'a'所有的字符都是相同的单位 10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.

最后一个字母 'a' 将会被写到第二行，因为第一行只剩下 2 个单位了。

所以，这个答案是 2 行，第二行有 4 个单位宽度。

注:

  • 字符串 S 的长度在 [1, 1000] 的范围。
  • S 只包含小写字母。
  • widths 是长度为 26的数组。
  • widths[i] 值的范围在 [2, 10]。

解题思路

  1. 初始化变量：

    • lineWidth：用来记录当前行已使用的宽度。
    • lines：记录行数。

  2. 遍历字符串 S：

    • 对于字符串中的每个字符 c，我们需要找到它对应的宽度 widths[c - 'a']，然后检查当前行剩余的空间。
    • 如果当前行能容纳该字符，则将该字符加入当前行并更新 lineWidth。
    • 如果当前行不能容纳该字符，则换行，增加 lines 并将该字符放入下一行。

  3. 最后的行宽：

    • 最后返回的结果中，第二个值应该是最后一行的宽度（即 lineWidth）。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 S 的长度。只需要遍历一次字符串，对于每个字符进行常数时间的计算。
  • 空间复杂度：O(1)，只使用了常数空间。

代码

/**
 * @param {string} S
 * @param {number[]} widths
 * @return {number[]}
 */
var numberOfLines = function (S, widths) {
	let lines = 1; // 至少有一行
	let lineWidth = 0; // 当前行的宽度

	for (let i = 0; i < S.length; i++) {
		let width = widths[S.charCodeAt(i) - 'a'.charCodeAt(0)];

		if (lineWidth + width <= 100) {
			// 当前行可以容纳这个字母
			lineWidth += width;
		} else {
			// 当前行不能容纳，换行
			lines++;
			lineWidth = width; // 新行开始，当前字母占用当前行的宽度
		}
	}

	return [lines, lineWidth];
};
Copyright © 2024 2xiao