建立站点的作用,权威迷失传奇新开网站,童装网站建设,建筑企业资质查询网站151. 反转字符串中的单词
给你一个字符串 s #xff0c;请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开
思路#xff1a;根据题目大意#xff0c;空格之间的就是一个单词#xff0c;所以我们需要利用…
151. 反转字符串中的单词
给你一个字符串 s 请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开
思路根据题目大意空格之间的就是一个单词所以我们需要利用双指针定位空格将空格之间的元素存入数组之中然后倒序输出 进行输出。但进一步思考我们不防直接从后面遍历倒序输入然后正序输出从而实现倒序。另外看例题知空格不一定是一个也可能是多个位置也可能在开头和结尾所以我们需要去空格。以上得到大体步骤
倒序遍历字符串 s记录单词左右索引边界 fast,solw 。 int fast s.size() - 1;
int solw s.size() - 1; 去空格 while(fast 0 s[fast] ) fast--; 每确定一个单词的边界则将其添加至单词列表 res ,并加入一个空格。 solw fast;//solw是后面的界限每次过完空格开始的时候就是fast的位置
while( fast 0 s[fast] ! ) fast--;//不是空格fast就不断往前
res.append(s.substr(fast1, solw-fast));//将单词加入到res中//s.substr(fast1, solw-fast);
字符串切割此时s[fast] “ ”;所以单词范围应该在[fast1,slow],
因为substr的第二参数为长度所以lensolw-(fast1)1; 最终返回res
全部代码
class Solution {//一、双指针倒序遍历 分割不需要删除头尾多余的空格
public:string reverseWords(string s) {string res ;int fast s.size() - 1;int solw s.size() - 1;while(fast 0){while(fast 0 s[fast] ) fast--;//去掉单词后面的空格solw fast;while( fast 0 s[fast] ! ) fast--;res.append(s.substr(fast1, solw-fast));//正常来说单词后 都要加空格。不加空格的情况字符串首字符为空格 且 遍历到 i0;if(fast 0 || s[0] ! ) res ; }//去掉尾部的一个多余空格res res.substr(0, res.size()-1);return res;}
};
知识点补充 字符串函数s.substr(); 在C 中substrsubstr();是用于字符串处理的预定义函数。string.h是字符串函数所需的头文件。
此函数将两个值pos和len作为参数并返回一个新构造的字符串对象其值初始化为该对象的子字符串的副本。从pos开始复制字符串直到pos len表示[pospos len为止。 用法如下
#includestring
string s;
s.substr (pos,len);
pos表示要截取的子字符串的起始位置len表示要截取的子字符串的长度。 43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2返回 num1 和 num2 的乘积它们的乘积也表示为字符串形式。
大体思路取出字符串里的数据转化为int类型模拟乘法即可。
取数据
// 将 num1、num2 分别存入 A、B 中for (int i 0; i len1; i) {A.push_back(num1[i] - 0);}for (int i 0; i len2; i) {B.push_back(num2[i] - 0);}
方法一尝试直接用int类型进行转换。但是int限制不够long也不够利用数组吧
这个也稍微讲一下范围内这个方法也不错 long res0,sum0; for(int i0;inum2.size();i){//模拟竖式for(int j0;jnum1.size();j){//模拟竖式resA[j]*B[i]res*10;//coutresendl;}sumsum*10res;res0;}方法一利用数组存出结果然后再处理进位如图这里牵扯到一个知识点就是n位*m位最终返回为mn-1位 // 模拟两数相乘的过程for (int i len2 - 1; i 0; i--) {for (int j len1 - 1; j 0; j--) {res[i j 1] A[j] * B[i];}}// 处理进位for (int i len1 len2 - 1; i 0; i--) {if (res[i] 10) {res[i - 1] res[i] / 10;res[i] res[i] % 10;}}
整体代码
class Solution {
public:string multiply(string num1, string num2) {if (num1 0 || num2 0) return 0;vectorint A, B;int len1 num1.size(), len2 num2.size();vectorint res (len1len2,0); // 存放相乘结果string ans ;// 将 num1、num2 分别存入 A、B 中for (int i 0; i len1; i) {A.push_back(num1[i] - 0);}for (int i 0; i len2; i) {B.push_back(num2[i] - 0);}// 模拟两数相乘的过程for (int i len2 - 1; i 0; i--) {for (int j len1 - 1; j 0; j--) {res[i j 1] A[j] * B[i];}}// 处理进位for (int i len1 len2 - 1; i 0; i--) {if (res[i] 10) {res[i - 1] res[i] / 10;res[i] res[i] % 10;}}// 构造结果字符串for (int i 0; i len1 len2; i) {if (i 0 res[i] 0) {continue; // 最高位不含前导零}ans to_string(res[i]); // 将数字转化为字符串}return ans;}
}; 14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串 。
这道题啊首先第一个想法就是横向比较如图 其实就是一个一个比较不断缩小最长公共前缀公共前缀使用Commen函数截取。这个函数太赞了
class Solution {
public:string longestCommonPrefix(vectorstring strs) {if(strs.size()0) return ;string con_strstrs[0];int i1;while(istrs.size()){string strstrs[i];con_strCommon(con_str,str);if(!con_str.size()) break;i;}return con_str;}string Common(string str1, string str2){int lenmin(str1.size(),str2.size());int index0;while (index len str1[index] str2[index]) {index;}return str1.substr(0,index);}
};
另外提交后还看到一种写法也很赞将字符串进行排序第一个和最后一个一定是最不相同的所以直接找第一个和最后一个的公共前缀即可。
class Solution {
public:string longestCommonPrefix(vectorstring str) {sort(str.begin(),str.end());string s1str.front();string s2str.back();int i0;while(s1[i]s2[i] is1.size() is2.size()){i;}return s1.substr(0, i);}
}; 知识点补充
1.字符串比较
字符串之间的大小取决于它们接顺序排列字符的前后顺序。
eg。str1abc”和 str2acc”它们的第一个字母都是a而第二个字母由于字母b比字母c要靠前所以bc于是我们可以说“abcacd”也可以说strl str2.如果说两个字符串 strl和 str2 相等则必须满足两个条件:
1.字符串 str1 和字符串 str2 的长度相等。
2.字符串 str1 和字符串 str2 对应位置上的各个字符都相同。而对于两个不相等的字符串我们可以以下面的规则定义两个字符串的大小:
从两个字符串的第0个位置开始依次比较对应位置上的字符编码大小。
如果 str1|i]对应的字符编码str2|i]对应的字符编码则比较下一位字符。
如果 str1|i] 对应的字符编码 str2[i]对应的字符编码则说明str1str2。比如:abc”acc”。
如果 str1[i] 对应的字符编码 str2|i]对应的字符编码则说明str1str2。比如:bcdbad如果比较到某一个字符串末尾另一个字符串仍有剩余:字符串 str1 的长度小于字符串 str2,即len(str1)len(str2)。则 str1str2。
所以前面在sort str后str应该是
[flower,flow,flight]----flight flow flower
2.
string aabcd1.获取字符串最后一个字符
auto ba.back(); //结果为 bd;2.修改字符串最后一个字符
a.back()!; //结果为 aabc!;3.获取字符串第一个字符
auto ba.front(); //结果为 ba;4.修改字符串第一个字符
a.front()!; //结果为 a!bcd;方法三还有一种方法就是纵向扫描
纵向扫描时从前往后遍历所有字符串的每一列比较相同列上的字符是否相同如果相同则继续对下一列进行比较如果不相同则当前列不再属于公共前缀当前列之前的部分为最长公共前缀。 class Solution {
public:string longestCommonPrefix(vectorstring strs) {if (!strs.size()) {return ;}int length strs[0].size();//行int count strs.size();//列数for (int i 0; i length; i) {char c strs[0][i];for (int j 1; j count; j) {if (i strs[j].size() || strs[j][i] ! c) {//到头或者有不同return strs[0].substr(0, i);}}}return strs[0];}
};
终于结束了
