代码随想录 Day17 字符串 | LC344 反转字符串 LC541 反转字符串II 卡码网54替换数字

一、反转字符串

题目:

力扣344:反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例1:

输入:s = [“h”,“e”,“l”,“l”,“o”]
输出:[“o”,“l”,“l”,“e”,“h”]

示例2:

输入:s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出:[“h”,“a”,“n”,“n”,“a”,“H”]

提示:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

解题思路分析:


自己的思路:

用两个指针,一个从头开始遍历,一个从尾部开始遍历,并且一边遍历一边交换字符位置,直到左右指针相遇(指向同一个位置,这是奇数个字符的时候;或者错过,即left>right),这是偶数个字符的时候);

交换的时候,用一个临时变量temp来存储left位置的字符,把right赋给left,temp赋给right,完成交换。

代码:

//定义左右指针
int left = 0;
int right = s.length - 1;
//循环遍历,进行交换
while(left < right) {//临时变量,存储取出来的字符char temp;//利用temp完成字符交换temp = s[left];s[left] = s[right];s[right] = temp;//交换结束后left和right同时向中间移动一个位置left++;right--;
}

复杂度分析:

  • 时间复杂度:O(n)
  • 空房间复杂度:O(1)

说明:

如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。

双指针法图示:

反转字符串

补充:

还可以使用异或操作来完成交换:也可以避免使用额外空间

异或操作:比较两个二进制位。如果两个二进制位相同,则结果为 0;如果两个二进制位不同,则结果为 1。

s[left] ^= s[right]; //构造 a ^ b 的结果,放入a中
s[right] ^= s[left]; //将a ^ b 的结果再 ^b,存入b中,此时b=a,a=a ^ b
s[left] ^= s[right]; //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换

题解:


用temp交换数值
在这里插入图片描述

用异或操作交换数值:
在这里插入图片描述

二、反转字符串II

题目:

力扣541:反转字符串II

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

示例1:

输入:s = “abcdefg”, k = 2
输出:“bacdfeg”

示例2:

输入:s = “abcd”, k = 2
输出:“bacd”

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

解题思路分析:


这道题目其实就是比上一题多了一些规则;

这里for循环中可以不写i++,而是直接写i += (2*k),直接让i移动2k个位置,而不是一个一个去移动;

大家如果习惯性写i++的话,还得移动并计数判断有没有到2k,这样代码就变得很复杂了。

所以当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。

代码讲解:

//将字符串转换成数组去操作
char[] ch = s.toCharArray();
//循环遍历字符串数组
for(int i = 0; i < s.length(); i += (2 * k)) {//判断是否还剩k个字符,避免操作空字符串//左闭右开,反转的时候不包含第i+k这个字符,所以边界条件可以等于i+kif(i + k < s.length()) {//对前k个字符进行反转int left = i;int right = i + k - 1;while(left < right) {char temp = s.charAt(i);ch[left] = ch[right];ch[right] = temp;left++;right--;}}else{//对尾部不够k时剩余的字符进行反转int left = i;int right = ch.length - 1;while(left < right) {char temp = ch[left];ch[left] = ch[right];ch[right] = temp;left++;right--;}}
}
return new String(ch);

代码可以更加简洁:

让right等于ch.length-1和i+k-1的最小值;

也就是判断尾部剩余的字符个数够不够k,来决定right是取i+k-1(剩余字符大于等于k个),还是取ch.length-1(不够k个)。

因为如果剩余字符大于等于k个,那么ch.length-1大于等于i+k-1;剩余字符不够k个时,i+k-1大于ch.length-1。

相当于直接用取最小值来完成了尾部剩余字符个数够不够k个的判断。

代码如下:

//将字符串转换成数组去操作
char[] ch = s.toCharArray();
//循环遍历字符串数组
for(int i = 0; i < ch.length; i += (2 * k)) {int left = i;//判断是否还剩k个字符,避免操作空字符串int right = Math.min(ch.length - 1, i + k - 1);//对字符串进行翻转while(left < right) {char temp = ch[left];ch[left] = ch[right];ch[right] = temp;left++;right--;}
}
return new String(ch);

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

总结:


如果操作字符串或者数组,是成段的去操作的,那么可以考虑让指针成段的跳,而不是i++一个一个去走;

这里就需要跳出固有思维,更加灵活的解决问题。

另外,在遇到边界问题时,别忘了前面学过的区间开闭原则!

题解:


在这里插入图片描述

三、替换数字

题目:

卡码网54:替换数字

时间限制:1.000s 空间限制:128MB

题目描述

给定一个字符串 s,它包含小写字母和数字字符,请编写一个函数,将字符串中的字母字符保持不变,而将每个数字字符替换为number。 例如,对于输入字符串 “a1b2c3”,函数应该将其转换为 “anumberbnumbercnumber”。

输入描述:

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述:

打印一个新的字符串,其中每个数字字符都被替换为了number

输入示例:

