目錄
- JS67 JO49 L8字元串轉換整數atoi（!!!!!）
- L5 最長回文子串（字元串+雙指針）
- JS58 翻轉單詞順序（字元串+雙指針）
- JO44 翻轉單詞序列（同上）
- JS58 JO43左旋轉字元串
- JS5 JO2替換空格
- JS48 L3 無重複字元的最長子串（位元組常考!!!!!，子串+滑動視窗+哈希表）
- JO34 第一個隻出現一次的字元（字元串+哈希表）
- JS50 第一個隻出現一次的字元（字元串+哈希表）
- JO54 字元流中第一個不重複的字元（字元串+隊列+哈希表）
- JO53 表示數值的字元串
#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; //不能出現兩個标志位
}
- 思路：回文子串是對稱的，周遊字元串，以目前字元為中心，從中心開始向兩邊擴散來判斷回文串
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);
}
};
- 難點：識别出每個單詞
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;
}
- 方法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;
}
};
- 方法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);
}
};
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;
}
};
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;
}
};
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;
}
};
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 ' ';
}
};
- 利用隊列的先入先出特性保證元素的先後順序
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 '#';
}
};
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;
}
};