本文共 1362 字,大约阅读时间需要 4 分钟。
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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”]
方法一:
执行用时 :44 ms/48 ms, 击败了75.10%/33.85% 的用户, 内存消耗 :6.3 MB, 击败了8.20%的用户最常用的方法,性能中规中矩
func reverseString1(s []byte) { l := len(s) for i := 0; i < l/2; i++ { s[i], s[l-1-i] = s[l-1-i], s[i] }}
方法二:
执行用时 :40 ms/32 ms, 击败了93.00%/100.00% 的用户, 内存消耗 :6.3 MB, 击败了8.20%的用户将循环条件
l/2
的值单独放入一个变量x
,执行效率直接爬升第一,可见循环时应尽量减少计算
func reverseString2(s []byte) { l := len(s) x := l / 2 for i := 0; i < x; i++ { s[i], s[l-1-i] = s[l-1-i], s[i] }}
方法三:
执行用时 :44 ms/36 ms, 击败了75.10%/98.96% 的用户, 内存消耗 :6.3 MB, 击败了8.20%的用户语句最省,不再由变量
l
存储数组长度的值,性能比方法二高,但没想到竟然比方法一性能高
func reverseString3(s []byte) { for i := 0; i < len(s)/2; i++ { s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i] }}
方法四:
执行用时 :76 ms/68 ms/44 ms, 击败了8.95%/13.49%/75.1% 的用户, 内存消耗 :6.3 MB/6.2 MB/6.3MB, 击败了8.20%的用户根据方法二的原理,原本想索性把
l-1
的计算也省了,但如果这样就必须要加个if
条件判断,这反而导致了性能直线下降。
func reverseString4(s []byte) { l := len(s) - 1 if l < 0 { return } x := l / 2 for i := 0; i <= x; i++ { s[i], s[l-i] = s[l-i], s[i] }}
l
指切片长度,i
指索引
l/2
的次数,循环时l-1-i
和i
位置的值互换即可。 我们借用本题对增减变量、增减if
条件语句进行了性能测试,结果还是明确的:
多次循环的地方尽量不要计算,尽量减少非必要条件语句的使用。
转载地址:http://btkpi.baihongyu.com/