Text Justification-K6K4.com

原题： https://leetcode.com/problems/text-justification/description/

题意：

给定一组单词和一个长度L。格式化该单词数组，使得形成每行具有完全相同的L个字符，并充分（左和右）对齐的文本。

你可以利用贪婪的方法，在每一行中尽可能多的装入单词。必要的时候单词间填充空格' ' 从而使得每一行都精确地具有L个字符。

单词间的空格应该尽可能的均匀。如果实在无法分配均匀，那么左边的空格应该比右边的空格多。

对于文本中的最后一行需要特殊处理，最后一行中单词间不能存在空格。

约定：（1）单词数组中的每个单词长度都不会超过L。

例子：

words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16
返回：
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

标签：单词、justification、空格、text、一行、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-10 19:19:47 1楼#1层

Java :

public class Solution {  
    public List<String> fullJustify(String[] words, int L) {  
        List<String> ans = new ArrayList<String>();  
          
        int n = words.length;  
        int i = 0;  
        while (i < n) {  
            int len = words[i].length();  
            int j = i + 1;  
            while (j < n && len + 1 + words[j].length() <= L) {  
                len += 1 + words[j].length();  
                j++;  
            }  
              
            String line = words[i];  
            if (j == n) { // if this is the last line  
                for (int k = i + 1; k < n; k++) {  
                    line += " " + words[k];  
                }  
                while (line.length() < L) {  
                    line += " ";  
                }  
            } else {  
                int extraWhite = L - len;  
                int whiteNum = j - i - 1;  
                  
                if (whiteNum == 0) { // if this line has only one word  
                    while (line.length() < L) {  
                        line += " ";  
                    }  
                } else {  
                    for (int k = i + 1; k < j; k++) {  
                        line += " ";  
                        for (int p = 0; p < extraWhite/whiteNum; p++) {  
                            line += " ";  
                        }  
                        if (k - i <= extraWhite%whiteNum) {  
                            line += " ";  
                        }  
                        line += words[k];  
                    }  
                }  
            }  
            ans.add(line);  
              
            i = j;  
        }  
          
        return ans;  
    }  
}

Bingo

2017-08-10 19:20:51 2楼#1层

C++:

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> res;
        int i = 0;
        while (i < words.size()) {
            int j = i, len = 0;
            while (j < words.size() && len + words[j].size() + j - i <= L) {
                len += words[j++].size();
            }
            string out;
            int space = L - len;
            for (int k = i; k < j; ++k) {
                out += words[k];
                if (space > 0) {
                    int tmp;
                    if (j == words.size()) { 
                        if (j - k == 1) tmp = space;
                        else tmp = 1;
                    } else {
                        if (j - k - 1 > 0) {
                            if (space % (j - k - 1) == 0) tmp = space / (j - k - 1);
                            else tmp = space / (j - k - 1) + 1;
                        } else tmp = space;
                    }
                    out.append(tmp, ' ');
                    space -= tmp;
                }
            }
            res.push_back(out);
            i = j;
        }
        return res;
    }
};

取消

回复

推荐圈子

LeetCode交流圈