LeetCode 字符串[L1]

443. 压缩字符串

双指针一个读一个写

 int compress(vector<char>& chars) {
        int i,j,len=0;       
        for(i=0,j=0;i<chars.size();i=j)
        {
            while(j<chars.size()&&chars[j]==chars[i])
                j++;
            chars[len++]=chars[i];
            int t=j-i;
            if(t==1)
                    continue;
            else if(t>9)
            { 
                stack<int>st;  
                while(t)
                {
                   st.push(t%10);
                   t/=10;
                }
                while(!st.empty())
                {
                    chars[len++]=st.top()+'0';
                    st.pop();
                }
            }
            else
                chars[len++]=t+'0';
        }
        return len;
    }

---

434. 字符串中的单词数

双指针取单词

int countSegments(string s) {
        int cnt=0,j;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=' ')
        {
            j=i;
            cnt++;
            while(s[j]!=' '&&j<s.size())
                j++;
            i=j;
        }
    }
    return cnt;    
    }

---

459. 重复的子字符串

写了半天错的下标从一开始的kmp，心累，换方法了

• 解法1：周期性

bool repeatedSubstringPattern(string s) {
       int t=0,i,len=s.size();
        for(int t=1;t<=len/2;t++)
        {
            if(len%t!=0)
            continue;
            for(i=t;i<len&&s[i%t]==s[i];i++);
            if(i==len) return true;
        }
        return false;
    }

• 解法2 ：next求最小循环节

bool repeatedSubstringPattern(string s) {
        int n=s.size();
        vector<int>ne(n+1);
        for (int i = 1, j = 0; i < n; i ++ )         
        {
            while (j>0&&s[i]!=s[j])j=ne[j-1]; 
            if (s[i] == s[j]) j++;
            ne[i] = j;
        }
        int k=n-ne[n-1];
        if(ne[s.size()-1]==0) return false;
        return s.size()%k==0;
    }

---

58. 最后一个单词的长度

 int lengthOfLastWord(string s) {
        int len=0;
        for(int i=s.size()-1;i>=0;i--)
        {
            if(s[i]!=' ')
                len++;
            else if(len!=0)
            {
                return len;
            }
        }
        return len;
    }

---

14. 最长公共前缀

string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return ""; 
        string str="";
        int m=strs[0].size();
        for(int i=1;i<strs.size();i++)
        {
            if(strs[i].size()<m)
                m=strs[i].size();
        }
        for(int i=0;i<m;i++)//字符串第m个字符
        {
            char s=strs[0][i];
            for(int j=1;j<strs.size();j++)
            {
                if(s!=strs[j][i])
                    return str; 
            }
            str+=s;
        }
        return str;
    }

---

20. 有效的括号

栈的应用

bool isValid(string s) {
        map<char,int> mp;
        int flag=0;
        string str="({[)}]";
        stack<int>st;
        for(int i=0;i<str.size();i++)
            mp[str[i]]=i+1;
        for(int i=0;i<s.size();i++)
        {
            int num=mp[s[i]];
            if(num>=1&&num<=3) st.push(num);
            else if(!st.empty()&&st.top()==num-3) st.pop();
            else
            {
                flag=1;
                break;
            } 
        }
        if(!st.empty()||flag==1)return false;
        else    return true; 
    }

---

125. 验证回文串

记一笔 c++的几个内置函数

islower(char c) 是否为小写字母
isuppper(char c) 是否为大写字母
isdigit(char c) 是否为数字
isalpha(char c) 是否为字母
isalnum(char c) 是否为字母或者数字
toupper(char c) 字母小转大
tolower(char c) 字母大转小

bool isPalindrome(string s) {
        vector<char>temp;
        if(s.size()==0)
            return true;
        for(int i=0;i<s.size();i++)
        {
            if(isalpha(s[i]))//是字母
                temp.push_back(tolower(s[i]));
            else if(isdigit(s[i]))
                temp.push_back(s[i]);
        }
        vector<char>str=temp;
        reverse(str.begin(),str.end());
        if(temp==str)
            return true;
        else
            return false;
    }

---