Leedcode刷题——2 字符串

注：以下代码均为c++

1. 反转字符串

void reverseString(vector<char>& s) {
        int n = s.size();
        int i, j;
        for(i = 0, j = n - 1; i < j; i++, j--){
            swap(s[i], s[j]);
        }
    }

2. 整数反转

int reverse(int x) {
    int rev = 0;
    while(x != 0){
        if(rev < INT_MIN / 10 || rev > INT_MAX / 10)
            return 0;
        int digit = x % 10;
        x = x / 10;
        rev = rev * 10 + digit;
    }
    return rev;
}

3. 字符串中的第一个唯一字符

思想：哈希表

int firstUniqChar(string s) {
    unordered_map<char, int> hash;
    int i;
    /*for(i = 0; i < s.size(); i++){
        if(hash.count(s[i]) == 0)
            hash[s[i]] = 1;
        else
            hash[s[i]]++;
    }*/
    for(i = 0; i < s.size(); i++) {
        hash[s[i]]++;  //哈希表默认value值为0，可以直接++，不用像上面一样先赋值再加。
    }
    for(i = 0; i < s.size(); i++){
        if(hash[s[i]] == 1)
            return i;
    }
    return -1;
}

4. 有效的字母异位词

思路：哈希表

bool isAnagram(string s, string t) {
    unordered_map<char, int> maps, mapt;
    int i;
    if(s.size() != t.size())
        return false;
    for(i = 0; i < s.size(); i++){
        maps[s[i]]++;
        mapt[t[i]]++;
    }
    if(maps == mapt)
        return true;
    else
        return false;
}

5. 验证回文串

bool isPalindrome(string s) {
    int i, j;
    int n = s.size();
    for(i = 0, j = n - 1; i < j; i++, j--){  //注意for循环内部需要判断i < j
    	//找到下一个字母或数字
        while(i < j && isalnum(s[i]) == 0)  //isalnum()判断是否为字母和数字
            i++;
        //找到前一个字母或数字
        while(i < j && isalnum(s[j]) == 0)
            j--;
        if(i < j && tolower(s[i]) != tolower(s[j]))
            return false;
    }
    return true;
}

6. 字符串转换整数

int myAtoi(string s) {
    int i = 0, n = s.size();
    int symbol = 1;  // +
    int num = 0;

    //1 判断空格
    while(i < n && s[i] == ' ')
        i++;
    //2 判断正负
    if(i < n && s[i] == '-'){
        symbol = -1;  // -
        i++;
    }
    else if(i < n && s[i] == '+')
        i++;
    //3 若非数字返回0
    if(i < n && !isdigit(s[i]))
        return 0;
    //4 若为数字，越界处理要注意，这个地方好坑啊。。。
    while(i < n && isdigit(s[i])){
        if(num > INT_MAX/10  || (num == INT_MAX/10 && s[i]-'0' > INT_MAX % 10))
            return symbol == 1 ? INT_MAX: INT_MIN;
        else
            num = num * 10 + (s[i] - '0');
        i++;
    }
    return symbol * num;
}

7. 实现strStr()

思路：
字符串匹配问题
法1：暴力法

int strStr(string haystack, string needle){
    int i = 0, j = 0;
    int n = haystack.size(), m = needle.size();
    while(i < n && j < m){
        if(haystack[i] == needle[j]){
            i++;
            j++;
        }
        else{  //若不匹配，退回，从上一次匹配的下一个开始
            i = i - j + 1;
            j = 0;
        }
        if(j == m)
            return i - j;
    }
    return -1;
}

法2：kmp算法

vector<int> build_next(string needle){
    int m = needle.size();
    vector<int> next;
    next.push_back(0);
    int prefix_len = 0;  //当前共同前后缀的长度
    int i = 1;
    while(i < m){
        if(needle[prefix_len] == needle[i]){
            prefix_len++;
            next.push_back(prefix_len);
            i++;
        }
        else{
            if(prefix_len == 0){
                next.push_back(0);
                i++;
            }
            else
                prefix_len = next[prefix_len - 1];
        }
    }
    return next;
}
int strStr1(string haystack, string needle){
    int n = haystack.size(), m = needle.size();
    vector<int> next = build_next(needle);
    int i = 0, j = 0;
    while(i < n){
        if(haystack[i] == needle[j]){  //若匹配，指针后移
            i++;
            j++;
        }
        else if(j > 0)  //若不匹配，根据next跳过子串前面一些字符
            j = next[j-1];
        else  //若第一个字符就不匹配
            i++;
        if(j == m)
            return i-j;
    }
    return -1;
}

8. 外观数列

string countAndSay(int n) {
    int i, j, k;  //i为索引，j为计数器
    //每一次计算只需要知道它的前一个字符串即可，不需要知道每一项，所以用两个字符串分别记录当前项和前一项。
    string str1 = "1", str2;
    for(k = 0; k < n - 1; k++){
        i = 0;
        while(i < str1.size()){
            j = 0;
            while(i+1 < str1.size()  && str1[i] == str1[i+1]){
                j++;
                i++;
            }
            //法1
            //str2.push_back(j+1+'0');  //int转char +'0'
            //str2.push_back(str1[i]);
            //法2
            str2 += to_string(j+1);
            str2 += str1[i];
            i++;
        }
        str1 = str2;
        str2.clear();
    }
    return str1;
}

9. 最长公共前缀

string longestCommonPrefix(vector<string>& strs) {
    int i, j;
    string prefix = strs[0];  //假设一个字符串为最长公共前缀
    //遍历后面的每一个字符串
    for(i = 1; i < strs.size(); i++){
        for(j = 0; j < strs[i].size(); j++){
            if(strs[i][j] != prefix[j]){
                prefix = prefix.substr(0, j);  //截取字符串，注意需要赋值操作。从下标0开始取j个
                break;
            }
        }
        if(j < prefix.size())
            prefix = prefix.substr(0, j);
    }
    return prefix;
}