leetcode【字符串—中等】151.翻转字符串里的单词

简介: leetcode【字符串—中等】151.翻转字符串里的单词

题目


题目来源leetcode


leetcode地址:151. 翻转字符串里的单词,难度:中等。


题目描述(摘自leetcode):


给你一个字符串 s ,逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明:
输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。
示例 1:
输入:s = "the sky is blue"
输出:"blue is sky the"
示例 2:
输入:s = "  hello world  "
输出:"world hello"
解释:输入字符串可以在前面或者后面包含多余的空格,但是翻转后的字符不能包括。
示例 3:
输入:s = "a good   example"
输出:"example good a"
解释:如果两个单词间有多余的空格,将翻转后单词间的空格减少到只含一个。
示例 4:
输入:s = "  Bob    Loves  Alice   "
输出:"Alice Loves Bob"
示例 5:
输入:s = "Alice does not even like bob"
输出:"bob like even not does Alice"
提示:
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词


本地调试代码:


class Solution {
    public int search(int[] nums, int target) {
        ....
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容
        System.out.println(solution.search(arr, 2));//数组、目标值
    }
}



题解


NO1:拼接法


优化前(Stringbuilder拼接)

思路:从前往后进行遍历,遇到空格往后移动一步,遇到非空格先记录下当前索引,接着一直遍历到该单词的后一个位置,取出该单词最终进行拼接返回。


代码:


//"the sky is blue" => "blue is sky the"
public String reverseWords(String s) {
    StringBuilder str = new StringBuilder();
    int i = 0;
    //遍历字符串结束
    while(i<s.length()){
        //过滤空字符串
        while(i<s.length() && s.charAt(i) == ' '){i++;}
        if( i == s.length()){
            break;
        }
        int temp = i;
        while(i<s.length() && s.charAt(i) != ' '){i++;}
        String word =  s.substring(temp,i);
        str = new StringBuilder(word).append(" ").append(str);
    }
    if(str.length()>0){
        return str.substring(0,str.length() - 1);
    }
    return "";
}



这里直接使用了String的api来进行截取字符串操作,并且来进行合并多个单词时频繁创建StringBuilder,不仅仅影响时间还有空间复杂度。



优化后(char[],时间复杂度最优解)

思路:这里是从后往前进行遍历,首先遇到!=空格的先记录索引left,紧接着继续向前移动直到为邻接点或者=空格停止,此时我们就能够拿到对应单词的范围索引,将该单词取出依次存储到新字符数组中。


代码:时间复杂度O(n)、空间复杂度O(n)


这里是没有任何API进行调用的,纯对字符数组进行操作,所以比优化前的效果好很多
public String reverseWords(String s) {
    //源字符数组
    char[] initialArr = s.toCharArray();
    //新字符数组
    char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 ",最终末尾的空格不会返回
    int newArrPos = 0;
    //i来进行整体对源字符数组从后往前遍历
    int i = initialArr.length-1;
    while(i>=0){
        while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
        //此时i位置是边界或!=空格,先记录当前索引,之后的while用来确定单词的首字母的位置
        int right = i;
        while(i>=0 && initialArr[i] != ' '){i--;} 
        //指定区间单词取出(由于i为首字母的前一位,所以这里+1,),取出的每组末尾都带有一个空格
        for (int j = i+1; j <= right; j++) {
            newArr[newArrPos++] = initialArr[j];
            if(j == right){
                newArr[newArrPos++] = ' ';//空格
            }
        }
    }
    //若是原始字符串没有单词,直接返回空字符串;若是有单词,返回0-末尾空格索引前范围的字符数组(转成String返回)
    if(newArrPos == 0){
        return "";
    }else{
        return new String(newArr,0,newArrPos-1);
    }
}




No2:双反转+移位


思路:并没有开辟新的数组或字符串来进行拼接,而是在原始字符数组上来进行操作。


①反转字符串 "the sky is blue "=> " eulb si yks eht"


②遍历" eulb si yks eht",过程中先对某个单词进行反转再移位


对第一个单词进行操作举例:" eulb si yks eht" =反转> " blue si yks eht" =移位> "blue si yks eht"

代码:时间复杂度O(n)、空间复杂度O(1)


/**
  * 空间复杂度O(1)解法
  */
public String reverseWords(String s) {
    //步骤1:字符串整体反转(此时其中的单词也都反转了)
    char[] initialArr = s.toCharArray();
    reverse(initialArr, 0, s.length() - 1);
    //步骤2:遍历循环字符串
    int k = 0;
    for (int i = 0; i < initialArr.length; i++) {
        if (initialArr[i] == ' ') {
            continue;
        }
        int tempCur = i;
        while (i < initialArr.length && initialArr[i] != ' ') {
            i++;
        }
        for (int j = tempCur; j < i; j++) {
            if (j == tempCur) { //遍历开始前
                reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转,不反转从后往前遍历一个个填充有问题
            }
            initialArr[k++] = initialArr[j];
            if (j == i - 1) { //遍历结束
                //避免越界情况,例如=> "asdasd df f",不加判断最后就会数组越界
                if (k < initialArr.length) {
                    initialArr[k++] = ' ';
                }
            }
        }
    }
    if (k == 0) {
        return "";
    } else {
        //参数三:以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
        return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
    }
}
public void reverse(char[] chars, int begin, int end) {
    for (int i = begin, j = end; i < j; i++, j--) {
        chars[i] ^= chars[j];
        chars[j] ^= chars[i];
        chars[i] ^= chars[j];
    }
}


相关文章
|
2月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
2月前
|
存储 算法
LeetCode第43题字符串相乘
LeetCode第43题"字符串相乘"的解题方法,通过使用数组存储乘积并处理进位,避免了字符串转换数字的复杂性,提高了算法效率。
LeetCode第43题字符串相乘
|
2月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
2月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
|
2月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
25 4
|
2月前
|
Python
【Leetcode刷题Python】生词本单词整理
文章提供了一个Python程序,用于帮助用户整理和排版生词本上的单词,包括去除重复单词、按字典序排序,并按照特定的格式要求进行打印排版。
25 3
|
6天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
45 6
|
2月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
82 2
|
6天前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口