Text Justification — LeetCode

Text Justification — LeetCode

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

原标题链接: 
http://oj.leetcode.com/problems/text-justification/
 


这道题属于纯粹的字符串操作。要把一串单词安排成多行限定长度的字符串。主要难点在于空格的安排,首先每一个单词之间必须有空格隔开。而当当前行放不下很多其它的单词而且字符又不能填满长度L时。我们要把空格均匀的填充在单词之间。假设剩余的空格量刚好是间隔倍数那么就均匀分配就可以。否则还必须把多的一个空格放到前面的间隔里面。实现中我们维护一个count计数记录当前长度。超过之后我们计算共同的空格量以及多出一个的空格量,然后将当行字符串构造出来。最后一个细节就是最后一行不须要均匀分配空格。句尾留空就能够。所以要单独处理一下。时间上我们须要扫描单词一遍,然后在找到行尾的时候在扫描一遍当前行的单词,只是整体每一个单词不会被訪问超过两遍,所以整体时间复杂度是O(n)。而空间复杂度则是结果的大小(跟单词数量和长度有关,不能准确定义,假设知道最后行数r。则是O(r*L))。代码例如以下: 

public ArrayList<String> fullJustify(String[] words, int L) {
    ArrayList<String> res = new ArrayList<String>();
    if(words==null || words.length==0)
        return res;
    int count = 0;
    int last = 0;
    for(int i=0;i<words.length;i++)
    {
        if(count+words[i].length()+(i-last)>L)
        {
            int spaceNum = 0;
            int extraNum = 0;
            if(i-last-1>0)
            {
                spaceNum = (L-count)/(i-last-1);
                extraNum = (L-count)%(i-last-1);
            }
            StringBuilder str = new StringBuilder();
            for(int j=last;j<i;j++)
            {
                str.append(words[j]);
                if(j<i-1)
                {
                    for(int k=0;k<spaceNum;k++)
                    {
                        str.append(" ");
                    }
                    if(extraNum>0)
                    {
                        str.append(" ");
                    }
                    extraNum--;
                }
            }
            for(int j=str.length();j<L;j++)
            {
                str.append(" ");
            }       
            res.add(str.toString());
            count=0;
            last=i;
        }
        count += words[i].length();
    }
    StringBuilder str = new StringBuilder();
    for(int i=last;i<words.length;i++)
    {
        str.append(words[i]);
        if(str.length()<L)
            str.append(" ");
    }
    for(int i=str.length();i<L;i++)
    {
        str.append(" ");
    }
    res.add(str.toString());
    return res;
}

这道题属于那种文本编辑的子操作之类的题目,从算法思路上没有什么特别。不过还是相当多的实现细节,别easy在第一时间,你可能想练习几次哈。

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117327.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • VUE组件封装_vue组件内部双向绑定

    VUE组件封装_vue组件内部双向绑定官方:一个组件上的v-model默认会利用名为value的prop和名为input的事件。v-model实际上只是一个语法糖:<inputv-model=”password”>作用与以下相似:<inputtype=”text”:value=”password”@input=”password=$event.target.value”>也就是通过v-model传递的值,最终是传递给了子组件props中value属性,子组件修改valu

  • matlab创建数组的方法_创建数组的三种方法

    matlab创建数组的方法_创建数组的三种方法1直接方法:       A=[1,2,3;4,5,6];2冒号方法:      B=x:inc:b;3定数线性采样法:x=linspace(-1,1,10);4中等规模数组的数组编辑器创建法:在工作空间中右键创建一个名为“unnamed”的变量,双击,在里面输入数据,修改变量名   为“ABC”,运行“save ABC ABC”。将数组AB…

  • html5 sexteen,Prosecutors: Berlusconi had sex with teen 13 times

    html5 sexteen,Prosecutors: Berlusconi had sex with teen 13 timesPremierSilvioBerlusconipaidforsexwithanunder-ageMoroccanteen13timesathisvillanearMilan,prosecutorssaidinadocumentfiledTuesdayseekingindictmentsagainstthreeaidesforallege…

  • springboot Jpa多数据源(不同库)配置

    springboot Jpa多数据源(不同库)配置一、前言springboot版本不同对多数据源配置代码有一定影响,部分方法和配置略有不同。本文采用的springboot版本为2.3.12,数据源为mysql和postgresql二、配置实战2.1基础pom<dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter</ar

    2022年10月20日
  • ZooKeeper ACL权限设置

    ZooKeeper ACL权限设置

  • L3-001 凑零钱(回溯和0-1背包)[通俗易懂]

    L3-001 凑零钱(回溯和0-1背包)[通俗易懂]韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 10​4​​ 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。输入格式:输入第一行给出两个正整数:N(≤10​4​​ )是硬币的总个数,M(≤10​2​​ )是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。输出格式:在一行中输出硬币的面值 V​1​​ ≤V​2​​ ≤⋯≤V​k

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号