09 Feb 2018
替换空格
一、题目
请实现一个函数,把字符串中的每个空格替换成”%20”,例如“We are young.”,则输出“We%20are%20young.”。
二、解题思路
Notzuonotdied的解题思路
核心思想:将时间复杂度为$O(n^2)$的问题修改为$O(n)$的问题。
首先,判断字符串是否为空,如果为空就直接返回。
之后,判断字符串中空格的数量。根据空格的数量判断该字符串中有没有足够的空间替换成“%20”。计算公式:$finalLength = blanksCounts * 2 + stringSize$。
如果有足够空间,计算出需要的空间。根据最终需要的总空间,维护一个索引在数组最后。从后到前,遇到非空的就把该值挪到指针指向的位置,然后指针向前一位;遇到“ ”,则指针前移,依次替换为“02%”。
Kotlin实现
/**
* 替换空格符号
*
* @param target 目标数组
* */
fun replaceBlank(target: CharArray) {
// 去掉占位符‘*’,计算实际的数组长度
var targetLength = target.size
target.forEach { char -> if (char == '*') targetLength-- }
// 如果是空就直接返回
if (target.isEmpty()) {
println("空数组~")
return
}
// 如果不为空就检查空字符的个数
var blankCount = 0
target.forEach { char -> if (char == ' ') blankCount++ }
// 如果空格的数量为0的话,直接退出
if (blankCount == 0) {
println("没有空格~")
return
}
// 计算替换后的最终长度
var finalLength = blankCount * 2 + targetLength
// 如果得出来的长度大于数组的长度,就直接返回
if (finalLength > target.size) {
println("越界了~")
return
}
targetLength--
finalLength--
while (finalLength > 0 && finalLength > targetLength) {
if (target[targetLength] == ' ') {
target[finalLength--] = '0'
target[finalLength--] = '2'
target[finalLength--] = '%'
} else {
target[finalLength--] = target[targetLength]
}
targetLength--
}
println(target)
}
fun main(args: Array<String>) {
/**
* 因为数组是固定长度的,所以采用‘*’作为空位
* */
// 前面出现空格
var string = " We are young!******"
replaceBlank(string.toCharArray())
// 中间出现空格
string = "We are young!****"
replaceBlank(string.toCharArray())
// 末尾出现空格
string = "We are young! ******"
replaceBlank(string.toCharArray())
// NULL
string = ""
replaceBlank(string.toCharArray())
// 越界情况
string = "We are young! "
replaceBlank(string.toCharArray())
// 连续的空格
string = "We are young! **************"
replaceBlank(string.toCharArray())
}
输出结果
%20We%20are%20young!
We%20are%20young!
We%20are%20young!%20
空数组~
越界了~
We%20are%20young!%20%20%20%20**
Til next time,
LinkWorld
at 21:00