thảo luận Leetcode mỗi ngày

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:

        def get_words_in_line(start):
            num_chars = len(words[start])
            line_words = [words[start]]
            curr = start + 1

            while curr < len(words) and num_chars + 1 + len(words[curr]) <= maxWidth:
                line_words.append(words[curr])
                num_chars += 1 + len(words[curr])
                curr += 1
            
            return line_words

        def get_line(line_words, start):
            end = start + len(line_words) - 1
            if end == len(words) - 1 or len(line_words) == 1:
                line = " ".join(line_words)
                return line + " " * (maxWidth - len(line))

            num_chars = 0
            for word in line_words:
                num_chars += len(word)

            num_spaces = maxWidth - num_chars
            space_beetween = num_spaces // (len(line_words) - 1)
            left_space = num_spaces % (len(line_words) - 1)

            line = [words[start]]
            for i in range(start + 1, end + 1):
                curr_space = " " * space_beetween
                if left_space > 0:
                    curr_space += " "
                    left_space -= 1
                line += [curr_space, words[i]]
            
            return "".join(line)

        result = []
        curr_start = 0

        while curr_start < len(words):
            line_words = get_words_in_line(curr_start)
            curr_line = get_line(line_words, curr_start)

            result.append(curr_line)
            curr_start += len(line_words)
        
        return result

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        cnt,sum_len,n = 0,0,len(words)
        cur_w, ans = [],[]
        for word in words:
            if sum_len + len(word) + cnt > maxWidth:
                if cnt == 1:
                    tmp = cur_w[0] + " " * (maxWidth - sum_len)
                else:
                    tmp = cur_w[0]
                    r = (maxWidth - sum_len) % (cnt - 1)
                    t = (maxWidth - sum_len) // (cnt - 1)
                    for i in range(cnt-1):
                        tmp += " " * (t + (1 if r > 0 else 0)) + cur_w[i+1]
                        r -= 1
                cnt,sum_len = 0,0
                cur_w = []
                ans.append(tmp)
            cnt += 1
            sum_len += len(word)
            cur_w.append(word)
        ans.append(" ".join(cur_w) + " " * (maxWidth - sum_len - cnt + 1))
        return ans

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        var left = 0;
        var length = 0;
        var result = new List<string>();
        for(int right = 0; right < words.Length; right++)
        {
            length += words[right].Length + 1;
            if(right + 1 == words.Length || length + words[right + 1].Length > maxWidth)
            {
                var line = GetWords(words, left, right);
                result.Add(CreateLine(line, maxWidth, words.Length - 1 == right));
                left = right + 1;
                length = 0;
            }
        }

        return result;
    }

    private List<string> GetWords(string[] words, int left, int right)
    {
        var result = new List<string>();
        for(int i = left; i <= right; i++)
        {
            result.Add(words[i]);
        }

        return result;
    }

    private string CreateLine(List<string> words, int maxWidth, bool isEnd)
    {
        var length = -1;
        foreach(var word in words)
        {
            length += word.Length + 1;
        }

        var totalNeededSpaces = maxWidth - length;
        var numWords = words.Count - 1;

        if(numWords == 0 || isEnd)
          return string.Join(" ", words) + new string(' ', totalNeededSpaces);

        var spacesPerWord = totalNeededSpaces/numWords;
        var neededExtraSpace = totalNeededSpaces%numWords;
        for(int i = 0; i< neededExtraSpace; i++)
        {
            words[i] = words[i] + " ";
        }
        
        for(int i = 0; i < numWords; i++)
        {
            words[i] = words[i] + new string(' ', spacesPerWord);
        }

        return string.Join(" ", words);
    }
}

