详情可见：https://mp.weixin.qq.com/s/Eb6ewVajH56cUlY9LetRJw

1288.删除被覆盖的区间

解法：先根据开端进行排序，而后遍历，看两者的左右是否被覆盖。

这里只需要比较右边，因为左边已经按照大小进行排序了！

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {    return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);});
        int ans = n;
        int rmax = intervals[0][1];
        for (int i = 1; i < n; ++i) {
        //为什么只判断右边界？
        //因为上一个区间的左边界必定小于下一个区间的左边界！
        //因此只要右边界被包含，那么必定区间被覆盖
            if (intervals[i][1] <= rmax) {
                --ans;
            }
            else {
                rmax = max(rmax, intervals[i][1]);
            }
        }
        return ans;
    }
};

56.合并区间

Ps：按照区间起点升序排列，开头就是最小的，结尾就是重合区间最大的。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        vector<int> tmp = {0, 0};//tmp第一个元素表示区间起始位置，第二元素表示终点位置
        sort(intervals.begin(), intervals.end());  //这里排序会按照第一个数大小排，若大小相等再按照第二个数排
        tmp = intervals[0];            //初始化第一个区间
        for (int i = 1; i < intervals.size(); i ++ )    //遍历所有区间
        {
            if (tmp[1] < intervals[i][0])  //合并区间的右端点小于当前区间左端点，说明不能合并当前区间
            {
                res.push_back(tmp);     //已经合并完一个区间
                tmp = intervals[i];    //初始化新区间
            }
            else
            {
                tmp[1] = max(tmp[1], intervals[i][1]);//合并区间的右端点大于当前区间左端点，说明可以合并当前区间
            } //这里合并只需要修改右端点即可，即右端点取最大值
        }
        res.push_back(tmp);           //扫尾
        return res;
    }
};

986.区间列表的交集

57.插入区间

PS：这是从相反的方向解决问题；

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        bool placed = false;
        vector<vector<int>> ans;
        //只有这么三种情况：
        //相交
        //在左
        //在右，依次判断即可
        for (const auto& interval: intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ans.push_back({left, right});
                    placed = true;                    
                }
                ans.push_back(interval);
            }
            else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ans.push_back(interval);
            }
            else {
                // 与插入区间有交集，计算它们的并集
                left = min(left, interval[0]);
                right = max(right, interval[1]);
            }
        }
        if (!placed) {
            ans.push_back({left, right});
        }
        return ans;
    }

2）回文串（字符串/链表）

思路：

// 左侧指针
ListNode left;
booleanisPalindrome(ListNode head){
    left = head;
return traverse(head);
}
booleantraverse(ListNode right){
if (right == null) return true;
boolean res = traverse(right.next);
// 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
return res;
}

链接：

https://mp.weixin.qq.com/s/tCgEoOlZKS_ohuTx1VxJ-Q

234.回文链表

409.最长回文串

回文串；动态规划；

解题思路：

• 中心扩张，选中任何一个为中点，向两边扩展，如果两边的字符相等，则继续扩展，否则，更新结果；
• 细节在于回文长度可能为奇数也可能为偶数，这就造成中心点的坐标选择问题，一是在选点的时候看i与i+1的字符是否相等来微调；二是参考这个答案：链接

516.最长回文子序列

解题思路：

• 跟求回文子串有很多相似的地方
• 这么来思考：假设已知dp[i+1]和dp[j-1]，如何求dp[i][j]？很明显，跟s[i] s[j]有关
• 如果两者相等，那自然就是子问题+2；
• 如果两者不等，那就需要做出取舍s[i] s[j]不能同时位于一个子序列中，那个子区间最大，就取哪个，于是

<font style="color:rgb(51, 51, 51);background-color:rgb(248, 248, 248);">dp[i][j] = max(dp[i + </font><font style="color:rgb(0, 128, 128);">1</font><font style="color:rgb(51, 51, 51);background-color:rgb(248, 248, 248);">][j], dp[i][j - </font><font style="color:rgb(0, 128, 128);">1</font><font style="color:rgb(51, 51, 51);background-color:rgb(248, 248, 248);">]);</font>

• 参考链接

234.回文链表

回文串；链表；

解题思路：

• 依次压入栈中，依次弹出比对
• 仿照二叉树后序遍历的思路，借助递归来实现上述栈的效果，参考链接
• 还有一种方式，利用快慢指针，找到中点，分割链表，而后反转中点之后的链表，这样就可以进行比对。

反转链表

反转链表，有两种通用解法：递归返回头结点；迭代两相背刺；

206. 反转链表

反转链表；

解题思路：

• 递归的方式：理解递归的重点就是明白递归函数的作用，比如反转链表以递归实现如下： 若是直接跳进递归的逻辑中，云山雾绕，很难理解。
• 想想 reverse作用是什么？ 传入一个链表头节点，返回反转过后的头结点，并将这个新的头结点last，一直return回去。
• 迭代的方式：基本思路是保存当前节点的前后节点，并令当前节点的next指向其前节点（俗称，背刺！），依次背刺上一节点直到当前节点的next为null即可，返回当前节点。核心代码如下：

变种：反转链表前N个节点

其实在上一道题的基础上改一下就好。

解题思路：

• 首先遍历一遍，看看长度够不够N，不够直接返回失败；
• 递归的方式：增加一个全局变量，表示进入递归的次数，而后保存N个节点之后的第N+1个节点的指针，因为我们需要将两部分链表连接起来；
• 迭代的方式：同上，也是需要保存第N+1个节点的指针；

92. 反转链表 II

反转链表；递归

解题思路：

• 这道题，最终需要将情况细分到反转前N个链表上来
• 首先，reverseBetween（head，m，n），如果其中调用reverseBetween（head.next，m-1，n-1），那么如此递归下去，必将有m-1=1，这不就变成了反转前N个节点么？
• 仔细看看代码的递归妙用！
• 如果是迭代的方式，那么需要先遍历找到第m个节点，而后进行链表的反转，而后找到第n个节点，将反转过后的链表与之前的链表进行合并；

25. K 个一组翻转链表

反转链表；

解题思路：

• 第一种解法：递归，将K个一组反转链表，变为反转[a,a+k）区间的链表；参考链接其中reverse(a,b)是以迭代的方式实现的；
• 第二种解法：迭代，

股票买卖

股票买卖的题型其实根本是动态规划。根据下面的题来由易到难来理解一下。

重点理解：dp数组的含义；状态转移方程；遍历的方向；有没有空间优化的可能。

labuladong的教程：链接

leetcode上的教程：链接

剑指offer 63.股票的最大利润（买卖股票的最大收益 |）

股票买卖；动态规划；暴力法

解题思路：

• dp[i][k]，k取0/1，表示第i天，手头是否有股票，当前有多少钱(如果买入就是负数)；
• 初始状态：dp[0][0]=0,表示第一天手头无股票，那就无收入；dp[0][1]=-prices[0]，表示第一天买了股票，那么就是负收益；
• 那么状态转移方程就出来了：
• dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])——第i天我手头没有股票，有两种可能，要么是我昨天就没买股票，要么就是今天眼疾手快脱手了。
• dp[i][1]=max(dp[i-1][1],-prices[i])——第i天我手头有股票，要么是昨天就买了，要么是今天才买了股票进场罚站。（且只能买入一手，故利润直接为-价格）
• 最后返回什么？dp[n-1][0]，因为最后一天，肯定是手头没有股票了，才会有最大收益！
• 答案直接点题目链接，自己写过，如果想进行空间压缩，可以只保留前一天的数据
• 还有另外一种方式——暴力法：找某个元素之前的最小元素，这就是可能的最大值，可以通过记录之前的最小值，将复杂度降到O(N)，参考链接
• 还可以使用一维的dp数组，表示前i天的最大收益，核心：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
• 

122. 买卖股票的最佳时机 II

动态规划；股票买卖；

解题思路：

• dp[i][k]的含义跟上一道题一样
• 初始状态也一样
• 状态转移有些区别：
• dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
• dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])——因为我们计算的是总共的利润，所以需要将之前的收入给加起来

• 贪心：如果今天的股价比昨天的股价高，那就加上差值<font style="color:rgb(89, 89, 89);background-color:rgb(247, 247, 247);"> res += diff;</font>

LRU/LFU

LRU(Least Recently Used,最近最少使用),强调的是时间上的排序,即越久没有使用的缓存\页面进行删除\替换.

LFU(Least Frequency Used,最少频率使用),强调的是频率!当频率相同时,再比较时间!

LRU的解法

利用HashMap加双端链表,整个链表以时间来排序,.

hashmap用来获取链表节点,双端链表进行维护时间的顺序.

不能使用小顶堆,因为在get的时候,无法实现对堆内cache的更新和重排!

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;
public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
    //很重要
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        //需要更新两个的节点
        head->next->prev = node;
        head->next = node;
    }
    //很重要
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    //很重要
    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }
    //很重要
    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

LFU的解法

可以使用Set来保证其frequency排序, 再用一个HashMap实现key到value的映射。

struct CacheNode {
    int key;
    int value;
    int freq;
    long tick;

    // 小顶堆
    bool operator<(const CacheNode& other) const {
        if (freq < other.freq) {
            return true;
        } else if (freq == other.freq && tick < other.tick) {
            return true;
        }

        return false;
    }
};

class LFUCache {
public:
    LFUCache(int _capacity) {
        capacity = _capacity;
        tick = 1;
    }

    int get(int key) {
        auto iter = mp.find(key);
        if (iter == mp.cend()) {
            return -1;
        }

        int value = iter->second.value;
        touch(iter->second);

        return value;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        auto iter = mp.find(key);
        if (iter != mp.cend()) {
            // key exists, update value and touch
            iter->second.value = value;
            touch(iter->second);
            return;
        }

        if (mp.size() == capacity) {
            // Remove the first node in cache
            const CacheNode& node = *cache.cbegin();
            mp.erase(node.key);
            cache.erase(node);
        }


        // Create a new node and save to set and map
        CacheNode node{key, value, 1, tick++};
        mp[node.key] = node;
        cache.insert(node);
    }

private:
    long tick;
    int capacity;
    unordered_map<int, CacheNode> mp; // save the object instead of ptr
    set<CacheNode> cache; // Balance BST

    void touch(CacheNode& node) {
        cache.erase(node);
        node.freq++;
        node.tick = tick++;
        cache.insert(node);
    }

};

滑动窗口

567.字符串的排列

滑动窗口；多指针；

5min mid

解题思路：

• 先遍历s1字符串，存储至hashtable1中；
• 建立两个指针left和right，分别表示左右边界；一个valid，表示有多少个字符满足了条件
• 新建一个hashtable2，遍历s2，并根据该字符是否在s1中，修改hashtable2中次数，当该字符在两个hash表中出现的次数相等时，valid+1；
• 开始进行左边界的收缩，条件为窗口大小大于s1.size。根据左边界的字符，对hashtable2以及valid进行修改

还有一种关于记录出现次数的方法，见到一个利用负数、0、正数，分别表示多出现了、刚好、还需要出现几次三种状态，使得代码很精简：链接

class Solution {
    public:
    bool checkInclusion(string s1, string s2) {

        int n=s1.size();
        int m=s2.size();
        if(n>m) return false;
        vector<int>cnt1(26),cnt2(26);
        //窗口为n的字符串 是否相同
        for(int i=0;i<n;i++)
        {
            ++cnt1[s1[i]-'a'];
            ++cnt2[s2[i]-'a'];
        }
        if(cnt1==cnt2) return true;
        //
        for(int i=n;i<m;i++)
        {
            //在数组右端添加字符
            ++cnt2[s2[i]-'a'];
            //移除最左端字符
            --cnt2[s2[i-n]-'a'];
            if(cnt1==cnt2) return true;
        }
        return false;
    }
};

作者：7aughing-6olickmiv
    链接：https://leetcode.cn/problems/permutation-in-string/solution/hua-dong-chuang-kou-by-7aughing-6olickmi-95j9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1358. 包含所有三种字符的子字符串数目

滑动窗口；多指针；

心路历程：

由于之前做过求字符串字典序的题，所以照着写，最后发现过不了最后的测试用例，原因在于左右边界循环次数太多，时间复杂度达O(n^2)。

因此必须使用滑动窗口来收缩范围。

滑动串口的精髓就在于，找到合适的右边界，而后不断的收缩左边界，直到条件不满足为止。

这个过程一般会利用hash表来进行存储相应的个数或者位置信息，如果忘了滑动窗口的过程，看这个滑动窗口详解。

知识补充：min_element和max_element可以找到容器中的最小最大元素的指针，详见：[链接](https://blog.csdn.net/hanshihao1336295654/article/details/82747931)

class Solution {
public:
    int numberOfSubstrings(string s) {
        int res = 0, l = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); i++) {
            m[s[i]]++;
            while (m['a'] > 0 && m['b'] > 0 && m['c'] > 0) {
                res += s.size() - i;# 往后的序列都是啊！
                m[s[l++]]--;
            }
        }
        return res;
    }
};

76.最小覆盖子串

滑动窗口；多指针；

10min hard

心路历程：

这道题是一道典型的滑动窗口题，难处理的是如何才算是满足条件？

这里的取巧方式是，s与t各有一个hash表，如果在遍历过程中两个hash表中某数字数量相等，则说明该字符达标了。当字符达标的数目达到字符的个数时，说明一个覆盖的子串已经找到了。而后收缩左边界，直到字符达标数目不在达标为止。

知识补充：利用substr成员函数可以直接从string取出指定位置长度的子串：[链接](https://baike.baidu.com/item/substr/2171?fr=aladdin)

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;

        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = INT_MAX;
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c])
                    valid++;
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.count(d)) {
                    if (window[d] == need[d])
                        valid--;
                    window[d]--;
                }                    
            }
        }
        // 返回最小覆盖子串
        return len == INT_MAX ?
            "" : s.substr(start, len);
    }
};

438. 找到字符串中所有字母异位词

滑动窗口；

秒了 mid

心路历程：就是上一道题的变种，只增加了索引的存储。由此可见，滑动窗口其实玩来玩去就是那样，重点在于抓住它的精髓。

3.无重复的最长子串

滑动窗口；

1min mid

心路历程：在判定条件上稍微卡了一会，后来发现只要新加入的字符串大于1就计算一次长度，而后收缩左边界，直到这个新元素为1为止，而后再次扩展右边界，如此循环。

//暂时AC
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        window[c]++;
        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}
};

两数之和

框架：

双指针前后递进，大小判断，同时加上特殊条件的判定；

vector<int> twoSum(vector<int>& nums, int target) 
{ 
    // 先对数组排序     
    sort(nums.begin(), nums.end());     
    // 左右指针     
    int lo = 0, hi = nums.size() - 1;     
    while (lo < hi) {     
        int sum = nums[lo] + nums[hi];     
        // 根据 sum 和 target 的比较，移动左右指针     
        if (sum < target) {             
            lo++;         
        } else if (sum > target) {             
            hi--;         
        } else if (sum == target) { 
            return {nums[lo], nums[hi]};         
        }    
    } 
    return {}; 
} 
PS:有些题目中还可能遇到不只一对两数相加满足条件，求多组并且还要去重，这时可以用：
if (sum < target)      
    lo++; 
else if (sum > target) 
    hi--; 
else {         
    res.push_back({left, right}); 
    // 跳过所有重复的元素 
    while (lo < hi && nums[lo] == left) 
        lo++; 
    while (lo < hi && nums[hi] == right) 
        hi--;    
}

PPS：有些题目中要求返回下标，这个时候sort就不行，可以考虑用暴力法，或是用hash表存储（target-nums[i]）,而后看后续是否有数字满足；

1.两数之和

15.三数之和

PS：这道题是复用了两数之和的函数而实现的；

PS2：这道题所谓的双指针其实就是将两数之和的函数给内置到了三数之和中；

18.四数之和

区间合并与分割

56.合并区间

注：匿名函数的使用，sort是容器函数，需要借助匿名函数进行自定义的比较。

还可以这么写：

57.插入区间

注：place表示是否已经将改区间给放进去了，如果放进去了，那么在右边的直接往里边丢就行。

大数计算

大数计算的题型，一般计算的整数都超过Long Long的范围了，所以需要字符串或者容器来作为中间介质。

核心计算逻辑就是这个：

66. 加一

大数计算；

解题思路：

• 从后往前进行计算，取余数为当前位数，取商为进位；
• 如果最后一位计算之后，还有进位，那就往前插入一个1；
• 也可以转换成大数相加的方式，将1转换为“0000001”进行相加；
• 参考链接

2. 两数相加

大数计算；链表；多指针

解题思路：

• 两个指针，分别指向两个链表的开始位置
• 模拟相加的过程，一位一位的向后传递进位
• 如果某一个链表遍历完毕，那就只遍历另外一个链表即可
• 思考一下，如果链表不是逆序的，应该怎么处理？——只能先手动反转链表了

参考链接：链接

43. 字符串相乘

大数计算；字符串

解题思路：

• 我的解法，模拟乘法的过程，借助双指针，让某一个字符串的所有数与另外一个字符串的位依次相乘
• 在计算的时候需要保留进位，最后再相加
• 这种方式，相当于还要实现一遍字符串的相加，而后在过程中调用对应的函数
• 更便捷的解法，我们将乘法的计算过程进一步拆分一下
• 由上图可知，两个字符串i j位置的数相乘，那么结果只会影响到i+j 和i+j+1两位，其中i+j+1保存的是进位
• 那么我们完全可以遍历字符串，而后取位数相乘，将对应的位置存储于某一个数组中
• 而后将数组中的结果连接成字符串，结果不就出来了？
• 值得注意的是，以这种方式进行计算的时候，也需要从后往前进行遍历相乘，因为低位向高位有进位
• 同时注意进位，看这个答案：链接
• 参考链接：链接

数据结构

数据结构类型的题，是指需要理解各种常用的数据结构及算法，并通过算法来实现它

剑指offer09.用两个栈实现队列

数据结构；栈；队列

解题思路：

• 队列是先入先出，栈是先入先出，那么如果两个栈相互“串联”就可以模拟出先入先出了！
• 于是解法出来了，两个栈中一个负责接收“入队”，一个负责处理“出队”
• 当入队时，元素全部push进入第一个栈
• 当出队时，如果第二栈为空，那就将第一个栈的元素依次弹出pop并压入第二栈中，而后对第二个栈进行弹出
• 这样的时间复杂度，平均下来就是O(1)。
• 拓展：如何获取队首？其实可以对第二栈进行top访问，不进行弹出即可；

225.用两个队列实现栈

栈；队列；数据结构

解题思路：

• 两队列，一个负责接收入队push，另一个负责处理出队时的暂存区
• 入队时，数据全部放到第一队
• 出队时，将第一队的数依次出队放到第二队，只剩最后一个元素
• 而后将第二队的数据又重新赋值给第一队（这个部分本想用一个指针来指示，但是队列没有这样的操作），清空第二队
• 如此反复，时间复杂度较高，出队O(n),入队O(1)
• 拓展：其实用一个队列就可以了！在一个队列时，出队n-1个数据，并且依次再次入队，只需要返回第n个数据即可！这里有一道题解是入队O(n),出队O(1)

71. 简化路径

这道题建议直接将‘/’略过不做考虑！

而后将栈中的结果出栈，用‘/’连接在一起，值得注意的是，在C++中可以使用vector模拟栈，并且最后的结果还不用倒置。

图的奥秘

有关图的遍历与拓扑排序等；

先解决一个问题：如何存储图？

最简单的方式是利用一个二维数组来存储，如下：

图的遍历

以城市之间的距离为例，DFS和BFS都可以用作寻找最短路径。

如果是BFS，需要是队列来进行图的遍历并更新最短距离，其实BFS还可以用作求最少转机次数。将转机次数放在queue的结构体里面，也是一个很便捷的方法。

时间复杂度：O(N)，空间复杂度为O(N^2)；

因为DFS/BFS都需要遍历所有的点。

如果是任意两点之间的求最短路径，则需要每两个点进行一次BFS或DFS，即N^2次BFS和DFS。

Floyd-Warshall算法求最短路径

Floyd算法的基本思想就是对将各个顶点作为中转站，从而更新最短路径。

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。

它的时间复杂度是O(N^3)，在数据量不是很大的情况下有奇效。

这其实是一种动态规划的思想。

另外，如果图中有不可达的点，可以这样处理：

有个问题，那就是Floyd算法无法解决“负权回路”的图，因为每次经过负权的点，都会更新路径，并且如果一个图存在负权回路，那么也就不存在最短路径。

743.网络的延迟时间

最短路径；Floyd算法；

解题思路：

• 这道题完全就是Floyd算法的典型题；
• 

Dijkstra（**迪杰斯特拉**）算法求单源最短路径

何为单源最短路径？

即是求指定一个源点到其余各个顶点的最短路径。例如求下面1号顶点到2、3、4、5、6号节点的最短路径。

Dijstra算法的主要思想是：通过“边”来松弛（某节点1通过某相邻节点2中转，使得它到节点3的距离变短）各个节点到其他节点的距离。

以一号节点为例，如下是其初始路程：用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下：

