806 Number of Lines To Write String 寫字符串需要的行數(shù)
Description:
We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of 'a', widths[1] is the width of 'b', ..., and widths[25] is the width of 'z'.
Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.
Example:
Example1 :
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:
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.
Example2 :
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:
All letters except 'a' have the same length of 10, and
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.
Note:
The length of S will be in the range [1, 1000].
S will only contain lowercase letters.
widths is an array of length 26.
widths[i] will be in the range of [2, 10].
題目描述:
我們要把給定的字符串 S 從左到右寫到每一行上统扳，每一行的最大寬度為100個單位，如果我們在寫某個字母的時候會使這行超過了100 個單位畅姊，那么我們應(yīng)該把這個字母寫到下一行咒钟。我們給定了一個數(shù)組 widths 若未，這個數(shù)組 widths[0] 代表 'a' 需要的單位朱嘴， widths[1] 代表 'b' 需要的單位粗合，...萍嬉， widths[25] 代表 'z' 需要的單位舌劳。
現(xiàn)在回答兩個問題：至少多少行能放下S帚湘，以及最后一行使用的寬度是多少個單位甚淡？將你的答案作為長度為2的整數(shù)列表返回。
示例 :
示例 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的數(shù)組腾誉。
widths[i] 值的范圍在 [2, 10]。
思路:
遍歷字符串, 每次加到超過 100就重置
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
vector<int> numberOfLines(vector<int>& widths, string S)
{
int sum = 0, result = 0;
for (char c : S)
{
sum += widths[c - 'a'];
if (sum > 100)
{
sum = widths[c - 'a'];
result++;
}
}
return {++result, sum};
}
};
Java:
class Solution {
public int[] numberOfLines(int[] widths, String S) {
int sum = 0, result = 0;
for (char c : S.toCharArray()) {
sum += widths[c - 'a'];
if (sum > 100) {
sum = widths[c - 'a'];
result++;
}
}
return new int[]{++result, sum};
}
}
Python:
class Solution:
def numberOfLines(self, widths: List[int], S: str) -> List[int]:
_sum, result, base = 0, 0, ord('a')
for s in S:
_sum += widths[ord(s) - base]
if _sum > 100:
_sum = widths[ord(s) - base]
result += 1
return [result + 1, _sum]
