¥156.00 198.00

　　编辑推荐

　　本书适合于需要进行算法面试的读者,通过阅读本书可以掌握算法面试中求解问题的方法和技巧,提升自己的算法技能和思维方式,从而在面试中脱颖而出。同时,本书可以作为“数据结构”和“算法设计与分析”课程的辅导书,也可以供各种程序设计竞赛和计算机编程爱好者研习。

　　内容简介

　　本书旨在帮助读者更好地应对算法面试，提高算法和编程能力。书中按专题精选了LeetCode平台的一系列的热点算法题，并详细解释其求解思路和过程。全书分为三个部分，第Ⅰ部分为数据结构及其应用，以常用数据结构为主题，深入讲解各种数据结构的应用方法和技巧。第Ⅱ部分为算法策略及其应用，以基本算法设计方法和算法设计策略为主题，深入讲解各种算法设计策略的应用方法和技巧。第Ⅲ部分为经典问题及其求解，以实际中的一些问题为主题，深入讲解这些问题多种求解方法。

　　本书适合于需要进行算法面试的读者，通过阅读本书可以掌握算法面试中求解问题的方法和技巧，提升自己的算法技能和思维方式，从而在面试中脱颖而出。同时可以作为《数据结构》和《算法设计与分析》课程的辅导书，也可以供各种程序设计竞赛和计算机编程爱好者研习。

　　作者简介

　　李春葆,计算机学院教授，主要研究方向：数据挖掘、人工智能和软件工程。发表论文30余篇，主持和参加多项科研课题。著作教材多部。从事近30年C/C++语言、数据结构和算法设计等课程的第一线本科教学工作，具备丰富的教学经验，曾参与深圳名企的笔试和面试题库建设。

　　目录

　　第二部分算法设计策略及其应用

　　第15章穷举法

　　15.1穷举法概述

　　15.1.1什么是穷举法

　　15.1.2顺序列举设计方法

　　15.1.3组合列举设计方法

　　15.1.4排列列举设计方法

　　15.2顺序列举的算法设计

　　15.2.1LeetCode485——1的最多连续个数★

　　15.2.2LeetCode1464——数组中两个元素的最大乘积★

　　15.2.3LeetCode829——连续整数求和★★★

　　15.2.4LeetCode17——电话号码的字母组合★★

　　15.2.5LeetCode845——数组中的最长山脉★★

　　15.2.6LeetCode209——长度最小的子数组★★

　　15.2.7LeetCode134——加油站★★

　　15.3组合列举的算法设计

　　15.3.1LeetCode78——子集★★

　　15.3.2LeetCode90——子集Ⅱ★★

　　15.3.3LeetCode77——组合★★

　　15.3.4LeetCode1863——求出所有子集的异或总和再求和★

　　15.4排列列举的算法设计

　　15.4.1LeetCode46——全排列★★

　　15.4.2LeetCode60——排列序列★★★

　　15.4.3LeetCode52——n皇后Ⅱ★★★

　　推荐练习题

　　第16章递归

　　16.1递归概述

　　16.1.1递归的定义

　　16.1.2递归模型

　　16.1.3递归的执行过程

　　16.1.4递归算法的设计

　　16.1.5使用递归的注意事项

　　16.2基于递归数据结构的递归算法设计

　　16.2.1LeetCode2487——从链表中移除结点★★

　　16.2.2LeetCode21——合并两个有序链表★

　　16.2.3LeetCode814——二叉树的剪支★★

　　16.2.4LeetCode236——二叉树的最近公共祖先★★

　　16.2.5LeetCode114——将二叉树展开为链表★★

　　16.3基于归纳的递归算法设计

　　16.3.1LeetCode17——电话号码的字母组合★★

　　16.3.2LeetCode191——位1的个数★

　　16.3.3LeetCode231——2的幂★

　　16.3.4LeetCode394——字符串解码★★

　　推荐练习题

　　第17章分治法

　　17.1分治法概述

　　17.1.1什么是分治法

　　17.1.2二分查找及其扩展算法

　　17.2基本分治算法设计

　　17.2.1LeetCode169——多数元素★

　　17.2.2LeetCode53——最大子数组和★★

