字符串

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;

    }
};

字符串

上一篇:浅析.gitignore文件不起作用的原因及其解决办法


下一篇:VSTO 高性能的获取EXCEL中的合并单元格