DDL's homepage

字符串专题

发表于 Valine：

校招期间刷题做的一些笔记，主要配合leetcode, acwing平台使用。
这些题目是20年疫情期间一个一个做的，一开始啥也不会，acwing的一些视频对我算法学习帮助很大。
最近在回顾很多东西，发的日记，印象笔记里面的笔记，这些算法题现在没啥兴趣做了，但是我觉得以后有一天总还是要用得上的。

3.无重复字符的最长子串

主要思想：滑动窗口，双指针

数据结构：set，map 可以通过map优化性能，更加快速更新左边界

使用set 通过insert(),erease()来更新集合元素

方法1.set

1
2
3
4
5
6
7
8
9
10
11
12
int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int ans=0;
        for(int i=0,j=0;i<s.size();i++){
            while(set.count(s[i])) {
                set.erase(s[j++]);
            }
            set.insert(s[i]);
            if(ans<set.size()) ans=set.size();
        }
        return ans;
    }

方法2.map

参考acwing 提供了一种类似写法, 用哈希表存字符出现次数，当字符个数大于2即出现重复字符

1
2
3
4
5
6
7
unordered_map<char,int> ma;
int res;
for(int i=0,j=0;i<s.size();i++){
    ma[s[i]]++;
    while(s[i]>1) ma[s[j++]]--;
    res=max(res,j-i+1);
}

CountandSay

