📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3177| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[二分/排序/搜索] 总结几个BFS 的pattern

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
之前连续刷了很多BFS 类型的题目,按照自己的想法总结了些笔记,分享下,希望有帮助,总结的不好的地方 请指出

Shortest Path Between Single Source To Single Destination
Pattern:
  • Given one start state, find out the shortest path to another destination state
  • There might be some constraints on the path, e.g. walls, limited words in a dictionary, dead ends, etc
  • Within the shortest path, same state should be visited at most once, this requires maintain a visited array during traversing a path, should not release the state’ visited status (this is different than DFS backtracking where we must release the state)
  • Usually need to maintain a variable steps to indicate number of transitions from one state to another, different problems may use this concept differently, e.g. result needed from Word Ladder I = steps + 1
Code template
Queue<String> queue = new LinkedList<>();
queue.add(start);    // add the initial state
Set<String> visited = new HashSet<>();
int res = 0;    // how many steps to current state
while (!queue.isEmpty()) {
    res++;    // sometimes we need to update this after adding next level
    int n = queue.size();  // must get the size as the size will be changed within the loop after adding new elements
    for (int k = 0; k < n; k++) {    // pop out each element in current level
        String cur = queue.poll();
        // for each char in cur, try different options
        // if its a 2D matrix problem (cur means the x, y position), the options usually means go to its four neighbor
        for (int i = 0; i < cur.length(); i++) {
            // get the updated state for cur
            String updated = f(cur);
            // shortest path found
            if (findTarget(updated, target)) {   // sometimes we need to check this right after get the cur state, depends on what does res mean in the specific problems
                return res;
            }
            if (isConstraint(updated) || visited.contains(updated)) {    // such state is not allowed to visit
                continue;
            }

            queue.add(updated);
        }
    }
}
return -1;

Example
339. Nested List Weight Sum
364. Nested List Weight Sum II
* source is the top level, destination is the bottom level
* get sum for the path
127. Word Ladder I
126. Word Ladder II
752. Open the Lock
* in each state, each digit can go up or go down by 1, so two options/neighbors
* loop each possible option and add it into next level
* stop the BFS until hitting the target, and return the steps required
854. K-Similar Strings (more generic BFS problem)
* initial state is string A, end state is string B, ask for the min swaps (k) to convert A to B, this might not be so straightforward as a BFS problem, we should think BFS as more generic from state to state, instead of just position x to position y
* find out the neighbors of a given state is key (also make this problem more challenge than others) to solve this problem, i.e. smartly pick the j-th char to switch with i-th which can cause less BFS steps


Shortest Path Between Single Source To Multiple Destinations
Example:
675. Cut Off Trees for Golf Event
* Given a start point, ask for the total steps to reach to all destinations (trees) with ordered.
* First sort the destinations
* Use BFS to count steps from (x, y) to target position, with the sorted order i.e. start from (0, 0) to lowest height tree, then from that tree (destination) to next lowest tree, … until the last tree is hit
* Accumulated steps is the final result
864. Shortest Path to Get All Keys
* Given a start point, ask for the total number of moves to reach to all destinations (positions with keys)
* The order of the key to retrieve is unknown, but it also matters, as the keys retrieved so far can decide whether can pass some locks.
* If we simulate permutations of all keys, one of them indicates the right order of keys to be retrieved, then just do BFS to traverse each key in this permutation as destination (same as 675). However, getting the permutations take K! and it takes too much time
* A better way is do BFS with keys hold as one of state information, the goal is to hit a position where all the keys have been retrieved

