【leetcode 力扣刷题】字符串翻转合集（全部反转///部分反转）

字符串翻转合集

  • 344. 反转字符串
  • 541. 反转字符串Ⅱ
  • 151. 反转字符串中的单词
  • 剑指 Offer 58 - II. 左旋转字符串
    • 反转单词思路
    • 循环挪动
    • 子串和子串的拼接

344. 反转字符串

题目链接：344. 反转字符串
题目内容：
在这里插入图片描述
题目中重点强调了必须原地修改输入数组，即不能新建一个数组来完成字符串的反转。我们注意到：

  • 原来下标为0的，反转后是size - 1【原来下标是size - 1的，反转后是0】；
  • 原来下标是1的，反转后是size - 2【原来下标是size -2的，反转后是1】；
  • ……原来下标是i的，反转后变成了size - 1 - i【原来下标是size - 1 - i的，反转后是i】

因此可以用双指针，front = 0，behind = size -1；front向后移动，behind向前移动；front和behind对应元素交换位置即完成字符串的反转。交换元素需要额外申请一个元素的空间，因此空间复杂度是O(1)的。
代码如下（C++）：

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        //双指针
        for(int front = 0, behind = n - 1; front < behind ; front++, behind--){
        	//交换front、behind对应位置的元素
            char tmp = s[front];
            s[front] =s[behind];
            s[behind] = tmp;
        }
        return ;
    }
};

注意，这道题是考察反转字符串实现的逻辑，如果用reverse函数反转就失去了考察的意义。

541. 反转字符串Ⅱ

题目链接：541. 反转字符串Ⅱ
题目内容：
在这里插入图片描述
题目意思是，将字符串s分组：

  • 每一组包括2k个字符；
  • 每一组里面反转前k个字符，后面k个字符位置不变；
  • 对于最后一组，要是少于k个字符，那全部反转；要是在k~2k之间，照样反转前k个字符；

怎么实现分组呢？用start表示每组开始的下标，start从0开始，每次+2k。这里的反转每组前k个字符，可以直接调用reverse函数，也可以自己写一个反转的函数。
代码如下（C++）：


class Solution {
public:
    //自己定义的反转[start,end)间字符的函数
    void myReverse(string& s, int start, int end){
        for(int i = start, j = end -1; i < j; i++, j--)
            swap(s[i],s[j]);
    }
    string reverseStr(string s, int k) {
        int n = s.size();
        //遍历所有分组
        for(int start = 0; start < n ; start += 2*k){
            //判断前k个元素是否越界
            if(start + k < n) 
            	//反转前k个元素
                myReverse(s, start, start + k);//替换成内置函数 reverse(s.begin() + i, s.begin() + i + k);也可以
            else 
            	//反转最后剩余的不足k的元素   
                myReverse(s, start, n);//替换成内置函数 reverse(s.begin() + i, s.end());也可以
        }
        return s;
    }
};

151. 反转字符串中的单词

题目链接：151. 反转字符串中的单词
题目内容：
在这里插入图片描述
根据题目描述和示例，可以知道，所谓的反转单词，是反转单词间的顺序，但是单词内部的字符顺序是不变的。另外还需要处理多余的空格——最前面、最后面的空格需要全部删除；单词间的空格只保留一个。
首先处理掉多余的空格，再进行单词顺序的翻转。移除多余的空格，参考27. 移除元素，直接使用双指针，原地操作，移除掉多余空格后，s有效长度是小于等于实际长度的，resize一下就好。
一开始我的移除空格逻辑是：①第一个单词前，所有的空格都移除掉：用while，直到s[fats] != ‘ ’结束；②单词间的空格只保留一个，如果s[fast] == ‘ ’但是前面一个字符s[fast-1] != ‘ ’那么这个空格就保留，其他的就全部删除；③由于第二步，最后一个单词后如果有大于等于一个空格，最后会保留一个，最终是要把这个删除掉的。 当然过程中s[fast] != ‘ ’，就直接保留。【整体是双指针原地移动】
删除多余空格代码Ⅰ（C++）：

  		int fast;
        int count= 0;  //统计移除多余空格后的字符串长度，同样可以当slow指针用
        //删除前导空格，找到第一个单词起始的字符
        for(fast = 0; fast < n && s[fast] == ' ' ; )
            fast++;  
        while(fast<n){
        	//如果是空格
            if(s[fast] == ' '){ 
            	//前面一个字符不是空格，那么这个空格保留作为单词间的分隔符
                if(s[fast-1]!=' ') 
                    s[count++] = s[fast++];
                else
                	//否则就删掉空格，并且向后移动直到定位到不是空格的字符处
                    while(fast < n && s[fast] == ' '){
                        fast++;
                    };
            }
            //如果不是空格就保留
            else
                s[count++] = s[fast++];
        }
        //处理最后个单词后可能保留的一个空格
        if(s[count-1]==' ') count--;
        s.resize(count);

