Java C++算法題解leetcode1592重新排列單詞間的空格

更新時(shí)間：2022年09月14日 10:28:13 作者：AnjaVon

這篇文章主要為大家介紹了Java C++算法題解leetcode1592重新排列單詞間的空格示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：模擬

模擬就完了
統(tǒng)計(jì)空格數(shù)量和單詞數(shù)量，計(jì)算單詞間應(yīng)有的空格數(shù)，將它們依次放入結(jié)果字符串，若有余數(shù)則在末尾進(jìn)行填補(bǔ)。

Java

class Solution {
    public String reorderSpaces(String text) {
        int n = text.length(), spcnt = 0;
        List<String> words = new ArrayList<>();
        for (int i = 0; i < n; ) {
            if (text.charAt(i) == ' ' && ++i >= 0 && ++spcnt >= 0)
                continue;
            int j = i;
            while (j < n && text.charAt(j) != ' ')
                j++;
            words.add(text.substring(i, j)); // 單詞
            i = j;
        }
        StringBuilder res = new StringBuilder();
        int m = words.size(), dis = spcnt / Math.max(m - 1, 1);
        String spcs = ""; // 兩單詞間的空格
        while (dis-- > 0)
            spcs += " ";
        for (int i = 0; i < m; i++) {
            res.append(words.get(i));
            if (i != m - 1)
                res.append(spcs);
        }
        while (res.length() != n)
            res.append(" ");
        return res.toString();
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)，結(jié)果的空間開銷

C++

class Solution {
public:
    string reorderSpaces(string text) {
        int n = text.size(), spcnt = 0;
        vector<string> words;
        for (int i = 0; i < n; ) {
            if (text[i] == ' ' && ++i >= 0 && ++spcnt >= 0)
                continue;
            int j = i;
            while (j < n && text[j] != ' ')
                j++;
            words.emplace_back(text.substr(i, j - i)); // 單詞
            i = j;
        }
        string res;
        int m = words.size(), dis = spcnt / max(m - 1, 1);
        string spcs = ""; // 兩單詞之間的空格
        while (dis-- > 0)
            spcs += " ";
        for (int i = 0; i < m; i++) {
            res += words[i];
            if (i != m - 1)
                res += spcs;
        }
        while (res.size() != n)
            res += " ";
        return res;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)，結(jié)果的空間開銷

Rust

rust有很方便的函數(shù)用以統(tǒng)計(jì)空格和單詞，也有很方便的repeat構(gòu)成單詞之間需要的空格。

impl Solution {
    pub fn reorder_spaces(text: String) -> String {
        let spcnt = text.chars().filter(|&c| c == ' ').count();
        let words: Vec<String> = text.split_whitespace().map(|s| s.to_string()).collect();
        let mut res = String::new();
        if words.len() == 1 {
            res.push_str(&words[0]);
            res.push_str(&" ".repeat(spcnt));
            return res
        }     
        for i in 0..words.len() {
            res.push_str(&words[i]);
            res.push_str(&" ".repeat(
                if i < words.len() - 1 {
                    spcnt / (words.len() - 1)
                }
                else {
                    spcnt - spcnt / (words.len() - 1) * (words.len() - 1)
            }));
        }
        res
    }
}