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)


相关推荐

  • SQL语句学习

    SQL语句学习*以下内容是我在学习SQL(http://www.w3school.com.cn/sql/index.asp)的时候的学习笔记*学习时使用的数据库软件是MySQL数据库可视化工具SQLyogEn

  • 前端基础:100道CSS面试题总结

    前端基础:100道CSS面试题总结前言CSS是层叠样式表(CascadingStyleSheets)的简称。CSS主要作用是美化网页、布局页面。CSS规则主要由两个主要部分构成:选择器及一条或多条声明。在前端基础面试中,CSS是不会缺席的,下面就给大家分享下CSS的常见面试题。CSS面试题:介绍一下标准的CSS的盒子模型?低版本IE的盒子模型有什么不同的?CSS选择符有哪些?::before和:after中双冒号和单冒号有什么区别?解释一下这2个伪元素的作用。伪类与伪元素的区别CSS中

  • 从cer和pfx证书文件获取公、私钥

    从cer和pfx证书文件获取公、私钥一、背景最近在对接chinapay支付接口。chinapay会为每个商户号都会提供两个证书文件(cer和pfx),对接时使用chinapay提供的工具jar包,直接读取文件路径,进行请求体的签名、验签、加密、解密。chinapay提供的jar包工具类需要两个配置文件://该文件是:对方的公钥证书,内部只有公钥信息,用于请求的加密及响应的验签verify.file=/Users/macuser/Desktop/chinaPay/368_cp_test.cer//该文件是:自己的证书,

  • 部分经典vbs代码

    部分经典vbs代码部分经典vbs代码一、上代码:vbs代码,即VBScriptSetWshShell=WScript.CreateObject(“WScript.Shell”)WshShell.AppActivate”@窗口标题”fori=1to50WScript.Sleep200WshShell.SendKeys”^v”WshShell.SendKeysiWshShell.SendKeys”%s”Next二、操作步骤:打开Q_Q聊天窗口,拉出到独立窗口;新建文档,复制代码,根据

  • 经典汉罗塔问题解决方案[通俗易懂]

    经典汉罗塔问题解决方案[通俗易懂]汉罗塔问题将a的盘子移动到c针且一次只能移动一个盘,在移动过程中必须保持大盘在下,小盘在上。1、将n-1个盘子从a移动到b盘2、将a剩下的一个盘子移动到c盘3、将b的n-1个盘子移动到c盘#include<iostream>usingnamespacestd;voidmove1(chara,charc){ cout<<a<<“–>”<<c<<endl;}voidhanoi(intn,

发表回复

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

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