另外一个删除多余空格的逻辑，重点是针对s[fast] != ‘ ’进行分类讨论。直接从头开始遍历s，如果s[fast] != ‘ ’，就是找到了单词，应该直接保留：①slow == 0，表示这是第一个单词开始，单词前不能有空格，那么从当前的s[fast] != ‘ ’开始，一直到s[fast] == ‘ ’结束，中间的单词字符全都保留；②如果slow != 0，说明这不是第一个单词，当前单词和前面单词间需要有一个空格，那么先添加一个空格，再加入当前单词。
代码如下（C++）：

        int slow = 0;
        for(int fast = 0; fast < s.size() ; fast++){ 
        	//如果不是空格，就是单词
            if(s[fast] != ' '){
            	//如果slow不等于0，表示不是第一个单词，单词前需要加空格
                if(slow!=0) 
                    s[slow++] = ' ';   
                //找完这个单词全部字符，直到遇到空格             
                while(fast < s.size() && s[fast]!=' ')
                    s[slow++] = s[fast++];
            }
        }
        s.resize(slow); //slow表示指针也统计字符数

接下来解决怎么反转单词间的顺序？

  • 1、反转整个字符串【已经移除了多余空格了】，这个时候不仅单词的顺序已经反转了，单词内部的字符顺序也反转了；
  • 2、反转单词内字符的顺序，变成原始的顺序；

经过上面两步全部反转和单词内部反转就能实现单词顺序的反转，这两步是可以交换顺序的。实现的时候定义一个start表示单词的开始，end找到空格或者移动到string外，表示单词结束，反转[start，end)间的字符；end+1，即空格后下一个字符，又是下一个单词的开始。整体代码如下（C++）：

class Solution {
public:
    //自定义一个移除多余空格的函数
    void Remove_Spaces(string& s){
        int slow = 0;
        for(int fast = 0; fast < s.size() ; fast++){
            if(s[fast] != ' '){
                if(slow!=0) 
                    s[slow++] = ' ';                
                while(fast < s.size() && s[fast]!=' ')
                    s[slow++] = s[fast++];
            }
        }
        s.resize(slow);
    }
    
    string reverseWords(string s) {
        Remove_Spaces(s); //先移除多余空格
        int start = 0;
        //反转单词间字符顺序
        for(int end = 0;  end <= s.size() ; end++){
            //遇到空格反转前面一个单词
            if(end == s.size() || s[end] == ' '){
                reverse(s.begin()+start, s.begin()+end);
                //下一个单词的开始
                start = end+1;
            }
        }   
        //反转整个字符串s
        reverse(s.begin(), s.end());
        return s;
    }
};

代码中需要注意if(end == s.size() || s[end] == ‘ ’)，实际上对于||和&&这样的逻辑运算是短路运算的。在A||B中，如果A已经为true了整个表达式是true的，B不需要判断了；在A&&B中，如果A已经是false了整个表达式是false的，B也不需要判断了。式子end == s.size() || s[end] == ‘ ’需要把end == s.size() 写在前面，如果把s[end] == ‘ ’写在前面而end = s.size()的话，就会出现下标越界。

剑指 Offer 58 - II. 左旋转字符串

