壹 ? 引
今天做的一道题非常简单,原题来自leetcode第344题反转字符串,题目如下:
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]
我们先来分析题目,再来说说具体怎么做。
贰 ? 解题分析
简单分析题目其实说到底就是倒序排列数组,那么我们马上可以想到数组API reverse,单说实现我们完全可以这样:
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
s.reverse();
};
当然要是面试真遇到这题,肯定不允许这么做,我们可以把这道题理解为实现API reverse,所以还是得另辟途径。
倒序排列数组的本质,其实也是在做元素位置互换,有个规则,比如数组[1,2,3,4]
:
因为要倒序,所以是第一位与最后一位互换位置,第二位和第三位互换位置。
当然数组元素个数会有基数的情况,但这并不影响这个规律,比如[1,2,3,4,5]
还是如此,只是中间位的元素不用互换而已。
在实现代码前,官方已经提供了一个思路,双指针技巧,常规的循环比如for往往是从i=0
开始遍历,或者while倒序遍历,这两种都只有一个指针来表示当前遍历到了哪个索引。
而双指针则是从第一个元素与最后一个元素同时相对进行遍历,也就是成对的遍历,可以想象这样遍历的效率会大大提升。
我们已经知道了数组倒序排列是交换位置,那可以用i表示正序遍历,用一个j表示倒序遍历,每遍历一次交换两个元素,而满足遍历的条件仅仅是i<j
即可。
以数组[1,2,3,4]
来说,1与4遍历一次,2与3遍历一次,此时i为1,j为2,下一步i自增j递减i为2j为1很明显不符合条件。
再看数组[1,2,3,4,5]
,遍历2次后,i自增j递减都会变成3,同样不满足i<j,所以我们仅仅需要这个条件来决定是否还需要遍历。
说到这思路已经很清晰了,直接上代码:
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
var i = 0,
j = s.length - 1;
for (; i < j; i++, j--) {
[s[i], s[j]] = [s[j], s[i]];
};
};
我在阅读数组和字符串卡片的双指针技巧之前,一直不知道双指针是个啥,到现在心里才有答案。不过我在 JS leetcode 两数之和解答思路分析提供的第二种思路中也想到了从头和从尾同时遍历,虽然我是用了两个循环进行嵌套,不过还是有了点双指针的影子。
那么关于本题就说到这了。