Shortest Path Between Multiple Sources and Multiple Destinations
Pattern:
Starting state contains any of the source, destination points are not unique, for some problems, end state is one of destination is met, for others, end state is all destinations must be met
Example:
934. Shortest Bridge
* Find out the shortest path between any of sources to any of the destinations
* DFS first to isolate all cells in island 1 (as the sources, all cells in the rest of island as destinations)
* BFS to get the shortest path from any of sources to any of the destinations, stop the BFS once any destination is hit
847. Shortest Path Visiting All Nodes
* Find out the shortest path with starting at any of the node until all nodes have been reached from the start point
542. 01 Matrix (Same as 1162. As Far from Land as Possible)
* Shortest path between multiple sources (0 cells) to one destination (1 cell)
* First identify and collect all 0 cells to a queue (note that we do not start from those 1 cell)
* start from each of the 0 cell, mark all 1 cells reachable from such 0 with the distance
* for any 1 cell, the distance to such cell will be overridden by the path from any 0 cell with shorter distance, after all 0 cells have been iterated, the shortest path to each 1 will also be finalized
286. Walls and Gates (exactly same as 542)
For each empty room, find out the distance to its nearest gate
Start with each gate, populate all reachable empty rooms from this gate, mark the distance to each empty room
1162. As Far from Land as Possible (Similar as 542, for any source, the end state is one of destinations is met)
  • Ask for a water cell such that its distance to the nearest land cell is maximal
  • Reverse the problem, start with each land cell, mark all reachable water cells with a distance
  • After all land cells are done with the BFS, the water cell with max distance means it has the longest distance to its nearest land cell

721. Accounts Merge
  • For each account id, loop all its associated emails, for each emails, loop all associated account ids
  • BFS for each account id, at the end of BFS for a given account, all emails will be merged

317. Shortest Distance from All Buildings (For any source, the end state is all destinations must be met)
  • Ask for the total shortest distance from any empty land that can reach to a-ll buildings, revere the problem to get distance from any building to any empty land, (this is the idea of working backwards, same as 991. Broken Calculator)
  • BFS from each building, mark the distance to its reachable empty land.
  • At the end, each empty land will have the accumulated distance from reachable buildings and the total number of reachable buildings to this empty land
  • Loop the max from these empty land

296. Best Meeting Point (Similar to 317)
  • Ask for the total shortest distance from all homes to a point (can also be a home).
  • BFS from each home, mark the distance to its reachable positions (any position except this home).
  • At the end the position with min distance is the result

407. Trapping Rain Water II (PriorityQueue + BFS, very nice problem)
  • To have water trapped in a particular position, there must be higher neighbors around it, the lowest neighbor decide the water trapped
  • The most outside boundary position can not hold any water as no higher neighbor outside it, but the boundary can help decide whether the inner neighbors can hold water
  • combine the above, we start from the lowest boundary, do a BFS to its all neighbors, any inner neighbor that is lower than this boundary can hold water, keep adding the new inner neighbor to the queue for next level BFS
  • This is still a multiple sources (the most outside boundary, the inner boundaries) to multiple destination




Shortest Path with 3D State
Pattern
Need some additional information to hold to continue the BFS among all neighbors, i.e. at a particular position x, y, holding different information will decide the whether you can go further, so the queue should store position x, y and the addition status, all these are defined as one UNIQUE state
Example
864. Shortest Path to Get All Keys
847. Shortest Path Visiting All Nodes
  • State definition: the path that ends with node x and all nodes visited so far
  • End state: the path that ends with a node x and all nodes visited so far contains every node in the graph, the number of steps required in current path is final result



评分

参与人数 9大米 +22 收起 理由
不知道小帅 + 3 给你点个赞!
14417335 + 10
易兰小猫 + 1 赞一个
knetaland + 1 给你点个赞!
zhaotiemao + 1 赞一个

查看全部评分


上一篇:分享LC GF家前100高频题
下一篇:Sliding Window 题目的进一步归类
全局:
我想写这个一段时间了 您把我想说的都说了

还有一个题我觉得也是这个意思
就是minimum flip to make matrix 0
还有那个slide game

补充内容 (2020-2-8 22:32):
还有maze全家桶

补充内容 (2020-2-13 08:32):
shortest distance with obstacle elimination

评分

参与人数 2大米 +3 收起 理由
14417335 + 2
zhaotiemao + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
奋斗中 2024-2-8 07:14:39 | 只看该作者
全局:
谢谢lz分享!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表