是一道老题目了
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

    1. 1
    1. 11
    1. 21
    1. 1211
    1. 111221

  • 1 被读作 “one 1” (“一个一”) , 即 11。

  • 11 被读作 “two 1s” (“两个一”）, 即 21。

  • 21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。

  • 给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

解题思路：

  • 外层按照给定层次n 迭代
  • 内层对当前层次处理每一个字符，统计其个数

要点：

  • 数字转化为字符 通过加‘0’ 或者 to_string
  • 边界处理
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    string countAndSay(int n) {
           if(n==1) return string("1");
           string res="1";
           for(int i=1;i<n;i++){
               string buf;
               int str_len=res.size();
               for(int j=0;j<str_len;j++){
                   int count=1;
                   while(res[j]==res[j+1]&&j+1<str_len){
                       j++;
                       count++;
                   }
                   buf.push_back(count+'0');
                   buf.push_back(res[j]);
               }
               res=buf;
           }
           return res;
       }

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

考点：
无序字符串排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<vector<string>> groupAnagrams(vector<string>& strs) {
      unordered_map<string,vector<string>> hash_map;
      for(auto str: strs){
          string key=str;
          sort(key.begin(),key.end());
          hash_map[key].push_back(str);
      }
      vector<vector<string>> res;
      for(auto c: hash_map){
          res.push_back(c.second);
      }
      return res;
  }

151. 翻转字符串中的单词 时间O(n) 空间O(1)

给定一个字符串，逐个翻转字符串中的每个单词。
比如说：
输入: “the sky is blue”
输出: “blue is sky the”

如果是翻转整个的字符串呢？

解题思路：

  • 先翻转字符串中的每一个单词
  • 在翻转整个字符串

技能点

  • 遍历去除字符串开始空格
  • 从字符串提取单个单词，处理，注意index的边界判定
  • 思想in-place 替代字符串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    string reverseWords(string s) {
            int index=0;
            for (int i = 0; i < s.size(); i++)
            {
                while(s[i]==' ') i++; //去除连续空格
                if(s.size()==i) break;
                int j=i;
                while(s[j]!=' '&&j<s.size())j++;
                reverse(s.begin()+i,s.begin()+j);
                if(index) s[index++]=' ';
                while(i<j) s[index++]=s[i++]; // 这个很巧妙 in-place 
            }
            s.erase(s.begin()+index,s.end()); // 可能有多余空格情况
            reverse(s.begin(),s.end());
            return s;       
        }

联想
这个题目起始也可以用来去除字符串中的空格，面试时候经常考察。
要求

  1. 去除字符串开始所有空格，中间的连续空格只保存一个，末尾的空格全部去除
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    string s;
    int n=s.size();
    int index=0,i=0;
    while(i<n){
        while(s[i]==' ') i++;
        if(i==s.size()) break; //为了防止已经到末尾加上空格
        if(index) s[index++]=' ';
        while(s[i]!=' ')s[index++]=s[i++];
    }
    s.erase(k);

165. 版本号比较

难点:

  • 前导0的处理

提取符合特定要求的子字符串模式：

1
2
int j=i;
while(j<s.size()&&s[j]!='.') j++;

atoi() 函数用法
substring()用法
完整参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int compareVersion(string s1, string s2) {
        int i=0,j=0;
        while(i<s1.size()|| j<s2.size()){
            int x=i,y=j;
            while(x<s1.size()&&s1[x]!='.') x++;
            while(y<s2.size()&&s2[y]!='.') y++;
            int a=(x==i)?0:atoi(s1.substr(i,x-i).c_str());
            int b=(y==j)?0:atoi(s2.substr(j,y-j).c_str());
            i=x+1; //jump .
            j=y+1;
            if(a<b) return -1;
            if(a>b) return 1;
        }
        return 0;
    }

两个字符串，两个数组通过while(s1.size()||s2.size())来控制循环流

929. 独特的电子邮件地址

思路：

  • 分离本地和域名
  • 按照+，.规则来处理本地
  • 链接成新的邮件地址 存入到unordered_set
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int numUniqueEmails(vector<string>& emails) {
            unordered_set<string> hash_set;
            for(auto email:emails){
                int i=0;
                while(email[i]!='@') i++;
                string local =email.substr(0,i);
                string prefix=email.substr(i+1,email.size()-i);
                string newlocal;
                for(auto c: local){
                    if(c=='+') break;
                    if(c!='.') newlocal+=c;
                }
                string s=newlocal+'@'+prefix;
                hash_set.insert(s);
            }
            return hash_set.size();
            
        }
    小技巧
  • substr() 默认位置到 end() 因此在提取domin 的时候可以简写为email.sub(i+1);
  • 在寻找‘@’ 可以通过 string.find() http://www.cplusplus.com/reference/string/string/find/
1
2
if(c=='+') break;
if(c!='.') newlocal+=c;

这个是有顺序的，第二次写的时候给疏忽了。

5.最长回文子串

思路： 暴力枚举 时间复杂度 O(n*n)

  • 以中心点 分为奇偶向两边扩展
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    string longestPalindrome(string s) {
            string res;
            for (int i = 0; i < s.size(); i++)
            {   
                // 对奇数长度
                for( int j=i,k=i;j>=0&&k<s.size()&&s[k]==s[j];j--,k++)
                    if(res.size()<k-j+1) res=s.substr(j,k-j+1);
                for(int j=i,k=i+1;j>=0&&k<s.size()&&s[k]==s[j];j--,k++)
                 if(res.size()<k-j+1) res=s.substr(j,k-j+1);
            }
            return res;
        }

    在这里总结下判断回文字符串的几种常见方法

  1. 双指针从首尾向中间靠拢
  2. 从中间向两边，但是需要注意考虑奇偶情况，如果仅仅只是判断单个的字符串是否满足回文
    这样来做是划不来的，调用reverse()直接将字符串翻转比较

2020年2月11日

6. Z字形变换

这道题目描述有点长，属于一找规律的题目

关键规律：行数 n
自己画一下 Z图发现 首尾行为等差数列 2(n-1)
其他行为 两个交错的等差数列 第二个等差数列的首相需要注意下
以及对于边界条件的判断 n==1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string convert(string s, int n) {
        string res;
        if(n==1) return s;
        for (int i = 0; i < n; i++)
        {
            //rule 1 for begin row and end
            if(!i||i==n-1) 
                for (int j = i; j < s.size(); j+=2*(n-1))  res+=s[j];
            else{
            for (int j = i,k=2*(n-1)-i; j < s.size()||k<s.size(); j+=2*(n-1),k+=2*(n-1))
            {
                if(j<s.size()) res+=s[j];
                if(k<s.size()) res+=s[k];
            }
        }}
        return res;   
    }

208.前缀树(trie)

这个概念之前没有接触过
基本数据结构

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。
    以该题为例 都是小写字母 则有26个子节点

每个字符串需要有一个标志结尾，考虑上述因素定义如下数据结构

1
2
3
4
5
6
7
8
struct node{
        bool is_end;
        node* son[26];
        node(){
            for(int i=0;i<26;i++) son[i]=NULL;
            is_end=false;
        }
    }*root;

开始写的时候对面向对象的知识都丢了，不记得怎么来 new 一个对象。。。

trie 基础

目的：高效存储和查找字符串集合

特点：要么都是小写，大写，或者数字

使用数组来实现trie基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0; //表示从根节点开始遍历
    for (int i = 0; str[i]; i ++ ) //str[i] 作为判断条件 因为 字符串以`0`结尾
    {
        int u = str[i] - 'a'; //求孩子下标index
        if (!son[p][u]) son[p][u] = ++ idx;//如果孩子不存在分配新的节点，类比new ，注意是前置++
        p = son[p][u];
    }
    cnt[p] ++ ; //表示插入字符串个数++
}
// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

