剑指 Offer 05. 替换空格

【题目来源】

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

【题目内容】

【解题思路】

思路一：直接拷贝(执行用时：0 ms 内存消耗：5.6 MB)

• 将字符串的每一个字符串拷贝到目标字符串，如果为' '时，拷贝为'%20'，最后添加结尾符0，返回拷贝后的结果。

#define RES_MAX_SIZE 30000

char* replaceSpace(char* s){
    int strLen = strlen(s);
    char *res = (char*)malloc(sizeof(char) * RES_MAX_SIZE);
    int cur = 0;
    while (*s != 0) {
        if (*s == ' ') {
            res[cur++] = '%';
            res[cur++] = '2';
            res[cur++] = '0';
        } else {
            res[cur++] = *s; 
        }
        s++;
    }
    res[cur] = 0;
    return res;
}

【学习小结】

数组比Hash性能更好

相比于HashSet，使用数组绝对会有性能的提高，主要表现在如下的两个方面：

哈希表 (HashSet) 底层是使用数组 + 链表或者红黑树组成的，而且它的数组也是用不满的，有加载因子的。所以使用数组来代替哈希表，能节省空间

哈希表在判重的时候需要经过哈希计算，还可能存在哈希冲突的情况，而使用数组则可以直接计算得到 index 的内存位置，所以使用数组访问性能更好。

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/duo-chong-jie-fa-xun-xu-jian-jin-yi-zhi-dao-zui-yo/

调整执行顺序，性能提升

判断场景先执行nums[nums[cur]]，再执行nums[cur]，触发预取，提高性能。

将满足条件概率更大的条件放到前面，可以避免大量无效判断，提高性能。