力扣（leetcode）题目总结——字符串篇

【题目描述】

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。（答案必须是子串的长度，不是子序列）

1. 子串（Substring）：指的是一个字符串中连续的一段子字符串。例如，在字符串 “abcd” 中，“bc” 和 “abcd” 都是它的子串。
2. 子序列（Subsequence）：指的是从字符串中按照原有顺序但不一定是连续的选取字符组成的新字符串。换句话说，子序列是通过原始字符串中选择某些字符而不改变它们的相对顺序，在不一定连续的情况下形成的新字符串。在字符串 “abcd” 中，“ac” 和 “bd” 都是它的子序列，但不是子串。

【输入输出实例】

示例 1:

输入: s = “abcabcbb”
输出: 3 （无重复字符的最长子串是 “abc”，所以其长度为 3）

示例 2:

输入: s = “bbbbb”
输出: 1

示例 3:

输入: s = “pwwkew”
输出: 3

【算法思路】

利用滑动窗口的思想，设置滑动窗口的左指针和右指针，通过对给定字符串s的遍历，利用右指针不断扩大滑动窗口的右边界，且要保证窗口内不出现重复字符。如果出现重复字符，就要缩小左边界，缩小到左右边界内的窗口不出现重复字符。

每次移动都需要重新计算窗口的大小，判断当前窗口长度是否大于长度最大值，若大于长度最大值，则更新长度最大值。

【算法描述】

int lengthOfLongestSubstring(string s) 
{
    int MaxStr = 0;  //记录最长子串的长度
    int right = 0;  //右指针
    int left = 0;  //左指针
    for(int i = 0; i < s.size(); i++)  //遍历s
    {
        for(int j = left; j < right; j++)  //遍历滑动窗口
        {
            if(s[j] == s[i])  //遇到重复字符时，滑动窗口左指针移到重复元素的下一位
            {
                left = j + 1;
                break;
            }
        }
        right++;  //滑动窗口右指针每次都要右移
        MaxStr = max(MaxStr, right - left);  //找最长子串长度
    }
    return MaxStr;     
}

【题目描述】

将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行Z字形排列。比如输入字符串为"PAYPALISHIRING"，行数为3时，排列如下：

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

【输入输出实例】

示例 1：

输入：s = “PAYPALISHIRING”, numRows = 3
输出：“PAHNAPLSIIGYIR”

示例 2：

输入：s = “A”, numRows = 1
输出：“A”

【算法思路】

设numRows行字符串分别为s1, s2, … , sn，则容易发现：按顺序遍历字符串s时，每个字符c在Z字形中对应的行索引先从s1到sn，再从sn到s1，如此反复。

算法流程：按顺序遍历字符串s；

• res[i] += c：把每个字符c填入对应行si；
• i += flag：更新下一个字符c对应的行索引；
• flag = - flag：在达到Z字形转折点时，执行反向；
• 将所有字符c放入res[]各行中后，再将res各行字符串加起来。

【算法描述】

string convert(string s, int numRows) 
{
    if(numRows < 2)  //给定的行数numRows为1，直接返回s
    {
        return s;
    }
    vector<string> v(numRows);  //存放Z排列后每行的字符串
    string str;  //存放最后的结果
    int flag = -1;
    int i = 0;  //表示当前行
    for(int j = 0; j < s.size(); j++)  //遍历s
    {
        v[i] += s[j];   //拼接第i行字符串
        if(i == 0 || i == numRows-1)  //达到Z字形转折点时(即第一行和最后一行)，要改变方向
        {
            flag = -flag;
        }
        i += flag;  //更新下一个字符对应的行索引
    }
    for(int i = 0; i < numRows; i++)  //将v中字符串拼接起来即为按Z排列后的行输出
    {
        str += v[i];
    }
    return str;
}

【题目描述】

实现一个myAtoi(string s)函数，使其能将字符串转换成一个32位有符号整数。

函数 的具体实现如下：