　　17.2.3LeetCode241——为运算表达式设计优先级★★

　　17.2.4LeetCode95——不同的二叉搜索树Ⅱ★★

　　17.3快速排序和二路归并排序应用的算法设计

　　17.3.1LeetCode912——排序数组★★

　　17.3.2LeetCode215——数组中第k大的元素★★

　　17.3.3LeetCode315——计算右侧小于当前元素的个数★★★

　　17.3.4LeetCode493——翻转对★★★

　　17.4二分查找应用的算法设计

　　17.4.1LeetCode69——x的平方根★

　　17.4.2LeetCode167——有序数组中的两数之和Ⅱ★★

　　17.4.3LeetCode74——搜索二维矩阵★★

　　17.4.4LeetCode4——寻找两个正序数组的中位数★★★

　　17.4.5LeetCode744——寻找比目标字母大的最小字母★

　　17.4.6LeetCode153——寻找旋转排序数组中的最小值★★

　　17.4.7LeetCode33——搜索旋转排序数组★★

　　17.4.8LeetCode81——搜索旋转排序数组Ⅱ★★

　　17.4.9LeetCode315——计算右侧小于当前元素的个数★★★

　　17.4.10LeetCode493——翻转对★★★

　　17.4.11LeetCode215——数组中第k大的元素★★

　　17.4.12LeetCode378——有序矩阵中第k小的元素★★

　　17.4.13LeetCode410——分割数组的最大值★★★

　　17.4.14LeetCode1011——在D天内送达包裹的能力★★

　　推荐练习题

　　第18章DFS、BFS和拓扑排序

　　18.1DFS、BFS和拓扑排序概述

　　18.1.1深度优先搜索

　　18.1.2广度优先搜索

　　18.1.3拓扑排序

　　18.2深度优先遍历应用的算法设计

　　18.2.1LeetCode200——岛屿的数量★★

　　18.2.2LeetCode463——岛屿的周长★

　　18.2.3LeetCode130——被围绕的区域★★

　　18.2.4LeetCode529——扫雷游戏★★

　　18.2.5LeetCode365——水壶问题★★

　　18.2.6LeetCode332——重新安排行程★★★

　　18.3广度优先遍历应用的算法设计

　　18.3.1LeetCode200——岛屿的数量★★

　　18.3.2LeetCode130——被围绕的区域★★

　　18.3.3LeetCode529——扫雷游戏★★

　　18.3.4LeetCode365——水壶问题★★

　　18.3.5LeetCode1162——地图分析★★

　　18.3.6LeetCode847——访问所有结点的最短路径★★★

　　18.3.7LeetCode2608——图中的最短环★★★

　　18.3.8LeetCode2204——无向图中到环的距离★★★

　　18.3.9LeetCode127——单词接龙★★★

　　18.3.10LeetCode934——最短的桥★★

　　18.4拓扑排序应用的算法设计

　　18.4.1LeetCode1462——课程安排Ⅳ★★

　　18.4.2LeetCode802——找到最终的安全状态★★

　　18.4.3LeetCode269——火星词典★★★

　　推荐练习题

　　第19章回溯法

　　19.1回溯法概述

　　19.1.1什么是回溯法

　　19.1.2回溯法的算法设计

　　19.2子集树的回溯算法设计

　　19.2.1LeetCode78——子集★★

　　19.2.2LeetCode77——组合★★

　　19.2.3LeetCode40——组合总和Ⅱ★★

　　19.2.4LeetCode39——组合总和★★

　　19.2.5LeetCode90——子集Ⅱ★★

　　19.2.6LeetCode216——组合总和Ⅲ★★

　　19.2.7LeetCode491——递增子序列★★

　　19.2.8LeetCode131——分割回文串★★

　　19.2.9LeetCode93——复原IP地址★★

　　19.2.10LeetCode282——给表达式添加运算符★★★

　　19.2.11LeetCode22——括号的生成★★

　　19.2.12LeetCode301——删除无效的括号★★★

　　19.2.13LeetCode17——电话号码的字母组合★★

　　19.2.14LeetCode79——单词的搜索★★

　　19.2.15LeetCode797——所有可能的路径★★

　　19.2.16LeetCode332——重新安排行程★★★