a1b2c3

输出示例:

anumberbnumbercnumber

提示信息:

数据范围:
1 <= s.length < 10000。

解题思路分析:


首先扩充数组到每个数字字符替换成 “number” 之后的大小。

例如 字符串 “a5b” 的长度为3,那么 将 数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。

如图:
在这里插入图片描述

然后从后向前替换数字字符,也就是双指针法

i 指向新长度的末尾,j指向旧长度的末尾;

在这里插入图片描述

为什么要从后向前填充,从前向后填充不行么?

从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素整体向后移动。

其实很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作。

这么做有两个好处:

  1. 不用申请新数组。
  2. 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。

代码讲解:(ACM模式)

import java.utils.*
public class Main {public static void main(String[] args) {//输入字符串sScanner sc = new Scanner(System.in);String s = sc.next();//计算出新数组所需要的长度int len = s.length();for(int i = 0; i < s.length(); i++) {//如果是数字,就把数组长度+5(因为原来的数字所在的位置也会被覆盖,所以只用+5)if(s.charAt(i) >= 0 && s.charAt(i) <= 9) {len += 5;}}//申请新数组,把字符串s先放进数组char[] ch = new char[len];for(int i = 0; i < s.length(); i++) {ch[i] = s.charAt(i);}//开始双指针法,将数字替换成numberfor(int i = s.length() - 1, j = len - 1; i >= 0; i--) {//如果是数字,就从后往前插入number if(ch[i] >= '0' && ch[i] <= '9') {ch[j--] = 'r';ch[j--] = 'e';ch[j--] = 'b';ch[j--] = 'm';ch[j--] = 'u';ch[j--] = 'n';} else {//如果是字母,就直接放到后面ch[j--] = ch[i];}}}//输出结果System.out.println(ch);
}

题解:


在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

P8786 [蓝桥杯 2022 省 B] 李白打酒加强版

【dfs题解】---只有50分 (头一回自己用dfs做出来了dp的hard等级的大题&#xff0c;从来没有拿50分这么高兴过哈哈哈哈哈) #include <bits/stdc.h> using namespace std; int n,m; long long ans0; const long long mol1e97; void dfs(int h,int d,int sum) {if(h<0|…

VXWorks6.9 + Workbench3.3 开发环境部署

VxWorks系列传送门 一、安装包 有需要的朋友可以私信~ 二、安装 安装挺简单 1、先安装DVD-R147826.1-1-01-vx69.udf.iso 镜像中的Setup.exe程序&#xff0c;记住要使用管理员权限 2、再安装DVD-R147826.1-23-00.iso 镜像中的Setup.exe程序&#xff0c;同样要使用管理员权限 3…

69787987

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…

C-开发 visual Studio扩展插件介绍-格式化插件Xaml Styler、CSharpier介绍(扩展插件安装方法)

C#开发 visual Studio扩展插件介绍 扩展插件安装方法Xaml StylerCSharpier 提高C#开发效率常用的插件 扩展插件安装方法 菜单栏点击“扩展”→“管理扩展”。 打开扩展页面 右上角搜索需要安装的插件&#xff0c;然后点击下载 安装完成后&#xff0c;根据提示关闭VS进行安…

spring04:注解使用

spring04&#xff1a;注解使用 文章目录 spring04&#xff1a;注解使用前言&#xff1a;一、 Autowired Qualifier和 Resource 和 nullable1. Autowired 2. Resource &#xff1a;使用在类的属性上面&#xff08;和Autowired类似&#xff09;3. nullable 二、 Component 和 Re…

数据库体系概述:详述其基本概念、多样分类、关键作用及核心特性

数据库是一个用于存储、管理和检索数据的系统&#xff0c;它按照特定的数据结构和模式组织数据&#xff0c;确保数据的一致性、安全性和高效访问。 数据库&#xff08;Database, DB&#xff09;是一个长期存储在计算机内&#xff0c;用来组织、存储和管理大量数据的集合。数据…

yolov8草莓及病害检测项目开发(python开发,带有训练模型,可以重新训练,并有Pyqt5界面可视化)

本次检测系统&#xff0c;可以通过图片、视频或摄像头三种形式检测&#xff0c;检测出开花、结果、熟果、草莓叶子健康、叶子缺钙、灰叶斑病等八大类别。基于最新的YOLO-v8模型&#xff0c;下载后即可重新运行训练脚本&#xff0c;&#xff0c;也可以直接运行检测脚本&#xff…

StarRocks 物化视图:指标平台性能提升的新引擎

随着大数据技术的发展&#xff0c;企业对于实时数据分析和决策支持的需求日益增长。在这样的背景下&#xff0c;指标平台的构建成为了企业数据战略的核心组成部分。一个高效的指标平台不仅能够确保数据的准确性和一致性&#xff0c;还能显著提升数据分析的速度和灵活性。在这样…

在线药房数据惨遭Ransomhub窃取,亚信安全发布《勒索家族和勒索事件监控报告》

本周态势快速感知 本周全球共监测到勒索事件119起&#xff0c;与上周相比勒索事件有所增长。 本周Blacksuit是影响最严重的勒索家族&#xff0c;Ransomhub和Blackbasta恶意家族紧随其后&#xff0c;从整体上看Lockbit3.0依旧是影响最严重的勒索家族&#xff0c;需要注意防范。…

最简单知识点PyTorch中的nn.Linear(1, 1)

一、nn.Linear(1, 1) nn.Linear(1, 1) 是 PyTorch 中的一个线性层&#xff08;全连接层&#xff09;的定义。 nn 是 PyTorch 的神经网络模块&#xff08;torch.nn&#xff09;的常用缩写。 nn.Linear(1, 1) 的含义如下&#xff1a; 第一个参数 1&#xff1a;输入特征的数量…

Vue 引入config.js后别的js访问不到window对象下的属性

Vue项目里,我们项目配置的请求服务器地址都是在public里config.js里,如下例: 然后在index.html里引入config.js,如下图: 这里要注意的是,script的src要写上<%= BASE_URL %>,代码如下: <!DOCTYPE html> <html><head><meta charset="…

【深度学习】环境搭建ubuntu22.04

清华官网的conda源 https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ 安装torch conda install pytorch torchvision torchaudio pytorch-cuda12.1 -c pytorch -c nvidia 2.2.2 conda install 指引看这里&#xff1a; ref:https://docs.nvidia.com/cuda/cuda-installatio…

TechTool Pro for Mac v19.0.3中文激活版 硬件监测和系统维护工具

TechTool Pro for Mac是一款专为Mac用户设计的强大系统维护和故障排除工具。它凭借全面的功能、高效的性能以及友好的操作界面&#xff0c;赢得了广大用户的信赖和好评。 软件下载&#xff1a;TechTool Pro for Mac v19.0.3中文激活版 作为一款专业的磁盘和系统维护工具&#x…

SNRO 编号范围对象管控,唯一ID

事务代码:SNRO 代码引用: DATA: MAXTID TYPE I,NEWNO TYPE CHAR8. CALL FUNCTION NUMBER_RANGE_ENQUEUE EXPORTING OBJECT ZQC57 EXCEPTIONS FOREIGN_LOCK 1 OBJECT_NOT_FOUND 2 SYSTEM_FAILURE 3 OTHERS …

Docker学习笔记(二):在Linux中部署Docker(Centos7下安装docker、环境配置,以及镜像简单使用)

一、前言 记录时间 [2024-4-6] 前置文章&#xff1a;Docker学习笔记&#xff08;一&#xff09;&#xff1a;入门篇&#xff0c;Docker概述、基本组成等&#xff0c;对Docker有一个初步的认识 在上文中&#xff0c;笔者进行了Docker概述&#xff0c;介绍其历史、优势、作用&am…

npm创建Vue3项目

npm创建Vue3项目 1 创建Vue项目说明 2 安装3 运行 1 创建Vue项目 创建最新版的Vue项目&#xff0c;已经不推荐使用CLI构建方式了。参考如下即可。 npm create vuelatest如果发现一直动不了&#xff0c;切换网络试一下&#xff0c;个人热点尝试一下。 按下图的选项按需引入自…

Nacos快速入门(windows)

Nacos是 Dynamic Naming and Configuration Service的简称。Nacos能快速实现动态服务发现、服务配置、服务元数据及流量管理 下载启动Nacos Nacos下载启动&#xff08;windows&#xff09; 以下两种随意选择一种即可从github上下载源码方式启动 git clone https://github.com…

【pycharm】在debug循环时,如何快速debug到指定循环次数

【pycharm】在debug循环时&#xff0c;如何快速debug到指定循环次数 【先赞后看养成习惯】求关注收藏点赞&#x1f600; 在 PyCharm 中&#xff0c;可以使用条件断点来实现在特定循环次数后停止调试。这可以通过在断点处右键单击&#xff0c;然后选择 “Add Breakpoint” -&g…

Jenkins+AWS CodeCommit(git)

问题 需要使用Jenkins搭建一套CI流&#xff0c;即通过git代码托管拉取代码&#xff0c;构建自定分支的代码&#xff0c;构建出jar&#xff0c;并进一步构建出docker镜像&#xff0c;并推送到docker私有库中。 准备 AWS云准备 这里假设已经在CodeCommit已经存在私有git代码仓…

Macbook M1 Pro使用brew安装Docker并安装Nacos【超详细图解】

目录 一、安装 Docker 二、修改 Docker 镜像地址 三、拉取镜像-举例 Nacos 1.拉取镜像 2.查看本地镜像 3.删除镜像 四、启动容器 1.启动 Nacos 容器&#xff1a; I.方式一【推荐】 II.方式二【懒人推荐】 2.访问 Nacos Web 控制台 3.进入容器和退出容器 五、配置…