牛客338107602号

分类

题解(16)

/ 注册

全部文章（共27篇）

题解 | #快速幂#

总结：快速幂需要解决两个难点：1.大数的幂运算计算量很大，会耗费很长时间。2.计算的中间过程数很大会超出计算机的运算范围。难点1：可以通过将幂运算转换为乘法。如果指数是偶数，可以将底数变为aa,指数变为b/2,这样就降低了计算量但值不变。如果指数是奇数，底数底数变为aa,指数变为b/2,同时结果还要...

Java 分治

2022-07-06

0 7

题解 | #循环汉诺塔#

总结：1.本题可以使用动态规划，分为从A到B,从B到C两个状态。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(S...

Java 动态规划

2022-07-06

0 5

题解 | #汉诺塔问题#

总结：1.汉诺塔问题是经典的递归问题，移动n个盘从left借助mid移动到right,可以分解为先将n-1个盘从left借助right移动到mid,再把第n个盘从left直接移动到right，之后再将mid处的n-1个盘从mid借助left移动到right.其中移动n-1个盘的过程又可以划分为类似的...

Java 递归

2022-07-05

0 6

题解 | #ranko的手表#

总结：1.本题计算最大最小值，可以使用枚举法把所有符合规则的字符串保存起来，之后再计算最大最小值。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner s...

Java 枚举

2022-07-05

0 5

题解 | #二分查找-I#

总结：1.二分查找通过改变low,high,计算mid。防止出现大数问题，mid计算推荐mid=low+(high-low)/2 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，...

二分查找 Java

2022-07-04

0 4

题解 | #kotori和素因子#

总结：1.在计算素数时，除数只需要计算到Math.sqrt(n)，不需要遍历到n.而且虽然1不是素因子，但n/1可能是素因子，这种情况应该考虑在内。2.当将每个整数的因子统计好后，可以使用深度优先搜索，逐层寻找素因子，也可以使用数组统计已被访问过的因子。 import java.util.*; pu...

Java 深度优先搜索

2022-07-04

0 8

题解 | #岛屿数量#

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

深度优先搜索 Java

2022-07-03

0 8

题解 | #N皇后问题#

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

深度优先搜索 Java

2022-07-03

0 9

题解 | #走迷宫#

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

Java 广度优先搜索

2022-07-02

0 13

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

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

图 Java

2022-07-01

0 8