　　19.2.17LeetCode37——解数独★★★

　　19.2.18LeetCode679——24点游戏★★★

　　19.2.19LeetCode1723——完成所有工作的最短时间★★★

　　19.3排列树的回溯算法设计

　　19.3.1LeetCode46——全排列★★

　　19.3.2LeetCode47——全排列Ⅱ★★

　　19.3.3LeetCode60——排列序列★★★

　　19.3.4LeetCode51——n皇后★★★

　　精彩书摘

　　第3章〓栈

　　知识图谱

　　3.1栈概述

　　3.1.1栈的定义

　　栈的示意图如图3.1所示，栈中保存一个数据序列[a0，a1，…，an-1]，共有两个端点，栈底的一端(a0端)不动，栈顶的一端(an-1端)是动态的，可以插入(进栈)和删除(出栈)元素。栈元素遵循“先进后出”的原则，即最先进栈的元素最后出栈。注意，不能直接对栈中的元素进行顺序遍历。

　　图3.1栈的示意图

　　在算法设计中，栈通常用于存储临时数据。在一般情况下，若先存储的元素后处理，则使用栈数据结构存储这些元素。

　　n个不同的元素经过一个栈产生不同出栈序列的个数为1n+1Cn2n，这称为第n个Catalan(卡特兰)数。

　　栈可以使用数组和链表存储结构实现，使用数组实现的栈称为顺序栈，使用链表实现的栈称为链栈。

　　3.1.2栈的知识点

　　1. C++中的栈

　　在C++STL中提供了stack类模板，实现了栈的基本运算，而且在使用时不必考虑栈满上溢出的情况，但不能顺序遍历栈中的元素。其主要的成员函数如下。

　　 empty()： 判断栈是否为空，当栈中没有元素时返回true，否则返回false。

　　 size()： 返回栈中当前元素的个数。

　　 top()： 返回栈顶的元素。

　　 push(x)： 将元素x进栈。

　　 pop()： 出栈元素，只是删除栈顶元素，并不返回该元素。

　　例如，以下代码定义一个整数栈st，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。

　　C++：

　　1stack st;//定义一个整数栈

　　2st.push(1); 　　//进栈1

　　3st.push(2); 　　//进栈2

　　4st.push(3); 　　//进栈3

　　5while(!st.empty()) { 　　//栈不空时循环

　　6printf("%d ",st.top());//输出栈顶元素

　　7st.pop();//出栈栈顶元素

　　8}

　　另外，由于C++STL中的vector容器提供了empty()、push_back()、pop_back()和back()等成员函数，也可以将vector容器用作栈。

　　2. Python中的栈

　　在Python中没有直接提供栈，可以将列表作为栈。当定义一个作为栈的st列表后，其主要的栈操作如下。

　　 st，len(st)==0： 判断栈是否为空，当栈中没有元素时返回True，否则返回False。

　　 len(st)： 返回栈中当前元素的个数。

　　 st[-1]： 返回栈顶的元素。

　　 st.append(x)： 将元素x进栈。

　　 st.pop()： 出栈元素，只是删除栈顶元素，并不返回该元素。

　　说明： 在Python中提供了双端队列deque，可以通过限制deque在同一端插入和删除将其作为栈使用。

　　例如，以下代码用列表st作为一个整数栈，依次进栈1、2、3，再依次出栈所有元素，出栈结果是3，2，1。

　　Python：

　　1st=[]#将列表作为栈

　　2st.append(1)#进栈1

　　3st.append(2)#进栈2

　　4st.append(3)#进栈3

　　5while st:#栈不空时循环，或者改为while len(st)>0:

　　6print(st[-1],end=' ')#输出栈顶元素

　　7st.pop()#出栈栈顶元素

　　3. 单调栈

　　将一个从栈底元素到栈顶元素有序的栈称为单调栈，如果从栈底元素到栈顶元素是递增的(栈顶元素最大)，称该栈为单调递增栈或者大顶栈，例如[1，2，3](栈底为1，栈顶为3)就是一个单调递增栈; 如果从栈底元素到栈顶元素是递减的(栈顶元素最小)，称该栈为单调递减栈或者小顶栈，例如[3，2，1]就是一个单调递减栈。

