class062宽度优先遍历及其扩展【算法】 算法讲解062【必备】宽度优先遍历及其扩展 code11162.地图分析 //地图分析//你现在手里有一份大小为nxn的网格grid//上面的每个单元格都用0和1标记好了其中0代表海洋，1代表陆地。//请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的//并返回该距离。如果网格上只有陆地或者海洋，请返回-1。//我们这里说的距离是「曼哈顿距离」（ManhattanDistance）：//(x0,y0)和(x1,y1)这两个单元格之间的距离是|x0x1|+|y0y1|。//测试链接:https://leetcod...

class078树型dp-上【算法】 算法讲解078【必备】树型dp-上 code1333.最大BST子树 //最大BST子树//给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树的大小//其中，最大指的是子树节点数最多的//二叉搜索树（BST）中的所有节点都具备以下属性：//左子树的值小于其父（根）节点的值//右子树的值大于其父（根）节点的值//注意：子树必须包含其所有后代//测试链接:https://leetcode.cn/problems/largest-bst-subtree/ 树形dp：x头整树的maxBstSize不含x：max(左树maxBstSize,右...

class072最长递增子序列问题与扩展【算法】 code1300.最长递增子序列 //最长递增子序列和最长不下降子序列//给定一个整数数组nums//找到其中最长严格递增子序列长度、最长不下降子序列长度//测试链接:https://leetcode.cn/problems/longest-increasing-subsequence/ dp[i]：以i位置作结尾的最长递增子序列长度返回Max(dp[…]) 优化ends[i]：目前所有长度为i+1的递增子序列的最小结尾返回len code1动态规划code2优化 packageclass072; //最长递增子序列和最长不下降子序...

class074背包dp-分组背包、完全背包【算法】 算法讲解074【必备】背包dp-分组背包、完全背包 code1P1757通天之分组背包 //分组背包(模版)//给定一个正数m表示背包的容量，有n个货物可供挑选//每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组)//同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量//怎么挑选货物能达到价值最大，返回最大的价值//测试链接:https://www.luogu.com.cn/problem/P1757//请同学们务必参考如下代码中关于输入、输出的处理//这是输入输出处理效率很高的写法//提交以下的所有代码，...

class071子数组最大累加和问题与扩展-下【算法】 code1152.乘积最大子数组 //乘积最大子数组//给你一个整数数组nums//请你找出数组中乘积最大的非空连续子数组//并返回该子数组所对应的乘积//测试链接:https://leetcode.cn/problems/maximum-product-subarray/ 因为有负数，并且有负负得正 dp[i]：[0…i]子数组最大成绩 nums[i] nums[i]x最大[i-1] nums[i]x最小[i-1] packageclass071; //乘积最大子数组 //给你一个整数数组nums //请你找出数组中乘积最大...

class006二分搜索【算法】 算法讲解006【入门】二分搜索 code1有序数组中是否存在一个数字 //有序数组中是否存在一个数字 packageclass006; importjava.util.Arrays; //有序数组中是否存在一个数字 publicclassCode01_FindNumber{ //为了验证 publicstaticvoidmain(String[]args){ intN=100; intV=1000; inttestTime=500000; System.out.println("测试开始"); for(inti=0;i&...

class067二维动态规划 code164.最小路径和 //最小路径和//给定一个包含非负整数的mxn网格grid//请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。//说明：每次只能向下或者向右移动一步。//测试链接:https://leetcode.cn/problems/minimum-path-sum/ dp[i][j]：从(0,0)到(i,j)最小路径和dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j] 第0行：dp[0][j-1]+grid[0][j]第0列：dp[i-1][0]+grid[i-1][0] co...

class066一维动态规划 算法讲解066【必备】从递归入手一维动态规划 code1509斐波那契数列 //斐波那契数//斐波那契数（通常用F(n)表示）形成的序列称为斐波那契数列//该数列由0和1开始，后面的每一项数字都是前面两项数字的和。//也就是：F(0)=0，F(1)=1//F(n)=F(n1)+F(n2)，其中n>1//给定n，请计算F(n)//测试链接:https://leetcode.cn/problems/fibonacci-number///注意：最优解来自矩阵快速幂，时间复杂度可以做到O(logn)//后续课程一定会讲述！本节课不涉及！ dp[i]：从...

class061最小生成树【算法】 2023-12-811:48:12 算法讲解061【必备】最小生成树 code1P3366【模板】最小生成树 //Kruskal算法模版（洛谷）//静态空间实现//测试链接:https://www.luogu.com.cn/problem/P3366//请同学们务必参考如下代码中关于输入、输出的处理//这是输入输出处理效率很高的写法//提交以下所有代码，把主类名改成Main，可以直接通过 packageclass061; //Kruskal算法模版（洛谷） //静态空间实现 //测试链接:https://www.luogu.com.cn/...

