Leetcode第68题（文本左右对齐）

54 阅读 0 评论 36 点赞

我是靠谱客的博主醉熏天空，最近开发中收集的这篇文章主要介绍Leetcode第68题（文本左右对齐），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原题如下：

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例:

输入:
words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
maxWidth = 16
输出:
[
“This is an”,
“example of text”,
“justification. ”
]

这道题虽然被标记为困难，其实只是操作起来稍微繁琐一点，并不难，估计大多数人都很讨厌去看别人的代码，所以尽可能的把思想叙述清楚（思考问题最重要的是思路）

拿到一个words[ ]内含许多的string
1.首先需要考虑我们需要从开始部分（begin位置）最多可以拿多少个单词保证不超出他的限定字符个数假设可以拿的最后一个为 end （这里需要注意一下每两个单词之间必要要存在一个space）；
2.拿到begin—–>end这些单词后下一步就是要把他们合并起来（union（））合并的时候需要注意：不要上来就把begin——>end位置上的Word直接给加进去，因为那样你再去添加space的时候就会很难受~最好是先把这些空格补到
words [ ]里去（每个单独的Word需要补多少就补多少个space）之后再依次添加到总的string中去（ps: 这样想来原题中给的vector & words 是有一定的道理的）
3.下一次循环之前 begin 被替换为 end+1 （end 是select_words（）函数的返回值，返回的是1.中可以选择的最后一个单词的下标）

烂代码如下：

int select_words(vector<string>& words,int begin, int maxWidth){
        int end = begin+1;
        int total_size = words[begin].size();
        while (total_size + 1 < maxWidth && end<=words.size()-1){
            total_size = total_size + 1 + words[end].size();
            if (total_size > maxWidth) break;
            if (total_size == maxWidth) { end++; break; }
            end++;
        }
        return end - 1;
    }
    string union_words(vector<string>& words, int begin, int end, int maxWidth){
        string total;
        if (begin == end){ 
            total += words[begin];
            while (total.size() < maxWidth) total += " ";
            return total;
        }
        if (end == words.size() - 1){
            for (int i = begin; i <= end ; i++)
            {
                total += words[i]; total += " ";
            }
            while (total.size() < maxWidth) total += " ";
            while (total.size() > maxWidth) total.erase(total.size() - 1, 1);
            return total;
        }
        int words_size = end - begin + 1;//单词个数
        int last_size = maxWidth;//剩余可填充space个数
        for (int i = begin; i <= end; i++)
            last_size -= words[i].size();
        int pingjun_size = last_size / (words_size - 1);//这里是 平均个数 是不可能为0的(>=1)  why ?
        string space_str;
        for (int i = 1; i <= pingjun_size; i++) space_str += " ";
        for (int i = begin; i <= end - 1; i++)  words[i] += space_str;
        int shengxia_size = last_size % (words_size - 1);
        if (shengxia_size != 0){
            for (int i = begin, j = shengxia_size; j >= 1;){
                words[i] += " ";
                j--; i++;
            }
        }
        for (int i = begin; i <= end; i++)
            total += words[i];
        return total;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> total;
        int begin = 0, end = 0;
        while (begin<=words.size()-1){
        end = select_words(words, begin, maxWidth);
        string tmp = union_words(words, begin, end, maxWidth);
        total.push_back(tmp);
        begin = end + 1;
        }
        return total;
    }