力扣题解26-30

26 删除有序数组中的重复项

简单题

有序数组删除重复项，在我本科学习第一门编程语言python的时候老师就教了这样一个技巧：倒序删除，这样从后往前删除就不会影响前面的了。于是我也试了一下C++版本的。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        for(int i=nums.size()-1; i>0; i--){
            if(nums[i] == nums[i-1]) nums.erase(nums.begin()+i);
        }
        return nums.size();
    }
};
1
2
3
4
5
6
7
8
9

能通过，用时12ms。当然肯定不是最快的写法。这里还是学习一下快慢指针的方法。快指针用于寻找下一个不同的数，慢指针用于保存。这样的好处是一次循环，最后只要返回慢指针，就能知道有多少不重复的数了，不用管后面的数。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

用时4ms，快了一些。

27 移除元素

简单题

和上面一题一样，不多赘述。

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

中等题

在线性时间内进行字符串匹配的KMP算法，其核心思想就是当原串和模式串按指针匹配失败的时候，不直接回退到头，而是回退到已经匹配成功的模式串的前缀等于后缀的下一处。因此要构造一个next数组，表示匹配到某处失败后应该从哪个地方续上。next数组是仅仅关于模式串的，构造时间复杂度为O(m)。尝试举例用尽可能简单的语言描述模式串m=aaabbab的构造过程，实际上基本上是模式串进行自我匹配的过程。设置i指针用于每次更新next数组，j指针用于模式匹配。i初始化为1，因为next[0]为0。当i和j所指位置的字符能匹配，i要记录j的下一个位置。不能匹配的时候就要不断寻找next数组所指示的下一个位置直到能匹配或者j=0。

		for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
1
2
3
4
5
6
7
8
9

至于得到了next数组后如何使用来匹配就很简单了。一旦匹配不成功，模式串的指针就后退到next数组指示的地方就行了，原字符串的指针不用回退。

