【一刷《剑指Offer》】面试题 4:替换空格

简介: 【一刷《剑指Offer》】面试题 4:替换空格

力扣对应链接:LCR 122. 路径加密 - 力扣(LeetCode)

牛客对应链接:替换空格_牛客题霸_牛客网 (nowcoder.com)

核心考点 :字符串相关,特性观察,临界条件处理。


一、《剑指Offer》内容


二、分析问题

虽然是替换问题,但是生成的字符串整体变长了。因替换内容比被替换内容长,所以一定涉及到字符串中字符的移动问题。移动方向一定是向后移动,所以现在的问题无非是移动多少的问题。

因为是 ' ' -> "%20",是 1 换 3,所以可以先统计原字符串中空格的个数(设为 n),然后可以计算出新字符串的长度。所以,new_length = old_length + 2*n

最后,定义新老索引(或者指针),各自指向新老空间的结尾,然后进行 old->new 的移动。如果是空格,就连续放入“%20”,其他平移即可。

当然,C++ 有很多容器,也可以从前往后通过开辟空间来进行解决,也就是使用空间来换取时间。但是,最好不要在面试场景下这么做。


三、代码

//力扣上的这道题目是1换1,不需要扩充数组
class Solution {
public:
    string pathEncryption(string path) {
        for(int i=0; i<path.size(); i++)
            if(path[i]=='.')
                path[i]=' ';
        return path;
    }
};
 
//牛客网上的这道题目和原题也不太一样,这里传入的是string,原题是char*
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        string res;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]==' ') res+="%20";
            else res+=s[i];
        }
        return res;
    }
};
 
//下面写法尽量贴近原题(注意:原题是char*,C++要考虑'\0')
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        if(s.size()==0) return s;
        int cnt=0; //记录空格个数
        for(auto c:s)
        {
            if(c==' ')
                cnt++;
        }
        int old_end=s.size()-1;
        for(int i=0; i<cnt*2; i++)
            s.push_back(' ');
        int new_end=s.size()-1;
        while(old_end>=0 && new_end>=0)
        {
            if(s[old_end]==' ')
            {
                s[new_end--]='0';
                s[new_end--]='2';
                s[new_end--]='%';
                old_end--;
            }
            else
            {
                s[new_end--]=s[old_end--];
            }
        }
        return s;
    }
};

四、扩展

有两个排序的数组 A1 和 A2,内存在 A1 的末尾有足够多的空余空间容纳 A2。请实现一个函数,把 A2 中的所有数字插入到 A1 中并且所有的数字是排序的。

和前面的例题一样,首先想到的办法可能是从前到尾复制数字,但这样就会出现多次复制一个数字的情况。

更好的办法是从尾到头比较 A1 和 A2 中的数字,并把较大的数字赋值到 A1 的合适位置。

C 库函数中内存拷贝 memmove() 函数与此题有共同点,函数功能就是:将起始地址 src 且长度为 count 的内存拷贝到起始地址 dst 处,并返回 dst,返回是为了实现链式表达式。

函数原型为:void* __cdecl memmove(void *dst, const void *src, size_t count;


五、举一反三

合并两个数字(包括字符串)时,如果从前往后复制每个数字(或字符)需要重复移动数字(或字符)多次,那么我们可以考虑从后往前复制,这样就能减少移动的次数,从而提高效率。


相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面