algorithm / leetcode
17 minutes read (About 2516 words) 0 visits

leetcode_bfs

Leetcode Breadth-first Search Problem

here is the list of problem related to bfs in leetcode websites. (sorted according to problem’s difficulty level):

Easy:

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Level: Easy

Solution 1

BFS通常的做法是利用一个队列对元素进行添加和排除，FIFO。这里我们可以使用bfs对树进行逐层遍历，因为我们要判断是否对称，所以队列每次会pop出两个节点，并且保证这两个节点在位置上对称，随后对两个节点的子树进行添加到BFS队列中。

  • 如果这两个节点均为NULL，则继续遍历队里
  • 如果两个节点有一个为NULL，则返回false
  • 如果两个节点均不为NULL但值不同，则返回false
  • 如果两个节点均不为NULL且值相同，则继续遍历队列

两个节点子树插入时也要按照位置进行对应，显然如果left和right已经在位置上对称，则left->left与right->right对称，left->right与right->left节点对称。

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Compleixty: $O(N)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        
        TreeNode *left, *right;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()){
            left = q.front();
            q.pop();
            right = q.front();
            q.pop();
            
            if(left==NULL && right==NULL) continue;
            else if(left && right && left->val==right->val){
                q.push(left->left);
                q.push(right->right);
                
                q.push(left->right);
                q.push(right->left);
                continue;
            }
            
            return false;       
        }
        
        return true;
        
    }
};

Solution 2

同样的思想，只是此时我们可以用递归的方式来实现，有点类似于dfs，先判断最底层，然后逐层往上进行判断。参考leetcode中别人发布的代码

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return judge(root->left, root->right);        
    }
    
    bool judge(TreeNode* l, TreeNode* r){
        return (!l || !r)? l==r : l->val==r->val && judge(l->left, r->right) && judge(l->right, r->left);
    }
};

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).


Level: Easy

Solution 1

简单的使用bfs，每次遍历一层然后记录，最后对向量vector进行一个逆转操作

Complexity Analysis

  • Time Complexity：$O(N)$
  • Space Complexity: $O(N)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root) return {};
        vector<vector<int>> res;
        vector<TreeNode*> level={root};
        while(!level.empty()){
            res.push_back({});
            vector<TreeNode*> frontier;
            for(auto n: level){
                res.back().push_back(n->val);
                if(n->left) frontier.push_back(n->left);
                if(n->right) frontier.push_back(n->right);
            }
            level=frontier;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Solution 2

一样的思路，用dfs+postorder来进行遍历

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, vector<vector<int>> &res, int level){
        if(!root) return;
        if(level==res.size()) res.push_back({});
        dfs(root->left, res, level+1);
        dfs(root->right, res, level+1);
        res[level].push_back(root->val);
    }
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root) return {};
        vector<vector<int>> res;
        dfs(root, res, 0);
        reverse(res.begin(), res.end());
        
        return res;
    }
};

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Level: Easy

Solution 1

直接dfs进行计算depth，判断如果其中左右子树为空情况，则返回两个子树深度的最大值（因为要到叶子节点），否则返回两个子树深度小的那个

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int ld = minDepth(root->left);
        int rd = minDepth(root->right);
        
        if(!ld || !rd) return max(ld, rd) + 1;
        else return min(ld, rd) + 1; 
    }
};

Solution 2

用bfs进行逐层遍历，若发现某层中节点为叶子节点，则输出当前层数

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        
        vector<TreeNode*> level={root};
        int depth=1;
        while(!level.empty()){
            vector<TreeNode*> frontier;
            for(auto n: level){
                if(!n->left && !n->right) return depth;
                if(n->left) frontier.push_back(n->left);
                if(n->right) frontier.push_back(n->right);    
            }
            depth++;
            level=frontier;
        }
        return depth;
    }
};

559. Maximum Depth of N-ary Tree

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Solution 1

就是对二叉树的深度算法演变，求每个子树的最大深度

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN)$

Code

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int dfs(Node*root){
        if(!root) return 0;
        int md=0;
        for(auto np: root->children){
            md = max(md, dfs(np));
        }
        return md+1;
    }
    int maxDepth(Node* root) {
        return dfs(root);
    }
};

Solution 2

观察最深的level，bfs的做法，若当前为空，则范围level层数

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(N)$

Code

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) return 0;
        vector<Node*> frontier={root};
        int level=0;
        
        while(!frontier.empty()){
            level++;
            vector<Node*> next;
            for(auto n: frontier){
                for(auto cn: n->children){
                    if(cn) next.push_back(cn); 
                }
            }
            frontier = next;
        }
        
        return level;
    }
};

690. Employee Importance

You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Solution 1

直接用queue进行bfs就好了

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(N)$

Code

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
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> hash;
        for(auto e: employees) hash[e->id] = e;
        queue<int> q;
        q.push(id);
        int total_value=0;
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            total_value += hash[cur]->importance;
            
            for(auto sub: hash[cur]->subordinates) q.push(sub);
        }
        return total_value;
    }
};

Solution 2

用dfs来做一下

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(logN), worst case O(N)$

Code

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
/*
// Employee info
class Employee {
public:
    // It's the unique ID of each node.
    // unique id of this employee
    int id;
    // the importance value of this employee
    int importance;
    // the id of direct subordinates
    vector<int> subordinates;
};
*/
class Solution {
public:
    int dfs(unordered_map<int, Employee*> hash, int id){
        int res=hash[id]->importance;
        for(auto sub: hash[id]->subordinates){
            res += dfs(hash, sub);
        }
        return res;
    }
    int getImportance(vector<Employee*> employees, int id) {
        unordered_map<int, Employee*> hash;
        for(auto e: employees) hash[e->id] = e;
        return dfs(hash, id);
    }
};

993. Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Solution 1

利用bfs，逐层来找，这里用两个vector，若找到当前节点等于某个x或y，则在该层找到另一个节点且其不为兄弟（利用下标来判断，若下标除2不相等）

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(N)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if(!root) return false;
        
        vector<TreeNode*> frontier={root};
        while(!frontier.empty()){
            vector<TreeNode*> next;
            for(int i=0; i<frontier.size(); i++){
                if(!frontier[i]) continue;
                if(frontier[i]->val==x || frontier[i]->val==y){
                    int j=i;
                    while(++j<frontier.size()){
                        if(frontier[j] && (frontier[j]->val==x || frontier[j]->val==y) && j/2 - i/2 !=0) return true;
                    }
                    return false;
                }
                next.push_back(frontier[i]->left);
                next.push_back(frontier[i]->right);
            }
            frontier=next;
          
        }
        return false;
    }
};

Solution 2

还是利用bfs，逐层来找，这里用两个queue

Complexity Analysis

  • Time Complexity: $O(N)$
  • Space Complexity: $O(N)$

Code

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if(!root) return false;
        
        queue<TreeNode*> q1, q2;
        q1.push(root);
        
        while(!q1.empty()){
            bool siblings=false, cousins=false;
            while(!q1.empty()){
                TreeNode* cur = q1.front();
                q1.pop();
                
                if(cur==nullptr) siblings=false;
                else{ 
                    if(cur->val==x || cur->val==y){
                        if(!cousins) cousins=siblings=true;
                        else return !siblings;
                    }
                    q2.push(cur->left), q2.push(cur->right), q2.push(nullptr);
                } 
            }
            if(cousins) return false;
            swap(q1, q2);
        }
        return false;
    }
};

994. Rotting Oranges

In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Solution 1

bfs的做法，把最初烂掉的位置作为起始，bfs去探索周围四个方向未烂的位置并加入进去，左后判断好的橙子的数目是否为0

Complexity Analysis

  • TIme Complexity: $O(mn))$
  • Space Complexity: $O(mn)$

where $m$ and $n$ are the shape of the input grid.

Code

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
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int total=0, level=-1, count=0;
        
        int m=grid.size(); 
        int n=grid[0].size();
        
        vector<int> d1={-1, 0, 1, 0};
        vector<int> d2={0, 1, 0, -1};
        
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> frontier;
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(!grid[i][j]) continue;
                else if(grid[i][j]==2) {
                    frontier.push_back({i, j});
                    visited[i][j] = true;
                }
                else if(grid[i][j]==1) total+=1;
                
            }
        }
        
        while(!frontier.empty()){
            level++;
            vector<vector<int>> next;
            for(auto cur: frontier){
                for(int i=0; i<4; i++){
                    int r = cur[0] + d1[i];
                    int c = cur[1] + d2[i];
                    if(r>=0 && r<m && c>=0 && c<n && !visited[r][c] && grid[r][c]==1) {
                        next.push_back({r, c});
                        visited[r][c] = true;
                        count++;
                    }
                }
            }
            frontier=next;
        }
        
        return count==total? max(level, 0): -1;
    }
};

Solution 2

其实也是bfs，不过看到了别人的做法，几个c++函数用的挺有意思的，就自己也尝试了一下。
不过是一个in-place的做法，对grid中的进行一个修改

Complexity Analysis

  • Time Complexity: $O(mn*(m+n))$
  • Space Complexity: $O(1)$

Code

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
class Solution {
public:
    
    int rot(vector<vector<int>>& grid, int i, int j, int d){
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]!=1) return 0;
        grid[i][j] = d+3;
        return 1;
    }
    
    int orangesRotting(vector<vector<int>>& grid, int d=0, int fresh=0){
        
        for(int i=0; i<grid.size(); i++){
            fresh += count_if(begin(grid[i]), end(grid[i]), [](int j){ return j==1; });
        }
        for(auto old_fresh=fresh; fresh>0; d++){
            for(int i=0; i<grid.size(); i++){
                for(int j=0; j<grid[i].size(); j++){
                    if(grid[i][j] == d+2){
                        fresh -= rot(grid, i+1, j, d) + rot(grid, i, j+1, d) + rot(grid, i-1, j, d) + rot(grid, i, j-1, d);
                    }
                }
            }
            if(fresh == exchange(old_fresh, fresh)) return -1;
        }
        
        return d;
        
    }
};
#
graph_transformer_network
Minimum Increment to Make Array Unique
Follow

Categories

Tag Cloud

ARI Autoencoder Blog Deep Clustering Deep Learning F-Measures GNN Hexo Markov Chain NMI Purity Random Walk Unsupervised deeplearning leetcode math 聚类外部指标 论文分享

Recent

Archives

Tags

ARI 1
Autoencoder 1
Blog 1
Deep Clustering 1
Deep Learning 3
F-Measures 1
GNN 3
Hexo 1
Markov Chain 1
NMI 1
Purity 1
Random Walk 1
Unsupervised 1
deeplearning 1
leetcode 2
math 1
聚类外部指标 1
论文分享 1

Recent

Archives

Tags

ARI 1
Autoencoder 1
Blog 1
Deep Clustering 1
Deep Learning 3
F-Measures 1
GNN 3
Hexo 1
Markov Chain 1
NMI 1
Purity 1
Random Walk 1
Unsupervised 1
deeplearning 1
leetcode 2
math 1
聚类外部指标 1
论文分享 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×