力扣算法系统刷题详细题解记录二(字符串、双指针法、栈与队列)

news/2024/11/14 13:17:18/

力扣算法系统刷题题解记录二(字符串、双指针法、栈与队列)

前言

参考顺序和资料:《代码随想录》
二刷要认真做笔记啦,加油!
笔记模板:

#### 解题思路#### 示意图#### 代码

四、字符串

344.字符串反转

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

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

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:
输入:[“h”,“e”,“l”,“l”,“o”]
输出:[“o”,“l”,“l”,“e”,“h”]

解题思路

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

毕竟面试官一定不是考察你对库函数的熟悉程度, 如果使用python和java 的同学更需要注意这一点,因为python、java提供的库函数十分丰富。

如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。

建议大家平时在leetcode上练习算法的时候本着这样的原则去练习,这样才有助于我们对算法的理解。

不要沉迷于使用库函数一行代码解决题目之类的技巧,不是说这些技巧不好,而是说这些技巧可以用来娱乐一下。

真正自己写的时候,要保证理解可以实现是相应的功能。
在反转链表中,使用了双指针的方法。

那么反转字符串依然是使用双指针的方法,只不过对于字符串的反转,其实要比链表简单一些。

因为字符串也是一种数组,所以元素在内存中是连续分布,这就决定了反转链表和反转字符串方式上还是有所差异的。

示意图

在这里插入图片描述

代码

class Solution {public void reverseString(char[] s) {int left = 0;int right = s.length-1;    //left和right双指针是下标while(left<right){char temp = s[left];s[left] = s[right];s[right] = temp; left++;right--;}}
}

541.字符串反转

给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

解题思路

每隔2k个字符的前k的字符,写了一堆逻辑代码或者再搞一个计数器,来统计2k,再统计前k个字符。
其实在遍历字符串的过程中,只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点,这样写,程序会高效很多。
所以当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。

示意图

请添加图片描述

代码

class Solution {public String reverseStr(String s, int k) {char[] ch = s.toCharArray();for(int i = 0; i < ch.length; i += 2 * k){int start = i;//这里是判断尾数够不够k个来取决end指针的位置int end = Math.min(ch.length - 1, start + k - 1);	//判断尾数的个数是否小于k个 尾数的个数和k-1个相比//用异或运算反转 while(start < end){ch[start] ^= ch[end];ch[end] ^= ch[start];ch[start] ^= ch[end];start++;end--;}}return new String(ch);}
}

以下是代码的具体分析:
char[] ch = s.toCharArray();:将字符串 s 转换为字符数组 ch,以便进行字符级别的操作。
for(int i = 0; i < ch.length; i += 2 * k):通过循环遍历字符串 ch,每次递增 i 的值为 2k,以处理长度为 2k 的子串。
int start = i;:将 start 初始化为当前子串的起始索引 i。
int end = Math.min(ch.length - 1, start + k - 1);:计算子串的结束索引 end。这里使用 Math.min() 函数来判断子串是否不足 k 个字符,如果是,则将 end 设置为子串的最后一个字符索引,否则设置为 start + k - 1。
while(start < end):进入一个循环,该循环通过异或运算来反转子串中的字符。
ch[start] ^= ch[end]; ch[end] ^= ch[start]; ch[start] ^= ch[end];:这三行代码使用异或运算来反转 ch[start] 和 ch[end] 两个字符的值,实现字符交换。
start++; end–;:递增 start,递减 end,用于处理下一对字符。
return new String(ch);:将字符数组 ch 转换回字符串,并作为方法的返回值。
总体而言,这段代码通过划分长度为 2k 的子串,然后使用异或运算反转子串中的字符,最终将整个字符串的一部分进行了反转操作。


http://www.ppmy.cn/news/293677.html

相关文章

mt7628/7688 PWM驱动

MT7628/MT7688中的pwm&#xff0c;datasheet写的很糟糕&#xff0c;不像三星&#xff0c;还给你来个编程的流程图&#xff0c;配置哪个寄存器都会告诉你&#xff0c;一坨寄存器丢给你.. 它的PWM分为两种模式&#xff0c;OLD和new,这里我们用简单的OLD模式&#xff0c;NEW模式没…

Servlet运行原理及常见API

文章目录 一. Servlet运行原理二. Servlet常用API1. HttpServlet1.1. Servlet的生命周期1.2. Post请求的构造 2. HttpServletRequest2.1. 获取请求信息2.2. 前端给后端传输数据的三种方式2.2.1. 发送Get请求通过query string传输数据2.2.2. 发送Post请求通过form提交数据2.2.3.…

无线网卡芯片rtl8821CU-linux驱动解决方案

最近想在笔记本上kali上使用无线网络&#xff0c;但是vmware的kali虚拟机是无法使用笔记本自带的无线网卡的&#xff0c;于是在淘宝上买了个usb外置无线网卡。但是&#xff0c;网卡买回来了&#xff0c;才发现官网给的linux驱动尼玛竟然无法编译&#xff0c;打电话给官方客服。…

酷派7269_评测:酷派7269的整体性能简介及性价比如何

简单的说一下关于酷派7269的整体性能简介及性价比如何这方面的讯息&#xff0c;不少朋友对于酷派7269的整体性能简介及性价比如何这方面的信息颇感兴趣的。小编今天就为此整理一些相关的讯息&#xff0c;希望对有需要的朋友有所帮助。 酷派7269配备了一块4.5英寸屏幕&#xff0…

酷派大神9976A刷机

酷派大神9976A刷机 元旦回家&#xff0c;听嫂子讲自己的手机变得越来越卡。当然听到这个抱怨的时候&#xff0c;作为一个程序猿&#xff0c;下意识会嗤之以鼻。虽然Android系统会越用越卡&#xff0c;不如iOS&#xff0c;但是真正的程序猿对这样的论断还是觉得嗤之以鼻&#x…

【USB-WIFI模块:rtl8723bu (无线网卡的基于 x6818的移植)

这里写自定义目录标题 wpa_supplicant运行于后台&#xff0c;它需要借助控制台工具wpa_cli来进行手动操作&#xff0c;使用wpa_cli来搜索、设置、和连接网络。 【USB-WIFI模块&#xff1a;rtl8723bu &#xff08;无线网卡的基于 x6818的移植&#xff09; 需要在 X6818 开发板上…

LAN8742替换LAN8720

LAN8742可以替换LAN8720吗&#xff1f; 肯定可以的&#xff0c;LAN8742就是8720的升级版 两者引脚是pin to pin兼容的 8742比8720多了一个wol网络唤醒功能&#xff0c;8742和电脑直连时可以使用直连网线&#xff0c;芯片自己交叉tx和rx信号线。 那么用8742的驱动可以驱动87…

rollup打包ts报错:Original error: Cannot use import statement outside a module

在 package.json 的 scripts 对应的命令行后面&#xff0c;加上 --bundleConfigAsCjs&#xff0c;如&#xff1a; "scripts": {"test": "echo \"Error: no test specified\" && exit 1","dev": "rollup -c -w…