27.日常算法

1. 最后一个单词的长度

题目来源
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：
输入：s = “Hello World”
输出：5
解释：最后一个单词是“World”，长度为 5。

class Solution {
public:
    int lengthOfLastWord(string s) {
        int n = s.size();
        int end = n - 1;
        while (end >= 0){
            if (s[end] == ' ') end--;
            else break;
        }
        int idx = end;
        while (idx >= 0){
            if (s[idx] == ' ') break;
            idx--;
        }
        return end - idx;
    }
};

2. 最长公共前缀

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

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        for (int i = 0; i < strs[0].size(); i++){
            char ch = strs[0][i];
            for (int j = 1; j < strs.size(); j++){
                if (strs[j][i] != ch || i == strs[j].size()) 
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

二分查找

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int minlen = min_element(strs.begin(), strs.end(), [](const string& s, const string& t) {return s.size() < t.size();})->size(); // min_element返回的是strs中长度最短的字符串的迭代器，所以这里需要->size()获取长度
        int left = 0, right = minlen;
        while (left < right){
            int mid = (right - left + 1) / 2 + left;
            if (isCommon(strs, mid)){
                left = mid;
            }else right = mid - 1;
        }
        return strs[0].substr(0, right);
    }
    bool isCommon(vector<string>& strs, int len){
        string temp = strs[0].substr(0, len);
        for (int i = 1; i < strs.size(); i++){
            for (int j = 0; j < temp.size(); j++){
                if (temp[j] != strs[i][j]) return false;
            }
        }
        return true;
    }
};