JavaC++算法题解leetcode1592重新排列单词间的空格

2022-11-13 16:11:30 算法 空格 题解

题目要求

思路:模拟

  • 模拟就完了
  • 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补。

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();
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n),结果的空间开销

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;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n),结果的空间开销

Rust

  • rust有很方便的函数用以统计空格和单词,也有很方便的repeat构成单词之间需要的空格。
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
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(n),结果的空间开销

以上就是Java C++算法题解LeetCode1592重新排列单词间的空格的详细内容,更多关于Java C++ 单词间空格重排的资料请关注其它相关文章!

相关文章