没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构与算法3.0:500+题目详解及Java代码PDF
数据结构与算法3.0:500+题目详解及Java代码PDF
需积分: 10 3 下载量 96 浏览量
更新于2024-07-14
收藏 90.44MB PDF 举报
"数据结构和算法3.0"是一本包含五百多道算法题目及其详解和详细代码的PDF资料,由博哥编撰,他在微信公众号“数据结构和算法”上长期分享算法题,旨在帮助读者提高编程技能。这本书的主题聚焦在数据结构,特别是与算法相关的挑战,例如如何解决“俄罗斯套娃信封”问题。 在“俄罗斯套娃信封”问题中,给定一个二维整数数组envelopes,每个元素envelopes[i]=[wi, hi]代表一个信封的宽度和高度。目标是确定在不旋转信封的前提下,能够形成多少组“套娃”组合,即一个信封能被另一个更大的信封装入。这个问题考察的是空间占用和大小比较的算法设计,涉及到贪心策略或动态规划的思想,因为我们需要找到最大的信封集合,使得每一个信封都能嵌套在其后者的范围内。 示例1中的输入表明,四个信封分别是[5,4]、[6,4]、[6,7]和[2,3],通过组合,可以形成[2,3]放入[5,4],然后[5,4]放入[6,7],一共三组套娃。而示例2给出了一个简单的案例,三个相同大小的信封只能组成一组套娃。 博哥强调,这份文档包含了丰富的代码示例,方便读者学习和实践。他计划持续在公众号上发布更多算法题,并鼓励读者通过回复“pdf”获取最新版本。此外,由于早期的代码是截图形式,不便复制,后来改为可复制的格式,并考虑提供其他编程语言的代码转换指南,以便读者根据需求调整。 这是一份实用的资源,适合对数据结构和算法感兴趣的开发者,无论是初学者还是进阶者,都可以从中受益。通过解决这些题目,读者不仅能提升算法技巧,还能锻炼问题解决和代码实现能力。同时,博哥的热情分享和持续更新也体现了对知识传播的重视。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/16359181/bg11.jpg)
493,动态规划解打家劫舍 III
收录于话题
#算法图文分析
111个
The world is a book, and those who do not travel read
only a page.
世界是一本书,不旅行的人只读了其中的一页。
问题描述
在 上 次 打 劫 完 一 条 街 道 之 后 和 一 圈 房 屋 后 , 小 偷 又 发 现 了 一 个 新 的 可 行 窃 的 地 区 。 这 个
地 区 只 有 一 个 入 口 , 我 们 称 之 为 “ 根 ” 。 除 了 “ 根 ” 之 外 , 每 栋 房 子 有 且 只 有 一 个 “ 父 “ 房 子
与 之 相 连。 一 番侦 察 之后 , 聪明 的 小偷 意 识到 “ 这个 地 方的 所 有 房 屋 的 排 列 类 似 于 一 棵 二
叉树 ”。 如果 两个 直接 相连 的房 子在 同一 天晚 上被 打劫 ,房 屋将 自动 报警 。
计算 在不 触动 警报 的情 况下 ,小 偷一 晚能 够盗 取的 最高 金额 。
示例 1 :
1
2
3
4
输入: [3,2,3,null,3,null,1]
3
/ \
原创
山大王wld 2020-12-18数据结构和算法
![](https://csdnimg.cn/release/download_crawler_static/16359181/bg12.jpg)
示 例 2 :
动态规划解决
前 面 我 们 刚 讲 过 4 84 , 打 家劫 舍 II和 47 9 , 递 归 方 式 解 打 家 劫 舍 , 今 天 这 题 和 之 前 讲 的
这 两 道 题 完 全 不 同 , 因 为 前 面 两 题 所 偷 窃 的 房 屋 都 是 数 组 , 而 这 题 是 一 个 二 叉 树 。 但 这
道题 也可 以使 用动 态规 划来 解决 。
对于 二叉 树的 每一 个节 点都 有两 种状 态, 一种 是偷 ,一 种是 不偷 。我 们定 义一 个长 度为 2
的 数 组 d p , 其 中 d p[ 0] 表 示 不 偷当 前 这 个 节 点 所 能 偷 窃 的 最 高 金 额 , dp [1 ] 表 示 偷 当 前
节点 所能 偷窃 的最 高金 额。
我们 就从 根节 点开 遍历 这棵 二叉 树。
如果 偷根 节点 ,那 么就 不能 偷根 节点 的两 个子 节点 ,所 以
dp[1]=root.val+left.dp[0]+right.dp[0];
这里 的伪 代码 le ft .d p[ 0] 表示 的是 不能 偷当 前节 点的 左子 节点
如果 不偷 根节 点, 那么 我们 可以 偷子 节点 也可 以不 偷子 节点 ,我 们取 最大 值即 可, 所以
dp[0]=max(left.dp[0],left.dp[1])+max(right.dp[0],right.dp[1]);
5
6
7
8
9
10
2 3
\ \
3 1
输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
1
2
3
4
5
6
7
8
9
10
输入: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
![](https://csdnimg.cn/release/download_crawler_static/16359181/bg13.jpg)
那么 边界 条件 是什 么呢 ,就 是节 点为 空的 时候 ,直 接返 回0 即可 。
有了 递推 公式 和边 界条 件, 我们 来看 下最 终代 码
1 public int rob(TreeNode root) {
2 int[] robHelp = robHelper(root);
3 //取偷根节点和不偷根节点的最大值
4 return Math.max(robHelp[1], robHelp[0]);
5 }
6
7 public int[] robHelper(TreeNode root) {
8 //边界条件
9 if (root == null)
10 return new int[2];
11 //这里的left是个长度为2的一维数组,其中left[0]表示不偷root.left节点
12 //所能偷窃的最大金额,left[1]表示偷root.left节点所能偷窃的最大金额。
13 int[] left = robHelper(root.left);
14 //right节点同left
15 int[] right = robHelper(root.right);
16 //Math.max(right[0], right[1]), root.val + left[0] + right[0]表示
17 //的是不能偷当前节点,所以可以偷两个子节点,也可以不偷子节点,我们取最大的。
18 //root.val + left[1] + right[1]表示的是偷当前节点,所以不能偷两个子节点。
19 return new int[]{Math.max(left[0], left[1]) +
20 Math.max(right[0], right[1]), root.val + left[0] + right[0]};
21 }
总结
如 果 对 二 叉 树 的 遍 历 方 式 比 较 熟 悉 的 话 , 上 面 代 码 一 看 就 知 道 , 他 和 二 叉 树 的 后 续 遍 历
非 常 相 似 , 是 完 全 从 下 到 上 的 一 种 遍 历 方 式 , 每 一 个 节 点 都 记 录 了 两 种 状 态 , 一 种 是
偷 , 一 种 是 不 偷 。 每 次 从 下 往 上 走 的 时 候 这 两 种 状 态 都 会 记 录 下 来 …… 一 直 到 根 节 点 ,
最后 我们 只需 要返 回偷 根节 点和 不偷 根节 点的 最大 值即 可。
●465. 递归和动 态规 划解 三角 形最小路径和
●470,DFS和B FS 解合 并二 叉树
●455,DFS和B FS 解被 围绕 的区域
●445,BFS和D FS 两种 方式 解岛屿数量
![](https://csdnimg.cn/release/download_crawler_static/16359181/bg14.jpg)
492,动态规划和贪心算法解买卖股票的最佳时机 II
收录于话题
#算法图文分析
111个
The world is a fine place and worth fighting for.
这世界是值得为之奋斗的好地方。
问题 描述
给定 一个 数组 ,它 的第 i个 元素 是一 支给 定股 票第 i天 的价 格。
设 计 一 个 算 法 来 计 算 你 所 能 获 取 的 最 大 利 润 。 你 可 以 尽 可 能 地 完成 更 多 的交 易 ( 多 次 买
卖一 支股 票) 。
注 意 :你 不能 同时 参与 多笔 交易 (你 必须 在再 次购 买前 出售 掉之 前的 股票 )。
示 例 1 :
输 入 : [ 7 , 1 , 5 , 3 , 6 , 4 ]
输 出 : 7
解 释 : 在 第 2 天 ( 股 票 价 格 = 1 ) 的 时 候 买 入 , 在 第 3 天 ( 股 票 价 格 = 5 ) 的 时 候 卖
出 , 这 笔 交 易 所 能 获 得 利 润 = 5 - 1 = 4 。
随 后 , 在 第 4 天 ( 股 票 价 格 = 3 ) 的 时 候 买 入 , 在 第 5 天 ( 股 票 价 格 = 6 ) 的 时
候 卖 出 , 这 笔 交 易 所 能 获 得 利 润 = 6 - 3 = 3 。
原创
山大王wld 2020-12-16数据结构和算法
剩余937页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/bad7e4024bd245688e1abc576d331ee0_qq_37774399.jpg!1)
与或
- 粉丝: 23
- 资源: 8
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)