• 力扣刷题日志-Day2 （力扣151、43、14）

    151. 反转字符串中的单词 

    给你一个字符串 s ，请你反转字符串中 单词 的顺序。

    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开

    思路：根据题目大意，空格之间的就是一个单词，所以我们需要利用双指针定位空格，将空格之间的元素存入数组之中，然后倒序输出 ，进行输出。但进一步思考，我们不防直接从后面遍历，倒序输入然后正序输出，从而实现倒序。另外，看例题知空格不一定是一个，也可能是多个，位置也可能在开头和结尾，所以我们需要去空格。以上，得到大体步骤

    1. 倒序遍历字符串 s，记录单词左右索引边界 fast,solw 。 
      1. int fast= s.size() - 1;
      2. int solw= s.size() - 1;
    2. 去空格 
       while(fast >= 0 && s[fast] == ' ') fast--;
    3. 每确定一个单词的边界，则将其添加至单词列表 res ,并加入一个空格。 
      1. solw = fast;//solw是后面的界限，每次过完空格开始的时候就是fast的位置
      2. while( fast >= 0 && s[fast] != ' ') fast--;//不是空格fast就不断往前
      3. res.append(s.substr(fast+1, solw-fast));//将单词加入到res中
      4.  
      5. //s.substr(fast+1, solw-fast);
      6. 字符串切割，此时s[fast] ==“ ”;所以单词范围应该在[fast+1,slow],
      7. 因为substr的第二参数为长度，所以len=solw-(fast+1)+1;
    4. 最终，返回res

    全部代码：

    1. class Solution {//一、双指针（倒序遍历 + 分割）不需要删除头尾多余的空格
    2. public:
    3.     string reverseWords(string s) {
    4.         string res = "";
    5.         int fast= s.size() - 1;
    6.         int solw= s.size() - 1;
    7.         while(fast >= 0){
    8.             while(fast >= 0 && s[fast] == ' ') fast--;//去掉单词后面的空格
    9.             solw = fast;
    10.             while( fast >= 0 && s[fast] != ' ') fast--;
    11.             res.append(s.substr(fast+1, solw-fast));
    12.             //正常来说单词后 都要加空格。不加空格的情况：字符串首字符为空格 且 遍历到 i<0;
    13.             if(fast >= 0 || s[0] != ' ')  res += " ";  
    14.         }
    15.         //去掉尾部的一个多余空格
    16.         res = res.substr(0, res.size()-1);
    17.         return res;
    18.     }
    19. };

    知识点补充：

    字符串函数s.substr();

    在C ++中，substrsubstr();是用于字符串处理的预定义函数。string.h是字符串函数所需的头文件。

    此函数将两个值pos和len作为参数，并返回一个新构造的字符串对象，其值初始化为该对象的子字符串的副本。从pos开始复制字符串，直到pos + len表示[pos，pos + len）为止。

     用法如下：

    1. #include
    2. string s;
    3. s.substr (pos,len);

    pos表示要截取的子字符串的起始位置，len表示要截取的子字符串的长度。

    43. 字符串相乘

    给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

    大体思路：取出字符串里的数据，转化为int类型，模拟乘法即可。

    取数据：

    1. // 将 num1、num2 分别存入 A、B 中
    2.         for (int i = 0; i < len1; i++) {
    3.             A.push_back(num1[i] - '0');
    4.         }
    5.         for (int i = 0; i < len2; i++) {
    6.             B.push_back(num2[i] - '0');
    7.         }

    方法一：尝试直接用int类型进行转换。但是int限制不够，long也不够（利用数组吧）

    这个也稍微讲一下，范围内这个方法也不错

    1.     long  res=0,sum=0;  
    2.     for(int i=0;isize();i++){//模拟竖式
    3.             for(int j=0;jsize();j++){//模拟竖式
    4.                 res=A[j]*B[i]+res*10;
    5.                 //cout<
    6.             }
    7.             sum=sum*10+res;
    8.             res=0;
    9.         }

    方法一：利用数组存出结果，然后再处理进位，如图：这里牵扯到一个知识点就是n位*m位最终返回为m+n-1位

    1.  // 模拟两数相乘的过程
    2.         for (int i = len2 - 1; i >= 0; i--) {
    3.             for (int j = len1 - 1; j >= 0; j--) {
    4.                 res[i + j + 1] += A[j] * B[i];
    5.             }
    6.         }
    7.  
    8.         // 处理进位
    9.         for (int i = len1 + len2 - 1; i > 0; i--) {
    10.             if (res[i] >= 10) {
    11.                 res[i - 1] += res[i] / 10;
    12.                 res[i] = res[i] % 10;
    13.             }
    14.         }

    整体代码：

    1. class Solution {
    2. public:
    3.     string multiply(string num1, string num2) {
    4.         if (num1 == "0" || num2 == "0") 
    5.             return "0";
    6.         vector<int> A, B;
    7.         int len1 = num1.size(), len2 = num2.size();
    8.         vector<int> res (len1+len2,0); // 存放相乘结果
    9.         string ans = "";
    10.  
    11.         // 将 num1、num2 分别存入 A、B 中
    12.         for (int i = 0; i < len1; i++) {
    13.             A.push_back(num1[i] - '0');
    14.         }
    15.         for (int i = 0; i < len2; i++) {
    16.             B.push_back(num2[i] - '0');
    17.         }
    18.  
    19.         // 模拟两数相乘的过程
    20.         for (int i = len2 - 1; i >= 0; i--) {
    21.             for (int j = len1 - 1; j >= 0; j--) {
    22.                 res[i + j + 1] += A[j] * B[i];
    23.             }
    24.         }
    25.  
    26.         // 处理进位
    27.         for (int i = len1 + len2 - 1; i > 0; i--) {
    28.             if (res[i] >= 10) {
    29.                 res[i - 1] += res[i] / 10;
    30.                 res[i] = res[i] % 10;
    31.             }
    32.         }
    33.  
    34.         // 构造结果字符串
    35.         for (int i = 0; i < len1 + len2; i++) {
    36.             if (i == 0 && res[i] == 0) {
    37.                 continue; // 最高位不含前导零
    38.             }
    39.             ans += to_string(res[i]); // 将数字转化为字符串
    40.         }
    41.  
    42.         return ans;
    43.     }
    44. };

      14. 最长公共前缀

    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

    这道题啊，首先第一个想法就是：横向比较：如图： 

    其实就是一个一个比较不断缩小最长公共前缀，公共前缀使用Commen函数截取。（这个函数太赞了）

    1. class Solution {
    2. public:
    3.     string longestCommonPrefix(vector& strs) {
    4.         if(strs.size()==0) return " ";
    5.         string con_str=strs[0];
    6.         int i=1;
    7.         while(isize()){
    8.             string str=strs[i];
    9.             con_str=Common(con_str,str);
    10.             if(!con_str.size()) break;
    11.             i++;
    12.         }
    13.         return con_str;
    14.     }
    15.     string Common(string str1, string str2){
    16.         int len=min(str1.size(),str2.size());
    17.         int index=0;
    18.         while (index < len && str1[index] == str2[index]) {
    19.             ++index;
    20.         }
    21.         return str1.substr(0,index);
    22.     }
    23. };

    另外提交后还看到一种写法也很赞：将字符串进行排序，第一个和最后一个一定是最不相同的，所以直接找第一个和最后一个的公共前缀即可。

    1. class Solution {
    2. public:
    3.     string longestCommonPrefix(vector& str) {
    4.         sort(str.begin(),str.end());
    5.                 
    6.         string &s1=str.front();
    7.         string &s2=str.back();
    8.         
    9.         int i=0;
    10.         while(s1[i]==s2[i] && isize() && isize()){
    11.             ++i;
    12.         }
    13.         return s1.substr(0, i);
    14.     }
    15. };

     知识点补充：

    1.字符串比较：

    1. 字符串之间的大小取决于它们接顺序排列字符的前后顺序。
    2. eg。str1="abc”和 str2="acc”，它们的第一个字母都是a，而第二个字母，由于字母b比字母c要靠前，所以b"<"acd”，也可以说strl < str2.
    3.  
    4. 如果说两个字符串 strl和 str2 相等，则必须满足两个条件:
    5. 1.字符串 str1 和字符串 str2 的长度相等。
    6. 2.字符串 str1 和字符串 str2 对应位置上的各个字符都相同。
    7.  
    8.  
    9. 而对于两个不相等的字符串，我们可以以下面的规则定义两个字符串的大小:
    10. 从两个字符串的第0个位置开始，依次比较对应位置上的字符编码大小。
    11. 如果 str1|i]对应的字符编码==str2|i]对应的字符编码，则比较下一位字符。
    12. 如果 str1|i] 对应的字符编码< str2[i]对应的字符编码，则说明str1"abc”<"acc”。
    13. 如果 str1[i] 对应的字符编码> str2|i]对应的字符编码，则说明str1>str2。比如:"bcd">"bad"
    14.  
    15. 如果比较到某一个字符串末尾，另一个字符串仍有剩余:
    16.     字符串 str1 的长度小于字符串 str2,即len(str1)<len(str2)。则 str1
    17.

    所以前面在sort str后，str应该是

    ["flower","flow","flight"]---->flight flow flower

    2.

    1. string a="abcd"
    2.  
    3. 1.获取字符串最后一个字符
    4. auto b=a.back(); //结果为 b='d';
    5.  
    6. 2.修改字符串最后一个字符
    7. a.back()='!'; //结果为 a="abc!";
    8.  
    9. 3.获取字符串第一个字符
    10. auto b=a.front(); //结果为 b='a';
    11.  
    12. 4.修改字符串第一个字符
    13. a.front()='!'; //结果为 a="!bcd";

    方法三：还有一种方法就是：纵向扫描，

    纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

    1. class Solution {
    2. public:
    3.     string longestCommonPrefix(vector& strs) {
    4.         if (!strs.size()) {
    5.             return "";
    6.         }
    7.         int length = strs[0].size();//行
    8.         int count = strs.size();//列数
    9.         for (int i = 0; i < length; ++i) {
    10.             char c = strs[0][i];
    11.             for (int j = 1; j < count; ++j) {
    12.                 if (i == strs[j].size() || strs[j][i] != c) {//到头或者有不同
    13.                     return strs[0].substr(0, i);
    14.                 }
    15.             }
    16.         }
    17.         return strs[0];
    18.     }
    19. };

    终于结束了 

  • 相关阅读:
    二、W5100S/W5500+RP2040树莓派Pico＜DHCP＞
    【毕业季·进击的技术er】大学生计算机毕业设计应该这样写
    全网最详细单细胞保姆级分析教程(二) --- 多样本整合
    selenium常见异常以及处理方法
    C声明和初始化和赋值
    C++笔记20•数据结构:哈希(Hash)•
    WKWebKit总结
    阿里云物联网平台专用工具详细说明
    【Mybatis 源码】 Mybatis 是如何解析配置文件中的内容 -- properties
    SpringBoot ORM操作MySQL、REST接口架构风格、集成Redis和集成Dubbo
  • 原文地址：https://blog.csdn.net/m0_67403773/article/details/136595638