代码随想录 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)的算法了,因为每次添加元素都要将添加元素之后的所有元素整体向后移动。
其实很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
这么做有两个好处:
- 不用申请新数组。
- 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。
代码讲解:(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);
}
题解:
相关文章:

代码随想录 Day17 字符串 | LC344 反转字符串 LC541 反转字符串II 卡码网54替换数字
一、反转字符串 题目: 力扣344:反转字符串 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题…...

LeetCode 刷题汇总——题目序号顺序版
剑指 Offer——和为 S 的两个数字 剑指 Offer——数字在排序数组中出现的次数 剑指 Offer——和为 S 的连续正数序列 剑指 Offer——最小的 K 个数 剑指 Offer——连续子数组的最大和 剑指 Offer——数组中的逆序对 LeetCode 1——两数之和 LeetCode 2——两数相加 LeetCode 3…...

【Java】JDK1.8 HashMap源码,put源码详细讲解
📝个人主页:哈__ 期待您的关注 在Java中,HashMap结构是被经常使用的,在面试当中也是经常会被问到的。这篇文章我给大家分享一下我对于HashMap结构源码的理解。 HashMap的存储与一般的数组不同,HashMap的每一个元素存…...

自定义注解进行数据转换
前言: Java注解是一种元数据机制,可用于方法,字段,类等程序上以提供关于这些元素的额外信息。 以下内容是我自己写的一个小测试的demo,参考该文章进行编写:https://blog.csdn.net/m0_71621983/article/details/1318164…...

React - 你知道在React组件的哪个阶段发送Ajax最合适吗
难度级别:中级及以上 提问概率:65% 如果求职者被问到了这个问题,那么只是单纯的回答在哪个阶段发送Ajax请求恐怕是不够全面的。最好是先详细描述React组件都有哪些生命周期,最后再回过头来点题作答,为什么应该在这个阶段发送Ajax请求。那…...

spa、vue、elementUi
spa (single page application). 动态重写当前页面而非从服务器重新加载整个新页面。使应用程序更像一个桌面应用程序。所有的html、javascript、css通过单个页面检索加载资源。前端页面使用ajax与后端通信。一个项目只有一个html页面。所有的页面跳转都通过路由导航。 vue可用…...

tcp接受命令执行并回显
为了实现循环执行命令并能够多次从TCP客户端接收命令,您需要对上面的代码进行一些修改。下面是一个修改后的示例,它将在接收到新的TCP连接后进入一个循环,不断地读取命令、执行命令,并将结果发送回客户端,直到客户端断…...

LLMs之ToolAlpaca:ToolAlpaca(通用工具学习框架/工具使用语料库)的简介、安装和使用方法、案例应用之详细攻略
LLMs之ToolAlpaca:ToolAlpaca(通用工具学习框架/工具使用语料库)的简介、安装和使用方法、案例应用之详细攻略 目录 ToolAlpaca的简介 0、《ToolAlpaca: Generalized Tool Learning for Language Models with 3000 Simulated Cases》翻译与解读 1、数据集列表 2…...

TCP/IP协议介绍
TCP/IP协议 先看:程序员必备基础知识-TCP/IP协议详解.(超详细) 太厉害了,终于有人能把TCP/IP协议讲的明明白白了! 面试官:如何理解TCP/IP协议? 一个很全的介绍博客:史上最全的TCP/IP协议原理 对TCP三次握…...

选择排序解读
在计算机科学中,排序算法是一种将数据元素按照某种顺序排列的算法。今天,我们要探讨的是选择排序(Selection Sort),这是一种简单直观的排序方法,通过不断选择剩余元素中的最小(或最大࿰…...

Vue项目自动注入less、sass、scss、stylus全局变量
一、Vue2项目 // vue.config.js const path require(path) module.exports {css: {loaderOptions: {// 给 sass-loader 传递选项sass: {// / 是 src/ 的别名// 所以这里假设有 src/assets/style/var.sass 这个文件// 注意:在 sass-loader v8 中,这个选…...

DXP学习002-PCB编辑器的环境参数及电路板参数相关设置
目录 一,dxp的pcb编辑器环境 1,创建新的PCB设计文档 2,PCB编辑器界面 1)布线工具栏 2)公用工具栏 3)层标签栏 编辑 3,PCB设计面板 1)打开pcb设计面板 4,PCB观…...

Flutter 使用flutter_swiper_null_safety 实现轮播图
目录 引入flutter_swiper_null_safety 在pubspec.yaml文件中dependencies下添加以下依赖 然后执行命令进行下载 实现轮播图 引入flutter_swiper_null_safety 在pubspec.yaml文件中dependencies下添加以下依赖 flutter_swiper_null_safety: ^1.0.2 然后执行命令进行下载 flu…...

Maven的scope详解
依赖范围介绍 maven 项目不同的阶段引入到classpath中的依赖是不同的,例如,编译时,maven 会将与编译相关的依赖引入classpath中,测试时,maven会将测试相关的的依赖引入到classpath中,运行时,mav…...

如何修复在Deepin系统中因`apt-get autoremove systemd`导致的启动问题
博主猫头虎的技术世界 🌟 欢迎来到猫头虎的博客 — 探索技术的无限可能! 专栏链接: 🔗 精选专栏: 《面试题大全》 — 面试准备的宝典!《IDEA开发秘籍》 — 提升你的IDEA技能!《100天精通鸿蒙》 …...