• 读入字符串并丢弃无用的前导空格；
• 检查下一个字符(假设还未到字符末尾)为正还是负号，读取该字符(如果有 ’+’ 或 ’-’ )，确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
• 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串剩余部分将被忽略。
• 如果没有读入数字，则整数为0。如果整数超过32位有符号整数范围[−2³¹, 2³¹−1]，则需要截断这个整数，使其保持在这个范围内。具体来说，小于−2³¹的整数应该被固定为−2³¹，大于2³¹−1的整数应该被固定为2³¹−1。

注意：

• 本题中的空白字符只包括空格字符’ '。
• s由英文字母(大写和小写)、数字(0-9)、’ ‘、’+‘、’-’ 和 ‘.’ 组成。

【输入输出实例】

示例 1：

输入：s = " 42"
输出：42

示例 2：

输入：s = " -42"
输出：-42

示例 3：

输入：s = " ±42"
输出：0

示例 4：

输入：s = “4193 with words”
输出：4193

示例 5：

输入：s = “abcd 1234”
输出：0

示例 6：

输入：s = “2147483648”
输出：2147483647

【算法思路】

• 根据示例1，需要去掉前导空格；
• 根据示例2，需要判断第1个字符为 ‘+’ 和 ‘-’ 的情况，因此，可以设计一个变量flag来判断数字正负；
• 根据示例4，判断字符是否为数字字符，可以使用字符的ASCII码数值进行比较，即’0’ <= c <= ‘9’；
• 根据示例3和示例5，在遇到第1个不是数字字符的情况下，转换停止，退出循环；
• 根据示例6，如果转换以后的数字超过了int类型的范围，需要截取。由于输入的字符串转换以后也有可能超过int类型，因此需要提前判断是否越界(在最大数的倒数第二位判断)，只要越界就退出循环；

【算法描述】

int myAtoi(string s) {
    int len = s.size();
    int num = 0;  //存储最后结果
    int index = 0;
    bool sign = true;
    //去掉前导空格
    while(index < len && s[index] == ' ') {
        index++;
    }
    //防止s全为空格' '
    if(index == len) {  
        return 0;
    }
    //检查是否有正负号字符来判断正负
    if(s[index] == '+') {            
        sign = true;
        index++;
    } else if(s[index] == '-') {
        sign = false;
        index++;
    }
    //判断字符是否为数字字符，使用字符的ASCII码数值进行比较，即'0' <= c <= '9'
    while(index < len && s[index] >= '0' && s[index] <= '9') {
        int temp = s[index] - '0';  //转为int类型
        // 防止数据溢出
        if(sign) {
            if(num > 214748364 || (num == 214748364 && temp >= 7)) { //从倒数第二位开始判断是否溢出
                return 2147483647;
            }
        } else {
            if(num > 214748364 || (num == 214748364 && temp >= 8)) { //从倒数第二位开始判断是否溢出
                return -2147483648;
            }
        }          
        num = num*10 + temp;
        index++;
    }
    return sign ? num : -num;  //判断正负再输出
}

【题目描述】

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

【输入输出实例】

示例 1：

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

示例 2：

输入：strs = [“dog”,“racecar”,“car”]
输出：“”

【算法思路】

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

【算法描述】

string longestCommonPrefix(vector<string>& strs) 
{
    for(int i = 0; i < strs[0].size(); i++)   //横向遍历——选strs中任一字符串进行遍历(默认用第一个字符串)
    {
        for(int j = 1; j < strs.size(); j++)  //纵向遍历——遍历每行的同一位置字符
        {
            //当第j行字符串遍历完，或者出现了不为公共的前缀字符，直接返回截止到该位置的子串
            if(strs[j].size() == i || strs[j][i] != strs[0][i])
            {
                return strs[0].substr(0,i);
            }
        }
    }
    return strs[0];
}

【题目描述】

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从 0 开始)。如果needle不是haystack的一部分，则返回 -1。

【输入输出实例】

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释："sad"在下标0和6处匹配。第一个匹配项的下标是0，所以返回0。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释："leeto"没有在"leetcode"中出现，所以返回-1。

【算法思路】

方法一：暴力求解法

可以让字符串needle与字符串haystack中所有长度为m的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，haystack回溯到起始位置的下一个字符，needle回溯到起始位置，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回-1。

方法二：KMP解法

