CSDN package com.zhang.reflection.面试.算法模版.图.遍历; import java.util.*; /** * 图的宽度优先遍历 * 利用队列实现，从源节点开始依次按照宽度进队列，然后弹出，每弹出一个点， * 把该节点所有没有进过队列的邻接节点放入队列，直到 * 队列为空。 */ public class bfs { //图 static class Graph{ //点集<编号，实际的点> public HashMap<Integer,Node> nodes; //边集 public HashSet<Edge> edge...

弗洛伊德算法用于无向图，还可以用于解决负权边 package com.zhang.reflection.面试.算法模版.图.最短路径; public class 弗洛伊德 { //matrix为距离的二维矩阵，n为节点的个数，节点从1开始计数 private void floyd(int[][] matrix,int n){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ matrix[j][k]=Math.min(matrix[j][k],matrix[j][i]+matrix[i][...

题解  package com.zhang.reflection.面试.算法模版.动态规划; import java.io.*; import java.util.*; /** * 描述 * 今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区Ai和Bi，路费是Ci。 * 经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V1, V2 ,V3 ... VR，那么他们的总花费为从V1到V2的花费加上V2到V3的花费依次类推，注意从铁子班上到V1...

左程云n皇后 package com.zhang.reflection.面试.算法模版.回溯模版.棋盘; import java.util.Scanner; public class 状态N皇后 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(Num(n)); } private static int Num(int n) { if(n<1||n>32){ return 0; } //整个的限制 i...

状压dp 洛谷题目 b站视频例题 dp  package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /** * 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。 * 国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 * * 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N） * 所得的方案数 * 3 2 * 16 */ public class 状压dp { public static void mai...

package com.zhang.reflection.面试.算法模版.动态规划; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 * 输入文件中仅包含一行两个整数a、b，含义如上所述。 * 输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。 */ public class 数字计数 { public static void mai...

package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /** * 长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+7取模。 * 所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。 * 例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us" */ public class 串 { private static final int MOD = 1000000007; public static void main(Strin...

数位dp  package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /** * 数位dp：数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。 * 所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！ * * */ public class 数位dp { public static void main(String[] args){ Scanner sc=new Scanner(Sy...

力扣的打家劫舍III也做一做  package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /**打家劫舍三 * * 你是一个经验丰富的小偷，经过上次在街边和湖边得手后你准备挑战一次自己，你发现了一个结构如二叉树的小区，小区内每个房间都存有一定现金，你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 * 问，给定一个二叉树结构的小区，如之前两次行动一样，你无法在不触动警报的情况下同时偷窃两个相邻的房间，在不触动警报的情况下最多的偷窃金额。 */ public class 树形dp1 { pu...

力扣相同题目：二叉树中的最大路径和也需要看一看，用递归做的  import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] node=new int[n+1]; int[] parent=new int[n+1]; int[] dp=new int[n+1]; int[] dp1=new int[n+1]; for(int i=1;i<=n;i++){ node[i]=sc...

package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /** * 小红拿到了一棵有根树。根节点为1号节点。 * 所谓树，指没有回路的无向连通图。 * 现在小红想给一部分点染成红色。之后她有 q\q 次询问，每次询问某点的子树红色节点的个数。 * * 第一行一个正整数 nn ，代表树的节点个数。 * 第二行有 n-1n−1 个正整数，分别表示第 22 个节点到第 nn 个节点每个节点的父亲。 * 接下来一个长度为 nn 的、由'W'或'R'字符组成的字符串。第 ii 个字符为'W'代表该字符没被染色，若字符为'R...

题目解析  import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i <n ; i++) { a[i] = input.nextInt(); } for (int i = 0; i <n ; i++) { b[i] =...

package com.zhang.reflection.面试.算法模版.动态规划; import java.util.Scanner; /** * 给定一个由 '[' ，']'，'('，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。 * 例如当前串是 "([[])"，那么插入一个']'即可满足。 * * ([[]) * 1 */ public class 区间dp { public static void main(String[] args){ Scanner sc=new Scanner(System.in); String s=sc.next(); i...

package com.zhang.reflection.面试.算法模版.动态规划; /** * 给你一个字符串 s，找到 s 中最长的回文子串。 * * s = "babad" * "bab" * "aba" 同样是符合题意的答案。 */ public class 最长回文子串 { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 ...