环球速讯：Leetcode Practice -- 字符串

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球速讯：Leetcode Practice -- 字符串

2023-03-24 18:13:54 来源：博客园

14. 最长公共前缀
- 思路解析
151. 反转字符串中的单词
- 思路解析
125. 验证回文串
- 思路解析
415. 字符串相加
- 思路解析
3. 无重复字符的最长子串
- 思路解析
8. 字符串转换整数 (atoi)
- 思路解析

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

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

思路解析

string longestCommonPrefix(vector& strs) {    string res;    if (strs.empty()) {        return res;    }    for (size_t i = 0; i < strs[0].length(); i++) {        char pivotChar = strs[0][i];        for (size_t j = 1; j < strs.size(); j++) {            if (i >= strs[j].length() || strs[j][i] != pivotChar) {                return res;            }        }        res += pivotChar;    }    return res;}

151. 反转字符串中的单词

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

【资料图】

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

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

输入：s = "the sky is blue"输出："blue is sky the"

思路解析

string reverseWords(string s) {    stack strStack;    string oneWord;    for (size_t i = 0; i < s.length(); i++) {        if (s[i] == " ") {            if (!oneWord.empty()) {                strStack.emplace(oneWord);            }            oneWord.clear();            continue;        }        oneWord += s[i];    }    if (!oneWord.empty()) {        strStack.emplace(oneWord);    }    string resStr;    while (!strStack.empty()) {        resStr += strStack.top() + " ";        strStack.pop();    }    resStr = resStr.substr(0, resStr.length()-1);    return resStr;}

graph LR;ios-->ios_base;istringstream-->istream;istream-->ios;ostream-->ios;ostringstream-->ostream;

istream：从流中读取
ostream：写到流中去
istringstream：从string对象流中读取
ostringstream：写入到string对象流中

ostringstream：

Output stream class to operate on strings. 用于处理字符串的输出流
Objects of this class use a string bufferthat contains a sequence of characters. This sequence of characters can be accessed directly as a string object, using member str.
ostringstream类的对象使用一个string buffer来存储一系列的字符，这些字符序列可以直接用string对象访问。

istringstream：

This operator (>>) applied to an input stream is known as extraction operator. It is overloaded as a member function for:
对输入流应用>>，即为提取操作符，有三种接受方式：
arithmetictypes【算术类型，bool、short、long等等】
stream buffers
manipulators

使用>>可以从流中提取数据，多个单词使用空格分割。

string reverseWords(string s) {    istringstream is(s);    stack strStack;    string str;    while (is >> str) {        strStack.emplace(str);    }    string resStr;    while (!strStack.empty()) {        resStr += strStack.top() + " ";        strStack.pop();    }    resStr = resStr.substr(0, resStr.length() - 1);    return resStr;}

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

思路解析

