806. 写字符串需要的行数 : 简单模拟题

简介: 806. 写字符串需要的行数 : 简单模拟题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 806. 写字符串需要的行数 ,难度为 简单


Tag : 「模拟」


我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为 100100 个单位,如果我们在写某个字母的时候会使这行超过了 100100 个单位,那么我们应该把这个字母写到下一行。


我们给定了一个数组 widths,这个数组 widths[0]widths[0] 代表 'a' 需要的单位, widths[1]widths[1] 代表 'b' 需要的单位,..., widths[25]widths[25] 代表 'z' 需要的单位。


现在回答两个问题:至少多少行能放下 S,以及最后一行使用的宽度是多少个单位?

将你的答案作为长度为 22 的整数列表返回。


示例 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][1,1000] 的范围。
  • S 只包含小写字母。
  • widths 是长度为 2626 的数组。
  • widths[i]widths[i] 值的范围在 [2, 10][2,10]


模拟



根据题意进行模拟即可。


使用变量 a 代指当前有多少行是满的,使用变量 b 代指当前填充光标所在的位置。


代码:


class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int a = 0, b = 0;
        for (char c : s.toCharArray()) {
            int t = widths[c - 'a'];
            if (b + t > 100 && ++a >= 0) b = t;
            else b += t;         
        }
        if (b != 0) a++;
        return new int[]{a, b};
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:不使用 toCharArrayO(1)O(1),否则为 O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.804 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
6月前
根据用户输入的行数,打印出相应行数的直角三角形
根据用户输入的行数,打印出相应行数的直角三角形
37 1
|
6月前
|
Java
java字符串练习题4、统计一行字符串中所有的字符类型数量
java字符串练习题4、统计一行字符串中所有的字符类型数量
62 0
|
6月前
|
存储 Python
判断一个字符串中出现次数最多的字符,统计这个次数?
判断一个字符串中出现次数最多的字符,统计这个次数?
69 0
|
12月前
|
Python
foreach、for in 和for of的区别?判断一个字符串中出现次数最多的字符,统计这个次数?
foreach、for in 和for of的区别?判断一个字符串中出现次数最多的字符,统计这个次数?
48 0
|
JavaScript 前端开发
判断一个字符串中出现次数最多的字符,统计这个次数
判断一个字符串中出现次数最多的字符,统计这个次数
72 0
判断一个字符串中出现次数最多的字符 统计这个次数
判断一个字符串中出现次数最多的字符 统计这个次数
|
机器学习/深度学习 Cloud Native 安全
1790. 仅执行一次字符串交换能否使两个字符串相等:简单模拟
这是 力扣上的 1790. 仅执行一次字符串交换能否使两个字符串相等 ,难度为 简单。
实现任意行数的杨辉三角
实现任意行数的杨辉三角
55 0
实现任意行数的杨辉三角
1312. 让字符串成为回文串的最少插入次数
1312. 让字符串成为回文串的最少插入次数
1312. 让字符串成为回文串的最少插入次数
806. 写字符串需要的行数
806. 写字符串需要的行数
106 0