多拿好offer_gx

分类

题解(24)

/ 注册

全部文章（共24篇）

题解 | #迷宫问题#

BFS求出最短距离，然后再逆序输出即可。此题可以建模成一个无向无权网络，从起点开始最先搜索到的一定是到这个节点的最短距离。保存最短距离，此后再搜索到这个节点，必然不是最短距离，不用更新最短距离。此题保证最短路径唯一，所以只需要从最后一个节点倒序搜索即可，只需要满足上一个节点的距离+1等于当前节点...

Java 最短路图 BFS

2022-03-29

0 357

题解 | #素数伴侣#线性筛质数+二分图最大匹配

首先，使用线性筛质数，将60000以内的质数全部求出；可以看出两个数的和组成一个质数，那么这两个数必然一个是奇数，另一个是偶数，所以可以将奇数和偶数分成两个集合。使用匈牙利算法求解这两个集合的最大匹配。 import java.util.*; public class Main { ...

Java 质数线性筛质数二分图最大匹配匈牙利算法

2022-03-12

0 390

题解 | #二分查找-I#

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * ...

Java 二分查找

2022-01-05

0 455

题解 | #密码验证合格程序#

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

Java 字符串

2022-01-02

4 652

题解 | #连续子数组的最大和(二)#

双指针+额外O(1)的空间复杂度求解：使用两组数据求解，一组存最优解，一组存当前解。然后更新即可。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

Java 双指针贪心

2021-12-27

0 332

题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

对每一位分开考虑。例如对数abcdef的c位。当ab取0~ab-1时，c取1，def可以取0~999，所以此时的解有ab*10^3个；当ab取ab时，c的值可分为三种情况： c=0，此时c取不到1，结果为0 c=1，此时c可以取到1，def可以取0~def，结果为def+1 c>1，此时c可...

Java 数学

2021-12-26

0 327

题解 | #剪绳子（进阶版）#

数组+快速幂：由减绳子基础班可以得知，当绳子长度与3取余为1时，取出两个2米的绳子最优；当绳子长度与3取余为2时，取出一个2米的绳子最优。那么剩下绳子长度必然是3的整数倍b=len/3。结果就是a^b。但是b的数值非常大，暴力求解必然超时，所以此时采用快速幂进行求解。就是将b换成2的各个次幂之和。 ...

Java 数学

2021-12-26

0 522

题解 | #调整数组顺序使奇数位于偶数前面(二)#

双指针算法 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 ...

Java 双指针

2021-12-25

0 398

题解 | #字符流中第一个不重复的字符#

使用哈希表和队列，每次输入的字符，哈希表中对应的次数+1，当次数为1时，加入队列；同时将队列首部出现次数大于1的字符全部删除。 import java.util.*; public class Solution { //Insert one char from stringstream ...

Java 哈希表队列

2021-12-25

0 376

题解 | #数字序列中某一位的数字#

快速幂 public class Solution { public double Power(double base, int exponent) { double res = 1; if(exponent < 0) { exp...

Java

2021-12-22

0 375