Java&C++题解与拓展——leetcode806.写字符串需要的行数【么的新知识】

每日一题做题记录，参考官方和三叶的题解

文章目录

• 题目要求
• 思路：模拟
• • Java
  • Java+1
  • C++
  • Python
  • • 函数ord()
• 总结

题目要求

思路：模拟

简单题……就模拟呗……

定义 r o w row row为当前所在的行，定义 c u r cur cur表示当前行字符串末端位置。

用Unicode取每个字符的宽度 w w w，然后——

• w + c u r < = 100 w+cur <= 100 w+cur<=100，则该字符可以放在当前行；
• w + c u r > 100 w+cur > 100 w+cur>100，该字符越界，需要放到下一行， r o w row row自增， c u r cur cur重新计数为当前字符长度。
  

  
  

Java

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

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)，因为用了toCharArray

Java+1

给空间复杂度降到 O ( 1 ) O(1) O(1)，也就是把toCharArray换成charAt

class Solution {
    public int[] numberOfLines(int[] widths, String s) {
        int row = 0, cur = 0;
        for(int i = 0; i < s.length(); i++) {
            int w = widths[s.charAt(i) - 'a'];
            if(cur + w > 100 && ++row >= 0)
                cur = w;
            else
                cur += w;
        }
        if(cur != 0)
            row++;
        return new int[]{row, cur};
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

C++

class Solution {
public:
    vector<int> numberOfLines(vector<int>& widths, string s) {
        int row = 0, cur = 0;
        for(int i = 0; i < s.length(); i++) {
            int w = widths[s[i] - 'a'];
            if(cur + w > 100 && ++row >= 0)
                cur = w;
            else
                cur += w;
        }
        if(cur != 0)
            row++;
        return {row, cur};
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

Python

python没有自增，所以不能偷懒搞恒等式来简化代码，乖乖加一吧。

class Solution:
    def numberOfLines(self, widths: List[int], s: str) -> List[int]:
        row, cur = 0, 0
        for c in s:
            w = widths[ord(c) - ord('a')]
            if cur + w > 100:
                cur = w
                row += 1
            else:
                cur += w
        if(cur != 0):
            row += 1
        return [row, cur]

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

函数ord()

• 学习参考链接
• 返回字符的ASCII数值或Unicode数值，仅可传入字符作为参数，返回值为十进制整数。
  

  
  

总结

……模拟就没啥好说的，顺着思路走就完了……实在没啥好分析的

【属于是嫌简单题简单嫌困难题麻烦】

欢迎指正与讨论！