题目链接：剑指 Offer 58 - II. 左旋转字符串
题目内容：
在这里插入图片描述

反转单词思路

理解题意，其实和上一题反转单词是一样的思路，把前k个字符看成单词1，剩下的字符看成单词2，那就是把单词1和单词2交换顺序，单词内容的字符顺序是不变的。
代码如下（C++）：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
    	//反转单词1
        reverse(s.begin(), s.begin() + n);
        //反转单词2
        reverse(s.begin() + n, s.end());
        //整体反转，最终只反转了单词1和单词2的顺序
        reverse(s.begin(), s.end());
        return s;
    }
};

分析时间复杂度：reverse是O(n)的，三次reverse最终的时间复杂度也是O(n)的。

循环挪动

根据示例我们可以看出，这个左旋的过程，可以看做是把字符串向左移动k个位置，而下标越界的部分【就是往左多出来的部分】移动到尾部。这个过程可以通过①整个字符串向左移动1个位置，第一个位置移动到末尾；②循环移动k次。
注意，如果k等于size-1呢？时间复杂度变成了O(n^2)了。对于k大于了size/2的情况，右边部分更短，考虑将整个字符串向右移，右边第一个元素移动到字符串头部，移动size-k次。 整体的时间复杂度是O(nk)或者O(n(size-k))的。比上一种解法时间复杂度更高。
代码如下（C++）：

class Solution {
public:
    void left_move(string& s, int k){ //循环左移
        for(int i = 0; i < k; i++){
            char tmp = s[0];
            int j;
            for(j = 0; j < s.size() - 1; j++)
                s[j] = s[j+1];
            s[j] = tmp;
        }
    }
    void right_move(string& s, int k){ //循环右移
        int n = s.size();
        for(int i = 0; i < k; i++){
            char tmp = s[n-1];
            int j;
            for(j = n-1; j > 0; j--)
                s[j] = s[j-1];
            s[j] = tmp;
        }
    }
    string reverseLeftWords(string s, int n) {
    	//如果n在前半段就循环左移
        if(n <= s.size()/2)     
            left_move(s, n);
        //n在后半段就右移
        else
            right_move(s, s.size() - n);
        return s;       
    }
};

这个解题逻辑是没有问题的，但是当n很大的是，时间复杂度很高，以下是运行结果：
在这里插入图片描述

子串和子串的拼接

还有一种办法是把前面半截用新的string变量保存，然后拼接起来。代码如下（C++）：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string sub = s.substr(0, n);
        for(int i = 0; i < s.size() - n; i++)
            s[i] = s[i+n];
        for(int i = s.size() -n, j = 0; i < s.size() && j < n; i++, j++)
            s[i] = sub[j] ;  
        return s;
    }
};

这个时间复杂度也是O(n)的，但是需要额外的空间保存前半截子串。
总结还是第一种方法最优。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/96703.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

应用TortoiseSVN的SubWCRev管理VisualStudio C#项目编译版本号

应用TortoiseSVN的SubWCRev管理VisualStudio C#项目编译版本号

首先要安装 TortoiseSVN, 并确保TortoiseSVN的bin目录被加入到系统环境变量Path中。 1、拷贝Porperties目录下的文件AssemblyInfo.cs生成副本AssemblyInfo.template, 作为版本管理的模板文件。 2、修改模板文件中的想要管理的版本号信息 // [assembly: AssemblyVersion(&quo…
阅读更多...
SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录（第五天）MyBatis的注解开发

SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录（第五天）MyBatis的注解开发

SSM框架的学习与应用(Spring Spring MVC MyBatis)-Java EE企业级应用开发学习记录&#xff08;第五天&#xff09;MyBatis的注解开发 ​ 昨天我们深入学习了MyBatis多表之间的关联映射&#xff0c;了解掌握了一对一关联映射&#xff0c;一对多关联映射&#xff0c;嵌套查询方…
阅读更多...
【C语言】每日一题（除自身以外数组的乘积）

【C语言】每日一题（除自身以外数组的乘积）