当主串和匹配串在某个字符不匹配时，主串指针i不用回溯，匹配串指针j不一定要重新从1开始，根据匹配串的前后匹配结果令j回到next[j-1]处，即j = next[j-1]。为此，定义next[j]数组，表明当匹配串中第j个字符与主串中相应字符“失配”时，令匹配串跳到next[j-1]再继续匹配。

• 匹配思路

• 求匹配串的next数组

  口述过程：

  • 首先next[0]肯定为0
  • 任意下标i对应的next[i]为子串[0:i]中最大的前缀和后缀匹配个数
  • 匹配串下标i失配时，要回溯到next[i-1]，注意不是回溯到next[i]

  例如：求匹配串s为"ababa"的next数组

  next[0] = 0
  next[1] = 0    前缀a -- 后缀b  匹配个数0
  next[2] = 1    前缀a -- 后缀a  匹配个数1    
                 前缀ab -- 后缀ba  匹配个数0  -->  最大为1
  next[3] = 2    前缀a -- 后缀b  匹配个数0    
                 前缀ab -- 后缀ab  匹配个数2
                 前缀aba -- 后缀bab  匹配个数0  -->  最大为2
  next[4] = 3    前缀a -- 后缀a  匹配个数1    
                 前缀ab -- 后缀ba  匹配个数0
                 前缀aba -- 后缀aba  匹配个数3 
                 前缀abab -- 后缀baba  匹配个数0  -->  最大为3
  

  代码过程：

  利用两个指针（快指针i和慢指针j），直到快指针i到达s.size()为止，不断循环找s[0:i]子串中的前缀和后缀存在相同元素，并用next[i]来记录。若不存在相同元素时，则j不断回退到next[j-1]，直到s[i] == s[j]或j == 0。当回退到j == 0还不相等时，说明s[i]该字串的前缀和后缀不存在相同元素，即next[i] = 0，同时i++。

  

  

  

  

• 注意：匹配过程的代码int strStr(string haystack, string needle)和求next数组的代码vector<int> getNext(string& s)结构非常类似。

【算法描述】

//方法一：暴力求解法
int strStr(string haystack, string needle) 
{
    int m = haystack.size();
    int n = needle.size();
    for(int i = 0; i <= m - n; i++)    //遍历haystack中所有长度为n的子串
    {
        int hay = i;  //若失配，则回溯到haystack起始的下一个
        int nee = 0;  //若失配，则回溯到needle起始
        while(nee < n && haystack[hay] == needle[nee])
        {
            hay++;  //匹配成功，则继续向右匹配
            nee++;
        }
        if(nee == n)  //匹配成功
        {
            return i;  //返回第一个匹配项的下标
        }
    }
    return -1;
}

//方法二：KMP解法
int strStr(string haystack, string needle)
{
    vector<int> next = getNext(needle);  //求next数组
    int m = haystack.size();
    int n = needle.size();
    int i = 0;  //haystack字符串下标
    int j = 0;  //needle字符串下标
    while(i < m && j < n)
    {
        if(haystack[i] == needle[j])  //两字符串逐个匹配
        {
            i++;  j++;
        }
        else  //如遇到不匹配的元素，则j回退，i不用动
        {
            if(j == 0)  //如果j回退到s的第一个元素，
            {
                i++;  //说明haystack[i]字符一直没匹配到
            }
            else  //如果j不是位于s的第一个元素，
            {
                j = next[j-1];  //j回退到next[j-1]
            }
        }
    }
    if(j == n)  //匹配成功
    {
        return i - j; //i为haystack中匹配成功字符的最后一个字符下标，减去匹配串的长度，即为匹配成功字符的第一个字符下标
    }
    else  //匹配失败
    {
        return -1;
    }
}
//求next数组
vector<int> getNext(string& s)
{
    int n = s.size();
    int j = 0;   //慢指针
    int i = 1;   //快指针
    vector<int> next(n);  //next数组，初始化为0
    while(i < n)
    {
        if(s[i] == s[j])  //s[0:i]中的前缀和后缀存在相同元素
        {
            next[i] = j + 1;  //记录字串s[0:i]中前缀和后缀相同的元素个数
            i++; j++;  //继续向后寻找
        }
        else  //不存在相同元素时，则j回退
        {
            if(j == 0)  //如果j回退到s的第一个元素，
            {
                next[i] = 0;  //说明该字串的前缀和后缀不存在相同元素
                i++;
            }
            else  //如果j不是位于s的第一个元素，
            {
                j = next[j-1];  //j回退到next[j-1]
            }
        }
    }
    return next;  //返回next数组
}

