算法学习总结(leetcodecpp)

算法学习总结(leetcodecpp)

目录

一、二分查找

二、双指针

三、滑动窗口

---

我写的没人家好，就用的人家的链接。

一、二分查找

参考：

Charon_cc的博客【二分查找】详细图解。

题目:

• 35. 搜索插入位置

• 278. 第一个错误的版本

•   704. 二分查找

二、双指针

参考：

lady_killer9的博客双指针算法详解（快慢指针、对撞指针、滑动窗口）

题目:

• 977. 有序数组的平方

• 283. 移动零

• 334. 反转字符串

• 557. 反转字符串中的单词 III

• 189. 轮转数组

• 19. 删除链表的倒数第 N 个结点

• 876. 链表的中间结点

• 167. 两数之和 II - 输入有序数组

三、滑动窗口

参考：

ALGtactor的博客滑动窗口算法学习

• 3. 无重复字符的最长子串                                                                                                                 这个题目我感觉其他人解释的不太满意这里的题目我自己解释下吧。(我感觉你们可能更反感我解释的haha)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()== 0) return 0;
         unordered_set lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0;i < s.size();i++){
            while(lookup.find(s[i]) != lookup.end())
            //unordered_map也有find方法，得到的对象是一个iterator，在unordered_map中，如果find()没找到要找的key，就返回和end()一样的iterator值。
            {
                //如果s[i]，并没有在lookup里的时候，下一步从下一个相同的位置开始，比如abcdefdac到第二个d查出来，之前的abc都没用了。
                lookup.erase(s[left]);
                left++;
            }
            //每次i结束的时候就是看大小啦
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
        }
        return maxStr;
    }
};

这里用到了unordered_set这个stl库，顾名思义这是一个无序的集合。

unordered:无序的

set：集合

/滑稽

参考资料：unordered_set - C++ Reference

C++ STL unordered_set容器完全攻略

看不下去怎么办？？？？(我也是，不行就按照我下面的理解)

1.unordered_set lookup;构造函数，就理解我建了一个hashtable总可以吧。

2.lookup.find(s[i]) != lookup.end();首先end()函数是最后一个元素的下一个位置，所以说 end()对应的结果一定是元素不在无序集合内。所以，我们可以 用lookup.find(s[i])查询元素是否在结合内并与end()做一个比较，来知道其元素是否在无序集合内。

3.lookup.erase(s[left]);删除元素。

4.lookup.insert(s[i]);插入元素

大体说一下这道题的思想，举个栗子。o(*￣▽￣*)ブ

"abcdecabd"

1. 第一个for循环检索a，"abcdcad"，a不在无序集合中，那么仅仅把a存入无序集合中，然后更新最大值此时最大值为1。
2. 第二个for循环检索b，"abcdcad"，b不在无序集合中，那么仅仅把b存入无序集合中，然后更新最大值此时最大值为2。
3. 第三个for循环检索c，"abcdcad"，c不在无序集合中，那么仅仅把c存入无序集合中，然后更新最大值此时最大值为3。
4. 第四个for循环检索d，"abcdcad"，d不在无序集合中，那么仅仅把d存入无序集合中，然后更新最大值此时最大值为4。
5. 第五个for循环检索a，"abcdcad"，c在无序集合中，那么我们进入了while,此时left为0，所以我们删除了下标0位置的a，继续进入while循环删除b跟c，此时left为3，为什么这么删除呢？我们要看的是看连续的字符串中不存在相同的字符的最长的长度(我真废话)，第一个c作为一个拦路虎，把其左边的ab跟右边的dcad割裂了，如果看连续这个c肯定是不看的了，所以我们要把ab一块删除了。此时字符串我们遍历的过程变成"abcdcad"，把新的c存入无序集合中，然后更新最大值此时最大值为4。
6. 第六个for循环检索d，"abcdcad"，a不在无序集合中，那么仅仅把a存入无序集合中，然后更新最大值此时最大值为4。
7. 第七个for循环检索d，"abcdcad"，d在无序集合中，那么我们需要把第一个d及其左边都给删了，字符串变成"abcdcad"，把d存入无序集合中，然后更新最大值此时最大值为4。

• 567. 字符串的排列

考研只会的复建了。慢慢更新。