把字符串S
中的字符从左到右写入行中。 每行最大宽度度为100,如果往后新写一个字符导致该行宽度超过100,则写入下一行。
注意:一个字符的宽度不为1!给定一个数组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个字符都写进去,需要两个整行和一个用去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行,最后一行是4长度.
注意事项
-
S
的长度范围为[1, 1000]
. -
S
仅有26个小写字母组成. -
widths
的长度为26
. -
widths[i]
的范围为[2, 10]
.
class Solution {
public:
/**
* @param widths: an array
* @param S: a string
* @return: how many lines have at least one character from S, and what is the width used by the last such line
*/
vector<int> numberOfLines(vector<int> &widths, string &S) {
// Write your code here
int ret = 0;
int line = 1;
for(int i = 0;i < S.size(); i++)
{
ret = ret + widths[S[i] - 'a'];
if(ret == 100)
{
line++;
ret = 0;
}
else if((ret > 100) && (ret - widths[S[i] - 'a']) < 100)
{
line++;
ret = widths[S[i] - 'a'];
}
}
//cout<<ret<<endl;
vector<int> ans;
ans.push_back(line);
ans.push_back(ret%100);
return ans;
}
};