Home

LinkWorld Algorithm Blog

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

scribble