【算法千题案例】每日LeetCode打卡——96.写字符串需要的行数

呆呆敲代码的小Y

发布于 2021-12-27 08:29:04

3660

发布于 2021-12-27 08:29:04

文章被收录于专栏：呆呆敲代码的小Y 公众号

前言
- 原题样例：写字符串需要的行数
  - C#方法：遍历
  - Java 方法：简单遍历
- 总结

前言

算法题

每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
提示：本专栏解题编程语言一律使用 C# 和 Java 两种进行解题
要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧
今天是力扣算法题持续打卡第96天

算法题

原题样例：写字符串需要的行数

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

我们给定了一个数组 widths ，这个数组 widths[0] 代表 ‘a’ 需要的单位， widths[1] 代表 ‘b’ 需要的单位，…， widths[25] 代表 ‘z’ 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例1:

示例 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:

示例 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]。

C#方法：遍历

先遍历s，每行最后大于100重启一行

代码：

public class Solution {
    public int[] NumberOfLines(int[] widths, string s) {
         int[] res = new int[2];
            int num = 0;
            int n = 1;
            for (int i = 0; i < s.Length; i++)
            {
                if (100-num>= widths[s[i] - 'a'])
                {
                    num += widths[s[i] - 'a'];
                }
                else
                {
                    num = 0;
                    num += widths[s[i] - 'a'];
                    n++;
                }
                
            }
            res[0] = n;
            res[1] = num;
            return res;
    }
}

执行结果

通过
执行用时：128 ms，在所有 C# 提交中击败了90.00%的用户
内存消耗：39.4 MB，在所有 C# 提交中击败了70.90%的用户

Java 方法：简单遍历

思路解析 我们从左到右遍历字符串 S 中的每个字母，并用二元组 (lines, width) 实时统计当前的答案。

当遍历到一个字母 x 时，如果 width + widths[x] <= 100，那么就更新 width 并保持 lines 不变；如果 width + widths[x] > 100，那么就将 lines 的值加 1，并将 width 置为 widths[x]。

代码：

class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int lines = 1, width = 0;
        for (char c: S.toCharArray()) {
            int w = widths[c - 'a'];
            width += w;
            if (width > 100) {
                lines++;
                width = w;
            }
        }

        return new int[]{lines, width};
    }
}

执行结果

通过
执行用时：0 ms，在所有 Java  提交中击败了100.00%的用户
内存消耗：36.3 MB，在所有 Java 提交中击败了75.50%的用户

复杂度分析

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

总结

今天是力扣算法题打卡的第九十六天！
文章采用 C#和 Java 两种编程语言进行解题
一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/12/25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

java

编程算法

登录后参与评论

0 条评论

热度