　　维护单调栈的操作是在向栈中插入元素时可能需要出栈元素，以保持栈中元素的单调性。这里以单调递增栈(大顶栈)为例，假设要插入的元素是x：

　　(1) 如果栈顶元素小于(或者等于)x，说明插入x后仍然保持单调性。直接进栈x即可。

　　(2) 如果栈顶元素大于x，说明插入x后不再满足单调性，需要出栈栈顶元素，直到栈为空或者满足(1)的条件，再将x进栈。

　　例如，以下代码中定义的单调栈st是一个单调递增栈，执行后st从栈底到栈顶的元素为[1，2，3]。

　　C++：

　　1vector a={1,5,2,4,3};

　　2stack st;

　　3for(int i=0;i

　　4while(!st.empty() && st.top()>a[i])

　　5st.pop();　　//将大于a[i]的栈顶元素出栈

　　6st.push(a[i]);

　　7}

　　单调栈的主要用途是寻找下/上一个更大/更小元素，例如给定一个整数数组a，求每个元素的下一个更大元素，可以使用单调递减栈实现。由于在单调栈应用中通常每个元素仅进栈和出栈一次，所以时间复杂度为O(n)。

　　3.2扩展栈的算法设计

　　3.2.1LeetCode1381——设计一个支持增量操作的栈★★

　　【问题描述】请设计一个支持以下操作的栈。

　　(1) CustomStack(int maxSize)： 用maxSize初始化对象，其中maxSize 是栈中最多能容纳的元素的数量，栈在增长到maxSize之后将不支持 push 操作。

　　(2) void push(int x)： 如果栈还未增长到maxSize，将x添加到栈顶。

　　(3) int pop()： 弹出栈顶元素，并返回栈顶的值，或栈为空时返回-1。

　　(4) void increment(int k, int val)： 栈底的 k 个元素的值都增加 val。如果栈中元素的总数小于k，则栈中的所有元素都增加val。

　　示例：

　　CustomStack customStack=new CustomStack(3); 　　//栈的容量为3，初始为空栈[]

　　customStack.push(1);　　//栈变为[1]

　　customStack.push(2);　　//栈变为[1, 2]

　　customStack.pop(); 　　//返回栈顶值2，栈变为[1]

　　customStack.push(2);　　//栈变为[1, 2]

　　customStack.push(3);　　//栈变为[1, 2, 3]

　　customStack.push(4);//栈是[1, 2, 3]，不能添加其他元素使栈的大小变为4

　　customStack.increment(5, 100);　　//栈变为[101, 102, 103]

　　customStack.increment(2, 100);　　//栈变为[201, 202, 103]

　　customStack.pop();　　//返回栈顶值103，栈变为[201, 202]

　　customStack.pop(); 　　//返回栈顶值202，栈变为[201]

　　customStack.pop(); 　　//返回栈顶值201，栈变为[]

　　customStack.pop(); 　　//栈为空，返回-1

　　【限制】1≤maxSize≤1000，1≤x≤1000，1≤k≤1000，0≤val≤100。increment、push、pop操作均最多被调用 1000 次。

　　前言/序言

　　党的二十大报告指出： 教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。

　　在现代社会中，算法已经广泛应用于计算机科学的各个领域，如人工智能、数据挖掘、网络安全和生物信息学等。许多成功的案例都证明了算法的重要性和实用性，如搜索引擎的优化、社交网络的推荐系统、医疗诊断的辅助决策等。算法知识和技能对于程序员来说至关重要。算法面试是许多科技公司招聘过程中必不可少的一环，它考查的是候选人的编程能力、思维逻辑、问题解决能力以及算法设计技巧。通过算法面试，候选人可以展示自己的技能和知识，提升自己在求职市场上的竞争力。

　　LeetCode是一个在线刷题平台，提供了大量的算法题目供用户练习，帮助用户加深对数据结构与算法的理解和掌握。LeetCode于2011年诞生于美国硅谷，2018年2月由上海领扣网络引入中国并正式命名为力扣，其中文网站于同月测试上线，2018年10月力扣全新改版，更加注重于学习体验。许多北美大厂(如谷歌、微软和亚马逊等)在面试中都涉及算法及其相关知识，甚至直接从LeetCode出题(许多北美程序员从实习到全职，再到跳槽，一路上都在刷LeetCode)。国内大厂近几年也越来越重视对算法的考查，如腾讯、百度、华为和字节跳动等都是较看重算法面试的公司。