//方法三：库函数find
int strStr(string haystack, string needle)
{
    return haystack.find(needle);
}

【题目描述】

给定一个字符串s和一个字符串数组words。words中所有字符串长度相同。 s 中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联字串在 s 中的开始索引。可以以任意顺序返回答案。

【输入输出实例】

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：子串"barfoo"开始位置是0。它是words中以 [“bar”,“foo”] 顺序排列的连接。子串"foobar"开始位置是9。它是words中以 [“foo”,“bar”] 顺序排列的连接。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

【算法思路】

因为单词长度是固定的，我们可以计算出截取字符串的单词个数是否和words里相等，所以我们可以借用哈希表。

一个哈希表是word，用来存放words中的单词及出现的次数；一个哈希表hash是截取的字符串，即从 s 中不断划分单词，存放匹配成功的单词及出现的个数，再比较两个哈希是否相等。

先考虑如何能找到 s 划分的所有指定长度 n 的单词？从下标 i 开始把 s 划分为字母为 n 的单词，i 的取值为 0 ~ n-1，则只需要循环 n次就可以划分出所有长度为 n 的单词，因为从 i = n+1 开始划分与 i = 0 开始划分的单词是一样的。

从下标 i 开始划分 s，通过移动右指针right以间隔 n 来遍历 s。若此单词不在word中，表示匹配不成功，则要清除之前hash中记录的单词，并且移动窗口左指针到下一个单词继续匹配。若此单词在word中，表示匹配成功，则将该单词加入到hash中，并检查该单词是否匹配多次，即检查该单词在hash中出现的次数是否比word中高，若是则需要缩小窗口，也就是left右移，将移出窗口的单词在hash中–，直到hash中出现的次数小于word中次数。

最后只要成功匹配的单词数达到 m 时，则表示找到了一个串联子串，其left为该字串的起始下标，放入result即可。

【算法描述】

//滑动窗口
vector<int> findSubstring(string s, vector<string>& words) 
{
    vector<int> result;    //存放结果
    int m = words.size();    //单词数
    int n = words[0].size();    //每个单词的字母数
    int len = s.size();
    unordered_map<string, int> word;    //存放words中的单词及出现的个数
    for(string str : words)
    {
        word[str]++;
    }
    //从下标i开始把s划分为字母为n的单词
    //只需要循环n次就可以划分出所有长度为n的单词，因为从i = n+1开始划分与i = 0开始划分的单词是一样的
    for(int i = 0; i < n; i++)  
    {
        int left = i;   //滑窗左指针
        int right = i;  //滑窗右指针
        int count = 0;   //记录已成功匹配的单词数
        unordered_map<string, int> hash;   //存放匹配成功的单词及出现的个数
        while(right + n <= len)
        {
            string str(s.begin() + right, s.begin() + right + n);  //左闭右开：划分单词
            right += n;   //窗口右边界右移一个单词的长度
            if(word.find(str) == word.end())  //此单词不在words中，表示匹配不成功
            {
                count = 0;   //重置，清除之前记录的单词
                hash.clear();
                left = right;  //移动窗口左指针
            }
            else  //此单词在words中，表示匹配成功
            {
                hash[str]++;  //将单词加到hash中
                count++;
                while(hash[str] > word[str]) //一个单词匹配多次，需要缩小窗口，也就是left右移
                {
                    string temp(s.begin() + left, s.begin() + left + n);
                    hash[temp]--;
                    count--;
                    left += n;
                }
            }
            if(count == m)  //成功匹配的单词数达到m时，表示找到了一个串联子串
            {
                result.push_back(left);
            }
        }
    }
    return result;
}

【题目描述】

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

注意：不能使用任何内置的库或直接将输入转换为整数。

