牛客338107602号

分类

题解(16)

/ 注册

全部文章（共41篇）

题解 | #岛屿数量#

总结：1.根据题意可知，每找到一个连通分量就是一个岛屿。所以可以使用循环访问所有的点，每找到一个未被访问且值为1的点就是一个连通分量，岛屿数就加1.找到一个岛屿后就使用深度优先搜索把岛上所有的点遍历一遍，标记为已访问。 import java.util.*; public class Solut...

深度优先搜索 Java

2022-07-03

0 307

题解 | #N皇后问题#

总结：1.解决n皇后问题需要使用dfs解决，由于棋子不能同行同列，同一条斜线，需要先判断是否满足这一条件。左斜线的满足行列序号和相同，右斜线的点满足行列值序号差相同。为了保证查询条件时间复杂度为O1,故将该条件值保存在HashSet，使得查询速度为O1。 import java.util.*; ...

深度优先搜索 Java

2022-07-03

0 405

题解 | #走迷宫#

总结：1.需要考虑终点有障碍这一特殊情况。2.使用广度优先搜索可以解决这一问题，将无障碍的网格表示为1，有障碍或被访问过都表示为0. import java.util.*; public class Main{ public static void main(String[] args){ ...

Java 广度优先搜索

2022-07-02

0 338

题解 | #【模板】单源最短路1#

总结：1.java中boolean默认为flase,对象默认为null2.无权图计算单源最短路径可以使用广度优先算法，借助队列记忆将要访问的下一层顶点。可以使用visited[]标志顶点是否被访问过，以防止被多次访问。 import java.util.*; public class Main{ ...

图 Java

2022-07-01

3 329

题解 | #【模板】堆#

总结：1.堆插入元素时，从下往上调整，由于相邻子树已经是大根堆，只需要不断与父节点比较大小，将大的节点和父节点互换，直到到达根节点或小于父节点即可结束。2.堆删除元素时，为避免破坏ArrayList中堆的结构，可以将堆顶元素替换为最后一个元素，然后删除掉最后一个元素。堆删除元素后从上往下调整堆结构，...

Java

2022-07-01

0 350

题解 | #从中序与后序遍历序列构造二叉树#

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v...

Java

2022-06-30

0 335

题解 | #实现二叉树先序，中序和后序遍历#

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Sol...

Java 二叉树

2022-06-30

0 272

题解 | #【模板】单源最短路2#

Djkstra算法 import java.util.*; public class Main{ private static int[] path;//存储到达终点前的一个点 private static int[] path_len;//存储1号点到终点的最短路径长度 p...

Java 图

2022-06-29

0 476

题解 | #最小生成树#

Prim算法 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回最小的花费代价使得这n户人家连接起来 * @pa...

Java 最小生成树

2022-06-29

1 441

题解 | #【模板】拓扑排序#

import java.util.*; public class Main{ public static void main (String[] args){ Scanner sc = new Scanner(System.in); String[] str ...

Java 图

2022-06-27

0 347