　　本书提供一系列编者精心挑选的LeetCode问题，覆盖不同难度级别和C++/Python编程语言，旨在帮助读者提高编程技能和更深入地理解数据结构与算法的原理，以应对算法面试中的挑战。

　　本书内容

　　本书共25章，分为三部分。

　　第一部分(第1~14章)为数据结构及其应用，以常用数据结构为主题，深入讲解各种数据结构的应用方法和技巧，包含数组、链表、栈、队列和双端队列、哈希表、二叉树、二叉搜索树、平衡二叉树、优先队列、并查集、前缀和与差分、线段树、树状数组、字典树和后缀数组等。

　　第二部分(第15~22章)为算法设计策略及其应用，以基本算法设计方法和算法设计策略为主题，深入讲解各种算法设计策略的应用方法和技巧，包含穷举法、递归、分治法、DFS、BFS和拓扑排序、回溯法、分支限界法、A*算法、动态规划和贪心法等。

　　第三部分(第23~25章)为经典问题及其求解，以实际面试中的一些问题为主题，深入讲解这些问题的多种求解方法，对比分析不同方法的差异，包含跳跃问题、迷宫问题和设计问题等专题。

　　本书特色

　　(1) 全面覆盖： 本书对算法面试中可能涉及的各种主题进行了较为全面的覆盖，包括各种基础数据结构和常用的算法设计策略。

　　(2) 实战导向： 书中精选的许多LeetCode题目都是国内外互联网大厂的热门算法面试题，具有很强的实战性。

　　(3) 知识的结构化： 本书以数据结构和算法策略为主线，划分为若干知识点，通过实例和问题求解将相关的知识点串起来构成知识网络，不仅可以加深读者对算法原理的理解，而且可以拓宽读者对算法应用的视野。

　　(4) 求解方法的多维性： 同一个问题采用多种算法策略实现，如迷宫问题采用回溯法、分支限界法、A*算法和贪心法求解等。通过对不同算法策略的比较，使读者更容易体会每种算法策略的设计特点和优缺点，以提高算法设计的效率。

　　(5) 代码的规范化： 书中代码采用C++和Python语言编写，不仅在LeetCode平台上提交通过，而且进行了精心的代码组织和规范化，包括变量名称和算法策略的统一与标准化等，尽可能提高代码的可读性。

　　注： 书中以LeetCode开头+序号的题目均来自LeetCode平台。

　　配套资源获取方式

　　扫描封底的文泉云盘防盗码，再扫描目录上方的二维码获取。

　　如何刷题和使用本书

　　在互联网上和力扣平台上有许多关于LeetCode刷题经验的分享，读者可以酌情参考。编者建议读者在具备一定的数据结构和算法基础后按本书中的专题分类刷题，先刷数据结构部分后刷算法部分，先刷简单题目后刷困难题目(书中题目按难度分为3个级别，即★、★★和★★★，分别对应简单、中等和困难)，在刷题时要注重算法思路和算法实现细节，每个环节都要清清楚楚，并能够做到举一反三，同时将自己在线提交的结果与书中的时间和空间进行对比分析(值得注意的是书中列出的时间和空间是编者提交的结果，后面因环境的变化可能有所不同)。另外，经常进行归纳总结和撰写解题报告是提高编程能力的有效手段。在没有对一道题目进行深入思考和分析之前就阅读书中的代码部分甚至是复制、粘贴代码，这种做法不可取。总之，使用良好的刷题方法并且持之以恒，一定会收获理想的效果。

　　致谢

　　本书以LeetCode为平台，书中所有LeetCode题目及其相关内容都得到领扣网络(上海)有限公司的授权。本书的编写得到清华大学出版社魏江江分社长的大力支持，王冰飞老师给予精心编辑。本书在编写过程中参考了众多博客和LeetCode题解评论栏目的博文，编者在此一并表示衷心的感谢。

　　作者

　　2024年8月