算法的比较

广度优先搜索&深度优先搜索（Breadth First Search & Depth First Search）

 BFS优缺点：
 同一层的所有节点都会加入队列，所以耗用大量空间
 仅能非递归实现
 相比DFS较快，空间换时间
 适合广度大的图
 空间复杂度：邻接矩阵O（N^2）；邻接表O（N+E）
 时间复杂度：O（V+E）

 DFS优缺点：
 无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小
 有递归和非递归实现
 由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢
 适合深度大的图
 空间复杂度：邻接矩阵O（N^2）；邻接表O（N+E）
 时间复杂度：O（V+E）

//BFS只能非递归实现，将queue替换成stack之后就是DFS

Comments

Post a Comment

Popular posts from this blog

1427. Split Array into Fibonacci Sequence

Description 中文 English Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from S, or return [] if it cannot be done. 1 <= S.length <= 200 S contains only digits. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Ex...
Read more

Amazon OA 763. Partition Labels

class Solution { public:     vector<int> partitionLabels(string S) {         // 这是个好题         unordered_map<char, int> mp;         vector<int> res;         const int size = S.size();         if(size == 0){             return res;         }         for(int i = 0; i < size; i++){             mp[S[i]] = i;         }         int start = 0, end = 0;         for(int i = 0; i < size; i++){             end = max(end, mp[S[i]]);             if(i == end){                 res.push_back(i - start + 1);                 start = end + 1;     ...
Read more

05/25 周一

上午8点40多起床，今天天气很热33度最高 上午看了关于H1B的可能ban的事情 然后报税 搞了好久 到现在，吃过饭了。 2020年5月25日13:38:35 听九章上一个转行进入谷歌的讲座， 1，刷题态度 2，抽象总结 3，刷题就是一种学科 不想生活的这么卑微。 别人能做到的，我也可以！ 2020年5月25日17:11:38
Read more