class Solution {
public:
    int strStr(string haystack, string needle) {
        //使用KMP算法，先构造next数组，以0为next[0]
        int nsize = needle.size();
        int hsize = haystack.size();
        //添加哨兵
        haystack.insert(haystack.begin(),' ');
        needle.insert(needle.begin(),' ');
        
         //下面构造next数组，花费O(m)时间
        vector<int> next(nsize+1);
        //i为每次更新的next数组下标，j初始化为0就是省的溢出
         for(int i=2,j=0; i<=nsize; i++){
             while(j && (needle[i] != needle[j+1])) j = next[j]; //每次都按照next数组的指示向前回退，然后比较其下一个位置能不能和i位置匹配，不行就还得退
             if(needle[i] == needle[j+1]) j++; //前缀和后缀匹配
             next[i] = j; 
         }

        //根据next数组进行匹配，增加了哨兵所以从1开始
        for(int i = 1, j = 0; i <= hsize; i++){
            //不匹配，从next数组指示的下一个位置开始
            while(j && haystack[i] != needle[j + 1]) j = next[j];
            if(haystack[i] == needle[j + 1]) j++;
            if(j == nsize) return i - nsize;
        }
        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
24
25
26
27
28
29

30 串联所有单词的子串

困难题

题目很好理解，总的来说就是一个字符串匹配。只是需要匹配的字符串不唯一，而是可以由words里的字符串组合而成。

首先想到的当然是暴力搜索。为字符串设置一个指针，从0号位置向右移动，每个位置进行匹配，每次+1。而在每个位置上，都需要进行一次匹配。这里的匹配用最原始的方法，遍历words中未经匹配的字符串，如果有能匹配的就选择它，并将其从words中移除。以上思路得到的算法如下：

class Solution {
public:
    vector<int> res; //结果
    int ssize; //字符串的长度
    int wlen; //words向量中的字符串个数
    int wsize; //words向量中每个字符串的长度
    vector<int> findSubstring(string s, vector<string>& words) {
        ssize = s.size(); //字符串的长度
        wlen = words.size(); //words向量中的字符串个数
        wsize = words[0].size(); //words向量中每个字符串的长度
        int front = 0; //遍历指针
        int maxsize = ssize-wlen*wsize; //最大需要检查的指针的位置

        while(front<=maxsize){
            //深搜求解，每个位置要么找不到，要么找到一个就返回
            vector<string> C = words; //剩下的字符串 
            dp(front,front,C,s);
            front++;
        }
        return res;
    }

    void dp(int front, int cur, vector<string>& C, string& s){
        if(!C.size()) {
            //找到一种可能的解，直接退出
            res.push_back(front);
            return;
        }
        string next = s.substr(cur,wsize);
        vector<string>::iterator it=find(C.begin(),C.end(),next);
        if(it != C.end()){
            //下面一个字符串在剩下的列表中存在，更新C，注意只更新一个元素
            C.erase(it);
            dp(front,cur+wsize,C,s);
        }
    }
};
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

毫无悬念地超时了。原因在于：
1、每次往右移动一位。因为我们每次是比对一个单词，所以这样我们上一次做的比较就完全没有利用价值了，除非全部存起来。正确做法应该是每次向右移动wordlist中字符串长度个位置，这样位置和上一次计算的结果是对应的，就不需要重新计算中间的内容了
2、使用深搜这本身就没有考虑复用上次的计算结果，表现在每次都从头开始匹配，也没有记录之前的匹配结果。
结论：应该换成滑动窗口

虽然我也不太懂什么叫滑动窗口，不过看了题解，好像就是将字符串中words长度*words中每个字符串长度得到的最终字符串长度当成一个窗口，然后不断向右移动匹配。算法进行了以下优化：

1. 滑动窗口。在对字符串进行匹配检查的时候，指针从0开始每次向右移动words中字符串长度个位置。然后再回到1，重复上述操作，然后回到2……最后回到words中字符串长度-1的位置。这样我们和之前的做法一样，也遍历了所有位置，但是每次可以使用前一次得到的中间结果。
2. 判断是否匹配。使用hash表判断两个字符串是否相等。使用字符串为键，出现的次数为值。构造一个differ哈希表，使其等于滑动窗口的字符串与words的字符串的差。如果某一次发现当前滑动窗口代表的hash表中所有键的值都是0，那么就是滑动窗口和words没什么不同，匹配成功。这样每个位置我们只要执行一次hash表的遍历，长度为words的长度。算上遍历，总时间复杂度为O(m*n)。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res; //结果
        int ssize = s.size(); //字符串的长度
        int wlen = words.size(); //words向量中的字符串个数
        int wsize = words[0].size(); //words向量中每个字符串的长度
        int maxsize = ssize-wlen*wsize; //最大需要检查的指针的位置

        for(int i=0; i<wsize; i++){
            unordered_map<string,int> differ; //对比是否符合条件的hash表
            for(int j=0; j<words.size(); j++){
                ++differ[words[j]]; //首次使用[]调用会以0初始化
            }
            for(int j=i; j<i+wlen*wsize; j+=wsize){
                --differ[s.substr(j,wsize)];
            }
            bool success = true;
            for(auto kv:differ){
                if(kv.second != 0){
                    success = false;
                    break;
                }
            }
            if(success) res.push_back(i);
            //根据wordlist更新
            //根据第一个滑动窗口更新
            //判断一下如果所有键的值都是0，则匹配成功
            int front = i+wsize; //遍历指针，从i的下一个位置
            while (front<=maxsize){
                ++differ[s.substr(front-wsize,wsize)];
                --differ[s.substr(front+wlen*wsize-wsize,wsize)];
                bool sc = true;
                for(auto kv:differ){
                    if(kv.second != 0){
                        sc = false;
                        break;
                    }
                }
                if(sc) res.push_back(front);
                //删掉前一个，增加后一个，然后判断
                front += wsize;
            }
        }
        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
47

总结：在这道题里，我所理解的滑动窗口就是一个固定大小的窗口，然后每次对这个滑动窗口进行操作，时间复杂度应该是和滑动窗口有关的（？）。另外需要学习的是无序hash表的使用。

void printmap(const unordered_map<string,int>& mp){
	//按值或者按引用循环
    for(pair<string,int> kv:mp){
        cout<<kv.first<<" "<<kv.second<<endl;
    }
    for(auto& kv:mp){
        cout<<kv.first<<" "<<kv.second<<endl;
    }
}

int main(){
    //初始化
    unordered_map<string,int> mp1({{"we",1},{"dd",5}});
    //插入，insert或直接访问，找不到的元素会赋初始值0
    mp1.insert(pair<string,int>("da",3));
    mp1["dgadg"] = 9;
    //查找和计数
    unordered_map<string,int>::iterator it1 = mp1.find("da"); //可以找到
    cout<<"da的值为："<<it1->second<<endl;
    unordered_map<string,int>::iterator it2 = mp1.find("adgag"); //找不到
    //cout<second<
    printmap(mp1);
    //unordered_map::iterator it = mp1.find(3); //查找值不合法
    //cout<first<
    mp1.insert(pair<string,int>("da",4)); //尝试新增一个相同的键，失败
    printmap(mp1);
    cout<<"da的数量为："<<mp1.count("da")<<endl;
    cout<<"ddddddd的数量为："<<mp1.count("ddddddd")<<endl; //可以用这个判断键是不是存在，因为count只可能返回0或1


    return 0;
}
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