代码编织梦想

背景

俗话说,温故而知新。chatGPT效果太惊艳了!简直就是碾压的效果。但是还要有希望,先拾取,再创新。先了解,再超越吧。

ps: 再刷最后一遍算法题思路。顺便基于chatGPT3.5感受一下大模型的魔力。

字符串基础

C/C++每个字符串都以‘\0’作为结尾,这样就能很方便的找到字符串的最后尾部。由于这个特点,每个字符串都有一个额外字符的开销,稍不留神还会造成字符串的越界。如下,要想正确把0123456789复制到数组str中,需要声明一个长度为11字节的数组。

char str[10];
strcpy(str,"0123456789");

字符串数组与字符串指针

为节省内存,C/C++把常量字符串放在单独的一个内存区域。当几个指针赋值给相同的常量字符串时,他们实际会指向相同的内存地址。但是用常量内存初始化数组,情况却有所不同。

运行如下代码,会得到的结果是?

int main()
{
    char str1[]="hello world";
    char str2[]="hello world";

    char* str3="hello world";
    char* str4="hello world";

    if(str1==str2)
        printf("str1 and str2 are same.\n");
    else
        printf("str1 and str2 are not same.\n");

    if(str3==str4)
        printf("str3 and str4 are same.\n");
    else
        printf("str3 and str4 are not same.\n");

    return 0;    
}

str1和str2是两个字符串数组,我们会为它们分配两个长度为12字节的空间,并把“hello world”的内容分别复制到数组中去。这是两个初始地址不同的数组,因此str1和str2的值不相同。

str3和str4是两个指针,我们无须为它们分配内存以存储字符串的内容,而只需把它们指向“hello world”在内存中的地址就可以了。由于“hello world”是常量字符串,它在内存中只有一个拷贝,因此str3和str4的值相同。

算法题:替换空格

题目:请实现一个函数,把字符串中的每个空格替换成“%20”。例如,输入“We are happy.”,则输出“We%20are%20happy."。

思路:看到这个题目,我们首先应该想到原来一个空格字符,替换后变成了'%', '2', '0'这3个字符,因此字符串会变长。如果在原来的字符串上进行替换,则有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串,并在新的字符串上进行替换,那么我们可以自己分配足够多的内存。所以,要先明确出题者的需求。假如要在原字符串上进行替换,并保证输入的字符串后面有足够多的空余内存。

时间复杂度为O(n^2)的解法

最直观的做法是从头到尾扫描字符串,每次碰到空格字符的时候进行替换。由于把1个字符替换成3个字符,我们必须把后面所有字符都后移2字节,否则就会有2个字符被覆盖了。假设字符串的长度是n。对每个空格字符,需要移动后面O(n)个字符,因此对于含有O(n)个空格字符串而言,总的时间效率是O(n^2)。

44060db32f1a55e3dbd25dfaa5da0caf.png

时间复杂度为O(n)的解法

可以先遍历一次字符串,统计出字符串中空格的总数。然后从字符串的后面开始复制和替换。准备两个指针:p1和P2。P1指向原字符串的末尾,而P2指向替换之后的字符串的末尾。

接下来向前移动指针P1, 逐个把它指向字符复制到P2指向的位置,直到碰到第一个空格为止。碰到第一个空格之后,把p1向前移动一格,在P2之前插入字符串“%20”。由于“%20”的长度是3,同时把P2向前移动3格。如此P1接着向前复制,直到碰到第二个空格。当P1和P2指向同一个位置,表明所有空格都已经替换完毕。

36058c1f0330f8c666ce41eebe88cbd4.png

这种算法所有的字符都只复制(移动)一次,因此这个算法的时间复杂度是O(n)。

