算法之广度优先,深度优先,拓扑,贪心,并查集

2024-06-22 16:58
文章标签 算法 深度 贪心 查集 拓扑 优先 广度

本文主要是介绍算法之广度优先,深度优先,拓扑,贪心,并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1 图算法
    • 1.1 广度优先搜索
    • 1.2 深度优先搜索
    • 1.3 拓扑排序
    • 1.4 贪心算法
      • 1.4.1 定义
      • 1.4.2 示例
    • 1.5 并查集(不相交集合数据结构)
      • 1.5.1 并查集讲解
      • 1.5.2 Kruskal算法
      • 1.5.3 Prim算法
    • 1.8 Bellman-Ford算法

1 图算法

地图数据常常可以用图(Graph)这类数据结构表示，那么在图结构中常用的搜索算法也可以应用到路径规划中。

首先是两种针对无权图的基本图搜索算法：深度优先搜索(Depth First Search, DFS)、广度优先搜索(Breadth First Search, BFS)。它们的区别在于openlist(后面介绍)所选用的数据结构类型不同，前者使用栈，后者使用队列；之后引入一种启发式搜索算法：贪婪最佳优先算法(Greedy Best First Search, GBFS)，用来提高搜索效率，但是不能确保找到最优路径；最后介绍两种在路径规划中非常经典的算法：Dijkstra算法、A*算法，前者是广度优先算法(BFS)在带权图中的扩展，后者则是在前者中加入启发函数得到的算法，兼顾效率和完备性
https://zhuanlan.zhihu.com/p/346666812?utm_medium=social&utm_oi=1096915858005323776

1.1 广度优先搜索

广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索算法是图的基本算法之一，图是用来保存多对多的关系的数据结构，相对于树一对多的关系更为复杂，所以难度也会比树结构难一点，图的存储一般有连接表表示跟链接矩阵表示，相比来说链接矩阵的方式更为常用，也就是用数组来存储。而广度优先搜索算法其实就是图的遍历过程，数组的遍历大家都会，数组的遍历按照下标的顺序来遍历的，而图的遍历也有自己的方式，图是多对多的关系，我们可以按照各个节点直接的关联关系来遍历他们，这样便衍生出来深度优先跟广度优先，广度优先是先访问与跟当前节点相关联的所有节点，而深度优先则是按照关联关系一层层的遍历。如下图：
在这里插入图片描述

public class BFS {  private LinkedList list=new LinkedList();  public void BFS(int[][] map){  boolean[] visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  list.addLast(i);  while (!list.isEmpty()) {  //访问队列里面的第一个节点  int now=(Integer) list.removeFirst();  visited[now]=true;  // 将与该节点关联的且没有访问的节点加入到队列中。  for (int j = 0; j < visited.length; j++) {  if (map[now][j]==1&&!visited[j]) {  list.addLast(j);  }  }  }  }  }  }  
}

1.2 深度优先搜索

说完广度优先搜索后，我们来看图的另一种遍历形式，深度优先搜索算法，深度优先总是对刚发现的节点的出发边进行探索，直到该节点的所有出发边都被发现为止。一旦所有的出发边都被发现，搜索就回溯到前驱结点，来搜索前驱结点的出发边。反复进行直到全部遍历。我们用递归跟栈两种方式进行实现，其实归根到底递归也是栈实现的。

递归实现：

public class DFS {  private boolean[] visited;  public void dfs(int[][]map){  visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  core(map, i);  }  }  }  public void core(int[][]map,int node){  System.out.println(node);  visited[node]=true;  for (int i = 0; i < visited.length; i++) {  if (map[node][i]==1&&!visited[i]) {  core(map,i);  }  }  }  
}

栈实现：

