言和和和

树头结点没有父亲 其他节点只有一个父亲的有向无环图，直观理解为发散状在树上，从头结点出发到任何节点的路径是唯一的，不管是二叉树还是多叉树 树型dp是指在树上做动态规划，依赖关系比一般的动态规划简单因为绝大部分都是父依赖子 套路1 分析父树得到答案需要子树的哪些信息2 把子树信息的全集定义成递归返回值3 通过递归让子树返回全集信息4 整合子树的全集信息得到父树的全集信息并且返回 题目一 123456789101112131415161718192021222324252627282930313233343536373839404142434445// 最大BST子树// 给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小// 其中，最大指的是子树节点数最多的// 二叉搜索树（BST）中的所有节点都具备以下属性：// 左子树的值小于其父（根）节点的值// 右子树的值大于其父（根）节点的值// 注意：子树必须包含其所有后代public static int largestBSTSubtree(TreeNode root) { return f(roo...

狭义的贪心每一步做出在当前状态下的最好或者最优的选择，从而希望最终的结果是最好或者最优的算法 题目一 123456789101112131415161718192021// 最大数// 给定一组非负整数nums// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数// 测试链接 : https://leetcode.cn/problems/largest-number/public static String largestNumber(int[] nums) { int n = nums.length; String[] strs = new String[n]; for (int i = 0; i < n; i++) { strs[i] = String.valueOf(nums[i]); } Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b)); if (strs[0].equals("0")) { return &q...

可能性展开的常见方式1 基于两侧端点讨论的可能性展开2 基于范围上划分点的可能性展开 题目一 12345678910111213141516171819202122232425262728class Solution {package class076;// 让字符串成为回文串的最少插入次数// 给你一个字符串 s// 每一次操作你都可以在字符串的任意位置插入任意字符// 请你返回让s成为回文串的最少操作次数// 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/// 严格位置依赖的动态规划 public static int minInsertions(String str) { char[] s = str.toCharArray(); int n = s.length; int[][] dp = new int[n][n]; for (int l = 0; l < n - 1; l++) { dp[l]...

题目一 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071package class075;// 多重背包不进行枚举优化// 宝物筛选// 一共有n种货物, 背包容量为t// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值// 测试链接 : https://www.luogu.com.cn/problem/P1776// 请同学们务必参考如下代码中关于输入、输出的处理// 这是输入输出处理效率很高的写法// 提交以下的code，提交时请把类名改成"Main"，可以直接通过import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ja...

题目一// 分组背包(模版)// 给定一个正数m表示背包的容量，有n个货物可供挑选// 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)// 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量// 怎么挑选货物能达到价值最大，返回最大的价值// 测试链接 : https://www.luogu.com.cn/problem/P1757// 请同学们务必参考如下代码中关于输入、输出的处理// 这是输入输出处理效率很高的写法// 提交以下的所有代码，并把主类名改成”Main”，可以直接通过 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273public c...

01背包:每个背包要与不要两种可能性展开有依赖的背包:多个物品变成一个复合物品(互斥)，每件复合物品要和怎么要多种可能性展开不能用01背包来解，但是非常重要的问题：非负数组前k个最小的子序列和问题 题目一 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Main { public static int MAXM = 101; public static int MAXT = 1001; public static int[] cost = new int[MAXM]; public static int[] val = new int[MAXM]; public static int[] dp = new int[MAXT]; public static int t, n; public static void main(String[] args) throws IOException { BufferedRea...

题目一 要掌握优化nlogn 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162package class072;// 最长递增子序列和最长不下降子序列// 给定一个整数数组nums// 找到其中最长严格递增子序列长度、最长不下降子序列长度// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/public class Code01_LongestIncreasingSubsequence { // 最优解 // 时间复杂度O(n * logn) public static int lengthOfLIS2(int[] nums) { int n = nums.length; int[] ends = new int[n]; // len表示ends数组目前的有效区长度 // ends[0.....

题目一 1234567891011121314151617181920212223242526package class071;// 乘积最大子数组// 给你一个整数数组 nums// 请你找出数组中乘积最大的非空连续子数组// 并返回该子数组所对应的乘积// 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/public class Code01_MaximumProductSubarray { // 这节课讲完之后，测试数据又增加了 // 用int类型的变量会让中间结果溢出 // 所以改成用double类型的变量 // 思路是不变的 public static int maxProduct(int[] nums) { double ans = nums[0], min = nums[0], max = nums[0], curmin, curmax; for (int i = 1; i < nums.length; i++) { curmin = Math.mi...

题目一 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667package class070;// 子数组最大累加和// 给你一个整数数组 nums// 返回非空子数组的最大累加和// 测试链接 : https://leetcode.cn/problems/maximum-subarray/public class Code01_MaximumSubarray { // 动态规划 public static int maxSubArray1(int[] nums) { int n = nums.length; // dp[i] : 子数组必须以i位置的数做结尾，往左能延伸出来的最大累加和 int[] dp = new int[n]; dp[0] = nums[0]; int ans = nums[0]; for (int i = 1; i < n;...

尝试函数有3个可变参数可以完全决定返回值题目一 1234567891011121314151617181920212223242526272829303132333435363738394041424344package class069;// 一和零(多维费用背包)// 给你一个二进制字符串数组 strs 和两个整数 m 和 n// 请你找出并返回 strs 的最大子集的长度// 该子集中 最多 有 m 个 0 和 n 个 1// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集// 测试链接 : https://leetcode.cn/problems/ones-and-zeroes/class Solution { public static int zeros, ones; // 统计一个字符串中0的1的数量 // 0的数量赋值给全局变量zeros // 1的数量赋值给全局变量ones public static void zerosAndOnes(String str) { zeros = 0; ones = 0; f...