剑指Offer（专项突破版）：数据结构与算法名企面试题精讲

"• 以面试者|面试官双向视角剖析考点与解题思路 • 精选 119 道国内外名企高频面试题并深度拓展 • 针对面试难关，打通算法与数据结构突击捷径 • 读者可在力扣本书专区实时在线练习全部试题"

本书全面、系统地总结了在准备程序员面试过程中推荐的数据结构与算法。本书首先详细讨论整数、数组、链表、字符串、哈希表、栈、队列、二叉树、堆和前缀树等常用的数据结构，然后深入讨论二分查找、排序、回溯法、动态规划和图搜索等算法。除了介绍相应的基础知识，每章还通过大量的高频面试题系统地总结了各种数据结构与算法的应用场景及解题技巧。本书适合所有正在准备面试的程序员阅读。无论是计算机相关专业的应届毕业生还是初入职场的程序员，本书总结的数据结构和算法的基础知识及解题经验都不仅可以帮助他们提高准备面试的效率，还可以增加他们通过面试的成功率。

何海涛，现美国微软总部资深软件工程师，先后在Autodesk、思科、微软中国等跨国企业任职。著有《剑指Offer——名企面试官精讲典型编程题》、《Coding Interviews: Questions, Analysis and Solutions》（本书英文版）等书。多年来从事软件开发工作，对软件设计、开发、调试等均有较深的功底，对 C/C 、C#以及.NET等语言及平台都较为熟悉，对图形图像、CAD、设计模式、项目管理等领域均有专业经验。

第1章 整数 1 1.1 整数的基础知识 1 1.2 二进制 4 1.3 本章小结 13 第2章 数组 14 2.1 数组的基础知识 14 2.2 双指针 15 2.3 累加数组数字求子数组之和 22 2.4 本章小结 28 第3章 字符串 30 3.1 字符串的基础知识 30 3.2 双指针 31 3.3 回文字符串 41 3.4 本章小结 45 第4章 链表 46 4.1 链表的基础知识 46 4.2 哨兵节点 47 4.3 双指针 50 4.4 反转链表 58 4.5 双向链表和循环链表 66 4.6 本章小结 71 第5章 哈希表 73 5.1 哈希表的基础知识 73 5.2 哈希表的设计 74 5.3 哈希表的应用 82 5.4 本章小结 91 第6章 栈 92 6.1 栈的基础知识 92 6.2 栈的应用 93 6.3 本章小结 108 第7章 队列 109 7.1 队列的基础知识 109 7.2 队列的应用 110 7.3 二叉树的广度优先搜索 114 7.4 本章小结 125 第8章 树 126 8.1 树的基础知识 126 8.2 二叉树的深度优先搜索 127 8.3 二叉搜索树 141 8.4 TreeSet和TreeMap的应用 153 8.5 本章小结 160 第9章 堆 161 9.1 堆的基础知识 161 9.2 堆的应用 165 9.3 本章小结 172 第10章 前缀树 174 10.1 前缀树的基础知识 174 10.2 前缀树的应用 179 10.3 本章小结 191 第11章 二分查找 192 11.1 二分查找的基础知识 192 11.2 在排序数组中二分查找 193 11.3 在数值范围内二分查找 201 11.4 本章小结 205 第12章 排序 206 12.1 排序的基础知识 206 12.2 计数排序 208 12.3 快速排序 211 12.4 归并排序 215 12.5 本章小结 222 第13章 回溯法 224 13.1 回溯法的基础知识 224 13.2 集合的组合、排列 226 13.3 回溯法解决其他类型问题 235 13.4 本章小结 239 第14章 动态规划 241 14.1 动态规划的基础知识 241 14.2 单序列问题 248 14.3 双序列问题 266 14.4 矩阵路径问题 281 14.5 背包问题 293 14.6 本章小结 303 第15章 图 305 15.1 图的基础知识 305 15.2 图的搜索 307 15.3 拓扑排序 333 15.4 并查集 342 15.5 本章小结 354