Number of Lines To Write String

题目链接

传送门

题目大意

给定一个由小写字母a~z组成的字符串S,再给出一个widths数组,widths[0]代表字符a的宽度、widths[1]代表字符b的宽度等等。每行最宽100个单元,求将字符串S中每个字符替换成实际宽度后,所得行数和最后一行的宽度。

解题思路

用lineSum变量记录当前每行使用的宽度。
如果lineSum + 当前字符宽度 <= 100,则加入当前行;
否则移到下一行,row++,lineSum=0清空。
时间复杂度O(n)。

参考代码

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S) {
        int length = S.length();
        int lineSum = 0;
        int row = 1;
        for (int i = 0; i < length; i ++) {

            if (lineSum + widths[S[i] - 'a'] <= 100) {
                lineSum += widths[S[i] - 'a'];   
            } else {
                row ++;
                lineSum = 0;
                lineSum += widths[S[i] - 'a'];   
            }
        }

        vector<int> ret;
        ret.push_back(row);
        ret.push_back(lineSum);
        return ret;
    }
};

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图