摘要:小鹿题目反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组的形式给出。如果为奇数,当两个指针相等时,反转完毕。测试用例空字符串。奇数个数的字符串。长度为的字符串。考查内容对字符串的基本操作。
Time:2019/4/18
Title: Reverse String
Difficulty: Easy
Author: 小鹿
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:
1)反转字符串,第一想到的就是将字符窗倒序存储到数组中,可以先输出,然后再 for 循环加入到数组中。题目中要求需要原地修改输入数组,那么我们再想一个办法。2)数组中的操作,需要原地修改数组,第一想到的就是用到指针,为什么能想到用指针呢?当你做这种数组的也好还是链表的也好,做多了之后,下意识的给出解决方法然后去看看可不可行。
通过以上分析,得出两种方法:
字符串反转法
双指针法
字符串反转法:
1)字符串反转法很简单了,按照我们正常的思路走就可以了,首先输出数组中的字符拼接成字符串。
2)然后从字符串尾部开始遍历,正向输入数组。
双指针法:
1)定义两个指针,分别指向字符串头部和尾部。
2)两个指针指向的值进行交换。
3)注意终止条件。
如果为偶数,当头指针 - 1 等于尾指针时,反转完毕。
如果为奇数,当两个指针相等时,反转完毕。
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)。
1)对字符串的基本操作。2)数组的基本操作。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/103729.html
摘要:算法思路两种方法一般反转递归法一般解决定义三个指针,分别为,存储当前结点,指向反转好的结点的头结点,存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时,返回当前节点判断当前的链表是否为递归找到尾结点,将其存储为头结点。 Time:2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 题目:Reverse...
摘要:小鹿题目翻转字符串里的单词给定一个字符串,逐个翻转字符串中的每个单词。说明无空格字符构成一个单词。遇到空格之后,将单词进行倒序拼接。消除尾部的空格。测试用例空字符串。中间空格大于的字符串。 Time:2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿 题目:Reverse Words In a ...
摘要:反转字符串公众号爱写编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组的形式给出。解题思路第一个字符与最后一个交换位置,继而第二个与倒数第二个交换位置,一直交换到到中位数结束。持续交换它们所指向的元素,直到这两个指针相遇。 Leetcode 344:Reverse String 反转字符串 公众号:爱写bugWrite a function that reverses ...
摘要:反转字符串公众号爱写编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组的形式给出。解题思路第一个字符与最后一个交换位置,继而第二个与倒数第二个交换位置,一直交换到到中位数结束。持续交换它们所指向的元素,直到这两个指针相遇。 Leetcode 344:Reverse String 反转字符串 公众号:爱写bugWrite a function that reverses ...
摘要:先去空白,去掉空白之后取第一个字符,判断正负符号,若是英文直接返回,若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言 一直以来,前端开发的知识储备在数据结构以及算法层面是有所暂缺的,可能归根于我们的前端开发的业务性质,但是我认为任何的编程岗位都离不开数据结构以及算法。因此,我作为...
阅读 1838·2021-09-23 11:21
阅读 700·2019-08-30 15:55
阅读 834·2019-08-29 15:40
阅读 530·2019-08-29 12:56
阅读 3159·2019-08-26 12:00
阅读 3554·2019-08-23 18:24
阅读 2248·2019-08-23 17:08
阅读 1639·2019-08-23 17:03