68. Text Justification

LeetCode hard original: C# #array #csharp #greedy #hard #leetcode #string

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Дан mảng строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая chuỗi содержала ровно maxWidth символов и была полностью (слева и справа) выровнена.

Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая chuỗi имела ровно maxWidth символов.

Дополнительные пробелы между словами должны распределяться как можно более равномерно. Если количество пробелов в строке не делится поровну между словами, то пустые места слева будут содержать больше пробелов, чем места справа.

Для последней строки текста выравнивание должно быть по левому краю, и между словами не добавляются дополнительные пробелы.

Примечание:

Слово определяется как последовательность символов, не содержащих пробелы.

Длина каждого слова гарантированно больше 0 и не превышает maxWidth.

Đầu vàoной mảng words содержит хотя бы одно слово.

Ví dụ:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16

Output:

[

"This is an",

"example of text",

"justification. "

]

C# lời giải

đã khớp/gốc

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        var ans = new List<string>();
        int i = 0;
        while (i < words.Length) {
            var currentLine = GetWords(i, words, maxWidth);
            i += currentLine.Count;
            ans.Add(CreateLine(currentLine, i, words, maxWidth));
        }
        return ans;
    }
    private List<string> GetWords(int i, string[] words, int maxWidth) {
        var currentLine = new List<string>();
        int currLength = 0;
        while (i < words.Length && currLength + words[i].Length <= maxWidth) {
            currentLine.Add(words[i]);
            currLength += words[i].Length + 1;
            i++;
        }
        return currentLine;
    }
    private string CreateLine(List<string> line, int i, string[] words,
                              int maxWidth) {
        int baseLength = -1;
        foreach (var word in line) {
            baseLength += word.Length + 1;
        }
        int extraSpaces = maxWidth - baseLength;
        if (line.Count == 1 || i == words.Length) {
            return string.Join(" ", line) + new string(' ', extraSpaces);
        }
        int wordCount = line.Count - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;
        for (int j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (int j = 0; j < wordCount; j++) {
            line[j] += new string(' ', spacesPerWord);
        }
        return string.Join(" ", line);
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> FullJustify(vector<string> words, int maxWidth) {
        var ans = new List<string>();
        int i = 0;
        while (i < words.size()) {
            var currentLine = GetWords(i, words, maxWidth);
            i += currentLine.size();
            ans.push_back(CreateLine(currentLine, i, words, maxWidth));
        }
        return ans;
    }
    private List<string> GetWords(int i, vector<string> words, int maxWidth) {
        var currentLine = new List<string>();
        int currLength = 0;
        while (i < words.size() && currLength + words[i].size() <= maxWidth) {
            currentLine.push_back(words[i]);
            currLength += words[i].size() + 1;
            i++;
        }
        return currentLine;
    }
    private string CreateLine(List<string> line, int i, vector<string> words,
                              int maxWidth) {
        int baseLength = -1;
        foreach (var word in line) {
            baseLength += word.size() + 1;
        }
        int extraSpaces = maxWidth - baseLength;
        if (line.size() == 1 || i == words.size()) {
            return string.Join(" ", line) + new string(' ', extraSpaces);
        }
        int wordCount = line.size() - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;
        for (int j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (int j = 0; j < wordCount; j++) {
            line[j] += new string(' ', spacesPerWord);
        }
        return string.Join(" ", line);
    }
}

Java lời giải

đã khớp/gốc

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        int i = 0;

        while (i < words.length) {
            List<String> currentLine = getWords(i, words, maxWidth);
            i += currentLine.size();
            ans.add(createLine(currentLine, i, words, maxWidth));
        }

        return ans;
    }

    private List<String> getWords(int i, String[] words, int maxWidth) {
        List<String> currentLine = new ArrayList<>();
        int currLength = 0;

        while (i < words.length && currLength + words[i].length() <= maxWidth) {
            currentLine.add(words[i]);
            currLength += words[i].length() + 1;
            i++;
        }

        return currentLine;
    }

    private String createLine(
        List<String> line,
        int i,
        String[] words,
        int maxWidth
    ) {
        int baseLength = -1;
        for (String word : line) {
            baseLength += word.length() + 1;
        }

        int extraSpaces = maxWidth - baseLength;

        if (line.size() == 1 || i == words.length) {
            return String.join(" ", line) + " ".repeat(extraSpaces);
        }

        int wordCount = line.size() - 1;
        int spacesPerWord = extraSpaces / wordCount;
        int needsExtraSpace = extraSpaces % wordCount;

        for (int j = 0; j < needsExtraSpace; j++) {
            line.set(j, line.get(j) + " ");
        }

        for (int j = 0; j < wordCount; j++) {
            line.set(j, line.get(j) + " ".repeat(spacesPerWord));
        }

        return String.join(" ", line);
    }
}