【输入输出实例】

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

【算法思路】

• 如果num1和num2之一是0，则直接将0作为结果返回即可。
• 如果num1和num2都不是0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数num2，将乘数的每一位与被乘数num1的所有位相乘得到对应的结果，再将每次得到的结果累加。

需要注意的是，num2除了最低位以外，其余的每一位的相乘之后的运算结果都需要补0。

【算法描述】

//字符串相乘
string multiply(string num1, string num2) 
{
    if(num1 == "0" || num2 == "0")  //0乘任何数还为0
    {
        return "0";
    }
    string result = "0";  //存放最后结果
    for(int i = num2.size() - 1; i >= 0; i--)
    {
        string str;  //表示每一项num2[i]与num1所有项的乘积
        str.assign(num2.size() - i - 1, '0');  //后面补0
        int addNum = 0;  //表示进位
        for(int j = num1.size() - 1; j >= 0; j--)  //num2[i]与num1竖式相乘
        {
            str += (((num1[j]-'0') * (num2[i]-'0') + addNum) % 10) + '0';
            addNum = ((num1[j]-'0') * (num2[i]-'0') + addNum) / 10;  //更新进位
        }
        if(addNum != 0)  //最后乘完后还有进位，则在最高位补进位值
        {
            str += addNum + '0';
        }
        reverse(str.begin(), str.end());
        result = addStrings(result, str);  //将竖式相乘得到的每一项相加
    }
    return result;
}
//字符串相加
string addStrings(string num1, string num2)
{
    int i = num1.size() - 1;  //遍历num1的指针
    int j = num2.size() - 1;  //遍历num2的指针
    int addNum = 0;  //表示进位
    string s;  //存放最后结果
    while(i >= 0 || j >= 0 || addNum != 0)  //竖式加法
    {
        int x = (i >= 0 ? num1[i--]-'0' : 0);
        int y = (j >= 0 ? num2[j--]-'0' : 0);
        s += (x + y + addNum) % 10 + '0';
        addNum = (x + y + addNum) / 10;  //更新进位
    }
    reverse(s.begin(), s.end());
    return s;
}

【题目描述】

给你一个字符串s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

【输入输出实例】

示例 1：

输入：s = “Hello World”
输出：5 （最后一个单词是“World”）

示例 2：

输入：s = " fly me to the moon "
输出：4 （最后一个单词是“moon”）

示例 3：

输入：s = “luffy is still joyboy”
输出：6 （最后一个单词是“joyboy”）

【算法思路】

利用end下标来从后往前找第一个不为 ’ ’ 的字符下标，用begin下标从end开始从后往前找第一个为 ’ ’ 的字符下标，用两下标相减即为最后一个单词的长度。

【算法描述】

int lengthOfLastWord(string s) {
    int begin = -1;   //记录最后一个单词的起始(开区间)
    int end = s.size() - 1;   //记录最后一个单词的结尾(闭区间)
    for(int i = end; i >= 0; i--)   //从后往前找end
    {
        if(s[i] != ' ')    //从后往前找第一个不为' '的字符下标
        {
            end = i;
            break;
        }
    }
    for(int i = end - 1; i >= 0; i--)   //从后往前找begin
    {
        if(s[i] == ' ')   //从end开始往前找第一个为' '的字符下标
        {
            begin = i;
            break;
        }
    }
    return end - begin;  //下标相减即为单词长度
}

【题目描述】

有效数字（按顺序）可以分成以下几个部分：

1. 一个 小数 或者 整数
2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

【输入输出实例】

示例 1：

输入：s = “0”
输出：true

示例 2：
输入：s = “e”
输出：false

示例 3：
输入：s = “.”
输出：false

【算法思路】

重新整理下题目：

• 有效数字的要求：整数/小数 [e/E 整数]
  • 整数要求：
    （1）一个符号字符（可选）
    （2）至少有一位数字
  • 小数要求：
    （1）一个符号字符（可选）
    （2）至少有一位数字
    （3）要有一个点 '.'，例如1.1、.1、1.

【算法描述】