LeetCode 每日一题 ---- 【2923. 找到冠军 I】
LeetCode 每日一题 ---- 【2923. 找到冠军 I】 2923.找到冠军I方法一:暴力求解 2923.找到冠军I 方法一:暴力求解 从头遍历一遍二维数组,如果发现 gird[x][y] 1,说明 x 队赢过 y 队,下面我们就只需要子再判断一下是否…...

CMakeLists常用命令
# 设置cmake最低版本 cmake_minimum_required(VERSION 3.2)# project命令用于指定cmake工程的名称,实际上,它还可以指定cmake工程的版本号(VERSION关键字)、 #简短的描述(DESCRIPTION关键字)、主页URL&…...

英语 倒装结构中的主语和助动词,用于强调 inversion
I am used to travelling by air and only on one occasion have I ever felt frightened. 1、翻译为中文:我习惯了乘坐飞机旅行,只有在一次经历中我感到过害怕。 2、分析时态和句子语法是否正确:该句子使用了现在完成时(I am u…...

SQL注入---HTTP报头注入
文章目录 目录 文章目录 一.uagent注入 二.refeer注入 三.Cookie注入 前文中提到万能密钥的工作原理,然而万能密钥仅在源代码中没有代码审计,此时才被称之为万能密钥,而代码中有代码审计时需要分以下几种情况讨论 一.uagent注入 先看代码&a…...

docker安装sentinel
文章目录 前言安装docker指令安装制作docker-compose.yaml文件 查看网站 前言 Sentinel 是阿里巴巴开源的一款轻量级流量控制和熔断降级工具,可用于保护分布式系统中的服务。它可以帮助开发人员解决在分布式架构中面临的流量管理、服务保护、性能优化等问题。 安装…...

达梦的归档日志参数ARCH_RESERVE_TIME测试
达梦的参数ARCH_RESERVE_TIME测试 前面有提到和oracle相比,达梦的归档日志相关参数有个比较特别,可以通过设置它去规定归档日志的保留时间。 ARCH_RESERVE_TIME:归档日志保留时间,单位分钟,取值范围 0~2147483647。只…...

Linux网络 基础概念
目录 背景知识 互联网的发展 局域网和广域网 网络拓扑 网络协议栈 协议的概念 网络协议的分层 网络与操作系统的联系 网络传输的基本流程 IP地址和MAC地址 以太网通信 数据包的封装和分用 跨网段传输 背景知识 互联网的发展 计算机网络是计算机技术和通信技术相…...

装机指导。
everything winrar snipaste cmake git tortoisegit tortoisesvn inno setup vs2022 安装的时候注意sdk路径一定要默认!! 否则你会发现在你的sdk安装路径的根盘符下会多出一个Windows Kits,强迫症接受不了 默认的会跟已有的装在一起…...

解决windows docker context deadline exceeded问题
首先确保开启了wsl。cmd 直接输wsl,进入虚拟命令行代表开启 配置镜像 内容如下: {"builder": {"gc": {"defaultKeepStorage": "20GB","enabled": true}},"experimental": false,"f…...

django基于python的法院执法案件管理系统
本课题使用Python语言进行开发。代码层面的操作主要在PyCharm中进行,将系统所使用到的表以及数据存储到MySQL数据库中,方便对数据进行操作本课题基于WEB的开发平台,设计的基本思路是: 框架:django/flask 后端ÿ…...

tcp early retransmit 和 rack 中神奇的 1/4 minrtt
雨中跑步十公里,沿河看柳,发了一则朋友圈: 为什么采用 1/4 minrtt 作为重传和探测的延时,上图解释的已经很清楚了,主要还是怕乱序,关于乱序的度量,上图解释得非常清楚,乱序预期可在…...

【强化学习实践】Gym+倒立单摆+创建自己的环境
一、Gym Gym是OpenAI开发的一个强化学习算法测试环境集合包。Gym提供了多种标准的环境,包括经典的游戏(如Atari游戏)、机器人模拟任务以及其他各种类型的问题,供开发者测试和训练强化学习智能体。在Gym环境中,开发者可…...

实习记录小程序|基于SSM的实习记录小程序设计与实现(源码+数据库+文档)
知识管理 目录 基于SSM的习记录小程序设计与实现 一、前言 二、系统设计 三、系统功能设计 1、小程序端: 2、后台 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取: 博主介绍:✌️大厂码农|毕…...

Netty NioEventLoop详解
文章目录 前言类图主要功能NioEventLoop如何实现事件循环NioEventLoop如何处理多路复用Netty如何管理Channel和Selector管理Channel管理Selector注意事项 前言 Netty通过事件循环机制(EventLoop)处理IO事件和异步任务,简单来说,就是通过一个死循环&…...

互联网大厂常见面试题目
1. CPU 的内存结构分为哪几层,分别是用于放什么数据的,如果一个函数里面有全局变量,局部变量和静态变量数据是如何存放的 2.C多态的实现原理是什么,父类是如何找到子类的虚函数实现的 3.操作系统中的虚拟内存实现机制是什么&…...