目录
JS67 JO49 L8字符串转换整数atoi（!!!!!）
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int strToInt(string str) {
int len = str.size();
if(len == 0) return 0;
int index = 0; // 字符串游标
int sign = 1; // 记录符号位。默认为正
int bndry = INT_MAX / 10; // 边界
int result = 0; // 记录结果
// (1)先跳过开头的空格符
while(str[index] == ‘ ‘){
if(++index == len) return 0; // 输入全为空格情况
}
// (2)跳过空格后如果有符号位先记录符号位
if(str[index] == ‘-‘) sign = -1;
if(str[index] == ‘-‘ || str[index] == ‘+‘) index++;
// (3)接着处理数字字符
for(; index < len; ++index){
// 如果遇到不是数字字符，则数字字符处理结束
if(str[index] < ‘0‘ || str[index]>‘9‘) break;
// 当前字符仍是数字
// 在前面结果基础上，利用 INT_MAX/10 的值来提前一步判断是否会越界（与最大值去掉最低位后作比较）
if(result > bndry || (result == bndry && str[index] > ‘7‘))
return sign == 1 ? INT_MAX:INT_MIN;
//
result = result*10 + (str[index]-‘0‘);
}
return sign * result;
}
};
int main(){
string s = " -42 with";
Solution solu;
cout << solu.strToInt(s) << endl;
return 0; // -42
}
- 判断标志位可以更谨慎一些：
// (2)跳过空格后如果有符号位先记录符号位
int num = 0; // 记录标志位个数
while (index < len && (str[index] == ‘-‘ || str[index] == ‘+‘)){
if(str[index] == ‘-‘) sign = -1;
index++;
num++;
if(num > 1) return 0; //不能出现两个标志位
}
L5 最长回文子串（字符串+双指针）
- 思路：回文子串是对称的，遍历字符串，以当前字符为中心，从中心开始向两边扩散来判断回文串
class Solution {
public:
string longestPalindrome(string s) {
// 递归
// 使用双指针：左右指针（数组和字符串用，快慢指针是链表）
// 寻找回文串的核心思想是：
// 遍历字符串，以当前字符为中心，从中心开始向两边扩散来判断回文串
// 左指针从中心向左移动，右指针从中心向右移动，当左右指针指向的值不等时结束移动，此时左右指针之间的子串即为以该字符为中心的最长子串
// 对每个字符都执行以上操作
string res; // 保存最长子串
for(int i=0; i<s.size(); ++i){
// 寻找以s[i]为中心的回文串（奇数长度），如aba
// 寻找以s[i]和s[i+1]为中心的回文串（奇数长度），如abba
string s1 = palindrome(s, i, i); // 左右指针都为i
string s2 = palindrome(s, i, i+1); // 左指针为i,右指针为i+1
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
private:
// 寻找以某个字符为中心的最长子串
string palindrome(string &s, int left, int right){
// 注意索引的越界
while(left>=0 && right<s.size() && s[left]==s[right]){
left--;
right++;
}
// 左右指针之间的子串即为以该字符为中心的最长子串
return s.substr(left+1, right-left-1);
}
};
JS58 翻转单词顺序（字符串+双指针）
- 难点：识别出每个单词
class Solution {
public:
// 难点：怎么识别出每个单词
// 方法1：双指针，从后往前遍历，每得到一个单词，就添加到新字符串中
// left先行，找到一个单词边界后就取[left,right]
/*
string reverseWords(string s){
string ans="";
int left = s.size()-1;
int right = s.size()-1;
while(left >= 0){
// (1)先找到一个单词的末尾（跳过空格）
while(left>=0 && s[left] == ‘ ‘) left--;
if(left < 0) break;
// (2)right固定住一个单词的末尾
right = left;
// (3)left继续去找该单词的开头
while(left >=0 && s[left] != ‘ ‘) left--;
// (4)取出这个单词
ans += s.substr(left+1, right-left) + " ";
}
return ans.substr(0, ans.size()-1); // 为了去掉最后的空格
}
*/
// 方法2：使用istringstream：自动过滤空格
string reverseWords(string s){
istringstream ss(s);
string result;
string tmp; // 记录一个单词
while(ss >> tmp)
result = tmp + ‘ ‘ + result;//巧妙的把字符串放在前面实现反转，避免了使用栈
// substr函数取字符，主要是为了去掉最后多余的空格
return result.substr(0, result.size()-1);
}
};
int main(){
string s = " hello world! ";
Solution solu;
cout << solu.reverseWords(s) << endl; // world! hello
return 0;
}
JO44 翻转单词序列（同上）
- 方法1：可以借助栈，但下面的方法更简单
class Solution {
public:
string ReverseSentence(string str) {
string result = "", tmp = "";
for(int i = 0; i < str.size(); ++i){
if(str[i] == ‘ ‘){ // 当遇到空格时，将取出的单词放在之前结果的前面
result = " " + tmp + result;
tmp = "";
}
// 取出某个单词
else tmp += str[i];
}
if(tmp.size()) result = tmp + result;
return result;
}
};
- 方法2：利用stringstream
class Solution {
public:
string ReverseSentence(string str) {
stringstream s(str);
string result; // 记录结果
string tmp; // 记录一个单词
while(s >> tmp){
result = tmp + " " +result;
}
return result.substr(0, result.size() - 1);
}
};
- 方法3：不使用substr函数
class Solution {
public:
string ReverseSentence(string str) {
stringstream s(str);
string result; // 记录结果
string tmp; // 记录一个单词
bool flag = false;
while(s >> tmp){
if(!flag){
result = tmp;
flag = true;
}
else result = tmp + " " + result;
}
return result;
}
};
JS58 JO43左旋转字符串
- 方法1：运行时间9ms，占用内存512KB
class Solution {
public:
string reverseLeftWords(string s, int n) {
return s.substr(n)+ s.substr(0,n);
}
};
- 方法2：运行时间3ms，占用内存628KB
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.size();
if(len <= 1) return str;//可能为空
n = n%len;//并且n有可能比len大的情况
vector<char> temp(str.begin(),str.end());
for(int i = 0;i < n;++i)
temp.push_back(str[i]);
str.assign(n + temp.begin(),temp.end());
return std::move(str);
}
};
JS5 JO2替换空格
class Solution {
public:
string replaceSpace(string s) {
string res;
for(int i=0; i< s.size(); ++i){
if(s[i] == ‘ ‘){
res += "%20";
}
else{
res += s[i];
}
}
return res;
}
};
JS48 L3 无重复字符的最长子串（字节常考!!!!!，子串+滑动窗口+哈希表）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 选择特定条件子串问题：滑动窗口左右指针（）+哈希表
// 哈希表，key：字符；value：该字符出现次数
// 右指针先前进，前进过程判断新加入的字符是否在哈希表内，不在的话继续前进并且将该字符作为键加入哈希表
// 如果新加入的字符在哈希表中已有，则不断移动左指针直到窗口内重复字符消失
unordered_map<char, int> window;
// 左右指针
int left=0, right=0;
// 记录不含有重复字符的最长子串的长度
int len = 0;
while(right < s.size()){
// 不断向前移动右指针直到窗口内出现重复字符
// 将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 加入字符后对哈希表的影响
window[c]++;
// 判断新加入的字符是否是重复字符，是则开始移动左指针
while(window[c]>1){
// 存在重复字符了，不断移动左指针直到窗口内这个重复字符消失
// 将移出窗口的字符
char d = s[left];
left++;
// 移出窗口的字符后对哈希表的影响
window[d]--;
}
// 没有重复字符后更新不含有重复字符的最长子串的长度
if(right-left > len){ // 因为前面右移了窗口，所以不用减1了
len = right-left;
}
}
return len;
}
};
JO34 第一个只出现一次的字符（字符串+哈希表）
class Solution {
public:
int FirstNotRepeatingChar(string str) {
unordered_map<char, int> unmp;
// 先统计每个字符出现的次数
for(int i = 0; i < str.size(); ++i){
unmp[str[i]]++;
}
// 找到第一个出现次数为1的字符
for(int i = 0; i < str.size(); ++i){
if(unmp[str[i]] == 1) return i;
}
return -1;
}
};
JS50 第一个只出现一次的字符（字符串+哈希表）
class Solution {
public:
/*
方法一：哈希表
? 遍历字符串 s ，使用哈希表统计 “各字符数量是否 > 1”。
? 再遍历字符串 s ，在哈希表中找到首个 “数量为 1 的字符”，并返回。
算法流程：
初始化： 字典 (Python)、HashMap(Java)、map(C++)，记为 dic ；
字符统计： 遍历字符串 s 中的每个字符 c ；
若 dic 中 不包含 键(key) c ：则向 dic 中添加键值对 (c, True) ，代表字符 c 的数量为 1；
若 dic 中 包含 键(key) c ：则修改键 c 的键值对为 (c, False) ，代表字符 c 的数量 > 1>1 。
查找数量为 11 的字符： 遍历字符串 s 中的每个字符 c ；
若 dic中键 c 对应的值为 True ：，则返回 c 。
返回 ‘ ‘ ，代表字符串无数量为 1的字符。
*/
char firstUniqChar(string s) {
unordered_map<char, bool> map;
for(char c:s){
map[c] = map.find(c)==map.end();
}
for(char c:s){
if(map[c]) return c;
}
return ‘ ‘;
}
};
JO54 字符流中第一个不重复的字符（字符串+队列+哈希表）
- 利用队列的先入先出特性保证元素的先后顺序
class Solution
{
public:
//Insert one char from stringstream
queue<char> q;
unordered_map<char, int> unmp;
void Insert(char ch) {
// 如果是第一次出现， 则添加到队列中
if (unmp.find(ch) == unmp.end()) {
q.push(ch);
}
// 不管是不是第一次出现，都进行计数
++unmp[ch];
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce() {
while (!q.empty()) {
char ch = q.front();
// 拿出头部，如果是第一次出现，则返回
if (unmp[ch] == 1) {
return ch;
}
// 不是第一次出现，则弹出，然后继续判断下一个头部
else {
q.pop();
}
}
return ‘#‘;
}
};
JO53 表示数值的字符串
class Solution {
public:
/*
1、数字的情况：至少出现一个数字
2、e的情况：只能出现一个 ‘e‘ 或 ‘E‘ ，后面必须跟数字，且e前面必须有数字
3、+-：只能出现一次，即使出现第二次了，那他的前面也要是 e/ E ,出现第一次的话必须在开头或者
在E的后面
（+- 只出现在首位或者e/E的后第一个位置）
4、小数点：也只能出现一次，且不能在E的后面
5、合法字符的判断 除了 e +- . 以及数字之外 其余的字符都是错的
*/
bool isNumeric(string str) {
int len = str.size();
// 分别标记数字、正负号、小数点、e是否出现过
bool hasNum = false, sign = false, decimal = false, hasE = false;
for(int i = 0; i < len; ++i){
// 标记数字出现，只记录第一个数字的出现
if(str[i] >= ‘0‘ && str[i] <= ‘9‘)
hasNum = true;
// 处理e
else if(str[i] == ‘e‘ || str[i] == ‘E‘){
// e后面一定要接数字，即e不能结尾
if(i == len - 1) return false;
// 不能同时存在两个e，并且e前面必须有数字
if(hasE || !hasNum) return false;
hasE = true;
hasNum = false; // 重置，因为e后面也必须有数字
}
// 处理正负号
else if(str[i] == ‘+‘ || str[i] == ‘-‘){
// +- 的后面必须要出现数字，即+-最后
if( i == len - 1) return false;
// 第二次出现+-符号，则必须紧接在e/E之后，如+5e-6
if(sign && str[i-1] != ‘e‘ && str[i-1] != ‘E‘) return false;
// 第一次出现+-符号，要么在开头，要么必须紧接在e/E之后，如12e+5
if(!sign && i > 0 && str[i-1] != ‘e‘ && str[i-1] != ‘E‘) return false;
sign = true;
}
// 处理小数点
else if(str[i] == ‘.‘){
// e后面不能接小数点，小数点不能出现两次
if(hasE || decimal) return false;
decimal = true;
}
// 处理不合法的字符
else {
// 其他情况都是false
return false;
}
}
return hasNum;
}
};