bool isNumber(string s) {
    int n = s.size();
    int index = -1;
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'e' || s[i] == 'E') {
            if(index != -1) {
                return false;
            }
            index = i;
        }
    }
    // 没有e/E的情况，直接判断 整数/小数
    if(index == -1) {
        return checkInt(s, 0, n-1) || checkFloat(s, 0, n-1);
    }
    // 有e/E的情况，判断 整数/小数 e/E 整数
    return (checkInt(s, 0, index-1) || checkFloat(s, 0, index-1)) && checkInt(s, index+1, n-1);
}

// 检查是否为有效整数
bool checkInt(const string& s, int start, int end) {
    // 起始有符号位就跳过
    if(s[start] == '+' || s[start] == '-') {
        ++start;
    }
    if(start > end) {
        return false;
    }
    for(int i = start; i <= end; ++i) {
        if(s[i] < '0' || s[i] > '9') {
            return false;
        }
    }
    return true;
}

// 检查是否为有效小数
bool checkFloat(const string& s, int start, int end) {
    // 起始有符号位就跳过
    if(s[start] == '+' || s[start] == '-') {
        ++start;
    }
    if(start >= end) {
        return false;
    }
    bool point = false;
    for(int i = start; i <= end; ++i) {
        // 只能有一个'.'
        if(s[i] == '.') {
            if(point) {
                return false;
            }
            point = true;
        }
        else if(s[i] < '0' || s[i] > '9') {
            return false;
        }
    }
    return point;
}

【题目描述】

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

【输入输出实例】

示例 1:

输入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
输出:
[
“This is an”,
“example of text”,
"justification. "
]

示例 2:

输入:words = [“What”,“must”,“be”,“acknowledgment”,“shall”,“be”], maxWidth = 16
输出:
[
“What must be”,
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 “shall be”,
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:words = [“Science”,“is”,“what”,“we”,“understand”,“well”,“enough”,“to”,“explain”,“to”,“a”,“computer.”,“Art”,“is”,“everything”,“else”,“we”,“do”]，maxWidth = 20
输出:
[
“Science is what we”,
“understand well”,
“enough to explain to”,
“a computer. Art is”,
“everything else we”,
"do "
]

【算法思路】

1. 编写一行单词的空格填充算法，string fillSpace(vector<string>& words, int maxWidth, bool last)，根据题目要求，每个单词之间必须有一个分割空格，用 maxWidth - 所有单词长度 - 分割空格个数 就是剩余要填充的额外空格数，将剩余额外空格数按顺序从左往右填充到words[i]中，最后拼接起来即可。还有一种特殊情况，如果是最后一行单词last == true，或者该行只有一个单词，那么要把所有额外空格添加到末尾。
2. 遍历单词数组，找出一行可以容纳的单词，并求该行填充空格后的结果，放入结果数组。遍历完所有单词即可。

【算法描述】

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    int n = words.size();
    vector<string> result, currRow;
    int currLen = 0;
    for(int i = 0; i < n; ++i) {
        // 当前单词长度 + 本行已有单词长度 + 分割空格数不超过 maxWidth 
        if(words[i].size() + currLen + currRow.size() <= maxWidth) {
            currRow.push_back(words[i]);
            currLen += words[i].size();
        }
        else {
            // 超过则说明该行只能容纳这些单词，进一步填充空格
            result.push_back(fillSpace(currRow, maxWidth, false));
            currRow = vector<string>{words[i]};
            currLen = words[i].size();
        }
    }
    // 给最后一行填充空格
    result.push_back(fillSpace(currRow, maxWidth, true));
    return result;
}

// 给一行 words 填充空格
string fillSpace(vector<string>& words, int maxWidth, bool last) {
    int n = words.size();
    string result;
    int currLen = 0;
    // 给除最后一个单词外填充分割空格
    for(int i = 0; i < n; ++i) {
        if(i != n-1) {
            words[i] += ' ';
        }
        currLen += words[i].size();
    }
    // 如果是最后一行或者该行只有1个单词，则只能在最后填充额外空格
    if(last || n == 1) {
        words[n-1] += string(maxWidth - currLen, ' ');
    }
    else {
        // 否则按顺序从左往右填充额外空格
        for(int i = 0; i < maxWidth - currLen; ++i) {
            int index = i % (n-1);
            words[index] += ' ';
        }
    }
    // 将填充后的结果合并
    for(const auto& i : words) {
        result += i;
    }
    return result;
}

