Leetcode 26-30题

删除有序数组中的重复项

给定一个有序数组，要求原地删除重复出现的元素，返回删除后的数组的长度。

这里的原地删除其实可以这样表示，用双指针从前往后扫一遍，遇到新的没出现过的元素就放到前面去，就可以实现删除后的数组前面都是不重复的元素。类似如下过程：

1 1 2 3 4

1 1 2
1 2 2

1 2 1 3
1 2 2 3
1 2 3 3
1
2
3
4
5
6
7
8

int removeDuplicates(vector<int>& nums) {
    int k = 1;  // 第一个元素不用判断
    for(int i = 1; i < nums.size(); i ++) {
        if(i && nums[i] != nums[i - 1]) {
            nums[k] = nums[i];
            k ++;
        }
    }
    return k;
}
1
2
3
4
5
6
7
8
9
10

移除元素

给定数组和值val，原地删除所有数值等于val的元素，返回移除后数组的新长度。

和上一题的思想一样。

int removeElement(vector<int>& nums, int val) {
    int k = 0;
    for(int i = 0; i < nums.size(); i ++) {
        if(nums[i] != val) {
            nums[k] = nums[i];
            k ++;
        }
    }
    return k;
}
1
2
3
4
5
6
7
8
9
10

找出字符串中第一个匹配项的下标

给定字符串S，和模式串P，求P在S中所有出现的位置的起始下标

暴力做法：

