806. 写字符串需要的行数

806. 写字符串需要的行数

一、题目描述

我们要把给定的字符串 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著作权归领扣网络所有。商业转载请联系官方授权 非商业转载请注明出处。

二、思路分析

这道题考察了什么思想 你的思路是什么

这道题目采用的是模拟法。
我的思路是遍历字符串 并计算各字符的权重 然后求和 放入weights中 如果判断求和后weights大于100 就把weights设为该值 然后lines加一。最后返回[lines,weights]数组。

做题的时候是不是一次通过的 遇到了什么问题 需要注意什么细节

不是一次通过的 刚开始不知道returnSize有什么用 执行代码有问题 后来给该参数赋值即可pass。

有几种解法 哪种解法时间复杂度最低 哪种解法空间复杂度最低 最优解法是什么 其他人的题解是什么 谁的效率更好一些 用不同语言实现的话 哪个语言速度最快

没有看到什么其他特别好的解法。。。。。

三、AC 代码

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* numberOfLines(int* widths, int widthsSize, char * s, int* returnSize){

   int len strlen(s);

   int weights 0;

   int lines 1;

   for(int i 0;i len;i ){

       if(weights widths[s[i]- a ] 100){

           weights widths[s[i]- a ];

           lines ;

           continue;

       }

       weights widths[s[i]- a ];

   }

   int * res (int *)malloc(sizeof(int) * 2);

   *returnSize 2;

   res[0] lines;

   res[1] weights;

   return res;

}

四、总结

基础题目一个 我这种刚入门级菜鸟都能解决 你也行

C/C++编程题之删除字符串中出现次数最少的字符 实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。