【题目描述】

给你一个字符串 path ，表示指向某一文件或目录的绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

注意：在文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘///’）都被视为单个斜杠 ‘/’ 。

请注意，返回的规范路径必须遵循下述格式：

• 始终以斜杠 ‘/’ 开头；
• 两个目录名之间必须只有一个斜杠 ‘/’ ；
• 最后一个目录名（如果存在）不能以 ‘/’ 结尾；
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即不含 ‘.’ 或 ‘…’）。

返回简化后得到的规范路径。

【输入输出实例】

示例 1：

输入：path = “/home/”
输出：“/home” （注意，最后一个目录名后面没有斜杠）

示例 2：

输入：path = “/…/”
输出：“/” （从根目录向上一级是不可行的，因为根目录是你可以到达的最高级）

示例 3：

输入：path = “/home//foo/”
输出：“/home/foo” （在规范路径中，多个连续斜杠需要用一个斜杠替换）

示例 4：

输入：path = “/a/./b/…/…/c/…/”
输出：“/c/…”

【算法思路】

我们首先将给定的字符串 path 根据 '/' 进行分割，将分割结果放到字符串容器 v 中。根据题目中规定的「规范路径的下述格式」，v 中包含的字符串只能为以下几种： （ 如遇到连续 '/' ，当作一个 '/' 处理 ）

• 一个点 "." ；
• 两个点 ".." ；
• 由英文字母、数字、'.'、'/' 或 '_' 组成的目录名；

(1) 对于「一个点"."」，表示当前目录本身。所以我们只需要将字符串容器 v 中的"."直接删除即可。

(2) 对于「两个点".."」，表示切换到上一级目录。我们不仅要删除 v 中的".."，如果上一级还有文件/目录名称（即字符串容器不为空），我们就还要删除上一级的目录（即 “…” 的前一个目录）。

(3) 对于「正常的文件/目录名称」，我们无需进行任何处理。

这样一来，我们只需要遍历 v 中的每个字符串并进行上述操作即可。在所有的操作完成后，我们再次遍历 v ，将字符串拼接起来就可以得到简化后的规范路径。

算法优化：在将 path 根据 '/' 进行分割的同时将路径化简。每分割出一个字符串时，就进行判断：是 一个点"."、 两个点".." 还是 正常文件/目录名称 。

• 如遇到"."，直接不加入到 v 中；
• 如遇到".."时，不仅不加入到 v 中，还要删除上一级；
• 如遇到正常的文件/目录名称，直接放入 v 中。

最后遍历 v ，将字符串拼接起来就可以得到简化后的规范路径。

【算法描述】

//先将path根据'/'进行分割，再对分割后的字符串容器进行化简(除去".."和".")，最后将简化后的路径拼接起来
string simplifyPath(string path) 
{
    vector<string> v;   //将给定的字符串path根据'/'进行分割（若遇到多个连续'/'，当作一个'/'处理），存放到v中
    string result;    //存放简化后得到的规范路径 
    path += "/";    //字符串path末尾加"/"，保证可以把最后一个文件/目录名称分割出来
    int index = 1;    //记录'/'后第一个字符的下标
    for(int i = 1; i < path.size(); i++)    //遍历path，根据'/'进行分割
    {
        if(path[i] == '/')
        {
            if(i != index)    //遇到连续'/'时，不处理
            {
                v.push_back(path.substr(index, i-index));
            }
            index = i + 1;
        }
    }
    for(int i = 0; i < v.size(); i++)    //遍历分割后的字符串容器
    {
        if(v[i] == ".")    //遇到"."时，表示当前目录本身，直接删除"."即可
        {
            v.erase(v.begin() + i);
            i--;
            continue;
        }
        if(v[i] == "..")//遇到".."时，表示切换到上一级目录，不仅要删除".."，如果上一级还有文件/目录名称，也要删除上一级
        {
            v.erase(v.begin() + i);
            i--;
            if(i >= 0)    //上一级还有文件/目录名称，删除上一级
            {
                v.erase(v.begin() + i);
                i--;
            }
        }
    }
    for(string str : v)    //将简化后的路径拼接起来
    {
        result += "/" + str;
    }
    if(result.empty())    //简化后只剩下根目录
    {
        result = "/";
    }
    return result;
}