//S长度为n，P长度为m
for (int i = 1; i <= n; i ++ )
{
    //寻找原串
    bool flag = true;
    for (int j = 1; j <= m; j ++ )
    {
        if (s[i + j - 1] != p[j])
        {
            flag=false;
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

利用字符串的特殊信息来减少暴力枚举的次数

当我们匹配了一段失败后，会将模式串向后移动以希望能够继续匹配上

那么就存在第二次开始匹配能成功的一段字符串的前缀等于上一次匹配能成功的一段字符串的后缀

对于每一个点预处理出来一段后缀，要最长的一段后缀和前缀相等

字符串的某一段前后缀相等

$next$记录的就是当前作为后缀末位的$j$对应的前缀末位的位置

$next[i]=j$

$p[1,j]=p[i-j+1,i]$

S = "abababc"
P = "abababab"
     12345678
// 长度为i的前缀的border
//P的next数组
ne[1] = 0;	//a
ne[2] = 0;	//ab
ne[3] = 1;	//aba
ne[4] = 2;	//abab
ne[5] = 3;	//ababa
ne[6] = 4;	//ababab
ne[7] = 5;	//abababa
ne[8] = 6;	//abababab
1
2
3
4
5
6
7
8
9
10
11
12
13

KMP算法模板：

$O(n)$

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//在某个头文件里面有next，所以一般用ne作为数组名
int n, m;
string p, s;
int ne[N];

cin >> n >> p >> m >> s;
p = " " + p, s = " " + s;

//求模式串的Next数组：
for (int i = 2, j = 0; i <= n; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    // 对于前一个border，我们往后延长一位，如果p[i] == p[j + 1]，就可以得到长度+1的border
    // 如果不行，就去前缀的前缀判断
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= m; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == n)
    {
        // 匹配成功,输出匹配位置下标(此处从0开始计数，如果要从1开始就是i - n + 1)
        printf("%d ", i - n);
        j = ne[j];
    }
}
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

全新的理解方式：

前置知识

字符串匹配问题中，给出两个字符串 text 和 pattern (本题中 text 为 S, pattern 为 P)，需要判断 pattern 是否是 text 的子串。一般把 text 称为文本串，pattern 称为模式串。暴力的解法为：
枚举文本串 text 的起始位置 i ，然后从该位开始逐位与模式串 pattern 进行匹配。如果匹配过程中每一位都相同，则匹配成功；否则，只要出现某位不同，就让文本串 text 的起始位置变为 i + 1，并从头开始模式串 pattern 的匹配。假设 m 为文本串的长度，n 为模式串的长度。时间复杂度为 O(nm)。显然，当 n 和 m 都达到 $10^5$ 级别时无法承受。

next直观理解

假设有一个字符串 s (下标从 0 开始)，那么它以 i 号位作为结尾的子串就是 s[0…i]。对该子串来说，长度为 k + 1 的前缀与后缀分别是 s[0…k] 与 s[i-k…i]。我们构造一个 int 型数组（叫啥无所谓，就叫它 next吧）。其中，next[i] 表示使字串 s[0…i] 中前缀 s[0…k] 等于后缀 s[i-k…i] 的最大的 k。（注意相等的前缀、后缀在原字串中不能是 s[0…i] 本身。这点很重要，在后面感性分析时会用到）；如果找不到相等的前后缀，就令 next[i] = -1。显然，next[i] 就是所求最长相等前后缀中前缀的最后一位的下标。

第一种方法直接画线画出子串 s[0…i] 的最长相等前后缀：

第二种方法在上部给出后缀，下部给出前缀，再将相等的最长前后缀框起来。

next[i] 就是使子串 s[0…i] 有最长相等前后缀的前缀的最后一位的下标。（这里是从0开始的下标）

我们假设已经求出了 next[0] ~ next[i-1]，用它们来推算出 next[i]

还是用我们刚刚感性认识的 s = “abababc” 作为例子。假设已经有了 next[0] = -1、next[1] = -1、next[2] = 0、next[3] = 1，现在来求解 next[4]。如下图所示，当已经得到 next[3] = 1 时，最长相等前后缀为 “ab”，之后计算 next[4] 时，由于 s[4] == s[next[3] + 1] (这里的为什么要用 next[3]？想想至尊概念)，因此可以把最长相等前后缀 “ab” 扩展为 “aba”，因此 next[4] = next[3] + 1，并令 j 指向 next[4]。

接着在此基础上求解 next[5]。如下图所示，当已经得到 next[4] = 2 时，最长相等前后缀为 “aba”，之后计算 next[5] 时，由于 s[5] != s[next[4] + 1]，因此不能扩展当前相等前后缀，即不能直接通过 next[4] + 1 的方法得到 next[5]。既然相等前后缀没办法达到那么长，那不妨缩短一点！此时希望找到找到一个 j，使得 s[5] == s[j + 1] 成立，同时使得图中的波浪线 ~，也就是 s[0…j] 是 s[0…2] = “aba” 的后缀，而 s[0…j] 是 s[0…2] 的前缀是显然的。同时为了找到相等前后缀尽可能长，找到这个 j 应尽可能大。

实际上我们上图要求解的 ~ 部分，即 s[0…j] 既是 s[0…2] = “aba” 的前缀，又是 s[0…2] = “aba” 的后缀，同时又希望其长度尽可能长，那么 s[0…j] 就是 s[0…2] 的最长相等前后缀。也就是说，只需要令 j = next[2]，然后再判断 s[5] == s[j + 1] 是否成立：如果成立，说明 s[0…j + 1] 是 s[0…5] 的最长相等前后缀，令 next[5] = j + 1 即可；如果不成立，就不断让 j = next[j]，直到 j 回到了 -1，或是途中 s[5] == s[j + 1] 成立。

如上图所示，j 从 2 回退到 next[2] = 0，发现 s[5] == s[j + 1] 不成立，就继续让 j 从 0 回退到 next[0] = -1；由于 j 已经回退到了 -1，因此不再继续回退。这时发现 s[i] == s[j + 1] 成立，说明 s[0…j + 1] 是 s[0…5] 的最长相等前后缀，于是令 next[5] = j + 1 = -1 + 1 = 0，并令 j 指向 next[5]。

下面总结 next 数组的求解过程，并给出代码：

1. 初始化 next 数组，令 j = next[0] = -1。
2. 让 i 在 1 ~ len - 1范围内遍历，对每个 i ，执行 3、4，以求解 next[i]。
3. 直到 j 回退为 -1，或是 s[i] == s[j + 1] 成立，否则不断令 j = next[j]。
4. 如果 s[i] == s[j + 1]，则 next[i] = j + 1；否则 next[i] = j。

在此基础上我们进入 kmp，有了上面求 next 数组的基础，kmp 算法就是在照葫芦画瓢，给定一个文本串 text 和一个模式串 pattern，然后判断模式串 pattern 是否是文本串 text 的子串。
以 text = “abababaabc”、pattern = “ababaab” 为例。令 i 指向 text 的当前欲比较位，令 j 指向 pattern 中当前已被匹配的最后位，这样只要 text[i] == pattern[j + 1] 成立，就说明 pattern[j + 1] 也被成功匹配，此时让 i、j 加 1 继续比较，直到 j 达到 m - 1(m 为 pattern 长度) 时说明 pattern 是 text 的子串。在这个例子中，i 指向 text[4]、j 指向 pattern[3]，表明 pattern[0…3] 已经全部匹配成功了，此时发现 text[i] == pattern[j + 1] 成立，这说明 pattern[4] 成功匹配，于是令 i、j 加 1。

接着继续匹配，此时 i 指向 text[5]、j 指向 pattern[4]，表明 pattern[0…4] 已经全部匹配成功。于是试着判断 text[i] == pattern[j + 1] 是否成立：如果成立，那么就有 pattern[0…5] 被成功匹配，可以令 i、j 加 1 以继续匹配下一位。但此处 text[5] != pattern[4 + 1]，匹配失败。那么我们这里该怎么做？放弃之前 pattern[0…4] 的成功匹配成果，让 j 回退到 -1 开始重新匹配吗？那是暴力解的方法，我们来看一下 kmp 的处理。

为了不让 j 直接回退到 -1，应寻求回退到一个离当前的 j （此时 j 为 4）最近的 j’，使得 text[i] == pattern[j’ + 1] 能够成立，并且 pattern[0…j’] 仍然与 text 的相应位置处于匹配状态，即 pattern[0…j’] 是 pattern[0…j] 的后缀。这很容易令人想到之前的求 next 数组时碰到的类似问题。答案是 pattern[0…j’] 是 pattern[0…j] 的最长相等前后缀。也就是说，只需要不断令 j = next[j]，直到 j 回退到 -1 或者是 text[i] == pattern[j + 1] 成立，然后继续匹配即可。next 数组的含义就是当 j + 1 位失配时，j 应该回退到的位置。对于刚刚的例子，当 text[5] 与 pattern[4 + 1] 失配时，令 j = next[4] = 2，然后我们会发现 text[i] == pattern[j + 1] 能够成立，因此就让它继续匹配，直到 j == 6 也匹配成功，这就意味着 pattern 是 text 的子串。

kmp 算法的一般思路如下：

1. 初始化 j = -1，表示 pattern 当前已被匹配的最后位。
2. 让 i 遍历文本串 text，对每个 i，执行 3、4来试图匹配 text[i] 和 pattern[j + 1]。
3. 直到 j 回退到 -1 或者是 text[i] == pattern[j + 1]，否则不断令 j = next[j]。
4. 如果 text[i] == pattern[j + 1]，则令 j ++。如果 j 达到 pattern_len - 1，说明 pattern 是 text 的子串。

我们观察上面的分析，能否发现：求解 next 数组的过程其实就是模式串 pattern 进行自我匹配的过程。

考虑如何统计 pattern 在 text 中出现的起始下标：
当 j = m - 1 时表示 pattern 完全匹配，此时可以输出 i - j (text 的结束位置减去 pattern 的长度就是 pattern 在 text 中出现的下标)。但问题在于：之后应该从 pattern 的哪个位置开始进行下一次匹配？ 由于 pattern 在 text 的多次出现可能是重叠的，因此不能什么都不做就让 i 加 1继续进行比较，而是必须先让 j 回退一段距离。此时 next[j] 代表着整个 pattern 的最长相等前后缀，从这个位置开始让 j 最大，即让已经匹配的部分最长，这样能保证既不漏解，又使下一次匹配省去许多无意义的比较。

综上，这题代码如下：

int strStr(string haystack, string needle) {
    // 文本串为haystack，模式串为needle
    int n = needle.size(), m = haystack.size();
    haystack = " " + haystack, needle = " " + needle;
    vector<int> ne(n + 10);
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && needle[i] != needle[j + 1]) j = ne[j];
        if (needle[i] == needle[j + 1]) j ++ ;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && haystack[i] != needle[j + 1]) j = ne[j];
        if (haystack[i] == needle[j + 1]) j ++ ;
        if (j == n)
        {
            return i - n;
            j = ne[j];
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

两数相除

给定两个整数，被除数dividend，除数divisor，在不使用乘法、除法、整除运算的条件下实现两数整除。

只能存储32位有符号整数，若除法结果溢出，则返回$2^{31}-1$。

首先根据除数和被除数来判断结果符号，然后将除法转换到负数域来做，就能有效避免爆int的情况。

很显然的暴力做法就是将除法转化为减法，将被除数一直减到小于除数为止，并记录减的次数，但这样一定会超时。

因此可以采用增加步长的方式，每次将步长扩大两倍，即$p$，$2p$，$2^{2}p$，…，$2^{k}p<dividend$。

然后倒序遍历，如果dividend大于当前项，就用dividend减去这一项，累积答案。

$2^0\times 3=3,2^1\times 3=6,2^2\times 3=12,2^3\times 3=24,2^4\times 3=48,2^5\times 3=96$

$100-96=4$，答案累积$2^5$，$4-3=1$，答案累积$2^5+2=33$

转换到负数域之后，$(-100)-(-96)=-4$，答案累积$-2^5$

int divide(int dividend, int divisor) {
    // 判断符号并转换到负数域
    bool flag = (dividend < 0) ^ (divisor < 0);
    if(dividend > 0)    dividend = -dividend;
    if(divisor > 0) divisor = -divisor;

    // 计算divisor倍数
    vector<int> vt;
    int t = divisor;
    while(t >= dividend) {
        vt.push_back(t);
        // 判断越界情况
        if(t < INT_MIN - t || t < dividend - t) break;
        t += t;
    }

    // 倒序相加
    int ans = 0;
    for(int i = vt.size() - 1; i >= 0; i --) {
        if(dividend <= vt[i]) {
            dividend -= vt[i];
            ans -= pow(2, i);
        }
    }

    // 判断越界及符号情况
    if(!flag) {
        if(ans == INT_MIN)  return INT_MAX;
        ans *= -1;
    }
    return ans;
}
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

串联所有单词的子串

给定字符串s和一个字符串数组words，字符串数组中的字符串长度相同。

s中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

返回所有串联子串在s中的开始索引。

因为每个单词的长度相同，因此可以根据每次枚举的起始位置来将其划分为不同的组。

abcdefghijkl
若单词长度为3
划分1：abc def ghi jkl
划分2：bcd efg hij
划分3：cde fgh ijk
1
2
3
4
5

这样子划分之后，对于每个划分都可以转化为这样的滑动窗口问题：

将长度为m的组合看作一个个字母，在S中找一个子串，使得这个子串不重不漏的包含word中的所有字母。

首先枚举所有的划分起点，然后设立i，j两个指针，用一个哈希表记录当前窗口内每个单词出现的次数，并记录满足条件的单词个数num。

每次读入一个单词，如果不在字典中，那么i，j这一段内不符合要求，将i移动到j位置。

如果在字典中并且之前没出现过，则更新哈希表以及num。如果在字典中，但之前出现过，则需要右移i指针直到只出现一次。

如果找到答案则更新答案序列，并继续右移i。

vector<int> findSubstring(string s, vector<string>& words) {
    unordered_map<string, int> hash;
    vector<int> res;
    int n = s.size(), m = words.size(), len = words[0].size();
    if(n < m * len) return res;     // 如果字符串小于字典长度则没有匹配
    // 这里会有特使情况，比如字典里的字符串可能不止出现一次，这就需要另外记录字典里每个单词出现次数
    for(auto p : words) hash[p] ++; 

    for(int k = 0; k < len; k ++) {     // 划分组合，一共有len组，对每组进行双指针
        int num = 0;    // 满足条件的单词个数
        unordered_map<string, int> ump;    // 存储窗口中的满足条件的单词数量
        for(int i = k, j = k; j <= n - len; ) {     // 双指针
            string str = s.substr(j, len);
            if(hash.find(str) == hash.end()) {      // 若字典没有这个单词
                j = j + len;
                i = j;
                ump.clear();
                num = 0;                // 那么[i,j]都不符合要求
            }else {
                // 若字典中有这个单词
                ump[str] ++;
                // 若满足数量条件
                if(ump[str] == hash[str])    num ++;
                else if(ump[str] > hash[str]) {     // 如果多了就要右移i
                    while(i < j && ump[str] > hash[str]) {
                        string st = s.substr(i, len);
                        ump[st] --;         
                        // 如果这个单词原来是满足要求的现在不满足要求了
                        if(ump[st] == hash[st] - 1)   num --;
                        i += len;
                    }
                }
                if(num == hash.size()) {      // 满足要求
                    res.push_back(i);
                    // 将i加入答案后后移
                    string st = s.substr(i, len);
                    ump[st] --;
                    num --;
                    i = i + len;
                }
                j = j + len;
            }
        }
    }
    return res;
}
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