算法|【英雄哥六月集训】第 17天: 广度优先搜索算法|数据结构|宽度优先

系列文章【英雄哥六月集训】第 01天:数组
【英雄哥六月集训】第 02天:字符串
【英雄哥六月集训】第 03天:排序
【英雄哥六月集训】第 04天:贪心
【英雄哥六月集训】第 05天: 双指针
【英雄哥六月集训】第 06天:滑动窗口
【英雄哥六月集训】第 07天:哈希
【英雄哥六月集训】第 08天:前缀和
【英雄哥六月集训】第 09天:二分查找
【英雄哥六月集训】第 10天: 位运算
【英雄哥六月集训】第 11天: 矩阵
【英雄哥六月集训】第 12天: 链表
【英雄哥六月集训】第 13天: 双向链表
【英雄哥六月集训】第 14天: 栈
【英雄哥六月集训】第 15天: 二叉树
【英雄哥六月集训】第 16天: 队列
【英雄哥六月集训】第 17天: 广度优先搜索

文章目录

系列文章
广度优先搜索
一、灯泡开关 Ⅱ
二、员工的重要性
三、转化数字的最小运算数
总结
- 1. 位运算

广度优先搜索宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）
一、灯泡开关 Ⅱ 【算法|【英雄哥六月集训】第 17天: 广度优先搜索】672. 灯泡开关 Ⅱ

class Solution { Set set; // 10 1010 int TURN_EVEN = 0x2a; // 01 0101 int TURN_ODD = 0x15; // 00 1001 int TURN_3K_1 = 0x09; public int flipLights(int n, int presses) { // 因为二进制操作状态变换了，所以3盏还是6盏其实是一样的 n = Math.min(n, 6); // 最多枚举4^4 = 256，对灯的操作用二进制操作，所以复杂度为O(1) // 这里可以改变dfs枚举方式或用二进制迭代枚举，枚举每个操作是否出现，变成2^4 = 16 int m = Math.min(presses, 4); set = new HashSet<>(); // 比如n=6，state = 11 1111 int state = (1 << n) - 1; dfs(0, state, m, n); // print(set, n); return set.size(); }void print(Set set, int n) { for (int s : set) { for (int i = 31; i > 31 - n; i--) { System.out.print(((1 << i) & s) == 0 ? "0" : "1"); } System.out.println(); } System.out.println(); }private void dfs(int i, int cur, int k, int n) { if (i == k) { // 去掉不合法的灯状态，保留末尾n栈灯的状态 set.add(cur << (32 - n)); return; } // 反转所有灯 dfs(i + 1, ~cur, k, n); // 反转偶数位的灯, 异或 10 1010 dfs(i + 1, cur ^ TURN_EVEN, k, n); // 反转奇数位的灯, 异或 01 0101 dfs(i + 1, cur ^ TURN_ODD, k, n); // 反转3k+1的灯, 异或00 1001, 1, 4 dfs(i + 1, cur ^ TURN_3K_1, k, n); } }

二、员工的重要性 690. 员工的重要性

/* // Definition for Employee. class Employee { public int id; public int importance; public List subordinates; }; */class Solution { public int getImportance(List employees, int id) { Map map = new HashMap(); for (Employee employee : employees) { map.put(employee.id, employee); } int total = 0; Queue queue = new LinkedList(); queue.offer(id); while (!queue.isEmpty()) { int curId = queue.poll(); Employee employee = map.get(curId); total += employee.importance; List subordinates = employee.subordinates; for (int subId : subordinates) { queue.offer(subId); } } return total; } }

三、转化数字的最小运算数 2059. 转化数字的最小运算数

class Solution { public int minimumOperations(int[] nums, int start, int goal) { Deque q = new LinkedList<>(); q.offer(start); boolean[] visited = new boolean[1001]; visited[start] = true; int step = 0; while (!q.isEmpty()) { int size = q.size(); step++; while (size-- > 0){//当前队列元素对应同一个step int poll = q.poll(); for (int n : nums) { for (int x : new int[]{poll - n, poll + n, poll ^ n}) { if (x == goal) { return step; } if (x >= 0 && x <= 1000 && !visited[x]) { q.offer(x); visited[x] = true; } } } } } return -1; } }

总结 1. 位运算 <<
将a的二进制数左移2位，右补0。若a=15，即二进制数00001111，左移2位得00111100，即十进制数60（为简单起见，用8位二进制数表示十进制数15，如果用16位二进制数表示，结果是一样的）。