浅谈网站开发的意义,抚州市建设局网站查询,网站模板怎么设计软件,网站买源代码 个人主页#xff1a;秋风起#xff0c;再归来~ 文章所属专栏#xff1a;《剑指offer》典型编程题的极练之路 个人格言#xff1a;悟已往之不谏#xff0c;知来者犹可追 克心守己#xff0c… 个人主页秋风起再归来~ 文章所属专栏《剑指offer》典型编程题的极练之路 个人格言悟已往之不谏知来者犹可追 克心守己律己则安 目录 一、C/C中字符数组与字符常量
二、面试题替换空格
2.1时间复杂度为 Q(㎡)的解法不足以拿到 Offer
2.2 创建新的数组解题
2.3时间与空间复杂度分别为O(N)和O(1)的算法(搞定offer就靠它了
编辑
三. 完结散花 一、C/C中字符数组与字符常量
为了节省空间C/C把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时它们实际上会指向相同的内存地址。但用常量内存初始化数组情况却有所不同。下面通过一个面试题来学习这一知识点。
#define _CRT_SECURE_NO_WARNINGS#includestdio.hint main()
{char* s1 abcdef;char* s2 abcdef;char* s3[] { abcdef };char* s4[] { abcdef };if (s1 s2){printf(s1与s2相等\n);}else{printf(s1与s2不相等\n);}if (s3 s4){printf(s3与s4相等\n);}else{printf(s3与s4不相等\n);}return 0;
}
如果我们运行下面代码的话结果是什么呢 为什么呢
我们先通过调试来理解一下 我们可以看到s1和s2的值相等说明它们指向了同一块内存地址
反之s3与s4所指向的空间则是不同的 那这又是为什么呢 首先我们知道常量是不能被改变的当内存中开辟了一片空间存放一个字符串常量并且有一个指针指向它有朝一日我们不小心又创建了一个相同的常量字符串并且用另一个指针指向它这时内存并不会再创建一片空间来存放这个常量字符串而是直接让另一个指针指向向前开辟的空间。 那为什么字符数组却不同呢那是因为字符数组是可修改的如果它们指向同一块空间有朝一日我想修改这个字符数组那另一个字符数组必然也会被修改 二、面试题替换空格 描述 请实现一个函数将一个字符串s中的每个空格替换成“%20”。 例如当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 数据范围:0≤en(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。 题目链接点击进入 在网络编程中如果URL参数中含有特殊字符如空格“#”等则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可识别的字符。转换的规则是在%后面跟上ASCLL码的两位十六进制的表示。比如空格的ASCLL码是32即十六进制的0x20因此空格被替换为%20再比如#的ASCLL为35即十六进制的0x23他在URL中被替换为%23。
看到这个题目我们首先应该想到的是原来一个空格字符替换之后变成%、2和0这3个字符因此字符串会变长。如果是在原来的字符串上进行替换就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换那么我们可以自己分配足够多的内存。由于有两种不同的解决方案我们应该向面试官问清楚让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换并且保证输入的字符串后面有足够多的空余内存。
2.1时间复杂度为 Q(㎡)的解法不足以拿到 Offer 现在我们考虑怎么执行替换操作。最直观的做法是从头到尾扫描字符每次碰到空格字符的时候进行替换。由于是把1个字符替换成3个字串符我们必须要把空格后面所有的字符都后移2字节否则就有两个字符被覆盖了。 举个例子我们从头到尾把We are happy,中的每个空格替换成%20。为了形象起见我们可以用一个表格来表示字符串表格中的每个格子表示一个字符如图 所示。 注:(a)字符串Weare happy.。(b)把字符串中的第一个空格替换成%20”。黄色背景表示需要移动的字符。(c)把字符串中的第二个空格替换成”%20。黄色背景表示需要移动一次的字符红色色背景表示需要移动两次的字符。 我们替换第一个空格这个字符串变成图(b)中的内容表格中黄色背景的格子表示需要进行移动的区域。接着我们替换第二个空格替换之后的内容如图2.3(c)所示。同时我们注意到用红色背景标注的happy”部分被移动了两次。 假设字符串的长度是n。对每个空格字符需要移动后面O(n)个字符:因此对于含有 0(n)个空格字符的字符串而言总的时间效率是 O(n’)。 当我们把这种思路阐述给面试官后他不会就此满意他将让我们寻找更快的方法。在前面的分析中我们发现数组中很多字符都移动了很多次能不能减少移动次数呢?答案是肯定的。我们换一种思路把从前向后替换改成从后向前替换。
2.2 创建新的数组解题
结合代码注释和图解就很容易理解这种算法了~ char* replaceSpace(char* s ) {// write code hereif(sNULL)return NULL;//先记录与字符串的大小int lenstrlen(s);//记录空格的数量int count0;int i0;while(s[i]!\0){if(s[i] )count;i;}//创建一个新的字符数组char* newStr(char*)malloc(sizeof(char)*(lencount*2));//将原字符串的内容拷贝进新的字符数组遇到空格就替换int j0;int end0;while(s[end]!\0){if(s[end] ){newStr[j]%;newStr[j]2;newStr[j]0;}else{newStr[j]s[end];}end;}return newStr;
}
2.3时间与空间复杂度分别为O(N)和O(1)的算法(搞定offer就靠它了 char* replaceSpace(char* s ) {// write code hereint end0;if(sNULL)return NULL;int count0;//记录空格的数量while(s[end]!\0)//找到字符串的末尾{if(s[end] ){count;}end;}//找到替换过后字符串的末尾int newEndend2*count;//从后往前移动字符并且替换空格while(end0endnewEnd){if(s[end] ){s[newEnd--]0;s[newEnd--]2;s[newEnd--]%;}else{s[newEnd--]s[end];}end--;}return s;
}
这个算法的核心在于如何高效地将字符串中的空格替换为%20同时保证不覆盖或遗漏任何字符。算法的原理可以概括为以下几个步骤
步骤一计算空格数量首先我们需要遍历一遍输入的字符串统计其中空格的数量。这是因为每个空格都将被替换为三个字符%、2 和 0所以我们需要知道有多少个空格以便计算替换后字符串的总长度。
步骤二计算新字符串长度接下来我们根据原始字符串的长度和空格的数量计算出替换后字符串的总长度。由于每个空格替换为三个字符所以新字符串的长度将是原始长度加上空格数量乘以2因为每个空格增加了两个字符。
步骤三从后向前遍历并替换然后我们从字符串的末尾开始向前遍历原始字符串。这样做的目的是为了避免在替换过程中覆盖还未处理的字符。对于每个字符我们检查它是否是空格。如果是空格我们就将其替换为%20并更新新字符串的索引位置。如果不是空格我们则直接将字符复制到新字符串的对应位置并更新索引。
这个算法的关键在于利用了字符串的末尾空间从后向前进行替换操作避免了额外的内存分配和字符串拷贝。它只需要一次遍历就能完成替换操作时间复杂度是O(n)其中n是字符串的长度。因此这个算法是高效且实用的。
此外值得注意的是这个算法直接修改了输入的字符串而不是创建了一个新的字符串。这意味着在调用这个函数之后原始的字符串已经被修改。如果原始字符串不应该被修改那么在调用这个函数之前你需要先复制一份原始字符串。
注这个算法假设输入的字符串有足够的空间来容纳替换后的结果。如果原始字符串的空间不足以容纳替换后的结果那么这个算法可能会导致缓冲区溢出。因此在实际使用时你需要确保输入的字符串有足够的空间或者在调用这个函数之前先分配一个足够大的新字符串来存放替换后的结果。
值得一提的是这种算法在牛客上并不能通过全部的测试用例我估计是后台调用函数时传递的字符数组并没有足够大的空间导致数组越界访问了~ 一些感悟在面试的过程中我们也可以和前面的分析一样画一两个示意图解释自己的思路这样既可以帮助我们厘清思路也可以使我们和面试官交流更加的高效
三. 完结散花
好了这期的分享到这里就结束了~
如果这篇博客对你有帮助的话可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话可以点点关注避免找不到我了呢~
我们下期不见不散~~