/*length 为字符数组str的总容量,大于或等于字符串str的实际长度*/
void ReplaceBlank(char str[], int length)
{
    if(str == nullptr && length <= 0)
        return;

    /*originalLength 为字符串str的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(str[i] != '\0')
    {
        ++ originalLength;

        if(str[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 为把空格替换成'%20'之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(str[indexOfOriginal] == ' ')
        {
            str[indexOfNew --] = '0';
            str[indexOfNew --] = '2';
            str[indexOfNew --] = '%';
        }
        else
        {
            str[indexOfNew --] = str[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}

相关题目: 两个排序数组在其中一个上面完成有序合并

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

解答思路:

如果考虑A1,A2的从前往后进行比较插入,那么就会出现多次复制数字的情况,更好的办法就是从尾到头比较A1, A2中的数字,并把较大的数字复制到A1中合适的位置。从而减少移动的次数,提升效率。

彩蛋:chatGPT做算法

同样的题目,抛给chatGPT3.5,它首先给出了一个最容易实现的思路,然后在两轮人工提醒下,不断优化,得到了我们上面所述的最优解。

80fdc29b00a6c3b063bd9f99dcbc610c.png
a57de891608670e4e6b65345ff8a0141.png
329d0b7a3d1912513524cc5c31d99a9f.png
d94a7f089c942948f38df5be8961513c.png

点评一下chatGPT的回答:

前两轮chatGPT的回答都是正确的。但是第三轮的解答是错误的

比如,当发现arr1[i]大于arr2[j]时候,它为了减少arr1往后的移动次数,刻意不让arr1[i+1:]中元素都向右移动,而是要从arr1[i+1:]找到一个小于等于arr2[j]的数,这里因为arr1是有序数组,后面的数不可能比前面的数小,明显chatGPT的逻辑发生了混乱。

其实第三轮优化由于我的网络不太稳定,让chatGPT重新生成了3次回答,上面展示的是第3次生成的比较完整的回复,但是我录下了它前面2次回答的过程,虽然没写全,但是思路就是我们上面提到的双指针,从后往前对两个数组进行比较插入的方法。可能多次让它重新生成答案,误导了它,它以为这个回答思路不好吧。

前2次都因为网络问题只产生了一半答案就断了。如下:

第1次生成回答

4e76f702ba44ce5d0a97277a4b9ad51e.jpeg

第2次生成回答:

cafce2fc55fe5b0d0541a8b4ccadb67e.jpeg

看到这里,大家是什么感受?

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u010420283/article/details/129678137

字符串搜索算法boyer-moore由浅入深-爱代码爱编程

这篇长文历时近两天终于完成了,前些天帮伯乐在线翻译一篇文章《为什么GNU grep如此之快?》,里面提及到grep速度快的一个重要原因是使用了Boyer-Moore算法作为字符串搜索算法,兴趣之下就想了解这个算法,发现这个算法一开始还挺难理解的,也许是我理解能力不是很好吧,花了小半天才看懂,看懂了过后就想分享下,因为觉得这个算法真的挺不错的,以前一

数据结构和算法面试题系列—字符串_weixin_33852020的博客-爱代码爱编程

这个系列是我多年前找工作时对数据结构和算法总结,其中有基础部分,也有各大公司的经典的面试题,最早发布在CSDN。现整理为一个系列给需要的朋友参考,如有错误,欢迎指正。本系列完整代码地址在 这里。 0 概述 字符串作为数据结构中的基础内容,也是面试中经常会考察的基本功之一,比如实现 strcpy,strcmp等基本函数等,回文字符串

一篇文章带你了解JavaScript中的基础算法之“字符串类”-爱代码爱编程

作者 | Jeskson 来源 | 达达前端小酒馆 1 算法可以干什么呢?提高什么?有什么好处呢? 前端的同学需要提升编程核心内功,建立和健全算法知识体系,基础算法、数据结构、进阶算法,由浅入深讲解,透彻理解抽象算法,算法面试是关键一环,冲击大厂前端offer。 学习算法前掌握ES6哦!需要掌握单元测试的语言,Jest Jes

LeetCode算法刷题之旅:由浅入深-爱代码爱编程

LeetCode算法刷题之旅 文章目录 LeetCode算法刷题之旅简单题题1 两数之和题7 整数反转题9 回文数题13 罗马数字转整数 简单题 题1 两数之和 2020/4/1 18:30 给定一个整数数组nums和一个目标值target,请你在数组中找出和为目标值的那两个整数,并返回他们的数组下标。每种输入只产生一个答案

c++如何让字符串重复输出_字符串:KMP算法还能干这个!-爱代码爱编程

给「代码随想录」一个星标吧! ❝ 不瞒你说,重复子串问题,KMP很拿手 ❞ 题目459.重复的子字符串 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。 示例 1:输入: "abab"输出: True解释: 可由子字符串

Python 编程1000例(4):比较数字和字符串大小-爱代码爱编程

文章目录 一、比较数字大小二、比较字符串大小三、统计和筛选学生成绩 本系列文章通过 1000(一篇文章表示 1 个实例) 个实例 ,为读者提供较为详细的练习题目,以便读者举一反三,深度学习。本系列的文章涉及到 Python 知识点包括:Python 语言基础、运算符和表达式、语句和程序结构、列表和元组、字典和集合、字符串、正则表达式、函数、面向

算法入门一:顺序结构:-爱代码爱编程

文章目录 算法入门一:顺序结构:引言:顺序结构:1.洛谷 p5703 java 苹果采购问题:2.洛谷 p5704 java 字母转换问题3.洛谷 p5706 java 再分肥宅水4.洛谷 p1425 java 小鱼的游泳时间5.洛谷 p5708 java 三角形面积6.洛谷 p1421 java 小玉买文具7.洛谷 p5709 java Appl

动态规划算法-爱代码爱编程

一、前言 动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。 二、解析动态规划算法 1.特点 ①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解) ②所有问题都只需要解决一次(解决一次就是只需要由后面所说

c++ kmp算法字符匹配_字符串:都来看看kmp算法的看家本领-爱代码爱编程

在一个串中查找是否出现过另一个串,这是KMP的看家本领。 题目:28. 实现 strStr() 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。 示例 1:输入

c++ kmp算法字符匹配_通用高效字符串匹配算法sunday,比较kmp和bm算法而言,简单了许多...-爱代码爱编程

提起字符串匹配,可能很多人都会想到KMP算法 O(m+n),但是其实KMP并不常用,因为依然是慢的,常用的其实是BM算法 O(m/n)(Boyer-Moore算法),这就是很多文本编辑器的查找功能采用的算法,而Sunday算法是在其之上又做了一些改动。 思路 先说下BM算法 其核心就是两个启发策略: (1)坏字符算法 当出现一个

【数据结构】二叉树 上篇_二叉树可用顺序方式存储,也可使用链式存储,本关使用二叉树的链式存储方式。结点数-爱代码爱编程

文章目录 二叉树的存储方式二叉树的定义常见的二叉树满二叉树完全二叉树二叉搜索树平衡二叉搜索树(AVL树)红黑树 二叉树的遍历方式深度优先(DFS)广度优先(BFS) 二叉树的递归遍历leetcode