计算机课程网站建设实训报告总结,社区网站 租用服务器还是只需要购买空间,安康网站建设公司电话,网站建设需要代码文章目录1. 仅仅反转字母思路分析代码实现2. 字符串中的第一个唯一字符题目分析代码实现3. 《剑指offer》——替换空格解法一#xff1a;寻找替换思路分析代码实现优化解法二#xff1a;空间换时间思路分析代码实现4.字符串最后一个单词的长度思路分析代码实现5. 字符串相加思…
文章目录1. 仅仅反转字母思路分析代码实现2. 字符串中的第一个唯一字符题目分析代码实现3. 《剑指offer》——替换空格解法一寻找替换思路分析代码实现优化解法二空间换时间思路分析代码实现4.字符串最后一个单词的长度思路分析代码实现5. 字符串相加思路分析代码实现优化提升效率我们来看几道string相关的OJ来练习一下string的使用。 1. 仅仅反转字母
题目链接: link
我们一起来看一下题
思路分析 我们来分析一下题目这道题让我们干什么呢 给我们一个字符串该字符串中有英文字符也有非英文字符要求我们去反转字符串中的所有英文字母非英文字母的字符位置不动。 那是不是很简单啊左右两个指针分别指向首尾然后依次向中间移动寻找英文字母找到后停下来然后两个指针指向的英文字母进行交换接着继续向中间移动两者相遇结束。是不是跟一趟快排的逻辑有点像啊 代码实现
class Solution {
public:bool isletter(char x){if((xaxz)||(xAxZ))return true;return false;}string reverseOnlyLetters(string s) {int begin0;int ends.size()-1;while(beginend){while((beginend)!isletter(s[begin]))begin;while((beginend)!isletter(s[end]))end--;swap(s[begin],s[end]);begin; end--;}return s;}
};代码呢也比较简单相信大家都能看懂就不过多解释了。 2. 字符串中的第一个唯一字符
链接: link
题目分析 题目让我们找出字符串中第一个不重复的字符那我们最容易想到的就是暴力求解从头到尾遍历字符串依次拿每一个字符与其他字符进行比较如果没有与之重复的则当前字符就是要找的字符返回其下标有重复的就不是继续看下一个最终一个也没找到就返回-1。 当然这样的时间复杂度就是O(N^2) 那有没有好一点的方法呢 其实呢我们可以考虑用计数排序的思想去搞 题目说了只包含小写字母 所以字符串中字符的范围就是【a,z】那我们就可以创建一个大小为26的整型数组然后用一个相对映射去统计每个字母的出现次数a就映射到下标为0的位置b就映射到下标为1的位置依次类推。 那怎么让这些字母映射到对应的位置呢 减去’a’得到的值是不是就是它们映射的位置啊然后遍历字符串每个字母映射的值是几就让下标为几的元素初值全为0这样遍历过后每个字母出现的次数就统计出来了。下标0的元素的值就是a出现的次数1位置就是b出现的次数… 但是现在有一个问题那就是出现一次的字母可能不止一个我们怎么判断那个是第一个只出现一次的字母呢 这里我们不要去遍历统计次数的数组还是从前往后去遍历字符串然后看哪个字母的次数是1第一个是1的就是第一个只出现一次的字母。 代码实现
class Solution {
public:int firstUniqChar(string s) {int count[26]{0};for(auto e:s){count[e-a];}for(int i0;is.size();i){if(count[s[i]-a]1)return i;}return -1;}
};大家结合上面的分析再看一看代码相信就能理解了。 3. 《剑指offer》——替换空格
接下来我们来看一道《剑指offer》于string相关的题目——替换空格
解法一寻找替换
思路分析 大家思考一下这道题可以怎么解 是不是可以考虑用findreplace搞啊。 用find找的字符串中的所有空格然后用replace将其替换成%20不就行了嘛。 代码实现
我们来实现一下代码
class Solution {
public:string replaceSpace(string s) {size_t poss.find( );while(pos!string::npos)//find找不到返回npos{s.replace(pos,1,%20);poss.find( );}return s;}
};就通过了。
优化 那大家看一下我们刚才上面那样写好吗或者说有没有可以优化的地方 是可以做一些优化的。 来看find是不是可以指定开始查找的位置啊如果我们不传pos的话它默认是从起始位置开始查找的但是这里我们要查找所有的空格并且对它们进行替换那第一个空格被替换之后我们往后查找第二个的时候还有必要从头开始找吗是不是就可以从替换之后的尾部开始往后找啊这样效率是不是就高了一点会。 所以我们可以这样改进一下 那大家再想还可以再优化吗 其实还有一个地方可以做一些优化大家想我们这里replace是把空格替换成%20这样使用的空间是不是多了那replace在替换的过程中是不是有可能空间不够进行扩容啊那有没有什么办法可以避免replace的过程中可能会去频繁的扩容扩容是有消耗的特别是异地扩。 我们是不是可以计算出需要多少空间然后提前把空间开好啊。那大家说这里应该用什么 resize还是 reservereserve可以改变容量帮我们开空间而resize除了开空间还可以初始化但是这里有必要对开好的空间进行初始化吗 是不是没必要啊所以我们用reserve就行了。 那需要多少空间呢空格替换成%20所以每个空格多两个空间那我们可以统计一下空格数然后提前把空间开好 写一下代码
class Solution {
public:string replaceSpace(string s) {int count0;for(auto e:s){if(e )count;}s.reserve(s.size()2*count);size_t poss.find( );while(pos!string::npos){s.replace(pos,1,%20);poss.find( ,pos3);}return s;}
};解法二空间换时间
那除了上面那种方法其实还可以考虑另一种思路
思路分析 我们可以创建一个新的string对象然后遍历原串不是空格就直接到新串是空格就把%20到新串。 这样的好处是不需要像上面那样挪动数据了只不过多开了一点空间。 代码实现
这个代码就非常简单
class Solution {
public:string replaceSpace(string s) {string news;for(auto e:s){if(e! )newse;elsenews%20;}return news;}
};当然这种方法在的过程中也有可能会扩容所以我们也可以把reserve那一步加上。 4.字符串最后一个单词的长度
链接: link 输入一个字符串求它的最后一个单词的长度。 思路分析
那这是不是简单啊 我们是不是可以用rfind去搞啊。 找到倒数第一个空格的位置pos是不是就能计算出长度了 用size - pos -1是不是就是最后一个单词长度。 注意输入的字符串可能有空格所以我们输入用getline。 代码实现
写一下代码
#include iostream
using namespace std;int main() {string s;getline(cin,s);size_t poss.rfind( );if(pos!string::npos){couts.size()-pos-1endl;}
}提交一下
有一个测试用例没过 我们看到这个测试用例只有一个单词所以找不到空格但我们刚才没考虑找不到空格的情况。 那怎么解决 这种情况答案不就是这一个单词的长度嘛很好处理 #include iostream
using namespace std;int main() {string s;getline(cin,s);size_t poss.rfind( );if(pos!string::npos){couts.size()-pos-1endl;}else {couts.size()endl;}
}5. 字符串相加
链接: link
思路分析
我们来一起看一下 这道题是给定两个字符串形式的非负整数 num1 和num2 让我们计算它们的和并同样以字符串形式返回。 我们来分析一下应该怎么做 就拿这个例子来说 这里我们是不是应该倒着走啊从低位开始加首先取到两个字符串的最后一个字符相加76是13但是我们这里把3保存下来1是不是要进到上一位啊所以我们应该搞一个变量来保存进位 那然后再去加它们对应的倒数第二位依次往前走所以这应该是一个循环的过程那什么时候结束 是不是两个字符串全都遍历完才结束啊当然它们可能会有一个先走完那另一个剩下的每次跟0相加就行了。 所以我们应该先获取一下它们最后一个元素的下标end加一个数两者的end就- -一次减到-1就是遍历完了。 然后里面我就去循环走我们的这个逻辑。 代码实现
那我们来写一下代码
class Solution {
public:string addStrings(string num1, string num2) {int end1num1.size()-1;int end2num2.size()-1;while(end10||end20){}}
};那在循环里面我们就依次去取对应的两个字符进行相加了。 但是这里我们能直接用字符相加吗我们的字符取出来是啥是不是取的是它们对应的ASCII码值啊想拿到它对应的数字怎么办 是不是应该减去0啊 int val1num1[end1]-0; 但是呢这里还存在一个问题我们这里是不是只要有一个字符串没走完循环就不结束啊也就是即使在循环里面也有可能有一个已经走完了所以我们这里直接取这个end是不是可以越界啊所以加个判断 当然这个地方我们可以用三目运算符来简化一下 然后就该相加了但是相加是不是会产生进位啊所以我们再定义一个变量表示进位初值给个0。 那相加之后如果和大于等于10进位的值是不是就该变成1 了。当然如果小于10 那就还是0。 所以我们可以这样写 nextsum/10; 那另外如果和大于10我们是不是只留下各位的数就行了。 sum%10; 然后呢得出的结果我们是不是要存下来。 题目要求最后还是返回一个字符串所以我们再创建一个string对象保存结果。 但是现在面临一个问题我们先得到的是不是低位的数字啊它们应该放在后面所以这里我们每次保存得出的结果应该是头插到string对象中那我们就可以用insert每次插入到下标0的位置。 注意这里插入的时候要把字符0再加上。 那加完之后它们的end的位置是不是都要- -一下啊。 那这样循环结束是不是就得到结果了。 class Solution {
public:string addStrings(string num1, string num2) {int end1num1.size()-1;int end2num2.size()-1;int next0;//进位string ret;while(end10||end20){int val1(end10?num1[end1]-0:0);int val2(end20?num2[end2]-0:0);int sumval1val2next;nextsum/10;sum%10;ret.insert(0,1,sum0);end1--;end2--;}return ret;}
};我们来提交一下 有一些测试用例没过。我们来看一下 看当前报错给的这个用例1和9我们输出的是0什么问题啊 是不是循环结束之前最后一次得出的进位如果是0那就不用管了但如果是1 我们是不是还得加上去啊。 我们刚才是不是忽略掉这个情况了 class Solution {
public:string addStrings(string num1, string num2) {int end1num1.size()-1;int end2num2.size()-1;int next0;//进位string ret;while(end10||end20){int val1(end10?num1[end1]-0:0);int val2(end20?num2[end2]-0:0);int sumval1val2next;nextsum/10;sum%10;ret.insert(0,1,sum0);end1--;end2--;}if(next1)ret.insert(0,1,1);return ret;}
};这下就通过了。 但是大家看一下我们刚才的这种搞法效率是不是比较低啊我们这里每次都要调用insert头插挪动数据那是不是O(N^2)啊。 我们上一篇文章也提到了insert是不是能少用就少用啊。这里效率低主要就低在insert这里了。 所以能不能想办法改进一下啊。
优化提升效率
那我们可以怎么改进一下呢 insert头插需要挪动数据效率低那我们就不用头插了呗我们就依次放到后面一个个尾插最后我们再逆置一下不就行了嘛。 那逆置呢我们可以自己写一个函数。 但是其实不需要。因为C的算法库里其实给我们提供了逆置的函数我们可以直接用 我们看到这里使用的时候去传迭代器区间就行了。 修改成这样。 class Solution {
public:string addStrings(string num1, string num2) {int end1num1.size()-1;int end2num2.size()-1;int next0;//进位string ret;while(end10||end20){int val1(end10?num1[end1]-0:0);int val2(end20?num2[end2]-0:0);int sumval1val2next;nextsum/10;sum%10;//ret.insert(0,1,sum0);ret(sum0);end1--;end2--;}if(next1)//ret.insert(0,1,1);ret1;reverse(ret.begin(),ret.end());return ret;}
};效率明显就提升了。
那还有没有可以优化的地方 这里涉及到插入数据我们就可以考虑干嘛 是不是可以提前把空间开好以此来避免在插入数据的时候可能引发扩容。 那大家思考一下对于这道题我们应该提前开多少空间合适 大家想两个数相加结果最多是不是会比长的那个数的位数多出一位啊。 比如两个最大的两位数相加9999也就3位嘛。 所以 就可以这样搞一下。 class Solution {
public:string addStrings(string num1, string num2) {int end1num1.size()-1;int end2num2.size()-1;int next0;//进位string ret;ret.reserve(num1.size()num2.size()?num1.size()1:num2.size()1);while(end10||end20){int val1(end10?num1[end1]-0:0);int val2(end20?num2[end2]-0:0);int sumval1val2next;nextsum/10;sum%10;//ret.insert(0,1,sum0);ret(sum0);end1--;end2--;}if(next1)//ret.insert(0,1,1);ret1;reverse(ret.begin(),ret.end());return ret;}
};这篇文章就到这里欢迎大家指正
