[算法刷题打卡]Day11

1、Leetcode-面试经典150题目20- 14. 最长公共前缀

思路：

1、首先对于空的情况判断，直接返回“ ”

2、对于多个即两个以上的字符串找公共前缀，其实就是先两个两个找公共前缀。道理很简单，ans(S1,S2,S3,S4) =  ans(S4,ans(S3,ans(S1,S2)))

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        //首先，对于长度为0的情况
        if(!strs.size()) return " ";
        string ans = strs[0];//结果初始化为第一个字符串
        for(int i = 1;i < n;i ++){
            ans = longestCommonPrefix(ans,strs[i]);
        }
        return  ans;
    }
    string longestCommonPrefix(const string& str1 , const string& str2){
            //比较，首先长度要选两者最短
            int l = min(str1.size(),str2.size());
            int i = 0;//记录下标
            while(l){
                if(str1[i] == str2[i])
                    i ++;
                l--;

            }
        
            return str1.substr(0,i);
    }
};

  2、Leetcode-面试经典150题目21-151. 反转字符串中的单词

思路：

• #include <alogrithm>
• reverse（s.begin(),s.end()）翻转字符
• s.earse(s.begin(),s.end())消除除范围内的也可以只有一个参数

1、先将整体的字符串反转

2、逐个找到每个单词，记录开始和结尾，翻转并加上一个' '

3、对于每个单词的reverse范围 ( s.begin()+当前遍历下标-单词的长度 , s.begin()+当前遍历下标)

class Solution {
public:
    string reverseWords(string s) {
        //首先翻转字符串
        reverse(s.begin(),s.end());
        //记录当前下标idx 
        int idx =0;
        //记录start 和 end
        int start ,end;
        int n = s.size();
        for(start = 0;start < n ; ++ start){
           if(s[start] != ' '){
             //对于每个单词之间都需要加一个空格
            if(idx != 0 )//开头不需要加
                s[idx++] = ' ';

            end = start;
            while(end < n &&s[end] != ' '){
                s[idx ++] = s[end ++];
            }
            //遍历完之后,要开始翻转
            reverse(s.begin()+idx-(end - start),s.begin()+idx);

            //end给start，开始遍历下一个单词
            start = end;
           }
        }
        s.erase(s.begin()+ idx ,s.end());
        return s;
    }
};

 还有一种更快的，要用到istringstream，在C++中，istringstream是一个用于从字符串中提取数据的类。它是<sstream>标头文件中定义的istringstream类的一个实例。istringstream类允许你将一个字符串视为输入流，从中按照你指定的格式提取数据。

class Solution {
public:
    string reverseWords(string s) {
            istringstream iss(s);
            string ans ;
            string n;//用于存储每次取出来的单词
            while(iss >> n){
                if(ans != ""){
                    ans = n + " " + ans;                
                 }else{
                    ans = n;
                 }
                  
            }

          return ans; 
    }
};

每日一言：“生活就像一本书，不论有多么苦难的一页，都要勇敢地翻过去，因为转过下一页，你会发现风景依然美丽。”

2024年4月10日

softdream