var fullJustify = function(words, maxWidth) {
    const lines = [
        [0],
    ];
    const q = new Queue(words);
    while (!q.isEmpty()) {
        const l = lines[lines.length - 1];
        const next = q.dequeue();
        if (next.length + l[0] + (l[0] ? 1 : 0) > maxWidth) {
            // need break
            lines.push([next.length, next]);
        } else {
            l[0] += next.length + (l[0] ? 1 : 0);
            l.push(next);
        }
    }
    
    const n = lines.length;

    return lines.map((line, idx) => {
        if (idx === n-1 || line.length === 2) {
            return line.slice(1).join(' ').padEnd(maxWidth, ' ');
        }

        let spaces = maxWidth - (line[0] - (line.length - 2));
        
        return line.slice(1).map((w, i, arr) => {
            if (!i) {
                return w;
            }
            
            // console.log('calc gap', spaces, arr.length);
            const gap = Math.ceil(spaces / (arr.length - i));
            spaces -= gap;
            
            return ' '.repeat(gap) + w;
        }).join('');
    });
};

class Solution {
public:
    void justifyString(string& word, int maxWidth, bool isLeft){
        if(word.size() > maxWidth)
            word.pop_back();
        if(isLeft){
            while(word.size() < maxWidth)
                word.push_back(' ');
        }
        else{
            while(word[word.size() - 1] == ' ')
                word.pop_back();
            while(word.size() < maxWidth){
                for(int i = 0; i < word.size(); ++i){
                    if(word[i] == ' ' && word.size() + 1 <= maxWidth){
                        word.insert(begin(word) + i, ' ');
                        while(word[i] == ' ')
                            i++;
                    }
                }
            }
        }
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        vector<bool> isLeft;
        string temp;
        int wordCount = 0;
        for(const string& word : words){
            if(temp.size() + word.size() > maxWidth){
                result.push_back(temp);
                if(wordCount == 1)
                    isLeft.push_back(true);
                else
                    isLeft.push_back(false);
                temp.clear();
                wordCount = 0;
            }
            temp += word;
            temp += " ";
            wordCount++;
        }
        if(temp.size())
            result.push_back(temp);
        isLeft.push_back(true);
        for(int i = 0; i < result.size(); ++i)
            justifyString(result[i], maxWidth, isLeft[i]);
        return result;
    }
};

public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        // all items scope
        List<List<string>> linesWords = new List<List<string>>();
        List<int[]> paddingOfLineInfo = new List<int[]>();

        // in item scope
        List<string> currentLineWords = new List<string>();
        int currentLineWordCount = 0, currentLineLength = 0, newLineLength, padLength, padEachWordSpaceLength, remainSpaceLength, i, j, lineLength, wordLength = words.Length;

        for(i = 0; i < wordLength; i++) {
            newLineLength = currentLineLength + words[i].Length + (currentLineLength > 0 ? 1 : 0) /* space */;
            if(newLineLength > maxWidth) { // start padding
                // get padding info
                padLength = maxWidth - currentLineLength;
                if(currentLineWordCount > 1) {
                    padEachWordSpaceLength = padLength / (currentLineWordCount - 1);
                    remainSpaceLength = padLength % (currentLineWordCount - 1);
                } else {
                    padEachWordSpaceLength = padLength;
                    remainSpaceLength = 0;
                }

                // break line
                paddingOfLineInfo.Add(new int[]{padEachWordSpaceLength, remainSpaceLength});
                linesWords.Add(currentLineWords);
                currentLineWords = new List<string>();
                currentLineLength = 0;
                currentLineWordCount = 0;
               
                // add current word to the first place of the new line
                currentLineWords.Add(words[i]);
                currentLineWordCount = 1;
                currentLineLength = words[i].Length;
            } else {
                currentLineWords.Add(words[i]);
                currentLineWordCount++;
                currentLineLength += words[i].Length + (currentLineLength > 0 ? 1 : 0) /* space */;
            }

            if(i >= words.Length - 1) { // the last word
                // complete line
                linesWords.Add(currentLineWords);
            }
        }

        // return new List<string>();

        // print result
        lineLength = linesWords.Count;
        List<string> result = new List<string>();
        string currentLine, padStart;
        int padStartLength;
        for(i = 0; i < lineLength; i++) {
            currentLineWordCount = linesWords[i].Count;
            currentLine = "";
            for(j = 0; j < currentLineWordCount; j++) {
                padStartLength = 0; // pad start
                if(j > 0) { // not the first word in line
                    padStartLength++; // space
                    if(i < lineLength - 1) { // current line is not the last line
                        // add padding
                        padStartLength += paddingOfLineInfo[i][0] + (paddingOfLineInfo[i][1] > 0 ? 1 : 0);
                        if(paddingOfLineInfo[i][1] > 0) paddingOfLineInfo[i][1]--;
                    }
                }
                padStart = new string(' ', padStartLength);
               
                currentLine += padStart + linesWords[i][j];

                if(j >= currentLineWordCount - 1 && maxWidth - currentLine.Length > 0)
                    currentLine += new string(' ', maxWidth - currentLine.Length);
            }
            result.Add(currentLine);
        }

        return result;
    }
}