JavaScript lời giải

đã khớp/gốc

var fullJustify = function (words, maxWidth) {
    let ans = [];
    let i = 0;
    while (i < words.length) {
        let currentLine = getWords(i, words, maxWidth);
        i += currentLine.length;
        ans.push(createLine(currentLine, i, words, maxWidth));
    }
    return ans;
    function getWords(i, words, maxWidth) {
        let currentLine = [];
        let currLength = 0;
        while (i < words.length && currLength + words[i].length <= maxWidth) {
            currentLine.push(words[i]);
            currLength += words[i].length + 1;
            i++;
        }
        return currentLine;
    }
    function createLine(line, i, words, maxWidth) {
        let baseLength = -1;
        for (let word of line) {
            baseLength += word.length + 1;
        }
        let extraSpaces = maxWidth - baseLength;
        if (line.length === 1 || i === words.length) {
            return line.join(" ") + " ".repeat(extraSpaces);
        }
        let wordCount = line.length - 1;
        let spacesPerWord = Math.floor(extraSpaces / wordCount);
        let needsExtraSpace = extraSpaces % wordCount;
        for (let j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (let j = 0; j < wordCount; j++) {
            line[j] += " ".repeat(spacesPerWord);
        }
        return line.join(" ");
    }
};

Python lời giải

đã khớp/gốc

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        def get_words(i):
            current_line = []
            curr_length = 0

            while i < len(words) and curr_length + len(words[i]) <= maxWidth:
                current_line.append(words[i])
                curr_length += len(words[i]) + 1
                i += 1

            return current_line

        def create_line(line, i):
            base_length = -1
            for word in line:
                base_length += len(word) + 1

            extra_spaces = maxWidth - base_length

            if len(line) == 1 or i == len(words):
                return " ".join(line) + " " * extra_spaces

            word_count = len(line) - 1
            spaces_per_word = extra_spaces // word_count
            needs_extra_space = extra_spaces % word_count

            for j in range(needs_extra_space):
                line[j] += " "

            for j in range(word_count):
                line[j] += " " * spaces_per_word

            return " ".join(line)

        ans = []
        i = 0

        while i < len(words):
            current_line = get_words(i)
            i += len(current_line)
            ans.append(create_line(current_line, i))

        return ans

Go lời giải

đã khớp/gốc

func fullJustify(words []string, maxWidth int) []string {
    ans := []string{}
    i := 0
    for i < len(words) {
        currentLine := getWords(i, words, maxWidth)
        i += len(currentLine)
        ans = append(ans, createLine(currentLine, i, words, maxWidth))
    }
    return ans
}

func getWords(i int, words []string, maxWidth int) []string {
    currentLine := []string{}
    currLength := 0
    for i < len(words) && currLength+len(words[i]) <= maxWidth {
        currentLine = append(currentLine, words[i])
        currLength += len(words[i]) + 1
        i++
    }
    return currentLine
}

func createLine(line []string, i int, words []string, maxWidth int) string {
    baseLength := -1
    for _, word := range line {
        baseLength += len(word) + 1
    }
    extraSpaces := maxWidth - baseLength
    if len(line) == 1 || i == len(words) {
        return strings.Join(line, " ") + strings.Repeat(" ", extraSpaces)
    }
    wordCount := len(line) - 1
    spacesPerWord := extraSpaces / wordCount
    needsExtraSpace := extraSpaces % wordCount
    for j := 0; j < needsExtraSpace; j++ {
        line[j] += " "
    }
    for j := 0; j < wordCount; j++ {
        line[j] += strings.Repeat(" ", spacesPerWord)
    }
    return strings.Join(line, " ")
}

Algorithm

1️⃣

Создайте два вспомогательных метода getWords и createLine, описанные выше.

2️⃣

Инициализируйте список ответов ans и целочисленную переменную i для итерации по Đầu vàoным данным. Используйте цикл while для перебора Đầu vàoных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе.

3️⃣

Пока i < words.length, выполните следующие шаги:

Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i).

Увеличьте i на currentLine.length.

Создайте строку, вызвав createLine(line, i), и добавьте её в ans.

return ans.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.