Farenew的博客

2019.07.15

1. 字符串包含

给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短。请问,如何最快地判断字符串B中所有字母是否都在字符串A里?

  • 这个题暴力解会做太多的无用功. 很容易想到的, 可以通过排序对字符串进行排序, 然后两个字符串同时进行比较即可. 复杂度并不会很高.

  • 一个创新的想法是使用素数的特性, 因为素数只能被自身和1整除. 所以可以对每个字符赋值一个素数, 然后把A字符串的素数乘起来, 假设为S. 之后看B中每个字符是否能整除S.

    但这个想法的问题在于素数的乘积会很大, 导致溢出. 因此这个解也只能是理论上的.

  • 以素数为思考的, 类似的解法自然会想到位运算, 假如有26个字母, 那么只需要26 bit的数字就可以表示. C++中int是4byte, 即32 bit大小, 就足够了. 把A转换成位串, 对于B的每个字符, 移位后和A的位串做与运算, 看结果是不是True

第一个和最后一个都是自己想到的, 第二个是看字符串包含学到的, 深感素数的神奇.

2. 最小子串覆盖

lintcode 32

给定一个字符串source和一个目标字符串target,在字符串source中找到包括所有目标字符串字母的子串。

注意事项:

如果在source中没有这样的子串,返回"",如果有多个这样的子串,返回起始位置最小的子串。

说明:

在答案的子串中的字母在目标字符串中是否需要具有相同的顺序? ——不需要。

样例

给出source = “ADOBECODEBANC”,target = “ABC” 满足要求的解 “BANC”

这个题的解法是维持两个指针, 一个left, 一个right. 首先移动right, 直到所有的target都被包括(注意target中可能有重复字符, 也要考虑进来).

然后移动left, 缩小长度. 在缩小的时候, 不满足要求了, right需要继续向右移动. 必须保证当前的right-left+1中满足target.

时间复杂度是O(n)

3. 最长重复子串

leetcode 1044

给一个字符串,找出其中最长的重复子串。比如banana,输出ana。

  1. 这个最直观的思路就是暴力求解,对字符串的所有子字符串进行比较。但是这个复杂度很高,字符串找全部子串的复杂度是$O(n^2)$, 字符串比较的复杂度是$O(n)$, 所以总共需要$O(n^3)$的复杂度. 但是空间复杂度不会很高, 只有$O(n)$.

  2. 优化的策略是使用后缀数组, 对后缀数组进行排列, 然后比较. 可以参考这里

    思路大概是, 对所有的后缀字符串进行排序, 这样就可以把相同后缀的放到临近位置. 然后比较, 找出大的相同后缀. 但是复杂度也很高, 首先生成后缀数组需要$O(n)$, 排序需要$O(nlog(n) \times n)$, 因为排序需要$O(nlog(n))$, 其中排序时的字符串比较需要$O(n)$.

    最后比较排序好的字符串又需要$O(n^2)$. 所以最后的复杂度是$O(nlog(n) \times n)$.

    这个复杂度虽然降低了一点, 但在leetcode上做的时候仍然无法通过. 超时了, leetcode给的解法复杂度在$O(nlog(n))$, 非常可怕了.

代码:

int comlen(char* s1, char* s2){
    string a = string(s1);
    string b = string(s2);

    auto i = 0;
    while(i<a.length()){
        if(a[i] == b[i])
            i++;
        else
            return i;
    }
    return i;
}

bool stringComp(char* s1, char* s2){
    if(strcmp(s2, s1) == 1)
        return true;
    else
        return false;
}


string longestDupSubstring(string s){
    auto L = s.length();

    if(L == 0)
        return s;

    auto maxLen = 0;
    auto index = 0;

    char* suff[L];

    for(auto i=0; i<L; i++)
        suff[i] = &(s[i]);

    sort(suff, suff+L, stringComp);

    for(auto i:suff)
        cout << i << endl;

    for(auto i=0; i<L-1; i++){
        auto len = comlen(suff[i], suff[i+1]);
        if(len > maxLen){
            index = i;
            maxLen = len;
        }
    }

    string rts = string(suff[index]);
    return rts.substr(0, maxLen);
}

可以参考:

构造后缀数组有更高明的方法和技巧, 但是这就涉及到比较复杂的知识, 这部分内容不针对竞赛, 这里先不做深究.

4. 字符串模式删除

删除模式串中出现的字符,如“welcome to asted”,模式串为“aeiou”那么得到的字符串为“wlcm t std”,要求性能最优.

可以维持两个指针, 一个遍历, 一个指示要保留的位置. 用map来判断当前字符串是否需要删除. 假设字符串长度位$n$, pattern为$m$, 那么时间复杂度就是$O(m) + O(n)$, 空间复杂度为$O(1)$

代码:

string deleteByPattern(string s, string pattern){
    map<char, int> mp;
    for(auto i:pattern)
        mp.insert(pair<char, int>(i, 0));

    auto keep = 0;
    for(auto i=0; i<s.length(); i++){
        if(mp.find(s[i]) == mp.end()){
            s[keep] = s[i];
            keep++;
        }
    }

    return s.substr(0, keep);
}

5. 均分01串

给定一个字符串,长度不超过100,其中只包含字符0和1,并且字符0和1出现得次数都是偶数。你可以把字符串任意切分,把切分后得字符串任意分给两个人,让两个人得到的0的总个数相等,得到的1的总个数也相等。

例如,输入串是010111,我们可以把串切位01, 011,和1,把第1段和第3段放在一起分给一个人,第二段分给另外一个人,这样每个人都得到了1个0和两个1。我们要做的是让切分的次数尽可能少。 考虑到最差情况,则是把字符串切分(n - 1)次形成n个长度为1的串。

可以这样想, 因为它切开的字符串可以拼接,所以一开始就可以把这个字符串看成一个01构成的圆环,或者说一个圆上有偶数个1,显然必有一条直径可以均分两边的1,同时也均分了两边的0。这条直径的两个端点就是窗口。

总共2n个0和2n个1, 下标从0开始,$f(x)_{(x=0,1,…,2n)}$ 表示原串在$[x….x+2n-1]$的一段中 0 的个数与 1 的个数的差。

那么$f(0) + f(2n) = 0$(恰好是全部的 0 和 1)

  • 如果$f(0) = f(2n) = 0$相当于从中间切一刀成两段,可以完成,答案是 2
  • 否则$f(0) < 0$(或者 >0)$f(2n) > 0$(或者 <0)
    • f(x) 始终是偶数
    • 窗口滑动 f(x) -> f(x+1)
    • 0 和 1 的个数不变 差不变
    • 多了个 0,少了个 1,增加 2
    • 少了个 0,多了个 1,减少 2

窗口滑动过程中,偶数由负数到正数(或者由正数到负数)的过程中,必然能出现 f(y) = 0,即存在 0<=y<=2n 使得 f(y)=0

把$[y…2n+y-1]$作为一段,它包含n个0和n个1 剩余部分合并为一段 所以一共切成 3 段就可以 即只需要看第一个窗口就可以

如果第一个窗口f(0) == 0, 那么答案是 2,否则答案是 3

摘自均分 01