东莞哪里有网站建设厂家盐城网站定制

当前位置： 首页 > news >正文

东莞哪里有网站建设厂家,盐城网站定制,东营建设信息网官网网址,怀化市住房建设局网站数据结构—-结构–线性结构–字符串 一.字符串的定义方式 第一种#xff1a; char* str1Hello第二种#xff1a; char str2[]Hello;区别 1.所在区域不同 //str1在常量区//str2在这里的写法是在栈区2.元素是否可改 //str1中的元素不可改//st…数据结构—-结构–线性结构–字符串 一.字符串的定义方式 第一种 char* str1Hello第二种 char str2[]Hello;区别 1.所在区域不同 //str1在常量区//str2在这里的写法是在栈区2.元素是否可改 //str1中的元素不可改//str2中的元素可改//第一种 //用下标进行修改//第二种 //用strcpy函数进行修改 3.str1和str2是否可改 //str1可改它是指针可以改变指向 str1Haha;//str2不可改它是地址不可改4.大小不同 sizeof(str1);//4个字节sizeof(str2);//6个字节二.关于字符串替换的问题 题目 将一个足够长的字符串的空格替换成win原字符串为 only lovers left alive 此字符串是无限长的 e’字符后面有无限的空间 方法 1.暴力 申请一块新空间大小为 strlen(字符串)额外要用的空间 ​ 对原字符串进行遍历遇到空格就在新空间存入win不是的话就存入原字符 ​ 时间复杂度 O(n) 空间复杂度 O(n) 2.字符串切割拼接 ​ 切割的函数为strtok ​ 连接的函数为strcat ​ 时间复杂度 O(n) 空间复杂度 O(n) 3.栈 时间复杂度 O(n) 空间复杂度 O(n) 4.队列 时间复杂度 O(n) 空间复杂度 O(n) 5.暴力优化 ​ 1.在原有空间上定义两个指针 ​ 2.一个指向最后一个字符的位置另一个指向替换完空格后的地方此位置为strlen(字符串)额外要用的空间 ​ 3.两个指针同时向前移动遇到空格就在后面指针指向的位置替换成win先替换n然后指针向前移动以此类推直到替换完成不是空格就把前面指针指向的位置的内容替换到后面指针指向的位置然后两个指针一起向前移动直到前一个指针的下一个不是此字符串中的元素了。 ​ 时间复杂度 O(n) 空间复杂度 O(1) 三.关于字符串单词倒置的问题 题目 将一个字符串 “only lovers left alive进行单词倒置 倒置后的字符串为alive left lovers only” 方法 1.数组 ​ 定义两个指针一个指向字符串从后往前第一个不为空格的字符另一个最开始也是指向这里然后向前遍历当找到空格时将这一段的字符全部都放到新的数组里然后后面的指针来到第一个指针的位置从此位置向前再次找到第一个不为空格的字符之后另一个也指向这里接着向前遍历当找到空格时再将这一段的字符全部都放到新的数组里 ​ 两个指针一直重复上面的过程直到前面指针指向了字符串中的首元素看两个指针是否指向统一元素如果不是就将这一段的字符全部都放到新的数组里倒置完成如果是的话倒置完成。 ​ 时间复杂度 O(n) 空间复杂度 O(n) 2.倒置 ​ 先将整个字符串进行倒置然后将每个单词进行倒置 ​ 时间复杂度 O(n) 空间复杂度 O(1) 3.链表 ​ 将每一个单词都用一个链表存然后将链表从前到后采用头插法变成一个新链表即可 ​ 时间复杂度 O(n) 空间复杂度 O(n) 4.栈 ​ (1)一个栈数组 ​ 将字符串入栈如果遇到空格就将栈内元素出栈放到数组中数组提前申请好空间 ​ 如果字符串为空了就将栈内元素出栈放到数组中 ​ 时间复杂度 O(n) 空间复杂度 O(n) ​ (2)两个栈 ​ 将字符串全部入到第一个栈中然后将第一个栈中元素弹出入到第二个栈中 ​ 如果遇到空格就将第二个栈中的元素替换到原字符串的相应位置上这里会有一个指针来进行字符的替换每替换完一个指针就向后移动一位指针最开始指向字符串的首元素然后进行将第一个栈中的元素弹出 ​ 直到第一个栈中没有元素了如果第二个栈中有元素就将第二个栈中元素全部弹出替换原字符串中的相应位置上 ​ 时间复杂度 O(n) 空间复杂度 O(n) 5.字符串切割拼接 升级版于字符串单词倒置问题此题的网址为https://leetcode.cn/problems/reverse-words-in-a-string/ 题目 给你一个字符串 s 请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。 运用到上面分析的倒置的方法代码如下 //这里的代码是c语言下的 class Solution { public:string reverseWords(string s) {//删除首尾的空格s.erase(0, s.find_first_not_of( ));s.erase(s.find_last_not_of( )1);//整体进行翻转int begin1 0;int end1 s.size() - 1;while (begin1 end1) {char a s[begin1];s[begin1] s[end1];s[end1] a;begin1;end1–;}//每个单词进行翻转int begin 0;int end 0;char* p s[0];int index 0;int bool1 1;int bool2 1;int bool3 0;int bool4 0;int bool5 0;while (*p ! \0) {if (*p ! *(p 1) ! bool1%21) {begin index;bool1;bool3 1;}if ((*p (p - 1) ! bool1 % 2 0)) {end index - 1;bool1;bool4 1;}if ((p 1) \0 *p ! bool1 % 2 0) {end index;bool1;bool4 1;}int begin2 begin;int end2 end;while (begin2 end2 bool3 bool4) {bool5 1;char a s[begin2];s[begin2] s[end2];s[end2] a;begin2;end2–;}if (bool5) {bool3 0;bool4 0;bool5 0;}p;index;}//去除字符串间的空格string::iterator ite s.begin();while (ite!s.end()) {if (*ite *(ite 1) ) {ites.erase(ite);}else if (*ite (ite - 1) ) {ite s.erase(ite);}else {ite;}}return s;} }; 四.关于字符串的一道题 题目 ​ 一个字符串”abcdefgh“ 输入一个k将前k个字符移到字符串的后面且移动的k个字符顺序不变当k等于3时移动后的字符串为”defghabc“ 方法 ​ 1.队列/栈 ​ 2.链表/数组 ​ 3.字符串切割拼接 ​ 4.倒置 ​ 先将整个字符串进行倒置然后将0 ~ 第k-1字符包括它们之间的字符进行倒置将 k ~ 最后一个字符包括它们之间的进行倒置 ​ 时间复杂度 O(n) 空间复杂度 O(1) 五.关于字符串查找的问题 1.根据经验总结出下面四大查找问题 1.在一个串中找符合某个条件的字符 2.在一个串中找符合条件的某个串/某些串 3.在多个串中找某个串/某些串 4.在两个串中找符合条件的某些公共串 1.第一大查找问题中的题 题目 找到第一个只出现一次的字符 解决 1.队列计数器 2.map遍历 3.hash遍历 2.第二大查找问题中的题 题目 找到字符串中最长回文子串 解决 1.判断一个字符串是否是回文子串从中间断开然后翻转后面的字符串然后两个字符串进行对比看是否相等即可 2.然后再比较长度即可 3.第二大查找问题中的KMP算法 1.KMP算法的作用 KMP算法是用来找一个串字串在另一个串主串中出现的位置首元素的位置 2.KMP的实现 1.首先定义一个Next数组用来存字串中每个元素前面串的前缀字串和后缀字串相同最大的长度 1.定义两个相邻变量作为下标 2.如果后面那个下标所在的元素和前一个下标在next数组中充当下标所找到的元素相同则此元素所在下标的nexrt数组的值就是前一个元素下标在next数组中所找到元素的值1 3.如果不相同且前一个元素下标在标在next数组中所找到元素的值为0那么此元素所在下标的nexrt数组的值为0 4.如果不相同且前一个元素下标在标在next数组中所找到元素的值不为0那前一个变量就变为它所在下标在next数组中充当下标所找到的值-1然后重复操作2直到找到或者找到子串的头节点还没找到结束 2.子串与主串进行匹配 1.如果子串元素与主串元素相同继续往下比 2.如果子串元素与主串元素不相同那子串中的元素就变为当前元素下标前面那个的元素下标的Next数组的所指的子串元素如果到了子串的头元素也不相等那匹配串重头开始 3.直到子串遍历完了或者主串遍历完了结束 3.KMP代码的如下 //此代码是使用c写的 #includestdio.h #includestdlib.hint GetNext(const char* match) {int* pNext (int*)malloc(sizeof(int) * strlen(match));pNext[0] 0;int i 1;int j i - 1;while (i strlen(match)) {if (match[i] match[pNext[j]]) {pNext[i] pNext[j] 1;i;j i - 1;}else if (pNext[j] 0) {pNext[i] 0;i;j i - 1;}else {j pNext[j] - 1;}}return pNext; } int KMP(const char* src, const char* match) {if (src NULL || match NULL) return -1;//获得Next数组int* pNext GetNext(match);//匹配int i 0;int j 0;while (i strlen(match) j strlen(src)) {if (src[i] match[j]) {i;j;}else {//匹配串跳转if (j 0) {i;}else {j pNext[j - 1];}}}if (j strlen(match)){return i - j;}else {return -1;} }int main() {printf(%d\n, KMP(abcabcgweu3abcabcdusabcabcsfh, abcabc));//测试样例return 0; }4.第二大查找问题中的Sunday算法 1.Sunday算法的作用 KMP算法是用来找一个串字串在另一个串主串中出现的位置首元素的位置 2.Sunday的实现 1.首先申请一个256个空间大小的inr型的数组Next因为字符一共有256个所以可以定义一个有限长度的数组 1.申请完数组后将数组中的元素全部赋值为-1 2.遍历一遍子串给数组中的元素进行赋值存的是子串中每个元素在子串中从右往左第一次出现的下标 2.子串与主串进行匹配 1.定义两个变量用来遍历主串和子串还有一个标记变量用来找每回主串与子串匹配来时的那个下标 2.主串与子串进行匹配如果相同那么继续下一个如果不相同那子串从头开始主串则是从k所在下标加上子串长度然后减去当前所获得的字符在Next数组中充当下标的值开始 3.直到子串遍历完了或者主串遍历完了结束 3.Sunday代码的如下 //此代码是使用c写的 #include iostream #include string using namespace std;int Next[256];//申请一个Next数组用来存匹配串中各个元素的下标void funzhi(string a) {//初始化Next数组for (int i 0; i a.size(); i) {Next[a[i]] i;} } int peidui(string zhu, string pi) {//进行配对int i 0;//主串int j 0;//匹配串int length pi.size();//匹配串长度int k 0;//用来标记匹配串在主串中首元素的下标while (1) {if (zhu[i] ! pi[j]) {//如果主串元素与匹配串元素不相同if (k length zhu.size()) {//如果超出了主串的范围return -1;}k k length - Next[zhu[k length]];i k;j 0;}else {//如果主串元素与匹配串元素相同i;j;}if (j pi.size()) {//如果子串遍历完了return k;}} }