添加链接描述&#xff0c;链接奉上 方法&#xff1a; 暴力循环:前缀积后缀积&#xff08;分组&#xff09;: 暴力循环: 暴力循换真的是差生法宝&#xff0c;简单好懂&#xff0c;就是不实用&#xff0c;大多数的题目都会超过时间限制&#xff08;无奈&#xff09; 思路&…
阅读更多...
postgresql-字符函数

postgresql-字符函数

postgresql-字符函数 字符串连接字符与编码字符串长度大小写转换子串查找与替换截断与填充字符串格式化MD5 值字符串拆分字符串反转 字符串连接 concat(str, …)函数用于连接字符串&#xff0c;并且忽略其中的 NULL 参数&#xff1b;concat_ws(sep, str, …) 函数使用指定分隔…
阅读更多...
【JS案例】JS实现图片放大镜功能

【JS案例】JS实现图片放大镜功能

JS案例图片放大镜 &#x1f31f;效果展示 &#x1f31f;HTML结构 &#x1f31f;CSS样式 &#x1f31f;实现思路 &#x1f31f;具体实现 1.初始化数据图片 2.获取所需DOM元素 3.初始化页面 初始化缩略图 绑定事件 &#x1f31f;完整代码 &#x1f31f;写在最后 &…
阅读更多...
Centos7安装ZK-UI管理界面安装|Maven|Git|

Centos7安装ZK-UI管理界面安装|Maven|Git|

一: JDK1.8安装 参考: Centos7卸载|安装JDK1.8|Xshell7批量控制多个终端 二&#xff1a;Maven安装 2.1&#xff1a;下载maven安装包 maven 下载地址&#xff1a;https://mirror.bit.edu.cn/apache/maven/maven-3/ [rootwww ~]# mkdir -p /usr/local/maven [rootwww ~]# …
阅读更多...
STM32+RTThread配置以太网无法ping通，无法获取动态ip的问题

STM32+RTThread配置以太网无法ping通，无法获取动态ip的问题

记录一个非常蠢的问题&#xff0c;今天在移植rtthread的以太网驱动的时候出现无法获取动态ip的问题&#xff0c;问题如下&#xff1a; 设置为动态ip时不管是连接路由器还是电脑主机都无法ping通&#xff0c;也无法获取dns地址。 设置为静态ip时无法ping通主机。 使用wireshark…
阅读更多...
Docker笔记

Docker笔记

学习了神光大佬的《Nest 通关秘籍》后&#xff0c;对docker做了个笔记&#xff0c;并实操部署了一下个人项目&#xff0c;在此记录一下 是什么 Docker是一种开源的容器化平台&#xff0c;它可以将应用程序及其依赖项打包到一个可移植的容器中&#xff0c;使得应用程序能够在任…
阅读更多...
java八股文面试[JVM]——JVM调优

java八股文面试[JVM]——JVM调优

知识来源&#xff1a; 【2023年面试】JVM性能调优实战_哔哩哔哩_bilibili
阅读更多...
测试平台metersphere

测试平台metersphere

metersphere可以做接口测试、UI测试、性能测试。 metersphere接口测试底层是jmeter&#xff0c;可以做API管理&#xff0c;快捷调试&#xff0c;接口用例管理&#xff0c;接口自动化场景执行一键选取用例范围&#xff0c;生成测试报告。 会用jmeter&#xff0c;metersphere会…
阅读更多...
深入浅出AXI协议（3）——握手过程

深入浅出AXI协议（3）——握手过程

一、前言 在之前的文章中我们快速地浏览了一下AXI4协议中的接口信号&#xff0c;对此我们建议先有一个简单的认知&#xff0c;接下来在使用到的时候我们还会对各种信号进行一个详细的讲解&#xff0c;在这篇文章中我们将讲述AXI协议的握手协议。 二、握手协议概述 在前面的文章…
阅读更多...
VS的调试技巧

VS的调试技巧