//优化：将path根据'/'进行分割的同时将路径化简，再将化简后的路径拼接起来即可
string simplifyPath(string path) 
{
    vector<string> v;   //将给定的字符串path根据'/'进行分割（若遇到多个连续'/'，当作一个'/'处理），存放到v中
    string result;    //存放简化后得到的规范路径 
    path += "/";    //字符串path末尾加"/"，保证可以把最后一个文件/目录名称分割出来
    int index = 1;    //记录'/'后第一个字符的下标
    for(int i = 1; i < path.size(); i++)    //遍历path，根据'/'进行分割，同时将路径化简
    {
        if(path[i] == '/')
        {
            if(i != index)    //遇到连续'/'时，不处理
            {
                string str = path.substr(index, i-index);   //分割出来的文件/目录名称
                if(str == "..")   //遇到".."时，表示切换到上一级目录，不仅不加入".."，还要删除上一级
                {
                    if(!v.empty())
                    {
                        v.pop_back();
                    }
                }
                else if(str != ".")    //遇到"."时，表示当前目录本身，直接不加入"."即可
                {
                    v.push_back(str);   //只要不是遇到".."和"."，就说明是正常的文件/目录名称
                }
            }
            index = i + 1;
        }
    }
    for(string str : v)    //将简化后的路径拼接起来
    {
        result += "/" + str;
    }
    if(result.empty())    //简化后只剩下根目录
    {
        result = "/";
    }
    return result;
}

【题目描述】

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

【输入输出实例】

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

示例 2：

输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

【算法思路】

我们在 s 上滑动窗口，通过移动 right 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，就开始右移左指针 left 收缩窗口，如果能收缩，我们就收缩窗口直到得到最小窗口。

如何确定窗口内已经包含 t 全部字符？通过两个哈希表smap、tmap来存放s、t中字符出现次数，tmap在初始就记录好，smap在更新中逐渐记录，如果tmap中记录字符都小于smap中，说明s窗口已经覆盖t字符。

在扩大窗口时，右窗口新移入的字符，如果在t中，才记录到smap，每次扩大窗口都要检查当前窗口是否已经覆盖，如果覆盖就开始收缩左指针，缩小窗口，同时更新最小字串。

【算法描述】

string minWindow(string s, string t) {
    // 记录t字符串的各字符次数
    unordered_map<char, int> smap, tmap;
    for(const auto& i : t) {
        tmap[i]++;
    }

    int minNum = INT_MAX;       // 记录子串最小长度
    string result = "";         // 记录最小字串
    int left = 0, right = 0;    // 左右指针
    while(right < s.size()) {
        // 右窗口新加入字符是否为t中字符，若是则加入smap
        if(tmap.find(s[right]) != tmap.end()) {
            ++smap[s[right]];
        }
        // 当前s窗口内子串已经覆盖了t，右移左指针，记录最小字串
        while(check(tmap, smap)) {
            if(minNum > right-left+1) {
                minNum = right - left + 1;
                result = s.substr(left, minNum);
            }
            if(tmap.find(s[left]) != tmap.end()) {
                --smap[s[left]];
            }
            ++left;
        }
        ++right;
    }
    return result;
}

// 检查count中是否覆盖了origin中字符
bool check(unordered_map<char, int>& origin, unordered_map<char, int>& count) {
    for(const auto& i : origin) {
        if(count[i.first] < i.second) {
            return false;
        }
    }
    return true;
}

恭喜你全部读完啦！古人云：温故而知新。赶紧收藏关注起来，用之前再翻一翻吧~

📣推荐阅读

C/C++后端开发面试总结：点击进入 后端开发面经 关注走一波

C++重点知识：点击进入 C++重点知识 关注走一波

力扣（leetcode）题目分类：点击进入 leetcode题目分类 关注走一波