private LinkedList list=new LinkedList();  private boolean[] visited;  public void dfs(int[][] map){  visited=new boolean[map.length];  for (int i = 0; i < visited.length; i++) {  if (!visited[i]) {  list.addLast(i);  while (!list.isEmpty()) {  int now=(Integer) list.getLast();  visited[now]=true;  System.out.println(now);  int link=getlink(map, now);  if (link!=-1) {  list.add(link);  }else {  list.removeLast();  }  }  }  }  }  public int getlink(int[][]map,int node){  for (int i = 0; i < map.length; i++) {  if (map[node][i]==1&&!visited[node]) {  return i;  }  }  return -1;  }

1.3 拓扑排序

拓扑排序是图中所有节点的一种线性次序，首先拓扑排序是对有向无环图来说的，如果不满足这个条件则无法拓扑排序，拓扑排序就是遵循一定的规则对节点的排序，规则就是假设在图中有一条边是从a节点出发指向b节点，则在拓扑排序中b节点不可能排在a的前面。其实就是一直寻找入度为0的节点。我们也可以理解成b的完成必须依赖a的完成，a没有完成则b无法进行，其实这样理解的话我们先前说的线性规划也是一种拓扑排序，像我们平时的起床过程也是一种拓扑排序。
在这里插入图片描述
拓扑排序的实现：

public class TopoSort {        public void topsort(int[][]map){  int[] into=new int[map.length];  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map.length; j++) {  if (map[i][j]==1) {  into[j]++;  }  }  }  for (int i = 0; i < into.length; i++) {  int j=0;  while (into[j]!=0) {  j++;  if (j>into.length) {  return;  }  }  System.out.println(j);  into[j]=-1;  for (int k = 0; k < into.length; k++) {  if (map[j][k]==1) {  into[k]--;  }  }                            }                      }

1.4 贪心算法

1.4.1 定义

贪心算法相比动态规划更简单，也更高效。它总是做出局部最优选择，希望这样可以得到全局的最优选择。所以这种方法不能保证得到最优解，但是很多问题却都可以用这种方法。

贪心算法是一种基于贪心策略的算法，它在每一步选择中都采取当前状态下最优选择，以期望最终得到全局最优解。贪心算法通常用于求解最优化问题，如最小生成树、最短路径、背包问题等。
贪心算法的基本思想是：每一步都选择当前最优解，不考虑未来的后果。这种贪心策略可能会导致局部最优解，但并不一定能得到全局最优解。因此，在使用贪心算法时，需要证明贪心策略的正确性，即证明每一步的最优解能够导致全局最优解。

以下是一个简单的贪心算法示例：
假设有一组硬币，面值分别为1、5、10、50、100元，现在需要用最少的硬币凑出总值为200元的钱数。使用贪心算法，每一步都选择当前面值最大的硬币，直到凑出总值为200元为止。
具体步骤如下：

  • 选择面值最大的硬币100元，剩余金额为100元；
  • 选择面值最大的硬币100元，剩余金额为0元；
  • 总共使用了2枚硬币，得到最优解。

在这个例子中，贪心算法得到了全局最优解，因为每一步选择的最优解都能够导致全局最优解。但是，对于其他问题，贪心算法可能会得到局部最优解，而不是全局最优解。因此，在使用贪心算法时，需要仔细分析问题，证明贪心策略的正确性。

1.4.2 示例

假设我们有n个活动，只有一个教室，求在这个教室中一天最多可以举办多少活动（同一时间只能举办一个活动）。下面给出的是活动的开始时间跟结束时间。
输入：按每个活动完成时间排序（升序），开始时间数组S，完成时间数组F
输出：表示最大活动数的数组{X1,X2,…Xn},其中Xi=0（没选择）或者1（选择）

活动序号（i）1234567891011
活动开始（Si）130535688212
活动结束（Fi）4567991011121416

动态规划：

public class DPActity {  public void actity(){  Scanner sc=new Scanner(System.in);  int[][] map=new int[25][25];  for (int i = 0; i < 11; i++) {  map[sc.nextInt()][sc.nextInt()]=1;  }  for(int i=1;i<map.length;i++){  for(int j=0;j<=i;j++){  if(map[j][i]==1){  map[0][i]=max(map[0][i-1], 1+map[0][j]);  }else{  map[0][i]=max(map[0][i-1],map[0][i]);  }  }  }  System.out.println(map[0][24]);  }  public int max(int a,int b){  if(a>b){  return a;  }else{  return b;  }  }  public static void main(String[] args) {  new DPActity().actity();  }  }

