大型门户网站建设定制,医药公司网站建设备案,公司网络组建方案设计,html5电影网站源码php1.反转字符串LeetCode344. 20230911 难度为0#xff0c;此处就不放代码了 注意reverse和swap等一系列字符串函数什么时候该用#xff0c;记一记库函数 swap可以有两种实现#xff0c;涨知识了#xff0c;除了temp存值还可以通过位运算#xff1a;s[i] ^ s[j]; s[j] ^ s[i…1.反转字符串LeetCode344. 20230911 难度为0此处就不放代码了 注意reverse和swap等一系列字符串函数什么时候该用记一记库函数 swap可以有两种实现涨知识了除了temp存值还可以通过位运算s[i] ^ s[j]; s[j] ^ s[i]; s[i] ^ s[j];2.反转字符串LeetCode541. 20230917 这一题做的时候其实有点奇怪想了好多方法都被自己否掉然后看题解发现for里面i2k才恍然大悟又看到reverse里面用了s.begin()i这个用法这才明白为啥本题本来很简洁被我写得那么复杂 这个题在今天再重拾的时候觉得完全不用自己想就按部就班地按着题意写就行了 然后看到还有一个reverse的用法是reverse(s,i,ik),第一个而是字符串第二个和第三个是一个左闭右开的区间 3.替换空格 剑指Offer 05. 20230917 自己做的开了一个stringif else地一个个字符加进去了。 卡尔说的可以先用resize函数将s先变长到最终的长度然后用双指针法一个一个从后往前填字符。但是在写的时候犯了一个很蠢的错误resize之后的长度已经变了我还在用s.length()表示旧的s.length() 2 *num 表示新的。下面是正确的代码。 class Solution {
public:string replaceSpace(string s) {int spacenum 0;for(char i : s){if(i ) spacenum;}int size s.length();int left size - 1;s.resize(s.length() 2*spacenum); for(int right size 2*spacenum - 1; right 0; right--){if(s[left] ! ){s[right] s[left];left--;}else{s[right] 0;s[right - 1] 2;s[right - 2] %;left--;right - 2;}}return s;}
}; 4.翻转字符串里的单词 LeetCode 151. 20230919-10/03 思路还是蛮简单就是写的时候老转不过弯。 split函数似乎可以实现分割string里面的单词不过C里好像没有 2. 学习了一下erase函数没用到C标准库中的erase函数通常用于从容器例如std::vector、std::string、std::list等中删除元素例如 std::vectorint myVector {1, 2, 3, 4, 5}; // 删除第三个元素索引为2 myVector.erase(myVector.begin() 2); std::string myString Hello, World!; // 删除从索引6开始的5个字符 myString.erase(6, 5); std::vectorint myVector {1, 2, 3, 4, 5, 6}; // 删除第二个到第四个元素 myVector.erase(myVector.begin() 1, myVector.begin() 4); 然而erase背后的实现是O(N)的时间复杂度如果外面再套一个for循环就是O(N²)的复杂度。 3. 本题写的代码显示自己定义一个闭区间倒置函数然后经过两次倒转就可以。里面细节非常多什么时候1什么时候到末尾要判断什么时候-1都很凌乱 class Solution {
public:void m_reverse(string s, int a, int b){for(int i 0; i (b - a 1)/2; i){swap(s[a i], s[b - i]); }}string reverseWords(string s) {//去除空格int fast 0, slow 0;while(fast s.length()){if(s[fast] ! )s[slow] s[fast];else if(slow ! 0){while(s[fast] fast s.length()){fast;}if(fast ! s.length())s[slow] ;}else{fast;}}s.resize(slow);//全倒reverse(s.begin(),s.end());//闭区间m_reversefor(int i 0, j 0; i s.length(); i){while(s[i] ! i s.length())i;m_reverse(s, j, i - 1);couti jendl;coutsendl;j i 1;}return s;}
}; 5.左旋转字符串 剑指Offer 58 - II 20230917 简单的做法就是使用substr函数注意substr的第二个参数是“多长”而不是“到哪”。 string substr1 s.substr(0, n);
s s.substr(n, s.length() - n) substr1;
return s; 然后还有原地旋转的思路 先局部反转再整体反转很妙 reverse(s.begin(), s.begin() n);reverse(s.begin() n, s.end());reverse(s.begin(), s.end()); 里面两个注意点: 一个是reverse()里面的两个参数 首先std::vectorint vec {1, 2, 3, 4, 5}; auto it vec.begin() 2; // it指向第三个元素即3 std::cout *it std::endl; // 输出 3 因为vec.begin()指向第一个元素也即vec.begin()0那么2就是指向第三个元素 其次如果是reverse(vec.begin(), vec.begin() 2);要记住reverse的第一个参数是第一个元素第二个参数是最后一个元素的下一个元素。也即虽然begin()指的是1begin()2指的是3但是反转的是1,2此处反转成为{2,1,3,4,5}另一个是reverse、substr的内部实现及它们的时间复杂度 为什么要看内部实现因为做题的时候会想着要把时间复杂度降低但是使用库函数有的时候就会忽略掉本身这个函数自己实现的时候用的时间复杂度所以在这里简单看一下 reverse: 源码实现是while ((first!last)(first!--last)) { std::iter_swap (first,last); first; }也就是只遍历一遍即可而swap是之前讲过的要么是疑惑要么是temp存总之是用temp和数组定位。最终合起来的结果也就是遍历一遍对每个元素O(1)的时间复杂度最后是O(N)。 substr: 实现思路为创建一个新的字符串对象将原始字符串中的子字符串复制到新的字符串中。复制的时间复杂度与子字符串的长度成正比因此是 O(N)。 6.找出字符串中第一个匹配项的下标-KMP LeetCode28. 20231019 KMP居然是简单题吗好吧 将近一个月没写。 这道题连着看了得有好几天了但是依然不太会。今天终于约摸着把next数组和利用next数组进行匹配的代码写出来了但是其实还是没有完全理解。 class Solution {public:int strStr(string haystack, string needle) {//next数组int length needle.length();int next[length];next[0] 0;// int j 0;// 前缀末尾// 求next数组for(int i 1; i length; i){while(j 0 needle[i] ! needle[j]){j next[j-1];}if(needle[i]needle[j]){j;}next[i] j;}int n 0;//用next数组去做匹配for(int m 0; m haystack.length(); m){ while(n 0 haystack[m] ! needle[n])n next[n-1]; if(haystack[m] needle[n])n;if(n length)return m - length 1;}return -1;}}; aabaa前缀不带末尾针对a为空针对aa为a针对aab为aaa针对aaba为aaaaab针对aabaa为a,aa,aab,aaba 后缀不带头针对a为空针对aa为a针对aab为bab针对aaba为abaaba;针对aabaa为a,aa,baa,abaa 首先是求next数组。 1初始化的时候next数组第一个必为0这是因为位置0前后缀不可能相等后缀位置0没有。 2然后开始从i1挨个填next数组在填这个数组的时候就已经用到了kmp思想了。具体表现为填next[i]的时候j也不是一直从头开始匹配的。j先为0如果needle串s的s[i]!s[j],此时说明j要往前移动但是只移到next[j-1]那边注意点while、0如果needle串的s[i]s[j]就j;然后next[i]j进行到next[i1]。 然后是利用next数组进行匹配。 这个地方也就是遍历haystack串与模式串匹配就两个指针都自动后移不匹配就模式串的指针往前移依旧是while、0注意然后这个地方还有一个根据题意返回一下结果。 这个题让我自己想是完全不可能想出来的感觉以后还得复习三遍才能记住 7. 重复的子字符串 LeetCode 459. 20231019 第一种解法的思想是两个s拼接起来如果去头去尾还含有s那么s是可以由重复子串构成的。 理解 [xx {xxxx][xx} xxxx] 如果{xxxxxx}[xxxxxx]证明[xx{xx{xxxx]xx][xx}而[xx}[xx所以 [xx{xxxx][xx}所以xx为[xxxxxx]可用来重复的子串。大概这么理解吧不再看严格数学证明。 里面有两个亮点erase函数删除特定位置的元素以及string::npos代表没找到任何位置。 class Solution {
public:bool repeatedSubstringPattern(string s) {//方法1.移动匹配--具体表现为拼接-删除首尾-调用find库函数string ss ss;ss.erase(ss.length()-1,1);ss.erase(0,1);auto it ss.find(s);if (it ! string::npos)return 1;return 0;}
}; 第二种解法是KMP class Solution {
public:bool repeatedSubstringPattern(string s) {//方法2.KMP--两个思路中的关键数学证明//1. 如果是由子串重复构成那么最长相等前后缀不包含的那个子串就是所要求的子串。//2. 如果子串整除整个串那么整个串就是由这个子串重复构成的。这个依然看我关于[xx {xxxx][xx} xxxx] 的理解总而言之各个部分都相等。//下面首先是算next数组我们需要知道next[s.length()-1]等于多少因为这个值就代表我们整个串的相等前后缀有多长。然后用s.length()-next[s.length()-1] 除 s.length(), 如果能整除就返回1否则返回0。int length s.size();//int next[length]{0};int next[s.length()];next[0] 0;int j 0;for (int i 1; i length; i){while(j 0 s[j]!s[i])j next[j-1];if(s[j] s[i])j;next[i] j;}if(next[length-1] ! 0 (length % (length - next[length-1]) 0))return 1;return 0;}
}; 注1: next[length-1] ! 0 要加漏了完全没有相等前后缀的情形。 注2:int next[s.length()];这种用法很奇怪按本科讲的课来说应该写成int *next new int[s.length()];才行。 leetcode的奇怪机制·参数是(string s)在函数体内定义一个数组int array[s.length()];可以过·int array[s.length()]{0};过不了·int array[s.length()]; for (int i 0; i s.length(); i) {array[i] 0;}又能过 其他LeetCode刷题总结-字符串篇 - 舞动的心 - 博客园 (cnblogs.com) 还有什么题可刷待看
