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

目录
  • 题目要求
  • 思路:模拟
    • Java
    • C++
    • Rust

题目要求

思路:模拟

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

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++ 单词间空格重排的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • Java C++题解leetcode判定是否为字符重排

    目录 题目要求 思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结 题目要求 思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]

  • Java C++题解leetcode字符串轮转KMP算法详解

    目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); if (n == 0) retu

  • Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

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

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

  • Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    目录 题目要求 思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求 思路一:暴力模拟 由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Java C++ 算法题解leetcode1608特殊数组特征值

    目录 题目要求 思路一:枚举 + 二分 Java C++ 思路二:二分枚举 Java C++ 思路三:倒序枚举 Java C++ 题目要求 思路一:枚举 + 二分 逐一枚举值域内的所有值,然后二分判断是否合法. Java class Solution { public int specialArray(int[] nums) { Arrays.sort(nums); int n = nums.length; for (int x = 0; x <= nums[n - 1]; x++) { //

  • Java C++算法题解leetcode801使序列递增的最小交换次数

    目录 题目要求 思路:状态机DP 实现一:状态机 Java C++ Rust 实现二:滚动数组 Java C++ Rust 总结 题目要求 思路:状态机DP 实现一:状态机 Java class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1; i < n; i++) f[i][0] = f[i][1]

  • 剑指Offer之Java算法习题精讲排列与N叉树

    题目一  解法 class Solution { LinkedList<List<Integer>> ans = new LinkedList<List<Integer>>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> list = new LinkedList<Integer>(); boolean[] bo =

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • java 排序算法之选择排序

    目录 基本介绍 基本思想 思路分析 代码实现 演变过程 优化 算法函数封装 大量数据耗时测试 基本介绍 选择排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出来某个元素,再依规定交换位置后达到排序的目的. 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 基本思想 选择排序(select sorting)也是一种简单直

随机推荐