字符串替换算法思考


题目:URL中不允许出现空格等特殊字符,因此需要将用户输入的URL转义输出。如空格对应的ASCII码为32 即0x20,因此用%20代替。如 "we are one" 变换成"we%20are%20one"。要求程序的时间复杂度为O(n)。
思考:
方法一:从头到尾遍历,找到空格后,依次将空格后面元素后移两位,插入%20,然后遍历一遍即可完成。由于每次出现空格都需要将后面的所有元素做移动处理,因此这种方法的时间负责度为O(n^2)。
方法二:事先遍历一遍字符串,确定空格的个数,从而确定新字符串的长度,然后从尾部开始,逐一复制原始字符串元素到新的位置上,遇到空格时,新元素中插入0 2 %,原始元素指针后移一个单元即可。
前提:存储容量,确保原始字符数组大小足够容纳新的字符串。
这种算法的时间复杂度为O(n),很好的提高了效率。

#include "stdafx.h" #include <iostream> #include "string" using namespace std; void ReplaceBlank(char *p, int length); int _tmain(int argc, _TCHAR* argv[]) { char *str = "we are one"; char str2[20]; strcpy_s(str2,str); ReplaceBlank(str2,20); cout << str << endl; cout << str2; return 0; } void ReplaceBlank(char *p, int length) { if (p == NULL || length <= 0) return; //统计字符串长度 int original_length = 0; int num_blank = 0; int i = 0; while (p[i] != '\0') { if (p[i] == ' ') { num_blank++; } original_length++; i++; } int new_length = original_length + num_blank * 2; if (new_length > length) return; int original_index = original_length; int new_index = new_length; //移动或替换 时间复杂度O(n) while (original_index >= 0 && new_index > original_index) { if (p[original_index] == ' ') { original_index--; p[new_index--] = '0'; p[new_index--] = '2'; p[new_index--] = '%'; } else { p[new_index--] = p[original_index--]; } } }

题目2:有两个已经排序的数组A1 和 A2,A1的末尾有足够的空余空间容纳A2,现在要求将A2所有数字插入到A1中,并保持A1所有数组元素排序。

思路1:每次从A2中取一个元素,然后依次和A1中元素比较,找到合适位置后,移动插入位置后的所有元素,然后插入新元素,

循环进行,直至A2中所有元素均已插入到A1中。

思路2:

  1. 确定A1和A2各自的长度n1,n2,从而确定插入后的数组长度n=n1+n2;
  2. 三个指针,一个指向n1最后一个元素,一个指向n2最后一个元素,一个指向新数组的最后一个元素。
  3. 比较n1 n2最后一个元素的大小,将大的插入新数组中,然后指针移位
  4. 确保两个数组中所有元素全部插入后(n1<0,n2<0),程序结束。
void Conbine_Array(int *a, int A1_length, int *b, int A2_length)
{
    int new_length = A1_length + A2_length;

    int A1_index = A1_length - 1;
    int A2_index = A2_length - 1;
    int new_index = new_length - 1;

    while (A1_index >= 0 || A2_index >= 0)
    {
        if (A1_index >=0&& A2_index >=0)
        {
            if (a[A1_index] >= b[A2_index])
            {
                a[new_index--] = a[A1_index--];
            }
            else
            {
                a[new_index--] = b[A2_index--];
            }
        }
        else if (A1_index >= 0)
        {
            a[new_index--] = a[A1_index--];
        }
        else if (A2_index >= 0)
        {
            a[new_index--] = b[A2_index--];
        }
    
    }

}

优质内容筛选与推荐>>
1、谈《西游记》和泛项目
2、极路由1s(HC5661A)配置Pandorabox并如何使用校园网和pppoe拨号
3、DBScan聚类算法原理与实现整理
4、Java中Comparable接口和Comparator接口的简单用法
5、hdu 4759 大数+找规律 ***


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn