没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全力扣500题刷题笔记10

力扣500题刷题笔记10

leetcode

需积分: 0 2 下载量 201 浏览量 2022-08-04 16:02:29 上传评论收藏 1.86MB PDF 举报

温馨提示

试读

16页

1、建图并记录所有节点的入度 2、将所有入度为 0 的节点加入队列 3、取出队首的元素 now ，将其加入拓扑序列 4、访问所有 now 的邻接点 nxt ，将

资源详情

资源评论

资源推荐

力扣500题刷题笔记

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一

些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表

示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

示例 2：

提示：

1 <= numCourses <= 10^5

0 <= prerequisites.length <= 5000

prerequisites[i].length == 2

0 <= ai, bi < numCourses

prerequisites[i] 中的所有课程对互不相同

思路

(拓扑排序)

输入：numCourses = 2, prerequisites = [[1,0]]

输出：true

解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]

输出：false

解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先

完成课程 1 。这是不可能的。



拓扑排序：

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序

列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。

一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存在一条边出节点在入节点前

的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是

否存在环。

拓扑排序步骤：

1、建图并记录所有节点的入度。

2、将所有入度为 0 的节点加入队列。

3、取出队首的元素 now ，将其加入拓扑序列。

4、访问所有 now 的邻接点 nxt ，将 nxt 的入度减 1 ，当减到 0 后，将 nxt 加入队列。

5、重复步骤 3 、 4 ，直到队列为空。

6、如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。

时间复杂度分析：假设为点数，为边数，拓扑排序仅遍历所有的点和边一次，故总时间复杂度为

。

c++代码

class Solution {

public:

 bool canFinish(int n, vector<vector<int>>& edges) {

   vector<vector<int>> g(n);

   vector<int> d(n); // 存贮每个节点的入度

   for(auto edge : edges){

     g[edge[1]].push_back(edge[0]); //建图

     d[edge[0]]++; //入度加1

   }

   queue<int> q;

   for(int i = 0; i < n; i++){

     if(d[i] == 0) q.push(i); //将所有入度为0的节点加入队列。

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

题目

给定两个字符串 s 和 p ，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案

输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

示例 2:

思路

c++代码

   }

   int cnt = 0; //统计拓扑节点的个数

   while(q.size()){

     int t = q.front();

     q.pop();

     cnt++;

     for(int i : g[t]){ //访问t的邻接节点(出边)

       d[i]--;

       if(d[i] == 0) q.push(i);

     }

   }

   

   return cnt == n;

 }

};

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"

输出: [0,1,2]

解释:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

class Solution {

public:

 vector<int> findAnagrams(string s, string p) {

   unordered_map<char, int> hs, hp;

   for(int c : p) hp[c]++;

   vector<int> res;

   for(int i = 0, j = 0; i < s.size(); i++){

     hs[s[i]]++;

     while(hs[s[i]] > hp[s[i]]) hs[s[j++]]--;   

621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任

务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，

CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内

CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例 1：

示例 2：

示例 3：

提示：

1 <= task.length <= 104

tasks[i] 是大写英文字母

n 的取值范围为 [0, 100]

思路

c++代码

     if(i - j + 1 == p.size()){

       res.push_back(j);

     }

   }

   return res;

 }

};

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

  在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要

一个单位时间，所以中间出现了（待命）状态。

输入：tasks = ["A","A","A","B","B","B"], n = 0

输出：6

解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0

["A","A","A","B","B","B"]

["A","B","A","B","A","B"]

["B","B","B","A","A","A"]

...

诸如此类

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2

输出：16

解释：一种可能的解决方案是：

  A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -

> (待命) -> (待命) -> A

剩余15页未读，继续阅读

内容反馈

英次

粉丝: 20
资源: 306

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

力扣500题刷题笔记10

评论0

最新资源

力扣500题刷题笔记10

评论0

LeetCodeAnswer:力扣刷题笔记

力扣题库刷题笔记31-下一个排列

谷歌高畅Leetcode刷题笔记.pdf

力扣500题刷题笔记1

LeetCodeNotebook：自用力扣刷题笔记| https：leetcode-cn.com

力扣500题刷题笔记6

力扣500题刷题笔记5

力扣500题刷题笔记7

力扣500题刷题笔记3

力扣500题刷题笔记4

力扣500题刷题笔记8

力扣500题刷题笔记2

力扣500题刷题笔记9

力扣题库刷题笔记36-有效的数独

力扣题库刷题笔记42-接雨水（未通过）

力扣题库刷题笔记34-在排序数组中查找元素的第一个和最后一个位置

力扣刷题笔记总结记录666

labuladong的算法秘籍+刷题笔记V2.0

labuladong的刷题笔记V1.7(力扣版)

Leetcode刷题笔记.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

2024最新：Hvv中常见的面试问题

最新资源