将上述数组为估计值，因为后续需要做的工作就是对其更新。

我们看到1->2的路径最短，且1->2的过程不可能再短了（1到其他节点的距离都是正数，且到2是最短，总不可能还有通过其他节点中转使得1->2路径缩短吧？）

然后我们看到2号节点有“估计值”如下：

那么1号节点就可以通过2号节点来“松弛”1->3,1->4的路径，这时更新为：

接下来要做的就是从3,4,5,6（2已经走过了）找距离最小的那个节点进行中转，比如4号节点，再次更新；再从3,5,6选最近节点更新···如此反复，最终如下：

上述算法的基本思想就是：每次找到离源点（源点如1号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

Dijlstra算法基本步骤如下:

1. 顶点分为两个部分：已知最短路径P和未知最短路径Q。

最开始时P只有源点（如题目的1），其他全都在Q。这个可以用一个flag数组保存，如果flag[i]==1，那句表示在P，否则在Q。

1. P中源点设置dis到自身的距离为0，其他设置为边的长度即可；
2. 在Q中选一个离源点最近的点对源点的dis进行松弛，并更新相应的距离；
3. 将第3步所选的点从Q中删除，Q为空则算法结束；

实例代码如下：

上述算法的时间复杂度为O(N^2)，因为O(N)找到最近点，而后O(N)更新最近的距离。

其实是基于贪心策略的算法。

如何优化？

首先，使用堆排序来找最近的点，O(logn）；而后，对于边数M远小于N^2的稀疏图来说，可以将邻接矩阵改成邻接表，邻接表怎么存储？例如使用数组来实现邻接表（还可以使用指针链表）：

拓扑排序

207.课程表

图；拓扑排序；

解题思路：

顶点的度是指和该顶点相连的边的条数。特别是对于有向图来说，顶点的出边条数称为该顶点的出度，顶点的入边条数称为该顶点的入度，度=出度+入度；

有向无环图→ 一定存在入度为0的点，不然就没法解题了；

拓扑排序简单来说，是对于一张有向图 G，我们需要将 G 的 n 个点排列成一组序列，使得图中任意一对顶点 ，如果图中存在一条 u→v 的边，那么 u 在序列中需要出现在 v 的前面。亦可理解为对某点 v 而言，只有当 v 的所有源点均出现了，v 才能出现。

拓扑排序可以使用BFS与DFS来做，其中BFS较容易理解，主要是以下几个步骤：

• 让入度为 0 的点入列，它们无前置。
• 然后逐个出列，出列代表该节点已排序，减小其下个节点的入度。
• 如果下个节点的入度新变为 0，安排它入列、再出列……直到没有入度为 0 的节点可入列。
• 一般来说，出队次数必然节点数，否则就是有环。

思路链接

解题链接

1203.项目管理(拓扑排序)

图；拓扑排序；

• 解题思路：
• 相比于普通的拓扑排序，这道题的差异在于点之间有分组，即涉及到组间的排序
• 于是这道题分为两个步骤：第一是完成组与组的依赖关系，看是否存在一个拓扑排序，如果两个组之间相互依赖，任务会停摆；
• 第二是完成组内的排序；
• 其中，组与组以及组内的排序，其实都是拓扑排序，将组中所有的项目都抽象成一个点即可；
• 题解参考：链接

多线程

交替打印字符串（原子、条变量、锁）

原题链接

class FooBar {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    bool foo_done = false;
public:
    FooBar(int n) : n(n) {}

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [&]() { return !foo_done; });
            printFoo();
            foo_done = true;
            cv.notify_one();
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [&]() { return foo_done; });
            printBar();
            foo_done = false;
            cv.notify_one();
        }
    }
};

sleep_for()也可以起到 std::this_thread::yield()相似的作用, 但两者的使用目的是大不相同的。

条件变量

https://blog.csdn.net/zzhongcy/article/details/85248597?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242

并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

虽然并查集使用BFS/DFS在某些时候也是可以解题的，但是通用和简洁的解法是联合-查找算法（Union-find Algorithm）（该算法后面时间复杂度趋近于O(1)），该算法定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。即寻找到它的根节点
• Union：将两个子集合并成同一个集合。即将某一条路径上的点的最终父节点设置为另一条路径的最终父节点。如下，如果想要merge（8,5），那么过程如下：
• 上面这种合并的方式，在路径太长的时候，耗时较多，就像是一个链表在遍历，因此可以对其进行优化：直接将路径上的点指向最终父节点，而不是一级一级的找。

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。

