二叉树的最小深度  注意只有左子树（或者右子树）的情况就可以了，这时候就要单独递归该子树，切忌不要无脑递归两边。  具体代码： import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int run (TreeNode root) { return thi...

0子串 本题特点：基础解法并不难，但是对性能要求高。具体思路：  用总的子串数 - 0子串数，就是‘区间内全部连续子串的“自审值”之和’。 而0子串数可以使用前缀和的思路来快速计算出区间内的0子串数。 但是如果区间是以0开头的，则pre[j] - pre[i-1]的值中就会多包涵一些从i的左边开头在[i,j]区间内（包扩两个边界值）结尾的0子串，要减去这一部分。  具体代码如下： import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exce...

二维的01背包问题（附加组合背包）  按照一维背包（基础背包）的思路解题即可。 设dp[i][j][k]表示前i个物品（包括i）、在j的cost下、在k的人数限制下的最大战力。这个时候，需要特殊处理i=0的情况。 还有一种写法就是：dp[i][j][k]表示前i个物品（不包括i）、在j的cost下、在k的人数限制下的最大战力。i维度要+1，而且dp遍历的时候，i也从1开始。带来的一个情况就是在找最大值的时候，不能单纯的从i和j的最大值开始找（遍历k），而是连j也要遍历去找。仿佛是要把两个维度的空间都搜索一遍似的。 无论那种写法，都要注意排除前驱黑洞的情况。这种情况是不能迭代的。  具体的代码如...

迎面痛击较难的题目之第一题。  第一题竟然如此友好，一个简单的分桶排序即可；  代码如下： import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); boolean[] data = new boolean[500]; for(int i = 0; i < n; i++) { dat...

煞费苦心的牛客，杜撰了一个“画展的不和谐度”。化简之后，你就会说，这么简单的滑动窗口定义。 具体代码： import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int M = in.nextInt(); long[] data = new long[N]; for (int i = 0; i &lt...

经典双指针题目~ 熟悉的配方——  主线是右指针不断地去探索最大的符合条件的区间。 在探索的过程中，如果不满足区间条件，就右移左指针，直到[i,j]区间符合条件为止。这时候计算区间长度。  具体代码如下： import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(...

这个题目归类为双指针，才有点名副其实~ 解题思路如下：  主线是右指针不断地去探索最大的符合条件的区间。 在探索的过程中，如果不满足区间条件，就右移左指针，直到[i,j]区间符合条件为止。这时候计算区间长度。 细节和特点：  可以用map来记录元素值出现的位置，并在右指针右移的时候用了检查新区间是否引入了重复值。不过具体代码中没用map，而是使用了数组来实现位置记录功能。 新区间的长度大于max就新开辟一个list来记录区间长度；等于max就追加区间长度；否则就舍弃该“短”区间。    具体代码： import java.util.*; public class Main { public s...

哪来的双指针？  我实在想不出来双指针的解法. 还是用了单调递减队列来做的。 具体代码如下：  import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] firstLine = in.nextLine().split(" "); int n = Integer.parseInt(firstLine[0]);...

有限的超能力  我发现牛客上有些题目就喜欢这种在基础考点之上再加上一点点。比如这个题目就是bfs之外，加上一条激光。 思路解析：  先从end点出发，用bfs去遍历完所有可达空间，并记录可达空间的所有行和列，比如endI、endJ。 再从start出发，同样用bfs去遍历所有可达空间，如果这些可达空间属于endI和endJ，那么就是可以通的。 这里并没有真的模拟激光去打通一行或者一列。    具体代码如下： import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static vo...

思路非常清晰的一个dfs题目，但是要注意dfs的遍历方式。dfs的时候不要每次都从头开始，而是要想遍历一行数组一样不回头；也就是dfs当前层要基于上一层进行顺序遍历，而不是继续从头(0，0)节点重新遍历。 首先说明，以上两种方法都能得到正确的值，区别在于“从头遍历”的方法会超时。 为什么效果一样呢？因为“从头遍历法”中存在很多重复的。比如浅层dfs到深层dfs这种case会在深层dfs时由于“从头遍历”而再次遇到浅层dfs中访问过的点。 具体的“层层递进的dfs法”写法如下：  import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package x...

看标签是dfs，在核对n最多只有15，所以确定可以使用dfs。 在实现遍历所有的子序列时，只需要注意一点，那就是最外面的这一层不要漏掉。 具体代码如下：  import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); long m = in.nextLong(); long[] data = ...

根据FST的定义，知其等价于求“曼哈顿距离最值”。 套用公式：    一次遍历求出maxP、minP、maxQ、minQ，最后求最值即可。具体代码如下：  import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] data = new int[n]; for (int i = ...

这个题目虽然标题是并查集，但是真的用并查集的话，会超时；因为数据太多了。需要用特定的思路去优化，比如不用数组的形式表是group，不维护group而只计数。下面的算法的特点就是用一个long来表示一个group（天然编号）只维护组内的成员个数，而不维护具体是哪些成员（这一点就很不想并查集中的parent数组） import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(...

好一道双指针问题，以后遇到双指针必做。01子序列，这个概念稍显特殊，要想求解，请先熟悉它的统计方式。具体算法如下： import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] firstLine = in.nextLine().split(" "); long n = Long.parseLong...