Visual Studiohttps://visualstudio.microsoft.com/zh-hans/vs/ 目录 1、什么是调试&#xff1f; 2、debug和release 3、调试 3.1、环境 3.2、 快捷键 3.2.1、F10和F11 3.2.2、ctrlF5 3.2.3、F5与F9 3.2.3.1、条件断点 3.3、监视和内存观察 3.3.1、监视 3.3.2、内存 …
阅读更多...
多目标应用：基于多目标向日葵优化算法（MOSFO）的微电网多目标优化调度MATLAB

多目标应用：基于多目标向日葵优化算法（MOSFO）的微电网多目标优化调度MATLAB

一、微网系统运行优化模型 参考文献&#xff1a; [1]李兴莘,张靖,何宇,等.基于改进粒子群算法的微电网多目标优化调度[J].电力科学与工程, 2021, 37(3):7 二、多目标向日葵优化算法 多目标向日葵优化算法&#xff08;Multi-objective sunflower optimization&#xff0c;MOS…
阅读更多...
JavaScript基础语法01——初识JavaScript

JavaScript基础语法01——初识JavaScript

哈喽&#xff0c;大家好&#xff0c;我是雷工&#xff01; 最近有项目用到KingFusion软件&#xff0c;由于KingFusion是B/S架构的客户端组态软件&#xff0c;因此在学习KingFusion产品时会涉及许多前端的知识。 像JavaScript语言就是需要用的&#xff0c;俗话说&#xff1a;活到…
阅读更多...
Leedcode19. 删除链表的倒数第 N 个结点

Leedcode19. 删除链表的倒数第 N 个结点

给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 输入&#xff1a;head [1,2,3,4,5], n 2 输出&#xff1a;[1,2,3,5] 示例 2&#xff1a; 输入&#xff1a;head [1], n 1 输出&#xff1a;[] 示例 3&#xff1a; 输入&#xff1…
阅读更多...
java八股文面试[数据库]——MySQL索引的数据结构

java八股文面试[数据库]——MySQL索引的数据结构

知识点&#xff1a; 【2023年面试】mysql索引的基本原理_哔哩哔哩_bilibili 【2023年面试】mysql索引结构有哪些&#xff0c;各自的优劣是什么_哔哩哔哩_bilibili
阅读更多...
哈希的应用——布隆过滤器

哈希的应用——布隆过滤器

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;数据结构——位图 ☂️<3>开发环境&#xff1a;Visual Studio 2022 &#x1f4ac;<4>前言&#xff1a;布隆过滤器是由布隆&#xff08;Burton Howard Bloom&…
阅读更多...
论文解读：Image-Adaptive YOLO for Object Detection in Adverse Weather Conditions

论文解读：Image-Adaptive YOLO for Object Detection in Adverse Weather Conditions

发布时间&#xff1a;2022.4.4 (2021发布&#xff0c;进过多次修订) 论文地址&#xff1a;https://arxiv.org/pdf/2112.08088.pdf 项目地址&#xff1a;https://github.com/wenyyu/Image-Adaptive-YOLO 虽然基于深度学习的目标检测方法在传统数据集上取得了很好的结果&#xf…
阅读更多...
Postman中参数区别及使用说明

Postman中参数区别及使用说明

一、Params与Body 二者区别在于请求参数在http协议中位置不一样。Params 它会将参数放入url中以&#xff1f;区分以&拼接Body则是将请求参数放在请求体中 后端接受数据: 二、body中不同格式 2.1 multipart/form-data key - value 格式输入&#xff0c;主要特点是可以上…
阅读更多...
Fei-Fei Li-Lecture 16:3D Vision 【斯坦福大学李飞飞CV课程第16讲：3D Vision】

Fei-Fei Li-Lecture 16:3D Vision 【斯坦福大学李飞飞CV课程第16讲：3D Vision】

目录 P1 2D Detection and Segmentation P2 Video 2D time series P3 Focus on Two Problems P4 Many more topics in 3D Vision P5-10 Multi-View CNN P11 Experiments – Classification & Retrieval P12 3D Shape Representations P13--17 3D Shape Represen…
阅读更多...
最新文章

Copyright @ 2022~2023