class Solution {
public:
    string justify(vector<string> &words, int start, int end, int maxWidth, bool last = false){
        string result(maxWidth,' ');
        auto pos = 0;
        auto remainSpace = maxWidth;
        for (auto i = start; i < end; i++){
            remainSpace -= words[i].length();
        }
        auto avgSpace = remainSpace / max(end - start - 1,1);
        cout << "avgSpace: " << avgSpace << '\n';
        for (auto i = start; i < end; i++){
            for (auto j = pos; j - pos < words[i].length();j++){
                result[j] = words[i][j-pos];
            }
            if (last){
                pos+= (words[i].length() + 1);
            }else{
                pos += (words[i].length() + avgSpace);
                cout << "remainSpace: " << remainSpace << '\n';
                if (avgSpace * (end - i - 1) < remainSpace){
                    pos++;
                    remainSpace--;
                }
                remainSpace -= avgSpace;
            }           
        }
        return result;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<int> chunks;
        auto currLength = 0;
        for(auto i = 0; i<words.size(); i++){
            if(currLength == 0){
                chunks.push_back(i);
                currLength += words[i].length();
            }else{
                currLength += (1 + words[i].length());
                if(currLength > maxWidth){
                    chunks.push_back(i);
                    currLength = words[i].length();
                }
            }
        }
        vector<string> result(chunks.size());
        for (auto i = 0;i<chunks.size();i++){
            if (i < chunks.size() - 1){
                result[i] = justify(words,chunks[i], chunks[i+1], maxWidth);
            }else{
                result[i] = justify(words, chunks[i], words.size(),maxWidth,  true);
            }
        }
        return result;
    }
};

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        List<String> buffer = new ArrayList<>();
        int bufferlength = 0;
        int curL = 0;
        for (int j = 0; j < words.length; j++) {
            String word = words[j];
            curL += (curL > 0 ? 1 : 0) + word.length();
            if (curL > maxWidth) {
                int totalSpaceCnt = Math.max(1, buffer.size() - 1);
                int totalSpaceWidth = maxWidth - bufferlength;
                int spaceSize = totalSpaceWidth / totalSpaceCnt;
                int additionalSpace = totalSpaceWidth % totalSpaceCnt;
                StringBuilder sb = new StringBuilder();
                for (String s : buffer) {
                    sb.append(s);
                    if (sb.length() == maxWidth) break;
       
                    for (int i = 0; i < spaceSize; i++) {
                        sb.append(' ');
                    }
                    if (additionalSpace-- > 0){
                        sb.append(' ');
                    }
                }
                ans.add(sb.toString());
            
                buffer = new ArrayList<>();
                bufferlength = 0;
                curL = word.length();
            }
            buffer.add(word);
            bufferlength += word.length();

            if (j == words.length - 1) {
                StringBuilder sb  = new StringBuilder();
                for (String s : buffer){
                    sb.append(s);
                    if (sb.length() < maxWidth) sb.append(' ');
                }
                while(sb.length() < maxWidth) sb.append(' ');
                ans.add(sb.toString());
            }
        }

        return ans;
    }
}