虽然这样写的感觉代码也不多，但是如果我们用贪心的做法你会发现非常简单，而且好理解。因为我们的数值倒是按照结束时间排序的，所以一直选择结束时间最短的则获得最优解。在这里选择结束时间最早的活动就是我们的决策点。而贪心算法关键就是在选择决策点上。顺便一提像01背包问题不能用贪心算法来解但是分数 背包可以解决。

public void greedy(int[]s,int[]f){  int n=s.length;  int k=1;  for (int i = 2; i < n; i++) {  if (s[i]>=f[k]) {  k=i;  }  }  System.out.println(k);  }

1.5 并查集(不相交集合数据结构)

1.5.1 并查集讲解

在java中经典的数据结构基本都给实现好了，我们可以直接调用，但是并查集这种数据结构却没有很好的替代工具，在这里我们自己去实现并查集数据结构。首先我们先要去了解什么是并查集
并查集是一种非常经典常用的数据结构。像求连通子图跟我们下面要研究的最小生成树问题都会用到并查集。

  • 并查集:就是能够实现 若干个不相交集合，较快的合并和判断元素所在集合的操作。
  • 不相交集合:一个不相交集合维护了一个不相交动态集合{s1，s2，s3……}我们用一个代表标示每一个集合，他是这个集合的成员。我们不关心哪个成员作为代表，仅关心2次查询这个集合时放回结果应该相同（如果我们不修改集合）。

并查集主要就有三个方法：

  • make-set（x）：建立一个新集合唯一元素就是x，因为是不相交集合所以x不会出现在其他集合中
  • union（x，y）：将包含x和y的2个动态集合合并成一个新集合。
  • find-set(x)：返回一个指针，这个指针指向包含x的集合代表

这样说是不是有点懵，我们来看一个图。
在这里插入图片描述
上图两棵树就是一个不相交集合，a数的代表就是a而e树代表就是e，我们在a树上查找b则返回a而查找c也返回a说明b与c在同一结合上，而查找f返回e，说明b与e是在两个结合上，他们两个是不相交的。而union操作就是将两颗树合并成一棵树。

我们先给出一个一般的实现，数组表示不相交集合保存的各个集合的元素。初始化时：
在这里插入图片描述

每个元素都指向自己的父节点也就是自己。这种方式每个节点都指向自己的上一节点。而只有代表节点指向的是自己。所以我们根据这个来搜索代表节点。

