内容简介:Time:2019/4/18Title: Reverse StringDifficulty: Easy
Time:2019/4/18
Title: Reverse String
Difficulty: Easy
Author: 小鹿
题目:Reverse String(反转字符串)
Write a function that reverses a string. The input string is given as an array of characters char[]
.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters .
char[]
的形式给出。 不要给另外的数组分配额外的空间,你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
Example 1:
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Slove:
▉ 问题分析
2)数组中的操作,需要原地修改数组,第一想到的就是用到指针,为什么能想到用指针呢?当你做这种数组的也好还是链表的也好,做多了之后,下意识的给出解决方法然后去看看可不可行。
▉ 算法思路
通过以上分析,得出两种方法:
- 字符串反转法
- 双指针法
字符串反转法:
1)字符串反转法很简单了,按照我们正常的思路走就可以了,首先输出数组中的字符拼接成字符串。
2)然后从字符串尾部开始遍历,正向输入数组。
双指针法:
1)定义两个指针,分别指向字符串头部和尾部。
2)两个指针指向的值进行交换。
3)注意终止条件。
- 如果为偶数,当头指针 - 1 等于尾指针时,反转完毕。
- 如果为奇数,当两个指针相等时,反转完毕。
▉ 测试用例
2)偶数个数的字符串。 3)奇数个数的字符串。 4)长度为 1 的字符串。
▉ 双指针法
var reverseString = function(s) { //判断输入的字符串是否为空 if(s.length ==0) return s; //定义两个指针 let low = 0; let high = s.length - 1; // 循环反转字符 while(true){ // 分为奇数/偶数两种可能 if(low === high || high + 1 === low) break; let temp = s[low]; s[low] = s[high]; s[high] = temp; low++; high--; } // 返回反转好的字符串 return s; };
▉ 字符串反转法
var reverseString = function(s) { //判断输入的字符串是否为空 if(s.length ==0) return s; let str = ""; // 输出字符串 for(let i in s){ str = str+`${s[i]}`; } // 反转字符串输入 for(let i = s.length - 1,j = 0;i >= 0;i--,j++){ s[j] = str.charAt(i); } //返回反转好的字符串 return s; };
▉ 性能分析
字符串反转法
- 时间复杂度:O(n)。遍历整个数组,时间复杂度为 O(n)。
- 空间复杂度:O(n)。输出数组需要额外的存储空间,如果用数组存储,需要开辟大小为 n 大小的内存空间。如果需要数组输出拼接字符串,空间复杂度为 O(1) 了。
双指针法:
- 时间复杂度:O(n)。需要遍历 n/2 的数据,时间复杂度为 O(n)。
- 空间复杂度:O(n)。只需常量级别的内存空间,空间复杂度为O(1)。
▉ 考查内容
2)数组的基本操作。
欢迎一起加入到 LeetCode 开源 Github 仓库,可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡,共同完善我们的开源小仓库!
Github: https://github.com/luxiangqia...
欢迎关注我个人公众号:「一个不甘平凡的码农」,记录了自己一路自学编程的故事。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Leetcode 344:Reverse String 反转字符串(python、java)
- 使用位运算、值交换等方式反转java字符串-共四种方法
- LeetCode每日一题: 反转字符串中的元音字母(No.345)
- PHP细节:foreach、(汉子)字符串反转、isset,empty用法区别以及0、‘’、null之间关系
- LeetCode 之 JavaScript 解答第151题 —— 反转字符串中的单词 (Reverse Words in a String)
- Go数组反转练习
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
HTML5与CSS3权威指南(上册) (第3版)
陆凌牛 / 机械工业出版社 / 2015-9-1 / CNY 89.00
本书是HTML 5与CSS 3领域公认的标杆之作,被读者誉为“系统学习HTML 5与CSS 3的最佳著作”和“Web前端工程师案头必备图书之_”。 前两版累计印刷超过15次,网络书店评论超过8000条,98%以上的评论都是五星级的好评。不仅是HTML 5与CSS 3图书领域当之无愧的领头羊,而且在整个原创计算机图书领域是佼佼者。 第3版首先从技术的角度根据最新的HTML 5和CSS 3......一起来看看 《HTML5与CSS3权威指南(上册) (第3版)》 这本书的介绍吧!