class051二分答案法与相关题目【算法】 算法讲解051【必备】二分答案法与相关题目 code1875.爱吃香蕉的珂珂 //爱吃香蕉的珂珂//珂珂喜欢吃香蕉。这里有n堆香蕉，第i堆中有piles[i]根香蕉//警卫已经离开了，将在h小时后回来。//珂珂可以决定她吃香蕉的速度k（单位：根/小时)//每个小时，她将会选择一堆香蕉，从中吃掉k根//如果这堆香蕉少于k根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉//珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。//返回她可以在h小时内吃掉所有香蕉的最小速度k（k为整数）//测试链接:https://leetcode.cn/...

class035数据结构设计高频题【算法】 算法讲解035【必备】数据结构设计高频题 code1设计有setAll功能的哈希表 //setAll功能的哈希表//测试链接:https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967//请同学们务必参考如下代码中关于输入、输出的处理//这是输入输出处理效率很高的写法//提交以下的code，提交时请把类名改成"Main"，可以直接通过 思路：带时间戳 packageclass035; //setAll功能的哈希表 //测试链接:https://www.nowcode...

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

class077区间dp-下【算法】 算法讲解077【必备】区间dp-下 code1括号区间匹配 //完成配对需要的最少字符数量//给定一个由’[‘、’]‘、’(‘，’)‘组成的字符串//请问最少插入多少个括号就能使这个字符串的所有括号正确配对//例如当前串是“([[])”，那么插入一个’]'即可满足//输出最少需要插入多少个字符//测试链接:https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b//请同学们务必参考如下代码中关于输入、输出的处理//这是输入输出处理效率很高的写法//提交以下的code，提交时请把...

class079树型dp-下【算法】 算法讲解079【必备】树型dp-下 code12477.到达首都的最少油耗 //到达首都的最少油耗//给你一棵n个节点的树（一个无向、连通、无环图）//每个节点表示一个城市，编号从0到n1，且恰好有n1条路//0是首都。给你一个二维整数数组roads//其中roads[i]=[ai,bi]，表示城市ai和bi之间有一条双向路//每个城市里有一个代表，他们都要去首都参加一个会议//每座城市里有一辆车。给你一个整数seats表示每辆车里面座位的数目//城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车//相邻城市之间一辆车的油耗是一升汽油//请你返...

class083动态规划中用观察优化枚举的技巧-下【算法】 算法讲解083【必备】动态规划中用观察优化枚举的技巧-下 code11235.规划兼职工作 //规划兼职工作//你打算利用空闲时间来做兼职工作赚些零花钱，这里有n份兼职工作//每份工作预计从startTime[i]开始、endTime[i]结束，报酬为profit[i]//返回可以获得的最大报酬//注意，时间上出现重叠的2份工作不能同时进行//如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作//测试链接:https://leetcode.cn/problems/maximum-profit-in-job-s...

class082动态规划中用观察优化枚举的技巧-上【算法】 算法讲解082【必备】动态规划中用观察优化枚举的技巧-上 code1121.买卖股票的最佳时机 //买卖股票的最佳时机//给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格//你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票//设计一个算法来计算你所能获取的最大利润//返回你可以从这笔交易中获取的最大利润//如果你不能获取任何利润，返回0//测试链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock...

class081状压dp-下【算法】 算法讲解081【必备】状压dp-下 Code11434.每个人戴不同帽子的方案数 //每个人戴不同帽子的方案数//总共有n个人和40种不同的帽子，帽子编号从1到40//给你一个整数列表的列表hats，其中hats[i]是第i个人所有喜欢帽子的列表//请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数//由于答案可能很大，请返回它对10^9+7取余后的结果//测试链接:https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-othe...

class073背包dp-01背包、有依赖的背包【算法】 算法讲解073【必备】背包dp-01背包、有依赖的背包 code1P1048[NOIP2005普及组]采药 //01背包(模版)//给定一个正数t，表示背包的容量//有m个货物，每个货物可以选择一次//每个货物有自己的体积costs[i]和价值values[i]//返回在不超过总容量的情况下，怎么挑选货物能达到价值最大//返回最大的价值//测试链接:https://www.luogu.com.cn/problem/P1048//请同学们务必参考如下代码中关于输入、输出的处理//这是输入输出处理效率很高的写法//提交以下的所有代码，并...

class070子数组最大累加和问题与扩展-上【算法】 code153.最大子数组和 //累加和最大子数组和//给你一个整数数组nums//请你找出一个具有最大累加和的非空子数组//返回其最大累加和//测试链接:https://leetcode.cn/problems/maximum-subarray/ dp[i]：以i结尾的子数组[…i]的最大累加和(1)nums[i](2)dp[i-1]+nums[i]二者取最大的返回Max(dp[…]) code1动态规划code2空间压缩 packageclass070; //子数组最大累加和 //给你一个整数数组nums //返回非空子数组的...

class068更多的动态规划【算法】 算法讲解068【必备】见识更多二维动态规划题目 code1115.不同的子序列 //不同的子序列//给你两个字符串s和t，统计并返回在s的子序列中t出现的个数//测试链接:https://leetcode.cn/problems/distinct-subsequences/ dp[i][j]：s[前i个]子序列能够出现t[前j个]的个数=dp[i-1][j]+=dp[i-1][j-1],s[i-1]t[j-1] 第0行，0第0列，1 code1动态规划code2空间压缩 packageclass068; //不同的子序列 //给你两个字符串s和t...