Skip to content

Latest commit

 

History

History
239 lines (206 loc) · 9.5 KB

leetCode-68-Text-Justification.md

File metadata and controls

239 lines (206 loc) · 9.5 KB

题目描述(困难难度)

一个句子,和一个长度表示一行最长的长度,然后对齐文本,有下边几个规则。

  1. 同一个单词只能出现在一行中,不能拆分
  2. 一行如果只能放下一个单词,该单词放在最左边,然后空格补齐,例如 "acknowledgement#####",这里只是我为了直观,# 表示空格,题目并没有要求。
  3. 一行如果有多个单词,最左边和最右边不能有空格,每个单词间隙尽量平均,如果无法平均,把剩余的空隙从左边开始分配。例如,"enough###to###explain##to",3 个间隙,每个 2 个空格的话,剩下 2 个空格,从左边依次添加一个空格。
  4. 最后一行执行左对齐,单词间一个空格,末尾用空格补齐。

解法一

这道题关键就是理解题目,然后就是一些细节的把控了,我主要是下边的想法。

一行一行计算该行可以放多少个单词,然后计算单词间的空隙是多少,然后把它添加到结果中。

public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> ans = new ArrayList<>();
    //当前行单词已经占用的长度
    int currentLen = 0;
    //保存当前行的单词
    List<String> row = new ArrayList<>();
    //遍历每个单词
    for (int i = 0; i < words.length;) {
        //判断加入该单词是否超过最长长度
        //分了两种情况,一种情况是加入第一个单词,不需要多加 1
        //已经有单词的话,再加入单词,需要多加个空格,所以多加了 1
        if (currentLen == 0 && currentLen + words[i].length() <= maxWidth
            || currentLen > 0 && currentLen + 1 + words[i].length() <= maxWidth) {
            row.add(words[i]);
            if (currentLen == 0) {
                currentLen = currentLen + words[i].length();
            } else {
                currentLen = currentLen + 1 + words[i].length();
            }
            i++;
        //超过的最长长度,对 row 里边的单词进行处理
        } else {
            //计算有多少剩余,也就是总共的空格数,因为之前计算 currentLen 多算了一个空格,这里加回来
            int sub = maxWidth - currentLen + row.size() - 1;
            //如果只有一个单词,那么就直接单词加空格就可以
            if (row.size() == 1) {
                String blank = getStringBlank(sub);
                ans.add(row.get(0) + blank);
            } else {
                //用来保存当前行的结果
                StringBuilder temp = new StringBuilder();
                //将第一个单词加进来
                temp.append(row.get(0));
                //计算平均空格数
                int averageBlank = sub / (row.size() - 1);
                //如果除不尽,计算剩余空格数
                int missing = sub - averageBlank * (row.size() - 1);
                //前 missing 的空格数比平均空格数多 1
                String blank = getStringBlank(averageBlank + 1);
                int k = 1;
                for (int j = 0; j < missing; j++) {
                    temp.append(blank + row.get(k));
                    k++;
                }
                //剩下的空格数就是求得的平均空格数
                blank = getStringBlank(averageBlank);
                for (; k < row.size(); k++) {
                    temp.append(blank + row.get(k));
                }
                //将当前结果加入 
                ans.add(temp.toString());

            }
            //清空以及置零
            row = new ArrayList<>();
            currentLen = 0;

        }
    }
    //单独考虑最后一行,左对齐
    StringBuilder temp = new StringBuilder();
    temp.append(row.get(0));
    for (int i = 1; i < row.size(); i++) {
        temp.append(" " + row.get(i));
    }
    //剩余部分用空格补齐
    temp.append(getStringBlank(maxWidth - currentLen));
    //最后一行加入到结果中
    ans.add(temp.toString());
    return ans;
}
//得到 n 个空白
private String getStringBlank(int n) {
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < n; i++) {
        str.append(" ");
    }
    return str.toString();
}

时间复杂度:

空间复杂度:

但是这个算法,在 leetcode 跑,速度只打败了 30% 多的人,1 ms。然后在 discuss 里转了一圈寻求原因,发现大家思路都是这样子,然后找了一个人的跑了下,链接

public List<String> fullJustify(String[] words, int maxWidth) {
    int left = 0; List<String> result = new ArrayList<>();

    while (left < words.length) {
        int right = findRight(left, words, maxWidth);
        result.add(justify(left, right, words, maxWidth));
        left = right + 1;
    }

    return result;
}

