共计 914 个字符,预计需要花费 3 分钟才能阅读完成。
字符串翻转
之前面试中会经常碰到字符串反转的问题,并且要求不可使用自带函数,一般这个时候都是采用从尾到头进行循环,然后赋值给一个新字符串的方法
代码是这样的(自豪的使用 PHP):
<?php
$str = 'segmentfault';
$strLen = strlen($str);
$newStr = '';
for ($i = $strLen - 1; $i >= 0; $i--) {$newStr .= $str{$i};
}
echo $newStr.PHP_EOL;
这样一个字符串反转就完成了,从一个字符串中尾部开始获取字符串一次向前,然后把拿到的字符串按照顺序放到新的字符串中,就对原来的字符串实现了反转
最近发现了另外一种实现字符串反转的思路,对字符串上的字符进行交换,第一位和最后以为进行交换,第二位和倒数第二位进行交换,以此类推,这样原本需要把所有的字符都拿出来放到新数组中的操作就变成了,一次操作两个字符进行交换,一次变两次操作效率加倍
下面用代码实现一下:
<?php
$str = 'segmentfault';
$strLen = strlen($str);
for ($i = 0; $i < $strLen; $i++) {
$head = $i;
$tail = $strLen - ($i + 1);
if ($head == $tail || $head > $tail) {break;}
$tmp = $str{$head};
$str{$head} = $str{$tail};
$str{$tail} = $tmp;
}
echo $str;
通过上面这段代码也实现了字符串反转,同时减少了循环次数,也就是平常说的时间复杂度从 O(n) 变成了 O(logn)
同时要注意的是,在上面的代码中,相当于设置了两个指针,一个指向头部也就是前面,一个指向尾部也就是后面,然后对这个两个指针进行换位置的操作,实现反转
代码中的判断是因为,由于字符串的长度不固定,可能会出现两个指针在中间相遇,比如字符串长度为 7,前面有三个字符,后面有三个字符,两个指针在操作完三个字符之后,就会来到中间的字符上,这个字符是不需要在进行反转的
另外一种情况是,左右两边长度相等,最后尾指针的位置就会在头指针的前面,也就是下标比头指针小,这个时候就已经反转完成,可以结束操作了
正文完