长白崎の个人博客

数位DP 说明： 数位DP是为了解决某些数字匹配上面的问题，其中经典的写法是套用DFS算法实现数位DP。 视屏教学： 数位DP E37 数位DP Windy数_哔哩哔哩_bilibili 这里说一下，前导零的意思，就是这个数字的前面都是零，比如说我们要dp的数字的最数字的位数为123。但是我们在进行dfs的DP的时候会从1开始，那么一开始我们从1开始dfs的时候那么就是001。也就是前面占位的都是零，也就叫做前导零。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.util.Arrays;import java.util.Scanner;/** * @description: 数位DP * 这个是一个数位DP的模板，这里的数位DP主要是利用DFS来实现的。 * @author 长白崎 *...

树形DP的讨论 讨论： 关于树形DP。树形DP比较适合解决一些有相互关系和依赖的的题型，比较典型的有没有上司的舞会、金明的预算方案、这一类题目。 首先我先说一下关于树形DP，顾名思义其含义就是在树这种数据结构上进行DP算法的运算。 树上背包DP 讨论： 树上背包DP这类是比较典型的树形DP题目。其中主要写题步骤为这几点： 首先找到我们需要DP的容量。也就是我们常说的背包容积大小，然后就是找到我们的需要DP的物品，常规的树上DP题主要关键数据就这两个。这里我就拿比较典型的一道题来说一下。 (以下题目为蓝桥官方的VIP题，我看比较典型就把它截下来了) 由图可知，我们的背包容量为V。商场一共有N件物品。第i件物品的体积为$$w_i$$，价值为$$v_i$$，其中依赖的主物件为$$s_i$$。 这里我们定义从第二行输入的数据作为下标为1的物品，以此类推。在构建树的时候我们就以0作为根节点，1意思为第一件物品，2为第二件物品依次类推。 从这我们就可以下手，我们从测试数据作为例子进行引入。以下为我依据...

BFS 介绍： BFS中文叫做广度优先搜索，BFS算是暴力搜索的其中一种算法，这个算法主要还是可以解决一些最小路径的问题，以及搜索问题，比如迷宫问题等等，其主要思想就是通过穷举所有可能走的路并找到答案或者试出最优答案，不过他相对于DFS说其有点就在于广撒网，时间复杂度要比DFS低。 Java代码模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778/** * @description: TODO * @author 长白崎 * @date 2023/3/25 17:42 * @version 1.0 */import java.util.LinkedList;import java.util.Queue;/** * BFS算法模板，BFS算法的模板写法主要分为这几步骤： *...

BinarySearch 说明： BinarySearch中文又叫做二分查找，这是一种查找类的算法，但是其使用是有一定的限制的，那就是必须要区间类必须要满足相应的单调性，不然的话是无法使用的。 Java代码模板： 整形二分（左闭右闭）： 123456789101112131415161718192021//这是一个Java整数二分模板public static void binarySearch(){ //l为二分的左值，r为二分的右值，mid为二分的中间值 int l=0,r=100,mid; //这里的l<=r为二分的结束条件 while(l<=r){ //计算二分的mid mid = (l+r)>>1; //这里的check函数主要的作用就是通过已知的必要条件传入check进行综合分析然后判断应该之后的二分是右移还是左移 if(check(Object c)) l = mid+1; //这里是右移 else r...

DFS 介绍： DFS中文叫做深度优先搜索，DFS算是暴力搜索的其中一种算法，这个算法主要还是可以解决一些最小路径的问题，以及搜索问题，比如迷宫问题等等，其主要思想就是通过穷举所有可能走的路并找到答案或者试出最优答案。 Java代码模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657/** * @description: TODO * @author 长白崎 * @date 2023/3/25 16:34 * @version 1.0 *//** * DFS算法模板，DFS算法的模板写法主要分为这几步骤： * 1、判断是否到达要求条件 * 2、穷举所有可能走的方向 * 3、通过第2步穷举的方向然后去走，当然走之前还要过滤那些不合格的方向，比如这这个方向的下一步走过了，不能再走了，或者这个方向的下一步有墙也不能走等， * 实际的拦截条件根据题目要求添加。 */public class Main { ...

Dijkstra 说明： Dijkstra算法是一种求图的单元最短路径的算法 参考视屏：https://www.bilibili.com/video/BV1zz4y1m7Nq Java代码模板（基于链式向前星，Dijkstra算法时间复杂度O(nlogn)）： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;/** * Dijkstra模板 * @author 长白崎 * *//*6 91 5 41 6 12 4...

Java大数字运算使用技巧 说明： Java大数字使用技巧,这里只演示BigInteger了，BigDecimal高精度大数字就不演示了(用法基本一样)。 Java代码模板 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101import java.math.BigInteger;public class BigNumber { public static void main(String[] args) { } /** * 进制转换 */ public void testScale() { ...

Java日期类使用技巧 说明： Java特有的日期类的使用 Java代码模板： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112import java.time.Duration;import java.time.LocalDate;import java.time.LocalDateTime;import java.time.temporal.ChronoUnit;public class DateJudge { public static void main(String[] args) { LocalDateTime nowDateTime =...

Java正则使用技巧 说明： Java正则使用 Java代码模板： 1234567891011121314151617181920212223242526import java.util.regex.Matcher;import java.util.regex.Pattern; public class RegexMatches{ public static void main( String[] args ){ // 按指定模式在字符串查找 String line = "This order was placed for QT3000! OK?"; String pattern = "(\\D*)(\\d+)(.*)"; // 创建 Pattern 对象 Pattern r = Pattern.compile(pattern); // 现在创建 matcher 对象 Matcher m = r.matcher(line); if (m.find( )) { ...

KMP 说明： KMP算法其实主要的作用就是匹配子字符串，就比如： 父串：aabacdca 子串：acd 这里我们要查找父串中是否有子串，那么就可以用KMP算法。 而KMP算法其实有点像一个状态机，或者说一个dp？ 其主要特点还是记录转态回溯。 KMP主要难点在于其中next数组的计算。next数组的计算方式是“前缀和后缀公共部分的最大长度”。比如一个字符串ababa，他的前缀是可以是a，ab，aba，abab（不包含最后一位），后缀是a，ba，aba，baba（不包含第一位）。 Java代码模板： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455/** * @description: KMP算法 * KMP是一种字符串匹配算法，他是一种时间复杂度低，比较优秀的一种字符串匹配算法，一般可以拿来做一下字符串匹配类的题目。他与一般的暴力匹配比较其有点就是 *...