public class Ufsarry {  private int[] node;  private int max;  public void makeset(int n){  node=new int[n+1];  max=n;  //所有的节点都是不相交集合，代表节点都指向自己。  for (int i = 0; i < node.length; i++) {  node[i]=i;  }  }  public int findset(int x){  while (x!=node[x]) {  x=node[x];  }  return x;  }  public void union(int x,int y){  node[x]=y;  }  
}

下面我们要说的就是并查集优化，按秩合并与路径压缩。听着好像很高深，其实很哄人的。两张图就可以解释。
在这里插入图片描述
在这里插入图片描述
第一张图就是路径压缩，我们之前都是指向的上一节点，而压缩则是直接指向代表节点。
按秩合并则是我们外加一个属性来记录集合的秩。而秩多的则说明树比较高，我们将矮的树嫁接在高的树上，这样总的高度较小。而如果高度相同，则只需要将一个树嫁接过去，给他的秩加一即可。

public class Ufs {        private int[] father;  private int[] rank;  public void makeset(int x){  father[x]=x;  rank[x]=0;  }  public int findset(int x){  if (father[x]!=x) {  father[x]=findset(father[x]);  }  return father[x];  }  public void union(int x,int y){  x=findset(x);  y=findset(y);  if (x==y) {  return;  }else {  if (rank[x]>rank[y]) {  father[y]=x;  }else{  if (rank[x]==rank[y]) {  rank[y]++;  }  father[x]=y;  }  }  }    
}

优化后的代码并不比之前的代码复杂。我们这里是用的数组来实现的，当然也可以用链表来实现。我们下面要说的Kruskal算法的效率就要看，我们写的并查集的实现。而按秩合并与路径压缩是目前已知渐进时间最快的Kruskal算法实现方式。

1.5.2 Kruskal算法

说完并查集我们接着再来看这个Kruskal算法(克鲁斯卡尔算法)
什么是最小生成树呢，很形象的一个形容就是铺自来水管道，一个村庄有很多的农舍，其实这个村庄我们可以看成一个图，而农舍就是图上的每个节点，节点之间有很多的路径，而铺自来水管道目的就是为了让每家都能用上自来水，而至于自来水怎么铺就不关心了，而铺管子的人就会想如何才能最节省材料，那么最省材料的一条路径就是我们这个图的最小生成树。
而如何去构建一个最小生成树呢？这个就用到了我们之前说的贪心策略。 这里的觉得点就是一直寻找安全边，所以构建最小生成树的过程可以描述成， 循环一直寻找安全边加入到树中，直到树中包含所有节点

什么是安全边？

安全边的定义就是假设集合A是我们的最小生成树的子集，每一步都是选择一条边是A的还是最小生成树的子集，则那条边就是安全边

根据安全边选择策略不同有两种最短路径算法，分别是Kruskal算法跟prim算法。我们先来说Kruskal算法。首先我们先看一下图

在这里插入图片描述
在这里插入图片描述

大家可能已经看出来了，kruskal算法寻找安全边的方式，就是在所有的边中找最小的表，只要两个节点是两个不相交集合，就加入到最小生成树中，直到所有的节点都连接起来
大体伪代码描述：

  1. 循环所有的边；
  2. 构建一个最小优先队列；
  3. 构建一个并查集；
  4. 直到构建成最小生成树{ 从优先队列取出一个值，判断两个节点是不是不相交集合，是否加入到最小树中。 }
  5. 结束

javabean示例：

public class Bian implements Comparable<Bian>{  private int left;  private int right;  private int value;  public Bian(int i, int j, int k) {  this.left=i;  this.right=j;  this.value=k;  }此处省去getset方法@Override  public int compareTo(Bian o) {  if (this.getValue()>o.getValue()) {  return -1;  }  return 1;  }  
}

并查集

class Ufs{  private int[] father;  private int[] rank;  public void makeset(int max) {  father = new int[max];  rank = new int[max];  for (int i = 0; i < father.length; i++) {  father[i] = i;  }  }  public void union(int x, int y) {  if (rank[x] > rank[y]) {  father[y] = x;  } else {  if (rank[x] == rank[y]) {  rank[y]++;  }  father[x] = y;  }  }  public int findset(int x) {  if (father[x] != x) {  father[x] = findset(father[x]);  }  return father[x];  }  
}

核心代码其实就是一个循环过程，而之前的代码也全是在先前的准备工作

public void kruskal(int[][] map) {            Ufs ufs=new Ufs();  ufs.makeset(map.length);  ArrayList list=new ArrayList();  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map[i].length; j++) {  if(map[i][j]!=0){  Bian b=new Bian(i,j,map[i][j]);  list.add(b);  }  }  }  int max=0;  while(max<=map.length-1  && list.size()!=0 ){  Collections.sort(list);  Bian b=(Bian) list.remove(0);  int x=b.getLeft();  int y=b.getRight();  if(ufs.findset(x)!=ufs.findset(y)){  ufs.union(x, y);  System.out.println("连接"+x+","+y+"路径长度为"+b.getValue());  max++;  }  }  }

1.5.3 Prim算法

prim算法是另一种最小生成树算法。他的安全边选择策略跟kruskal略微不同，这点我们可以通过一张图先来了解一下。
在这里插入图片描述