bool isPalindrome(string s) {    // 清理字符串    string cleanStr;    for (size_t i = 0; i < s.length(); i++) {        if (isalnum(s[i])) {            cleanStr += tolower(s[i]);        }    }    // 判断其是否为回文串    int i = 0;    int j = cleanStr.length() - 1;    while (i < j) {        if (cleanStr[i++] != cleanStr[j--]) {            return false;        }    }    return true;}

C++中哪些字符串的判断与处理函数：

int isalpha(int c);：判断一个字符是否为字母，是非零，否零
int isalnum(int c);：判断一个字符是否为字母或数字，是非零，否零
int isdigit(int c);：判断判断一个字符是否为数字，是非零，否零
int islower(int c);：判断判断一个字符是否小写字母，是非零，否零
int isupper(int c);：判断判断一个字符是否大写字母，是非零，否零
int tolower(int c);：将一个字母转为小写字母
int toupper(int c);：将一个字母转为大写字母

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

输入：num1 = "11", num2 = "123"输出："134"

思路解析

模拟加法的基本运算步骤。

int charToInt(char c) {    return c - "0";}string addStrings(string num1, string num2) {    int i = num1.length() - 1;    int j = num2.length() - 1;    int jinwei = 0;    stack resStack;    while (i >= 0 && j >= 0) {        int tmp = charToInt(num1[i--]) + charToInt(num2[j--]) + jinwei;        resStack.emplace(tmp % 10);        jinwei = tmp / 10; // tmp >= 10 ? 1 : 0    }    while (i >= 0) {        int tmp = charToInt(num1[i--])+ jinwei;        resStack.emplace(tmp % 10);        jinwei = tmp / 10;    }    while (j >= 0) {        int tmp = charToInt(num2[j--]) + jinwei;        resStack.emplace(tmp % 10);        jinwei = tmp / 10;    }    if (jinwei) {        resStack.emplace(jinwei);    }    string res;    while(!resStack.empty()) {        res += std::to_string(resStack.top());        resStack.pop();    }    return res;}

3. 无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串的长度。

输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路解析

使用滑动窗口来判断窗口内的子串是否为最长子串。

【找最长子串类似于找最大子数组的和，都需要考虑所有子串/子数组，就可以从每个元素开始找子串或子数组，就可以考虑用滑动窗口了】

设窗口为[left, right]，针对当前元素s[right+1]，如果该元素不在窗口内，则直接向右扩张窗口：right = right+1；否则，说明该元素之前出现过，判断其之前出现的位置是否在窗口内，如果不在，就不需要考虑，如果在，就需要收缩窗口的左侧边界，即left = 当前元素上次出现的索引位置 + 1;

int lengthOfLongestSubstring(string s) {    if (s.empty()) {        return 0;    }    // 初始，窗口只有一个元素    int left = 0;    int right = 0;    unordered_map charIndexMap;    charIndexMap[s[0]] = 0;    int windowSize = 1;    for (size_t i = 1; i < s.length(); i++) {        // 当前字符出现过且在当前窗口内，则收缩窗口左边界        if (charIndexMap.count(s[i]) != 0 && left <= charIndexMap[s[i]]) {            left = charIndexMap[s[i]] + 1;        }        // 窗口一直在向右扩张        right++;        charIndexMap[s[i]] = i;        // 判断窗口大小是否需要更新        if (right - left + 1 > windowSize) {            windowSize = right - left + 1;        }    }    return windowSize;}

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 " " 。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

输入：s = "   -42"输出：-42解释：第 1 步："   -42"（读入前导空格，但忽视掉）             ^第 2 步："   -42"（读入 "-" 字符，所以结果应该是负数）              ^第 3 步："   -42"（读入 "42"）              ^解析得到整数 -42 。由于 "-42" 在范围 [-2^31, 2^31 - 1] 内，最终结果为-42 。

0 <= s.length <= 200
s由英文字母（大写和小写）、数字（0-9）、" "、"+"、"-"和 "."组成
思路解析

判断输入的字符是否为数字，如果为数字就提取出来。

注意，从前到后，只能访问到" "、‘+’、‘-’或数字，其他的均为无效，"+"、"-"或数字一旦开始就不能再遇到其它了，只能遇到数字，否则就可以终止了。

举例说明：[比较重要的就是理解题意，将所有情况考虑周全]

"+-0012" --> 0
"+0012" --> 12
"+00 12" --> 0
" aa 12" --> 0
" 12 aa" --> 12

int myAtoi(string s) {    int sign = 1; // 符号位，默认为正    bool startFlag = false; // "+"或"-"已经被遍历到，不能再出现了，再出现就属于不合法字符了    int64_t intNum = 0;    for (size_t i = 0; i < s.length(); i++) {        if (isdigit(s[i])) {            intNum = intNum * 10 + (s[i] - "0");            if (sign == 1 && intNum > INT_MAX) {                return INT_MAX;            }            if (sign == -1 && -intNum < INT_MIN) {                return INT_MIN;            }            startFlag = true;        } else if (s[i] == "-" && !startFlag) {            startFlag = true;            sign = -1;        } else if (s[i] == "+" && !startFlag) {            startFlag = true;        } else if (s[i] == " " && !startFlag) {            continue;        } else {            break;        }    }    intNum = intNum * sign;    if (intNum > INT_MAX) {        return INT_MAX;    }    if (intNum < INT_MIN) {        return INT_MIN;    }    return static_cast(intNum);}

关键词：

环球速讯：Leetcode Practice -- 字符串

14. 最长公共前缀

思路解析

151. 反转字符串中的单词

思路解析

125. 验证回文串

思路解析

415. 字符串相加

思路解析

3. 无重复字符的最长子串

思路解析

8. 字符串转换整数 (atoi)

思路解析