反转字符串 (LeetCode 344)

简介: 反转字符串 (LeetCode 344)

反转字符串 (LeetCode 344)

Description

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

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

Sample Input 1

s = ["h","e","l","l","o"]

Sample Output 1

["o","l","l","e","h"]

Sample Input 2

s = ["H","a","n","n","a","h"]

Sample Output 2

["h","a","n","n","a","H"]

Tips

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

算法思想:

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

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

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

真正自己写的时候,要保证理解可以实现是相应的功能。

接下来再来讲一下如何解决反转字符串的问题。

在反转链表中,使用了双指针的方法。

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

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

对于字符串,我们定义两个指针(也可以说是索引下标),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。

不难写出如下C++代码:

void reverseString(vector<char>& s) {
    for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
        swap(s[i],s[j]);
    }
}

循环里只要做交换s[i] 和s[j]操作就可以了,那么我这里使用了swap 这个库函数。大家可以使用。

因为相信大家都知道交换函数如何实现,而且这个库函数仅仅是解题中的一部分, 所以这里使用库函数也是可以的。

swap可以有两种实现。

一种就是常见的交换数值:

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

一种就是通过位运算:

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

这道题目还是比较简单的,但是我正好可以通过这道题目说一说在刷题的时候,使用库函数的原则。

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

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

本着这样的原则,我没有使用reverse库函数,而使用swap库函数。

在字符串相关的题目中,库函数对大家的诱惑力是非常大的,因为会有各种反转,切割取词之类的操作,这也是为什么字符串的库函数这么丰富的原因。

相信大家本着我所讲述的原则来做字符串相关的题目,在选择库函数的角度上会有所原则,也会有所收获。

C++代码如下:

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};

Java代码代码如下:

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果,并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ,存入b中,此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

// 第二种方法用temp来交换数值更多人容易理解些
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while(l < r){
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

Created by Ss1Two on 2023/2/8

目录
相关文章
|
Java Linux Maven
要自定义编译和打包Seata-All
要自定义编译和打包Seata-All
297 2
|
iOS开发 MacOS Python
在Mac 上搭建Pygame开发环境(含安装错误的解决办法)
在Mac 上搭建Pygame开发环境(含安装错误的解决办法)
1229 0
|
8月前
|
Arthas 监控 Java
记一次内存利用率问题排查
记一次内存利用率问题排查
|
数据可视化 Cloud Native Devops
云效流水线 Flow 测评
阿里云云效是一站式DevOps平台,提供项目协作、代码管理、流水线Flow等工具,支持公共云和专有云,助力企业实现研发敏捷。云效Flow是自动化CI/CD工具,通过可视化和YAML编排易于新手使用。在测评中,Flow因简单易用、功能齐全和与阿里云产品集成的性能得到好评,适合小团队低成本项目。相较于其他CI/CD工具,Flow在成本和功能上有竞争力,值得推荐。
644 4
|
SQL XML Java
Xml 映射文件中,除了常见的 select|insert|updae|delete 标签之外,还有哪些标签?
Xml 映射文件中,除了常见的 select|insert|updae|delete 标签之外,还有哪些标签?
269 0
|
分布式计算 大数据 数据处理
Apache Spark在大数据处理中的应用
Apache Spark是大数据处理的热门工具,由AMPLab开发并捐赠给Apache软件基金会。它以内存计算和优化的执行引擎著称,提供比Hadoop更快的处理速度,支持批处理、交互式查询、流处理和机器学习。Spark架构包括Driver、Master、Worker Node和Executor,核心组件有RDD、DataFrame、Dataset、Spark SQL、Spark Streaming、MLlib和GraphX。文章通过代码示例展示了Spark在批处理、交互式查询和实时数据处理中的应用,并讨论了其优势(高性能、易用性、通用性和集成性)和挑战。【6月更文挑战第11天】
431 6
|
SQL 数据挖掘
|
编解码 自然语言处理 算法
虚拟数字人之《手语翻译官》的技术实践
虚拟数字人之《手语翻译官》的技术实践
20703 0
虚拟数字人之《手语翻译官》的技术实践
|
存储 Java 程序员
Java 17 版本的新特性
Java 17 版本的新特性
616 0
|
存储 文件存储
Jmeter之实现参数化的不同方式详解
Jmeter参数化定义:动态的获取、设置或生成数据,是一种由程序驱动代替人工驱动的数据设计方案,提高脚本的编写效率以及编写质量。适用场景:当提交的数据量较大时,每次修改太麻烦,可以使用参数化。 本文介绍实现参数化的4种方式:1、用户定义的变量;2、CSV数据文件设置;3、用户参数;4、函数:计数器函数/随机数/时间戳。。。
535 0
Jmeter之实现参数化的不同方式详解