prim算法的安全边是从与当前生成树 相连接 的边中选择一条最短的一条，并且该边是应是生成树与生成树外一点的连接
所以我们prim算法用汉字描述的过程应为：

  1. 初始化
  2. 构造最小优先队列，将所有节点都加入到最小优先队列中，所有节点的key设置为无穷大，开始节点设置成0。
  3. 循环，直到队列为空
    {取出key值最小的节点加入到生成树中，变量与key相连接的边，看是否属于树中的节点相连，如果不是且key值比队列中节点的key值小则更新队列中该节点的key值，最小优先队列排序}
  4. 结束

下面的代码就是按照刚才的过程实现的，有很多需要优化的地方，当然算法还需要根据具体的题目，选择最好的写法，这里只是给出思想。

public class Prim {    private int MAX=1000;  private int NULL=-1;  public void prim(int[][]map){  Node[] nodes=new Node[map.length];  ArrayList list=new ArrayList();  for (int i = 1; i < map.length; i++) {  list.add(new Node(i, NULL, MAX));  }  list.add(new Node(0,NULL,0));  while(!list.isEmpty()){  Collections.sort(list);  Node n=(Node) list.remove(1);  System.out.println(n.getValue()+","+n.getLink()+","+n.getKey());  nodes[n.getValue()]=n;  for (int i = 0; i < map.length; i++) {  if(map[n.getValue()][i]!=0&&nodes[i]==null){  for (Object o : list) {  Node node=(Node) o;  if(node.getKey()==i&&map[n.getLink()][i]<node.getValue()){  node.setLink(n.getValue());  node.setKey(map[n.getLink()][i]);  }  }  }  }  }  }  
}  
class Node implements Comparable<Node>{  private int value;  private int link;  private int key;  省去getset方法public Node(int value, int link, int key) {  this.value = value;  this.link = link;  this.key = key;  }  @Override  public int compareTo(Node o) {  if (this.key>o.getKey()) {  return -1;  }  return 1;  }  }

1.8 Bellman-Ford算法

Bellman-Ford算法(音译贝尔曼福特算法)，单源最短路径算法，它是图算法之一，前面说的贪心，图的遍历，动态规划都是它的基础，单源最短路径其实说的就是图中节点到节点的最短路径。就像我们使用百度地图从哪到哪一样，找出最近的距离，而单源最短路径问 题不只是两点之间的路径，他有很多的变形，像单目的地最短路径问题，单节点对最短路径问题，所有节点对最短路径问题，最短路径的最优子结构问题。

在介绍这类算法之前我们先规定节点的基本属性，我们规定节点都有一个key值，key值记录的是 开始节点到本节点的最小距离，每个节点也都有一个p指针指向它的前驱节点。这里我们规定一个操作叫做松弛操作，我们的算法也是最终基于这个操作的。 松弛操作就是去更新key的值
在这里插入图片描述

节点B的key值为8,表示从开始节点到B节点之前的最短估计距离是8，而节点A的key值3，是说从开始节点到A节点最短估计是3，当我们发现这个边 时，从A到B的距离比较近，所以我们去更新B的key值，同时把B的前驱节点设置成A。这个过程就是松弛操作

我们说的Bellman-Ford算法是最简单的算法，就是从开始节点开始循环每一条边，对他进行松弛操作。最后得到的路径就是最短路径

public class BellmanFord {  private int[] rank;  private int max=1000;  public boolean bellmanford(int[][]map,int start,int end){  init(map.length, start);  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map[i].length; j++) {  if (map[i][j]!=0) {  relex(i,j,map[i][j]);  }  }  }  for (int i = 0; i < map.length; i++) {  for (int j = 0; j < map.length; j++) {  if (rank[j]>rank[i]+map[i][j]) {  return false;  }  }            }  return true;  }  public void init(int max,int start){  rank=new int[max];  for (int i = 0; i < rank.length; i++) {  rank[i]=max;  }  rank[start]=0;      }  public void relex(int s,int e,int length){  if(rank[e]>rank[s]+length){  rank[e]=rank[s]+length;  }          }  
}

这篇关于算法之广度优先,深度优先,拓扑,贪心,并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1084874。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2