党的二十大报告中指出: 教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力,深入实施科教兴国战略、人才强国战略、创新驱动发展战略,这三大战略共同服务于创新型国家的建设。高等教育与经济社会发展紧密相连,对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。
本书是《算法设计与分析》(第3版·微课视频·题库版)(李春葆等,清华大学出版社)的配套在线编程实验指导书。
全书分为10章,第1章是绪论,第2章是递归算法设计技术,第3~8章分别是穷举法、分治法、回溯法、分支限界法、动态规划和贪心法等算法设计策略,第9章和第10章分别是图算法和计算几何,与《教程》的前10章相对应。每章包含《教程》中的在线编程实验题及其解析,共计186道,其中来自LeetCode(力扣)55道,LintCode(领扣)71道,POJ(北大)52道,HDU(杭电)8道。LeetCode和LintCode是极好的在线编程训练、学习和交流平台,POJ和HDU是国内最优秀的ACM训练平台。LeetCode和LintCode题目用1~3星标记难易程度,分别为简单、中等和困难。
书中精心选取的在线编程题不仅涵盖算法设计与分析课程的主要知识点,还融合了各个知识点的运用和扩展,学习、理解和借鉴这些解题思路是掌握和提高算法设计能力的最佳途径。
以在线编程平台为实验环境具有明显的优势: 一是克服了单机编程测试数据不完整的缺陷,通常在线编程平台中测试数据较多而且具有针对性,更方便检测程序的正确性; 二是便于考查程序的时间和空间性能,通常在线编程平台在提交成功时都会给出程序的执行时间和消耗的内存空间大小,以便改进算法; 三是在线编程平台题目众多、资源丰富,可以选择一些有趣且难度适中的题目供学生实验,引导学生进入一片新的学习天地,激发学生的编程兴趣。
书中全部在线编程题均在相关在线编程平台中调试通过(选择的语言为C )。考虑向下的兼容性,所有程序调试运行采用较低版本的Dev C 5.11作为编程环境,稍加修改可以在其他C 环境中运行。
源码下载方法: 扫描封底的文泉云盘防盗码,再扫描目录上方的二维码下载。
在此感谢LeetCode、LintCode、POJ和HDU平台的大力支持。由于编者水平所限,尽管不遗余力,仍可能存在不足之处,敬请教师和同学们批评指正。
编者2024年1月
源码下载
第1章绪论/
1.1LintCode1200相对排名★/
1.2LintCode1901有序数组的平方★/
1.3LintCode211字符串置换★/
1.4LintCode772错位词分组★★/
1.5LintCode55比较字符串★/
1.6LintCode460在排序数组中找最接近的k个数★★/
1.7LintCode424求逆波兰表达式的值★★/
1.8LintCode1369最频繁单词★/
1.9LeetCode20有效的括号★/
1.10LeetCode1190反转每对括号间的子串★★/
1.11LeetCode496下一个更大元素Ⅰ★/
1.12LeetCode217存在重复元素★/
1.13LeetCode3无重复字符的最长子串★★/
1.14POJ3664选举时间/
1.15POJ2833平均数/
1.16POJ2491寻宝游戏/
第2章递归算法设计技术/
2.1LintCode452删除链表中的元素★/
2.2LintCode217无序链表中重复项的删除★/
2.3LintCode221链表求和Ⅱ★★/
2.4LintCode1181二叉树的直径★/
2.5LintCode1137从二叉树构建字符串★/
2.6LintCode649二叉树的翻转★★/
2.7LintCode424求逆波兰表达式的值★★/
2.8LeetCode50Pow(x,n)★★/
2.9LeetCode2312的幂★/
2.10LeetCode44通配符的匹配★★★/
2.11LeetCode1190反转每对括号间的
子串★★/
2.12LeetCode59螺旋矩阵Ⅱ★★/
2.13LeetCode1106解析布尔表达式★★★/
2.14POJ1664放苹果/
2.15POJ1747表达式/
2.16POJ1941Sierpinski分形/
2.17POJ3752字母旋转游戏/
第3章穷举法/
3.1LintCode1068寻找数组的中心索引★/
3.2LintCode1517最大子数组★/
3.3LintCode1338停车困境★/
3.4LintCode993数组划分Ⅰ★/
3.5LintCode406和大于s的最小子数组★★/
3.6LintCode1331英语软件★/
3.7LintCode397最长上升连续子序列★/
3.8LeetCode1534统计好三元组★/
3.9LeetCode204计数质数★★/
3.10LeetCode187重复的DNA序列★★/
3.11LeetCode2018判断单词是否能放入
填字游戏内★★/
3.12LeetCode2151基于陈述统计最多
好人数★★★/
3.13POJ2000金币/
3.14POJ1013假币问题/
3.15POJ1256字谜/
3.16POJ3187倒数和/
第4章分治法/
4.1LintCode1376等价字符串★★/
4.2LintCode31数组的划分★★/
4.3LintCode143颜色的分类Ⅱ★★/
4.4LintCode628最大子树★/
4.5LintCode900二叉搜索树中最接近的值★/
4.6LintCode931k个有序数组的中位数★★★/
4.7LintCode1817分享巧克力★★★/
4.8LintCode1753写作业★★/
4.9LintCode460在排序数组中找最接近的k个数★★/
4.10LintCode75寻找峰值★★/
4.11LeetCode912排序数组★★/
4.12LeetCode241为运算表达式设计优先级★★/
4.13LeetCode4寻找两个正序数组的中位数★★★/
4.14LeetCode148排序链表★★/
4.15LeetCode493翻转对★★★/
4.16LeetCode1985找出数组中第k大的整数★★/
4.17POJ2299UltraQuickSort/
4.18POJ2623中位数/
4.19POJ3104烘干/
4.20POJ3273每月花费/
第5章回溯法/
5.1LintCode1353根结点到叶子结点求和★★/
5.2LintCode802数独★★★/
5.3LintCode135数字组合★★/
5.4LintCode1915举重★★★/
5.5LintCode680分割字符串★★/
5.6LintCode136分割回文串★★/
5.7LintCode816旅行商问题★★★/
5.8LeetCode784字母大小写全排列★★/
5.9LeetCode1079活字印刷★★/
5.10LeetCode93复原IP地址★★/
5.11LeetCode22括号的生成★★/
5.12LeetCode89格雷编码★★/
5.13LeetCode301删除无效的括号★★★/
5.14POJ3050跳房子/
5.15POJ1724道路/
5.16POJ1699最佳序列/
5.17POJ1564求和/
5.18POJ2245组合/
5.19POJ1321棋盘问题/
5.20POJ2488骑士之旅/
第6章分支限界法/
6.1LintCode1376通知所有员工所需
的时间★★/
6.2LintCode1504获取所有钥匙的
最短路径★★★/
6.3LintCode1685迷宫Ⅳ★★/
6.4LintCode1428钥匙和房间★★/
6.5LintCode531六度问题★★/
6.6LintCode120单词接龙★★★/
6.7LintCode1888矩阵中的最短路径★★/
6.8LintCode803建筑物之间的
最短距离★★★/
6.9LeetCode1020飞地的数量★★/
6.10LeetCode752打开转盘锁★★/
6.11LeetCode773滑动谜题★★★/
6.12POJ1724道路/
6.13POJ2449第K条最短路径长度/
6.14POJ1376机器人/
第7章动态规划/
7.1LintCode41最大子数组★/
7.2LintCode110最小路径和★/
7.3LintCode118不同的子序列★★/
7.4LintCode1147工作安排★★/
7.5LintCode553炸弹袭击★★/
7.6LintCode107单词拆分Ⅰ★★/
7.7LintCode436最大正方形★★/
7.8LintCode394硬币排成线★★/
7.9LintCode125背包问题Ⅱ★★/
7.10LintCode440背包问题Ⅲ★★/
7.11LintCode563背包问题Ⅴ★★/
7.12LintCode669换硬币★★/
7.13LintCode94二叉树中的最大路径和★★/
7.14LintCode1306旅行计划Ⅱ★★★/
7.15LeetCode121买卖股票的最佳时机★/
7.16LeetCode122买卖股票的最佳时机Ⅱ★★/
7.17LeetCode123买卖股票的最佳时机Ⅲ★★★/
7.18LeetCode188买卖股票的最佳时机Ⅳ★★★/
7.19LeetCode309买卖股票的最佳时机(含冷冻期)★★/
7.20LeetCode714买卖股票的最佳时机(含手续费)★★/
7.21LeetCode91解码方法★★/
7.22LeetCode650只有两个键的键盘★★/
7.23LeetCode44通配符的匹配★★★/
7.24LeetCode10正则表达式的匹配★★★/
7.25LeetCode5最长回文子串★★/
7.26LeetCode516最长回文子序列★★/
7.27POJ2533最长递增子序列/
7.28POJ1458公共子序列/
7.29POJ1837平衡/
7.30POJ3624手链/
7.31POJ1276取款机/
7.32POJ1947重建道路/
7.33POJ2904邮箱制造商问题/
第8章贪心法/
8.1LintCode920会议室★/
8.2LintCode919会议室Ⅱ★★/
8.3LintCode184最大数★★/
8.4LintCode187加油站★★/
8.5LintCode304最大乘积★★/
8.6LintCode358树木规划★/
8.7LintCode719计算最大值★★/
8.8LintCode761最小子集★★/
8.9LintCode891有效回文Ⅱ★★/
8.10LeetCode122买卖股票的最佳时机Ⅱ★★/
8.11LeetCode11盛水最多的容器★★/
8.12LeetCode881救生艇★★/
8.13LeetCode1029两地调度★★/
8.14LeetCode402移掉k位数字★★/
8.15LeetCode763划分字母区间★★/
8.16LeetCode630课程表Ⅲ★★★/
8.17LeetCode1353最多可以参加的会议数目★★/
8.18POJ2782装箱/
8.19POJ3069标记/
8.20POJ1017产品包装/
8.21POJ1862Stripies/
8.22POJ3262保护花朵/
8.23POJ2970懒惰的程序员/
8.24POJ1065加工木棍/
第9章图算法/
9.1LintCode1565飞行棋Ⅰ★★/
9.2LeetCode1368至少有一条有效路径的
最小代价★★★/
9.3POJ1751高速公路问题/
9.4POJ1287网络/
9.5POJ1251维护村庄之路/
9.6POJ2349北极网络/
9.7POJ2387贝西回家/
9.8POJ1125股票经纪人的小道消息/
9.9POJ1724道路/
9.10POJ1087插头/
9.11HDU1535最小总费用/
9.12HDU1874畅通工程/
9.13HDU3572任务调度/
第10章计算几何/
10.1LeetCode223矩形面积★★/
10.2LeetCode963最小面积矩形Ⅱ★★/
10.3LeetCode149直线上最多的点数★★★/
10.4POJ1269线段交点/
10.5POJ2653捡棍子/
10.6POJ2318玩具/
10.7POJ1696太空蚂蚁/
10.8POJ2187选美比赛/
10.9HDU1115抬起石头/
10.10HDU4643GSM/
10.11HDU1348墙/
10.12HDU5721宫殿/
10.13HDU3007导弹/
附录A在线编程实验报告示例/