【创作激励】写原创好文，推荐加“精”
2024-09-18 13:49:43
发布于：浙江
写原创好文，推荐加“精”
为了鼓励优质内容创作，我们决定自12月起，长期征集优质内容，推荐加精，欢迎大家分享在社区刷题过程中的宝贵经验。
活动时间
长期有效，首次开启时间：12月1日
内容要求
不限算法解题思路、编程技巧、调试经验，或者是心得体会和学习方法，要求如下：
技术型
- 分享你在刷题过程中遇到的挑战和困惑；
- 详细描述你是如何解决这些问题的，包括算法解题思路、具体代码实现等；
- 可以分享具体题目的解题思路和代码；
干货型
对某一知识内容进行总结，有较高的收藏价值。
如何参与
- 在讨论区发布文章时，在标题添加#创作计划# ，即可被统计到。
活动奖励
优秀内容将被推荐至首页精华分区；
被加精的作者可以获得ACGO社区周边一套；
注意事项
- 参与活动的帖子需真实有效，没有抄袭或侵权行为；
- chatgpt代写文章，聊天记录等不计入活动；
- 我们将严格审查，不合规的帖子一经发现将取消参资格。
全部评论 29
我们要访问图中的每个节点，即图的遍历。
图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
我们根据访问节点的顺序与方式（根据搜索方法），可以分为广度优先（BFS）和深度优先（DFS），这是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路(走迷宫)，搜索引擎，爬虫等。我们分别来介绍
一、深度优先（DFS）
深度优先搜索（Depth-First-Search），简称 DFS。
我们以上图为例，现在需要访问每个节点，且只访问一次，可以看到，图分成了很多之路，主要思路是从图中一个未访问的顶点 V （比如A）开始，沿着一条路一直走到底，深入到不能再深入为止（够深），然后从这条路尽头的节点回退到上一个节点， 如果上一个节点存在没有探索的分支，便继续探索若没有则继续回退，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
这就是暴力穷举，
1.1 图解过程
1、我们从根节点 A 开始遍历，它相邻的节点有 B，E，先遍历节点 B，再遍历 B 的子节点 C
2、上图中一条路已经走到底了(C是叶子节点，再无可遍历的节点)，此时就从 C 回退到上一个节点 B，看下节点 B 是否还有除 C 以外的节点，发现 B有 D节点，然后遍历D，
3、同理，上图中一条路已经走到底了(D是叶子节点，再无可遍历的节点)，此时就从 D 回退到上一个节点 B，B的节点都遍历过了，然后在回到A， 同样的逻辑，再到，E、F1.2 java 实现
package com.test;import java.util.ArrayList;
import java.util.List;public class DepthFirstSearch {
// 定义图结构
private List<Integer>[] graph;// 构造函数，初始化图结构
public DepthFirstSearch(int numVertices) {
graph = new ArrayList[numVertices];
for (int i = 0; i < numVertices; i++) {
graph[i] = new ArrayList<>();
}
}// 添加边
public void addEdge(int v1, int v2) {
graph[v1].add(v2);
}// 深度优先搜索算法实现
public void dfs(int start) {
boolean[] visited = new boolean[graph.length]; // 标记每个顶点是否被访问过
dfsHelper(start, visited); // 递归实现深度优先搜索算法
}// 递归实现深度优先搜索算法
private void dfsHelper(int vertex, boolean[] visited) {
visited[vertex] = true; // 标记当前顶点已被访问过
System.out.print(geta(vertex)); // 输出当前顶点编号
for (int neighbor : graph[vertex]) { // 遍历当前顶点的邻居顶点
if (!visited[neighbor]) { // 如果邻居顶点未被访问过，则递归访问它
dfsHelper(neighbor, visited);
}
}
}private String geta(int index){
switch (index) {
case 0:
return "A";
case 1:
return "B";
case 2:
return "C";
case 3:
return "D";
case 4:
return "E";
case 5:
return "F";
}
return "";
}// 测试代码
2024-06-22 来自 广东
2#创作计划#
所谓回文数，就是正着读和反着读一样的数，例如，12321 和 5665 都是正着读和反着读一样的数，所以是回文数；而 1234 反着读是 4321，和正着读不一样，所以不是回文数。输入格式
输入一个正整数 n ( 0<n≤10
9
)。输出格式
如果 n 是回文数，则输出 YES；否则输出 NO。2024-03-05 来自 上海
0题目描述
你作为一个村的村长，保卫村庄是理所当然的了。今天，村庄里来了一只恶龙，他有 n 个头，恶龙到嘎人放火。你着急了。不过天无绝人之路，现在来了一个骑士团，里面有 m 位成员，每个人都可以砍掉一个大小不超过 x
i
的头，需要花费个 x
i
金币，求最砍掉龙的所有头的最小花费。提示
数据范围：1≤n,m≤20000
样例说明：
派出花费为7的骑士砍掉大小5
2024-03-05 来自 上海
0贪心
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n,m,a[20000],b[20000],sum=0,s;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;2024-03-05 来自 上海
0
有帮助，赞一个