发布时间:2024-06-07 08:01
【英雄哥六月集训】第 01天:数组
【英雄哥六月集训】第 02天:字符串
【英雄哥六月集训】第 03天:排序
【英雄哥六月集训】第 04天:贪心
【英雄哥六月集训】第 05天: 双指针
【英雄哥六月集训】第 06天:滑动窗口
【英雄哥六月集训】第 07天:哈希
【英雄哥六月集训】第 08天:前缀和
【英雄哥六月集训】第 09天:二分查找
【英雄哥六月集训】第 10天: 位运算
【英雄哥六月集训】第 11天: 矩阵
【英雄哥六月集训】第 12天: 链表
【英雄哥六月集训】第 13天: 双向链表
【英雄哥六月集训】第 14天: 栈
【英雄哥六月集训】第 15天: 二叉树
【英雄哥六月集训】第 16天: 队列
【英雄哥六月集训】第 17天: 广度优先搜索
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。(open-closed表)
672. 灯泡开关 Ⅱ
class Solution {
Set<Integer> 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<Integer> 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<Employee> employees, int id) {
Map<Integer, Employee> map = new HashMap<Integer, Employee>();
for (Employee employee : employees) {
map.put(employee.id, employee);
}
int total = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(id);
while (!queue.isEmpty()) {
int curId = queue.poll();
Employee employee = map.get(curId);
total += employee.importance;
List<Integer> 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<Integer> 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;
}
}
<<
将a的二进制数左移2位,右补0。若a=15,即二进制数00001111,左移2位得00111100,即十进制数60(为简单起见,用8位二进制数表示十进制数15,如果用16位二进制数表示,结果是一样的)。
正点原子IMX6ULL开发板设备树文件:imx6ull-alientek-emmc.dts
报错ImportError: numpy.core.multiarray failed to import
NLP经典论文:Attention、Self-Attention、Multi-Head Attention、Transformer 笔记
Istio系列学习(十一)----Istio的外部服务配置和代理规则配置
微服务的构建环境比较--Spring Cloud和Kubernetes
关于Pandas count()与values_count()的用法及区别
【论文翻译 KDD2020】AM-GCN: Adaptive Multi-channel Graph Convolutional Networks 自适应多通道图卷积网络
希云Docker培训视频百度云_希云cSphere-最佳实战Docker持续集成图文详解