//找到当前行最右边的单词下标
private int findRight(int left, String[] words, int maxWidth) {
    int right = left;
    int sum = words[right++].length();

    while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth)
        sum += 1 + words[right++].length();

    return right - 1;
}

//根据不同的情况添加不同的空格
private String justify(int left, int right, String[] words, int maxWidth) {
    if (right - left == 0) return padResult(words[left], maxWidth);

    boolean isLastLine = right == words.length - 1;
    int numSpaces = right - left;
    int totalSpace = maxWidth - wordsLength(left, right, words);

    String space = isLastLine ? " " : blank(totalSpace / numSpaces);
    int remainder = isLastLine ? 0 : totalSpace % numSpaces;

    StringBuilder result = new StringBuilder();
    for (int i = left; i <= right; i++)
        result.append(words[i])
        .append(space)
        .append(remainder-- > 0 ? " " : "");

    return padResult(result.toString().trim(), maxWidth);
}

//当前单词的长度
private int wordsLength(int left, int right, String[] words) {
    int wordsLength = 0;
    for (int i = left; i <= right; i++) wordsLength += words[i].length();
    return wordsLength;
}

private String padResult(String result, int maxWidth) {
    return result + blank(maxWidth - result.length());
}

private String blank(int length) {
    return new String(new char[length]).replace('\0', ' ');
}

看了下,发现思想和自己也是一样的。但是这个速度却打败了 100% ,0 ms。考虑了下,差别应该在我的算法里使用了一个叫做 row 的 list 用来保存当前行的单词,用了很多 row.get ( index ),而上边的算法只记录了 left 和 right 下标,取单词直接用的 words 数组。然后尝试着在我之前的算法上改了一下,去掉 row,用两个变量 start 和 end 保存当前行的单词范围。主要是 ( end - start ) 代替了之前的 row.size ( ), words [ start + k ] 代替了之前的 row.get ( k )。

public List<String> fullJustify2(String[] words, int maxWidth) {
    List<String> ans = new ArrayList<>();
    int currentLen = 0;
    int start = 0;
    int end = 0;
    for (int i = 0; i < words.length;) {
        //判断加入该单词是否超过最长长度
        //分了两种情况,一种情况是加入第一个单词,不需要多加 1
        //已经有单词的话,再加入单词,需要多加个空格,所以多加了 1
        if (currentLen == 0 && currentLen + words[i].length() <= maxWidth
            || currentLen > 0 && currentLen + 1 + words[i].length() <= maxWidth) {
            end++;
            if (currentLen == 0) {
                currentLen = currentLen + words[i].length();
            } else {
                currentLen = currentLen + 1 + words[i].length();
            }
            i++;
        } else {
            int sub = maxWidth - currentLen + (end - start) - 1;
            if (end - start == 1) {
                String blank = getStringBlank(sub);
                ans.add(words[start] + blank);
            } else {
                StringBuilder temp = new StringBuilder();
                temp.append(words[start]);
                int averageBlank = sub / ((end - start) - 1);
                 //如果除不尽,计算剩余空格数
                int missing = sub - averageBlank * ((end - start) - 1);
                String blank = getStringBlank(averageBlank + 1);
                int k = 1;
                for (int j = 0; j < missing; j++) {
                    temp.append(blank + words[start+k]);
                    k++;
                }
                blank = getStringBlank(averageBlank);
                for (; k <(end - start); k++) {
                    temp.append(blank + words[start+k]);
                }
                ans.add(temp.toString());

            }
            start = end;
            currentLen = 0;

        }
    }
    StringBuilder temp = new StringBuilder();
    temp.append(words[start]);
    for (int i = 1; i < (end - start); i++) {
        temp.append(" " + words[start+i]);
    }
    temp.append(getStringBlank(maxWidth - currentLen));
    ans.add(temp.toString());
    return ans;
}
//得到 n 个空白
private String getStringBlank(int n) {
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < n; i++) {
        str.append(" ");
    }
    return str.toString();
}

果然,速度也到了打败 100%,0 ms。

充分说明 list 的读取还是没有数组的直接读取快呀,还有就是要向上边的作者学习,多封装几个函数,思路会更加清晰,代码也会简明。