leetcode-806-Number of Lines To Write String
题目描述:
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 :
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.
Example :
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 length26
.widths[i]
will be in the range of[2, 10]
.
要完成的函数:
vector<int> numberOfLines(vector<int>& widths, string S)
说明:
1、这道题给定一个由字母组成的字符串和一个vector,vector长度为26,写着26个英文字母的宽度。要求把string中的字母写出来,按照vector中的长度写出来。
每一行最多只能有100个宽度,如果最后装不下了,那么就要写到第二行。
比如已经有了98个宽度了,现在要再写一个'a',‘a’的宽度为4,那么这时就必须写到第二行,第一行剩下两个宽度,第二行拥有四个宽度。
要求写出string中的所有字母,返回一共有多少行,和最后一行的宽度。
2、题意清晰,这道题也就变得异常容易了。
代码如下:
vector<int> numberOfLines(vector<int>& widths, string S)
{
int s1=S.size(),sum=0,row=0;//sum记录每一行的宽度,row记录行数
for(int i=0;i<s1;i++)
{
sum+=widths[S[i]-'a'];
if(sum>100)
{
sum=widths[S[i]-'a'];//初始化下一行的宽度
row++;
}
}
return {row+1,sum};
}
实测2ms,beats 100% of cpp submissions。
最新文章
- EF上下文对象线程内唯一性与优化
- HTML5实战与剖析之触摸事件(touchstart、touchmove和touchend)(转)
- LaTex学习笔记——LaTeX公式换行
- xss实例-什么都没过滤的情况
- 安装Python+Pywin32(version 3.3)
- 基于jQuery的TreeGrid组件详解
- 【Java】理解 UDDI 注册中心的 WSDL
- paip.输入法编程---带ord gudin去重复-
- 转载 50种方法优化SQL Server数据库查询
- NSIndexPath的初始化方法
- Hadoop完全分布式搭建过程中遇到的问题小结
- Spark学习之键值对操作总结
- 详解散列hashCode在HashMap中的使用原理
- 12 Linux Which Command, Whatis Command, Whereis Command Examples
- 关于EL表达式随笔记录
- Mycat读写分离、主从切换、分库分表的操作记录
- hello1 web项目中web.xml作用分析
- 安装SourceTree遇到的一个个坑
- Cocos2d-X中的动作特效
- Bzoj3105:[CQOI2013]新Nim游戏
热门文章
- Weblogic10.3.6部署解决CXF webService 调用报错: “Cannot create a secure XMLInputFactory”
- rtx 二次开发,查找所有部门
- PHP中PSR
- spring.net 继承
- Selenium运用-漫画批量下载
- mysql:unknown variable &#39;default -collation=utf8_general_ci&#39;
- kalilinux系统设置
- oracle问题:新建了一个PDM文件,建表后生成的sql语句中含有clustered
- 在java中对数据库进行增删改查
- 深入理解java虚拟机(四)垃圾收集算法及HotSpot实现