进一步了解推荐阅读:一文搞懂并查集：原文链接

并查集

547. 省份数量

解题思路：

• 并查集的典型解法
• 首先以一个二维矩阵来表示省份之间的链接关系，以N表示初始时的省份数量
• 而后运用并查集的方式进行合并，何时需要合并？如果M[i][j]==1，就表示需要合并，如果merge(i,j)成功，N—；如果合并不成功，说明已经合并过了，那么N不变
• 最后的结果就是省份的数量
• DFS/BFS解法，查看：链接

std::vector<int> fa;
void init(int N) {
    fa.resize(N);
    for (int i = 0; i < N; i++) {
        fa[i] = i;//对应自身
    }
}
//返回 x 所属集合的ID
int find(int x) {
    int r = x;
    while(fa[r] != r) {
        r = fa[r];
    }
    //进行路径压缩
    while(fa[x] != x) {
        int t = fa[x];
        fa[x] = r;
        x = t;
    }
    return x;
}
bool merge(int u, int v) {
    int ru = find(u);
    int rv = find(v);
    if (ru == rv) {
        return false;
    }
    fa[ru] = rv;
    return true;
}
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        init(N);
        int anw = N;
        for (int i = 0; i < N; i++) {
            // i+1是因为之前的已经被合并过了
            for (int j = i+1; j < N; j++) {
                if (M[i][j] && merge(i, j)) {
                    anw --;
                }
            }
        }
        return anw;
    }
};

200.岛屿的数量

解题思路：

• 有三中那个思路，一种是这章的重点——并查集，另一种方法是利用BFS；还有一种方式是利用DFS
• 如果并查集的思路，怎么处理合并问题？如何表示一个二维矩阵的坐标呢？可以使用icols+j，相当于从第一列开始数的顺序。那么如何处理这里所谓的链接？之前省份的那道题是给出了链接关系，而岛屿的链接问题，可以以向右和向下进行判断，是否有岛屿，从而进行合并，**在遍历的过程中记录空地 0 的数量，那么最终的岛屿数量就是colsrows-空地的数量-剩余联通分量的数量。（联通分量就是说合并了多少次岛屿**）
• 如果是DFS，一般是利用栈或者递归的方式实现，递归的方式更简洁。先建立一个visited二维数组，表示所有的点都没有访问过，DFS的精髓，就是从一个点出发，依次进行上下左右的访问，会将途中访问过的点进行标记，下一次就不会对其进行访问了。
• 如果是BFS，一般是利用队列来迭代实现，只要队列不为空，那就继续进行扩展。思路跟DFS一样，利用一个二维的visited数组表示该点有没有被访问过，如果被访问/或者是水那就下一个点。
• 三种答案建议参考链接

1319. 连通网络的操作次数

并查集；

解题思路：

• 剥开外壳，这就是一个规规矩矩的并查集题
• 首先，通过并查集，我们是不是可以获得当前网络连接中的“子网个数”？
• 如何才能让所有子网互通？ 那就在子网之间两两加上一根线，一共需要 子网数量-1 的线
• 于是，线够不够就是所有子网能不能联通的关键。那么到底有多少根线可以使用？
• 在并查集合并的过程中，如果发现两个电脑其实已经是互通的了，那么这根线就是多余的！
• 多余的线数量>=需要的线数量，就能够合并 可以参考：链接

剑指 Offer II 116. 朋友圈

并查集；DFS；BFS

解题思路：

• 跟省份那道题有什么区别？
• DFS解法链接，注意，DFS的方法就是计算进入了几次DFS，因为进入一次，在遍历的过程中会将visited标志为1
• BFS解法链接，注意，BFS的方法就是看进入了几次队列的迭代操作，因为进入一次，会遍历所有可能达到的点
• 解法都简单，关键是处理的细节很到位！链接

类似题型

岛屿的数量||

改成了初始全部为水，而后将对应位置的水置为1的过程；

128.最长连续序列

这道题的方法很多，可以使用先sort再滑动窗口（用桶排序，不推荐）、set（时间复杂度略高）、unordered_set（速度快，因为不用往上下都遍历）、并查集（都合并到最小的那个数，同时用一个unordered_map来存储个数）参考链接