专栏首页Michael阿明学习之路LeetCode 806. 写字符串需要的行数

LeetCode 806. 写字符串需要的行数

1. 题目

我们要把给定的字符串 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]。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-lines-to-write-string 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string S) {
        int curwidth = 0, lines = 1;
        for(int i = 0; i < S.size(); ++i)
        {
        	if(curwidth+widths[S[i]-'a'] > 100)
    		{
    			++lines;
    			curwidth = widths[S[i]-'a'];
    		}
    		else
    			curwidth += widths[S[i]-'a'];
        }
        return {lines,curwidth};
    }
};

4 ms 8.5 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 393. UTF-8 编码验证(位运算)

    Michael阿明
  • LeetCode 788. 旋转数字

    我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后,我们仍可以得到一个有效的,且和 X 不同的数。要求每位数字都要被旋转。

    Michael阿明
  • LeetCode 第 20 场双周赛(294 / 1541,前19.07%,第1次全部通过)

    全国排名:294/1541,前19.07%;全球排名:885/4347,前20.4%

    Michael阿明
  • 互联网行业法律动态报告(2014年10月)

    互联网行业法律动态报告(2014年10月) 腾讯互联网与社会研究院法律研究中心 重点摘要: 2014年10月,网络治理、知识产权、竞争规则、电子商...

    腾讯研究院
  • Leetcode-Easy 806. Number of Lines To Write String

    给一个字符串S,从左到右将它们排列行,每行最大长度为100,,同时给定一个数组withds,widths[0]对应着 a的宽度, widths[1]对应着b的宽...

    致Great
  • 不同时间复杂度的规模上限

    饶文津
  • R中的向量化运算

    1、R中的向量化运算-seq seq(1, 10, by=1) seq(1, 10, by=0.1) seq(1.9, 10, by=0.1) #注意,不...

    Erin
  • Python内置函数sorted()从入门到精通

    Python内置函数sorted()可以对列表、元组、字典、集合、字符串、range对象以及其他可迭代对象进行排序,返回排序后的列表,支持使用key参数指定排序...

    Python小屋屋主
  • 互联网法律动态报告(10月版)

    互联网法律动态报告(10月版) 腾讯互联网与社会研究院 法律研究中心 重点摘要: ●2014年10月,网络治理、知识产权、竞争规则、电子商务、互联...

    腾讯研究院
  • Python基础——切片实例

    py3study

扫码关注云+社区

领取腾讯云代金券