trie 不仅能用来存储字符串，也能够存储0-1bit,如下面例子

421. 数组中两个数的最大异或值

不要觉得构建字典树麻烦，能对时间性能有很大提升。

思路

按整数从高位到低位异或比较，在字典树中查找最大的异或对

这里看起来比较复杂的点在于trie的构建，需要自己定义数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct node{
    node*son[2];
    node(){
        for(int i=0;i<2;i++) son[i]=nullptr;
    }
    
};
class trie{
public:
        trie(){
            root =new node();
        }
        //将元素插入到字典树
        void insert(int x){
            auto p=root;
            for(int i=31;i>=0;i--){
                int path=(x>>i)&1;
                if(!p->son[path]) p->son[path]=new node();
                p=p->son[path];
            }            
        }
    //查找x 对应的异或最大值
    int find(int x){
        auto p=root;
        int res=0;
        for(int i=31;i>=0;i--){
            int path=(x>>i)&1;
            if(p->son[!path]) {//优先选相反位 这样异或值最大
                res=res*2+!path;
                 p=p->son[!path]; 
            }
            else{
             res=res*2+path;
             p=p->son[path];}
        }
        return res;
    }
    
private:
        node* root;
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        trie t;
        int res=0;
        for(int i=0;i<nums.size();i++){
            t.insert(nums[i]);
            res=max(res,nums[i]^t.find(nums[i]));
        }
        return res;

    }
};

时间复杂度分析，树的查找时间复杂度为logn, 循环n次，所以整个的时间复杂度为nlogn, 但是题目里面的要求是O(n)， 如何进一步优化

1371. 每个元音包含偶数次的最长子字符串

给你一个字符串 s，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’，在子字符串中都恰好出现了偶数次。

解题思路: 哈希表+状态压缩+前缀和

将5个元音字母出现次数的奇偶视为一种状态，一共有32种状态，不妨使用一个整数代表状态，第0位为1表示a出现奇数次，第一位为1表示e出现奇数次……以此类推。仅有状态0符合题意。

而如果子串[0，i]与字串[0,j]状态相同，那么字串[i+1,j]的状态一定是0，因此可以记录每个状态第一次出现的位置，此后再出现该状态时相减即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findTheLongestSubstring(string s) {
        int n=s.size();
        unordered_map<int,int> map; //前缀和->第一次出现
        map[0]=-1;
        string p="aeiou";
        int mask=0,res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<5;j++){
                if(s[i]==p[j]){
                    mask^=1<<j;
                }
            }
            if(map.count(mask)) res=max(res,i-map[mask]);
            else map[mask]=i;
        }
        return res; 
    }

227. 基本计算器 II(加减乘除表达式)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int calculate(string s) {
        s=s+"+0"; //数据预处理防止  最后一个运算符可能用不到
        stack<int> nums;
        int n=s.size();
        long long num=0;
        char sign='+'; //前一个字符 这里由于+/- 优先级最低 初始化
        for(int i=0;i<n;i++){
           if(s[i]<='9'&&s[i]>='0') num=num*10+s[i]-'0'; //可能出现符号溢出
            if(s[i]=='/'||s[i]=='*'||s[i]=='+'||s[i]=='-'){
                if(sign=='+') nums.push(num);
                if(sign=='-')nums.push(-num);
                if(sign=='*'){
                    int t=nums.top();
                    nums.pop();
                    nums.push(t*num);
                }
                if(sign=='/'){
                    int t=nums.top();
                    nums.pop();
                    nums.push(t/num);
                }
                sign=s[i];
                num=0;
            }
        }
        int res=0;
        while(nums.size()){
            //cout<<nums.top()<<endl;
            res+=nums.top();
            nums.pop();
        }
        return res;

    }