Leetcode 刷题笔记-Leetcode 101 第12章 字符串

Leetcode 刷题笔记-Leetcode 101 第12章 字符串

字符串

字符串比较

Leetcode 242

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t互为字母异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        if(s == t){
            return true;
        }
        return false;
    }
};

分析：哈希表或者直接排序

一遍AC

Leetcode 205

给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char,char> mp1;
        unordered_map<char,char> mp2;
        for(int i=0;i<s.size();++i){
            if(mp1.find(s[i]) == mp1.cend()){
                mp1[s[i]] = t[i];
            }
            if(mp2.find(t[i]) == mp2.cend()){
                mp2[t[i]] = s[i];
            }
            if(mp1[s[i]] != t[i] || mp2[t[i]] != s[i]){
                return false;
            }
        }
        return true;
    }
};

分析：通过字典比较即可

错误：开始想用统计的方法去做，后面用字符字典的方式也有一些小错误，应该是比较两遍的。

Leetcode 647

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

class Solution {
public:
    int countSubstrings(string s) {
        int countsum = 0;
        int n = s.size();
        for(int i=0;i<n;++i){
            countsum += 1;
            int leftindex = i-1;
            int rightindex = i+1;
            while(leftindex >= 0 && rightindex < n && s[leftindex] == s[rightindex]){
                ++countsum;
                --leftindex;
                ++rightindex;
            }
        }
        for(int i=0;i<n-1;++i){
            if(s[i] == s[i+1]){
                ++countsum;
                int leftindex = i-1;
                int rightindex = i+2;
                while(leftindex >= 0 && rightindex < n && s[leftindex] == s[rightindex]){
                    ++countsum;
                    --leftindex;
                    ++rightindex;
                }
            }
        }
        return countsum;
    }
};

分析：遍历扩展即可，注意分两种情况讨论一下

一遍AC

Leetcode 696

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。重复出现（不同位置）的子串也要统计它们出现的次数。

class Solution {
public:
    int countBinarySubstrings(string s) {
        int n = s.size();
        int countsum = 0;
        for(int i=0;i<n-1;++i){
            if(s[i] != s[i+1]){
                ++countsum;
                int leftindex = i-1;
                int rightindex = i+2;
                while(leftindex >= 0 && rightindex < n && s[leftindex] == s[leftindex+1] && s[rightindex] == s[rightindex-1]){
                    ++countsum;
                    --leftindex;
                    ++rightindex;
                }
            }
        }
        return countsum;
    }
};

分析：和上一道题目相同，甚至只考虑一种情况就可以了，比上一道题目还要简单一点。

一遍AC

字符串理解

Leetcode 227

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        char preSign = '+';
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                num = num * 10 + int(s[i] - '0');
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
                switch (preSign) {
                    case '+':
                        stk.push_back(num);
                        break;
                    case '-':
                        stk.push_back(-num);
                        break;
                    case '*':
                        stk.back() *= num;
                        break;
                    default:
                        stk.back() /= num;
                }
                preSign = s[i];
                num = 0;
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};

分析：栈和字符串的应用

错误：最后的运算顺序有问题，没有能自己实现。

字符串匹配

Leetcode 28

给你两个字符串 haystack和 needle，请你在 haystack字符串中找出 needle字符串的第一个匹配项的下标（下标从 0开始）。如果 needle不是 haystack的一部分，则返回 -1。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size();
        int n = needle.size();
        for(int i=0;i<m-n+1;++i){
            if(haystack.substr(i,n) == needle){
                return i;
            }
        }
        return -1;
    }
};

分析：可以使用KMP算法，但是不会，简单一点就直接字符串匹配即可。

一遍AC

练习

Leetcode 409

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写 。比如 "Aa" 不能当做一个回文字符串。

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> mp;
        int n = s.size();
        for(int i=0;i<s.size();++i){
            if(mp.find(s[i]) == mp.cend()){
                mp[s[i]] = 1;
            }
            else{
                ++mp[s[i]];
            }
        }
        int ans = 0;
        int sign = 0;
        for(auto it : mp){
            if(it.second % 2 == 0){
                ans += it.second;
            }
            else{
                if(sign == 0){
                    ans += it.second;
                    sign = 1;
                }
                else{
                    ans = ans + it.second / 2 * 2;
                }
            }
        }
        return ans;
    }
};

分析：统计数数即可

一遍AC

Leetcode 3

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char,int> mp;
        int n = s.size();
        int right = 0;
        int maxlen = 0;
        int left = 0;
        while(left < n){
            while(right < n && (mp.find(s[right]) == mp.cend() || mp[s[right]] == 0)){
                ++mp[s[right]];
                ++right;
            }
            maxlen = max(maxlen,right-left);
            --mp[s[left]];
            ++left;
        }
        return maxlen;
    }
};

分析：滑动窗口经典算法

错误：与或非的括号忘记添加了

Leetcode 772

付费题目

Leetcode 5

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        int countsum = 1;
        string result = s.substr(0,1);
        int n = s.size();
        for(int i=0;i<n;++i){
            int temp = 1;
            int leftindex = i-1;
            int rightindex = i+1;
            while(leftindex >= 0 && rightindex < n && s[leftindex] == s[rightindex]){
                temp += 2;
                --leftindex;
                ++rightindex;
            }
            if(temp > countsum){
                countsum = temp;
                result = s.substr(leftindex+1,rightindex-1-(leftindex+1)+1);
            }
        }
        for(int i=0;i<n-1;++i){
            if(s[i] == s[i+1]){
                int temp = 2;
                int leftindex = i-1;
                int rightindex = i+2;
                while(leftindex >= 0 && rightindex < n && s[leftindex] == s[rightindex]){
                    temp += 2;
                    --leftindex;
                    ++rightindex;
                }
                if(temp > countsum){
                    countsum = temp;
                    result = s.substr(leftindex+1,rightindex-1-(leftindex+1)+1);
                }
            }
        }
        return result;
    }
};

分析：还是这种题，都第三道了

错误：开始有些索引没考虑好错了一些，后来调通了。

总结

字符串还可以，主要是熟悉一下字符串的处理过程，其余的知识点其他的数据结构中都有。