344 - 反转字符串(reverse-string)

Create by jsliang on 2019-07-22 19:06:50
Recently revised in 2019-07-22 19:24:28

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 暴力破解
3.2 解法 - 双指针

二 前言

返回目录

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

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

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

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

示例 2:
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 暴力破解

返回目录

  • 解题代码
var reverseString = function(s) {
  return s.reverse();
};
  • 执行测试

  • s['h', 'e', 'l', 'l', 'o']

  • return
['o', 'l', 'l', 'e', 'h']
  • LeetCode Submit
✔ Accepted
  ✔ 478/478 cases passed (168 ms)
  ✔ Your runtime beats 92.8 % of javascript submissions
  ✔ Your memory usage beats 22.13 % of javascript submissions (47 MB)
  • 知识点

  • reverse()reverse() 方法将数组中元素的位置颠倒,并返回该数组。该方法会改变原数组。reverse() 详细介绍

  • 解题思路

看到这道题的第一眼,我就觉得非常熟悉,我是否曾经做过?

然后我仔细审了下题:反转数组、原地操作。

所以我直接上了代码:

var reverseString = function(s) {
  return s.reverse();
};

最后就告诉我提交成功了,enm...是我变强了还是 LeetCode 的简单类型的题目重复了?

  • 进一步思考

如果不使用 JS 原生 API,有其他解法吗?

3.2 解法 - 双指针

返回目录

  • 解题代码
var reverseString = function(s) {
  for (let i = 0; i < (s.length - 1) / 2; i++) {
    let temp = s[s.length - 1 - i];
    s[s.length - 1 - i] = s[i];
    s[i] = temp;
  }
  return s;
};
  • 执行测试

  • s['h', 'e', 'l', 'l', 'o']

  • return
['o', 'l', 'l', 'e', 'h']
  • LeetCode Submit
✔ Accepted
  ✔ 478/478 cases passed (152 ms)
  ✔ Your runtime beats 98.85 % of javascript submissions
  ✔ Your memory usage beats 65.2 % of javascript submissions (46.6 MB)
  • 解题思路

首先,我们想到头尾调转。

当我们有数组:['0', '1', '2', '3', '4'] 的时候,我们需要调转的是:

  • '0''4'
  • '1''3'

然后,它们转换成编程来讲,即是:

  • '0''4'i === 0j === s.length - 1 - i
  • '1''3'i === 1j === s.length - 1 - i

OK,顺势推导,我们就可以完成这道题的题解。

最后,返回不返回 s 都是 OK 的,因为它要求的是原地遍历,最终 LeetCode 会取传进去的参数 s 进行查看。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-22 19:24:29

results matching ""

    No results matching ""