编程之法-面试和算法心得

1 . 目 录 致谢 整理说明 阅前必读 目录 程序员如何准备面试中的算法 第一章 字符串 1.0 本章导读 1.1 旋转字符串 1.2 字符串包含 1.3 字符串转换成整数 1.4 回文判断 1.5 最长回文子串 1.6 字符串的全排列 1.10 本章习题 第二章 数组 2.0 本章导读 2.1 寻找最小的 k 个数 2.2 寻找和为定值的两个数 2.3 寻找和为定值的多个数 2.4 最大连续子数组和 2.5 跳台阶 2.6 奇偶排序 2.7 荷兰国旗 2.8 矩阵相乘 2.9 完美洗牌 2.10 K个最小和 2.15 本章习题 第三章 树 3.0 本章导读 3.1 红黑树 3.2 B树 3.3 最近公共祖先LCA 3.5 R树：处理空间存储问题 本文档使用 书栈(BookStack.CN) 构建 - 1 - 

2 . 3.10 本章习题 第四章 查找匹配 4.1 有序数组的查找 4.2 行列递增矩阵的查找 4.3 出现次数超过一半的数字 第五章 动态规划 5.0 本章导读 5.1 最大连续乘积子串 5.2 字符串编辑距离 5.3 格子取数 5.4 交替字符串 5.6 最长递增子序列 5.10 本章习题 第六章 海量数据处理 6.0 本章导读 6.1 关联式容器 6.2 分而治之 6.3 simhash算法 6.4 外排序 6.5 MapReduce 6.6 多层划分 6.7 Bitmap 6.8 Bloom filter 6.9 Trie树 6.10 数据库 6.11 倒排索引 6.15 本章习题 第七章 机器学习 7.1 K 近邻算法 7.2 支持向量机 附录 更多题型 附录A 语言基础 附录B 概率统计 附录C 智力逻辑 本文档使用 书栈(BookStack.CN) 构建 - 2 - 

3 . 附录D 系统设计 附录E 操作系统 附录F 网络协议 sift算法的编译与实现 教你一步一步用c语言实现sift算法、上 教你一步一步用c语言实现sift算法、下 算法题 40亿个数中快速查找 hash表算法 一致性哈希算法 倒排索引关键词不重复Hash编码 从头到尾彻底理解傅里叶变换算法、上 从头到尾彻底理解傅里叶变换算法、下 后缀树 基于给定的文档生成倒排索引的编码与实践 搜索关键词智能提示suggestion 最小操作数 最短摘要的生成 最长公共子序列 木块砌墙 附近地点搜索 随机取出其中之一元素 本文档使用 书栈(BookStack.CN) 构建 - 3 - 

4 .致谢 致谢 当前文档 《编程之法：面试和算法心得》 由 进击的皇虫 使用 书栈(BookStack.CN) 进行 构建，生成于 2018-02-20。 书栈(BookStack.CN) 仅提供文档编写、整理、归类等功能，以及对文档内容的生成和导出工 具。 文档内容由网友们编写和整理，书栈(BookStack.CN) 难以确认文档内容知识点是否错漏。如 果您在阅读文档获取知识的时候，发现文档内容有不恰当的地方，请向我们反馈，让我们共同携手， 将知识准确、高效且有效地传递给每一个人。 同时，如果您在日常生活、工作和学习中遇到有价值有营养的知识文档，欢迎分享到 书栈 (BookStack.CN) ，为知识的传承献上您的一份力量！ 如果当前文档生成时间太久，请到 书栈(BookStack.CN) 获取最新的文档，以跟上知识更新换 代的步伐。 文档地址：http://www.bookstack.cn/books/The-Art-Of-Programming-By-July 书栈官网：http://www.bookstack.cn 书栈开源：https://github.com/TruthHun 分享，让知识传承更久远！ 感谢知识的创造者，感谢知识的分享者，也感谢每一位阅读到此处的 读者，因为我们都将成为知识的传承者。 本文档使用 书栈(BookStack.CN) 构建 - 4 - 

5 .整理说明 整理说明 《编程之法：面试和算法心得》 作者：julycoding 来源：The-Art-Of-Programming-By-July 当前项目整理自该书原作者托管在GitHub上的项目，该项目的文章已于2014年6月30日基本停止更 新，所有进一步的修改、改动、优化请见2015年10月14日上市销售的纸质版《编程之法：面试和算 法心得》。 纸质版书籍内容更优，纸质版书籍购买地址： http://item.jd.com/11786791.html 本文档使用 书栈(BookStack.CN) 构建 - 5 - 

6 .阅前必读 阅前必读 About Start Reading How To Contribute Code Style Ver Note Contributors Expressing Thanks Copyright July’ PDF About July的新书《编程之法：面试和算法心得》纸质版在本github上的基础上做了极大彻底的改进、优 化，无论是完整度、还是最新度、或质量上，都远非博客、github所能相比。换言之，新书《编程之 法》的质量远高于博客、github。 此外，散落在网上其他任何地方的“编程之法”电子材料均是盗版自本github，更无质量可言。所 以，July只唯一推荐《编程之法》纸质版。 《编程之法》纸质版已于2015年10月14日陆续开卖！目前，京东、当当、亚马逊等各大网店均已有 现货销售。比如京东：http://item.jd.com/11786791.html 。 另，新书《编程之法：面试和算法心得》的勘误在此文最 末：http://blog.csdn.net/v_july_v/article/details/49302193 看过结构之法算法之道blog的朋友可能知道，从2010年10月起，July 开始整理一个微软面试100 题的系列，他在整理这个系列的过程当中，越来越强烈的感觉到，可以从那100题中精选一些更为典 型的题，每一题详细阐述成章，不断优化，于此，便成了程序员编程艺术系列。 原编程艺术系列从2011年4月至今，写了42个编程问题，在创作的过程当中，得到了很多朋友的支 持，特别是博客上随时都会有朋友不断留言，或提出改进建议，或show出自己的思路、代码，或指正 bug。为更好的改进、优化、增补编程艺术系列，特把博客上的这个程序员编程艺术系列和博客内其 它部分经典文章同步到此，成立本项目。 若发现任何问题、错误、bug，或可以优化的每一段代码，欢迎随时pull request或发issue反 馈，thanks。 update July于2015年正式创业，任七月在线创始人兼CEO，公司官网为：https://www.julyedu.com/ ，致力于培养100万AI人才。 本文档使用 书栈(BookStack.CN) 构建 - 6 - 

7 .阅前必读 Start Reading 中文目录 Enhancement in progress English Contents Translation in progress How To Contribute 邀请大家帮忙把github上的文章导出到word上，欢迎到这里认 领：https://github.com/julycoding/The-Art-Of-Programming-By- July/issues/337 」 一章一章的测试所有代码，指正 bug，修正错误。 「必选，可到这里认 领：https://github.com/julycoding/The-Art-Of-Programming-By- July/issues/210 」 优化原文章上的C/C++ 代码，优化后的代码可以放到ebook/code文件夹内，并注意代码命名规 范的问题：https://github.com/julycoding/The-Art-Of-Programming-By- July/issues/234 。 「必选」 添加其它语言如Java、python、go 的代码，放在ebook/code文件夹内，同样如上，注意代码 命名规范的问题。 「可选」 重绘所有的图片：https://github.com/julycoding/The-Art-Of-Programming-by- July/issues/80 翻译成英文版，参考中文目录，把翻译后的文章编辑到这English Version,注：不必逐字翻 译，精简大气即可（如有兴趣翻译，请到这里领取感兴趣的章节翻 译：https://github.com/julycoding/The-Art-Of-Programming-by- July/issues/84 ) 自己主导续写新的章节； 任何你想做的事情，包括痛批你觉得写的烂的章节，所有你的意见都将改进此系列。 你可以做以上任何一件或几件事情，如遇到任何问题或疑惑，咱们可以随时讨论： https://github.com/julycoding/The-Art-Of-Programming-by-July/issues? state=open。 「如不知如何在github上提交及同步作者的更新，可参考此 文：http://www.cnblogs.com/rubylouvre/archive/2013/01/24/2874694.html 」 Code Style 本项目暂约定以下代码风格(不断逐条添加中)： 关于空格 所有代码使用4个空格缩进 运算符后使用一个空格 本文档使用 书栈(BookStack.CN) 构建 - 7 - 

8 .阅前必读 “,” 和for循环语句中的”;” 后面跟上一个空格 条件、分支保留字，如 if for while else switch 后留出一个空格 “[]”, “.”和”->” 前后不留空格 用空行把大块代码分成逻辑上的“段落 关于括号 大括号另起一行 即便只有一行代码也加大括号 C 指针中的指针符靠近类型名，如写成int p，而不写成int p 关于标点 中文表述，使用中文全角的标点符号，如：（）、。，？ 数学公式（包括文中混排的公式）和英文代码，使用英文半角的标点符号，如：(),.?… 关于注释 注释统一用中文 尽量统一用”//“，一般不用”/*…*/“ 关于命名 类名为大写字母开头的单词组合 函数名比较长，由多个单词组成的，每个单词的首字母大写，如int MaxSubArray()；函数名 很短，由一个单词组成，首字母小写，比如int swap() 变量名比较长，由多个单词组成的，首个单词的首字母小写，后面紧跟单词的首字母大写，如 maxEnd；变量名很短，由一个单词组成，首字母小写，如left 变量尽量使用全名，能够描述所要实现的功能，如 highestTemprature；对于已经公认了的 写法才使用缩写，如 tmp mid prev next 变量名能“望文生义”，如v1, v2不如area, height 常量的命名都是大写字母的单词，之间用下划线隔开，比如MY_CONSTANT il < 4384 和 inputLength < MAX_INPUT_LENGTH，后一种写法更好 一个函数只专注做一件事 时间复杂度小写表示，如O(nlogn)，而不写成O(N*logN) 正文中绝大部分采用C实现，少量C++代码，即以C为主，但不去刻意排斥回避C++； 关于的地得 形容词（代词） + 的 + 名词，例如：我的小苹果 副词 + 地 + 动词，例如：慢慢地走 动词 + 得 + 副词，例如：走得很快 关于参考文献 本文档使用 书栈(BookStack.CN) 构建 - 8 - 

9 .阅前必读 格式：主要责任者.书名〔文献类型标识 ] .其他责任者.版本.出版地：出版者，出版年.文献 数量.丛编项.附注项.文献标准编号。例子：1 刘少奇.论共产党员的修养.修订 2 版.北京：人 民出版社，1962.76 页. 专业术语 统一一律用“树结点”，而不是“树节点”。 用左子树、右子树表示树的左右子树没问题，但是否用左孩子、右孩子表示树或子树的左右结 点？ .. 此外，更多C++ 部分可参考Google C++ Style Guide，中文版见：http://zh- google-styleguide.readthedocs.org/en/latest/contents/ ； 有何问题或补充意见，咱们可以随时到这里讨论：https://github.com/julycoding/The-Art- Of-Programming-By-July/issues/81 。 Ver Note 2010年10月11日，在CSDN上正式开博，感谢博客上所有读者的访问、浏览、关注、支持、留 言、评论、批评、指正； 2011年1月，在学校的时候，第一家出版社联系出书，因“时机未到，尚需积累”的原因婉拒，随 后第二家、第三家出版社陆续联系，因总感觉写书的时机还没到，一律婉拒； 2011年10月， 当时在图灵教育的杨海玲老师（现在人民邮电信息技术分社）再度联系出书，再 度认为“时机未到”； 2013年12月30日，本项目在众多朋友的努力之下，冲到github流行趋势排行榜全球第一，自己 也在众人助推下冲到全球开发者第一。 2014年1月18日，想通了一件事：如果什么都不去尝试，那么将年年一事无成，所以元旦一过， 便正式确认今2014年之内要把拖了近3年之久的书出版出来； 2013年12月-2014年3月，本github的Contributors 转移结构之法算法之道blog的部分经 典文章到本github上，感谢这近100位Contributors，包括但不限于： Boshen（除我之外，贡献本github的次数最多） sallen450 marchtea（专门为本github书稿弄了一个HTML网页） nateriver520（劝我把书稿放在github上，才有了本github） 2014年3月，通读全部文章，修正明显错误，并邀请部分朋友review本github上的全部文章， 包括cherry、王威扬、邬勇、高增琪、武博文、杨忠宝等； 2014年4月 整个4月，精简篇幅，调整目录，Contributors 贡献其它语言代码，并翻译部分文章； 4月25日，跟人民邮电出版社信息技术分社签订合同，书名暂定《程序员编程艺术：面试和算法 心得》，有更好的名字再替换。 2014年5月，逐章逐节逐行逐字优化文字描述，测试重写优化每一段每一行每一个代码，确 定代码基本风格； 本文档使用 书栈(BookStack.CN) 构建 - 9 - 

10 .阅前必读 2014年6月 第一周，压缩篇幅，宁愿量少，但求质精； 第二周，全面 review； 第三周，本github的部分Contributors 把全部文章从github转到word上，这部分 contributors 包括包括：zhou1989、qiwsir、DogK、x140yu、ericxk、 zhanglin0129、idouba.net、gaohua、kelvinkuo等； 第四周，继续在Word 上做出最后彻底的改进，若未发现bug或pull request，本github将暂 不再改动； 6月30日，与出版社约定的交稿日期延期，理由：目前版本不是所能做到的最好的版本。 2014年7月，邀请部分好友进行第一轮审稿，包括曹鹏、邹伟、林奔、王婷、何欢，其中，曹鹏 重写优化了部分代码。此外，葛立娜对书稿中的语言描述做了不少改进； 2014年8月 8月上旬，新增KMP一节内容； 8月下旬，重点修改SVM一节内容； 2014年9月 9月上旬，和一些朋友一起重绘稿件中的部分图和公式，这部分朋友包括顾运（@陈笙）、 mastermay、在山东大学读研二的丰俊丙、厦门大学电子工程系陈友和等等； 9月下旬，再度邀请另一部分好友进行第二轮审稿，包括许利杰、王亮、陈赢、李祥老师、 litaoye等，并在微博上公开征集部分读者审稿，包括李元超、刘琪等等； 2014年10月 10月8日起，开始一章一章陆续交Word 稿给出版社初审 10月9日，第一章、字符串完成修改； 10月10日，第二章、数组完成修改； 10月22日，第三章、树完成修改； 2014年11月 11月5日，第三章、树完成第二版修改，主要修正部分图片、公式、语言描述的错误； 2014年12月 12月1日，第四章、查找完成修改。至此，前4 章的修改稿交付出版社。 12月8日，第五章、动态规划完成修改，等出版社反馈中。一个人坚持有点枯燥。 12月31日，第六章仍未修改完。 2015年1月 1月12日凌晨，第六章、海量数据处理完成修改，交付出版社。 本文档使用 书栈(BookStack.CN) 构建 - 10 - 

11 .阅前必读 2015年4月 4月27日凌晨，交完第七章初稿，接下来编辑老师反馈，我修改审阅反馈稿。且书名由原来的 《程序员编程艺术：面试和算法心得》暂时改为《编程之法：面试和算法心得》。 2015年5月 5月2日，开始写书的前言，大致是：为何要写这本书，写的过程是怎样的；这是本什么书，有何 特色，内容是什么，为什么这么写；写给谁看，怎么看更好。当然我还会加一些自己觉得比较个 性化的内容。 5月5日，审阅完编辑老师的第一章反馈，并合并。 5月6日，审阅完第二章的一半。海玲姐两位老师给出了大量细致、详尽的修改建议，包括文字表 述、语言表达、标点符号、字体格式、出版规范，尤其是正斜体、大小写、上下角。 5月15日，和海玲姐审完第一、二章，标点、术语、表述、逻辑、图片、代码等一切细节。书稿 进入一审阶段。 2015年6月 6月28日，经过反复修改、确认，书稿第一、二、三章基本定稿。 2015年7月 7月10日，书稿全部七章基本定稿，即将进入二审。 7月23日，补齐前言、封底、内容提要、邀请曹鹏、邹伟两位博士写推荐序，书稿进入二审，出 版社重绘全部图片和公式。 2015年8月 8月6日，三审结束。书稿取得阶段性的胜利。 8月下旬，发稿审批。 2015年9月 9月上旬，排版校对，出胶片、印刷、装订成书 9月21日，几经易稿，终于敲定新书封面。 9月22日，开始印刷。 2015年10月 进入10月份，万众期待的《编程之法》，终于终于要来了！ 10月13日晚，终于拿到第一批样书。 10月14日下午三点半，我的新书《编程之法》终于在异步社区上首发开卖！ 10月28日，新书正式上架京东。目前京东、当当、亚马逊等各大网店均已有现货销售。 Contributors 本文档使用 书栈(BookStack.CN) 构建 - 11 - 

12 .阅前必读 感谢所有贡献的朋友：https://github.com/julycoding/The-Art-Of-Programming-by- July/graphs/contributors ，因为有各位之力，本项目才能于13年年底冲到github流行趋势排 行榜全球第一。非常期待你的加入，thanks。 同时，欢迎加入《编程之法》讨论交流QQ群：74631723，需要写验证信息。 孤军奋战的时代早已远去，我们只有团结起来，才能帮助到更多人。@研究者July，始于二零一三年 十二月十四日。 Expressing Thanks 感谢我博客上所有读者的访问、浏览、关注、支持、留言、评论、批评、指正，仅以本书献给我 博客的所有读者。 感谢Boshen、sallen450、marchtea、nateriver520等朋友帮我把博客上的部分经典文章 移到GitHub上。 感谢zhou1989、qiwsir、DogK、x140yu、ericxk、zhanglin0129、idouba.net、 gaohua、kelvinkuo等朋友帮我把GitHub上的文章转为Word文件。 感谢顾运、mastermay、丰俊丙、陈友和等朋友帮忙重绘书中的部分图和重录书中的部分公式。 感谢cherry、王威扬、邬勇、高增琪、武博文、杨忠宝、葛立娜、林奔、王婷、何欢、许利杰 JerryLead、王亮、陈赢、李祥老师、litaoye、李元超、刘琪、weedge、Frankie等众多朋 友帮忙审校书稿。 特别感谢曹鹏、邹伟两位博士。感谢他们非常认真细致地看完了全部书稿，给出了非常多的建设 性意见，并为本书作序。 最后，再次感谢杨海玲老师以及出版社的编辑们。感谢杨海玲老师给出了大量细致的修改建议， 并且非常耐心地与我一轮一轮讨论和修改书稿。 感谢以上诸位，正因为他们的帮助，纸书《编程之法：面试和算法心得》的质量才不断提升，从而给 广大读者呈现的是更好的作品。 Copyright 本电子书的版权属于July 本人，严禁他人出版或用于商业用途，违者必究法律责任。July、二零一 四年五月十一日晚。 July’ PDF July’ PDF 《支持向量机通俗导论（理解SVM的三层境界）》Latex排版精细 版：http://vdisk.weibo.com/s/zrFL6OXKgnlcp ；Latex版本 ②：https://raw.githubusercontent.com/liuzheng712/Intro2SVM/master/Intro 本文档使用 书栈(BookStack.CN) 构建 - 12 - 

13 .阅前必读 2SVM.pdf 。 原《程序员编程艺术第一~三十七章 PDF》：http://download.csdn.net/detail/v_july_v/6694053 ，本github上的文章 已经对此PDF进行了极大的优化和改进。 《微软面试100题系列之 PDF》：http://download.csdn.net/detail/v_july_v/4583815 《十五个经典算法研究与总结之 PDF》：http://download.csdn.net/detail/v_july_v/4478027 编程艺术HTML网页版：http://taop.marchtea.com/ 截止到2014年12.9日，结构之法算法之道blog所有155篇博文集锦CHM文件下载地 址：http://pan.baidu.com/s/1gdrJndp July团队高校讲座PPT 2014年4月29日《武汉华科大第5次面试&算法讲座 PPT》：http://pan.baidu.com/s/1hqh1E9e ； 2014年9月3日西电第8次面试&算法讲座视 频：http://v.youku.com/v_show/id_XNzc2MDYzNDg4.html ； PPT：http://pan.baidu.com/s/1pJ9HFqb ； 北京10月机器学习班的所有上课PPT：http://yun.baidu.com/share/home? uk=4214456744&view=share#category/type=0； July新书初稿的4个PDF B树的PDF：http://yun.baidu.com/s/1jGwup5k ； 海量数据处理的PDF：http://yun.baidu.com/s/1dDreICL ； 支持向量机的PDF：http://yun.baidu.com/s/1ntwof7j ； KMP的PDF：http://yun.baidu.com/s/1eQel3PK ； 七月在线经典课程 《机器学习中的数学班》：https://www.julyedu.com/course/getDetail/41 。专为复 习、巩固机器学习中所需的数学基础。 《Python数据分析班》：https://www.julyedu.com/course/getDetail/43 ，入门数 学科学的最佳课程。 《计算机视觉班》：https://www.julyedu.com/course/getDetail/44 ，从CV基础到深 度学习实战，9.3日开班。 《机器学习与量化交易项目班》：https://www.julyedu.com/course/getDetail/46 ， 项目驱动、真实数据，市场上极为难得的项目班，16年9.24日开班。 11月深度学习班 [通向无人驾驶的必经之 路]：https://www.julyedu.com/course/getDetail/49 。国内首个GPU云实验平台，秒 杀同品类课程。 《kaggle案例实战班 [100%纯实 战]》：https://www.julyedu.com/course/getDetail/54 ，本周六12.24日起在线直 播 本文档使用 书栈(BookStack.CN) 构建 - 13 - 

14 .阅前必读 ¥2999包揽2017年全套数据课程和全年GPU：https://www.julyedu.com/sale/vip ，包 含论文班、GAN、迁移学习、强化学习、TensorFlow框架实战班等等.. 《第8期机器学习算法班》：https://www.julyedu.com/course/getDetail/65 ，BAT工 业实战、kaggle案例，国内最好ML课程。 七月在线「机器学习集训营」，线上线下项目实训，线下BAT专家面对面、手把手教学，尤为突 出BAT级工业项目实战辅导 + 一对一面试求职辅 导：https://www.julyedu.com/category/index/2/32 。且提供3个月GPU实战，更精讲 面试常见考点。 July’ blog CNN笔记：通俗理解卷积神经网络 http://blog.csdn.net/v_july_v/article/details/51812459 结构之法 算法之道ML/DL系列博 客：http://blog.csdn.net/v_JULY_v/article/category/1061301 教你从头到尾利用DL学梵高作画 ① CPU版教 程：http://blog.csdn.net/v_july_v/article/details/52683959 ；② GPU版教 程：http://blog.csdn.net/v_july_v/article/details/52658965 学汪峰作词 MAC torch char-rnn 教程：https://ask.julyedu.com/question/7405 基于torch学汪峰写歌词、聊天机器人、图像着色/生成、看图说话、字幕生 成：http://blog.csdn.net/v_july_v/article/details/52796239 教你从头到尾利用DQN自动玩flappy bird（全程命令提示，GPU+CPU 版）：http://blog.csdn.net/v_july_v/article/details/52810219 beautiful soup和网络爬虫初步：http://mp.weixin.qq.com/s? __biz=MzI4MTQ2NjU5NA==&mid=2247483666&idx=1&sn=af802b39d42d9073e24c0867 90457004&chksm=eba9829fdcde0b8929ae724f0b41d49091c88fc1e07f697c5030516f 33b1bcfcffdace83bcf7&mpshare=1&scene=23&srcid=1102C9RJJ1RXE6bHwFQzLy6W# rd 16年度最火课程TOP 10免费试听：https://www.julyedu.com/sale/christmas 如何学习数据科学、机器学习与深度学习（附学习路 线）：http://blog.csdn.net/v_july_v/article/details/54561427 《机器学习集训营第三期》：http://www.julyedu.com/weekend/train3 ，学习机器学习 的最佳选择，三个月挑战起薪三十万。 国内首个AI题库陆续发布，「BAT机器学习面试1000 题」：http://blog.csdn.net/column/details/17609.html 持续更新.. 本文档使用 书栈(BookStack.CN) 构建 - 14 - 

15 .目录 目录 目录 第一部分 数据结构 第二部分 算法心得 第三部分 综合演练 目录 第一部分 数据结构 第一章 字符串 1.0 本章导读 1.1 旋转字符串 1.2 字符串包含 1.3 字符串转换成整数 1.4 回文判断 1.5 最长回文子串 1.6 字符串的全排列 1.10 本章习题 第二章 数组 2.0 本章导读 2.1 寻找最小的 k 个数 2.2 寻找和为定值的两个数 2.3 寻找和为定值的多个数 2.4 最大连续子数组和 2.5 跳台阶 2.6 奇偶排序 2.7 荷兰国旗 2.8 矩阵相乘 2.9 完美洗牌 2.15 本章习题 第三章 树 3.0 本章导读 3.1 红黑树 3.2 B树 3.3 最近公共祖先LCA 3.10 本章习题 本文档使用 书栈(BookStack.CN) 构建 - 15 - 

16 .目录 第二部分 算法心得 第四章 查找匹配 4.1 有序数组的查找 4.2 行列递增矩阵的查找 4.3 出现次数超过一半的数字 第五章 动态规划 5.0 本章导读 5.1 最大连续乘积子串 5.2 字符串编辑距离 5.3 格子取数 5.4 交替字符串 5.10 本章习题 第三部分 综合演练 第六章 海量数据处理 6.0 本章导读 6.1 关联式容器 6.2 分而治之 6.3 simhash算法 6.4 外排序 6.5 MapReduce 6.6 多层划分 6.7 Bitmap 6.8 Bloom filter 6.9 Trie树 6.10 数据库 6.11 倒排索引 6.15 本章习题 第七章 机器学习 7.1 K 近邻算法 7.2 支持向量机 附录 更多题型 附录A 语言基础 附录B 概率统计 附录C 智力逻辑 附录D 系统设计 附录E 操作系统 附录F 网络协议 本文档使用 书栈(BookStack.CN) 构建 - 16 - 

17 .目录 注：上述所有的文章已于2014年6月30日基本停止更新（当然，如果有bug，请随时指出，一经 确认，立即修正）。所有进一步的修改、改动、优化请见2015年10月14日上市销售的纸质版 《编程之法：面试和算法心得》。感谢大家。 July、二零一四年八月十四日。 本文档使用 书栈(BookStack.CN) 构建 - 17 - 

18 .程序员如何准备面试中的算法 程序员如何准备面试中的算法 程序员如何准备面试中的算法 备战面试中算法的五个步骤 1、掌握一门编程语言 2、过一遍微软面试100题系列 3、苦补数据结构基础 4、看算法导论 5、刷leetcode或cc150或编程艺术系列 后记 程序员如何准备面试中的算法 备战面试中算法的五个步骤 对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来 说，备战面试中的算法，分为哪几个步骤呢？如下： 1、掌握一门编程语言 首先你得确保你已掌握好一门编程语言： C的话，推荐Dennis M. Ritchie & Brian W. Kernighan合著的《C程序设计语言》，和 《C和指针》； C++ 则推荐《C++ Primer》，《深度探索C++对象模型》，《Effective C++》； Java推荐《Thinking in Java》，《Core Java》，《Effictive Java》，《深入理解 Java虚拟机》。 掌握一门语言并不容易，不是翻完一两本书即可了事，语言的细枝末节需要在平日不断的编程练习中 加以熟练。 2、过一遍微软面试100题系列 我从2010年起开始整理微软面试100题系列，见过的题目不可谓不多，但不管题目怎般变化，依然是 那些常见的题型和考察点，当然，不考察任何知识点，纯粹考察编程能力的题目也屡见不鲜。故不管 面试题千变万化，始终不离两点：①看你基本知识点的掌握情况；②编程基本功。 而当你看了一遍微软面试100题之后(不要求做完)，你自会意识到：数据结构和算法在笔试面试中的 重要性。 本文档使用 书栈(BookStack.CN) 构建 - 18 - 

19 .程序员如何准备面试中的算法 3、苦补数据结构基础 如果学数据结构，可以看我们在大学里学的任一本数据结构教材都行，如果你觉得实在不够上档次， 那么可以再看看《STL源码剖析》。 然后，你会发现：大部分的面试题都在围绕一个点：基于各种数据结构上的增删改查。如字符串的查 找翻转，链表的查找遍历合并删除，树和图的查找遍历，后来为了更好的查找，我们想到了排序，排 序仍然不够，我们有了贪心、动态规划，再后来东西多了，于是有了海量数据处理，资源有限导致人 们彼此竞争，出现了博弈组合概率。 4、看算法导论 《算法导论》上的前大部分的章节都在阐述一些经典常用的数据结构和典型算法（如二分查找，快速 排序、Hash表），以及一些高级数据结构（诸如红黑树、B树），如果你已经学完了一本数据结构教 材，那么建议你着重看贪心、动态规划、图论等内容，这3个议题每一个议题都大有题目可出。同时， 熟悉常用算法的时间复杂度。 如果算法导论看不懂，你可以参看本博客。 5、刷leetcode或cc150或编程艺术系列 如主要在国外找工作，推荐两个面试编程网站：一个是http://leetcode.com/ ，leetcode 是国外一网站，它上面有不少编程题；另外一个是http://www.careercup.com/ ，而后这个 网站的创始人写了本书，叫《careercup cracking coding interview》，最终这本英文 书被图灵教育翻译出版为《程序员面试金典》。 若如果是国内找工作，则郑重推荐我编写的《程序员编程艺术》，有编程艺术博客版，以及在博 客版本基础上精简优化的编程艺术github版。除此之外，还可看看《编程之美》，与《剑指 offer》。 而不论是准备国内还是国外的海量数据处理面试题，此文必看：教你如何迅速秒杀掉：99%的海量数 据处理面试题。 此外，多看看优秀的开源代码，如nginx或redis，多做几个项目加以实践之，尽早实习（在一线互 联网公司实习3个月可能胜过你自个黑灯瞎火摸爬滚打一年）。 当然，如果你是准备社招，且已经具备了上文所说的语言 & 数据结构 & 算法基础，可以直接跳到本 第五步骤，开始刷leetcode或cc150或编程艺术系列。 后记 学习最忌心浮气躁，急功近利，即便练习了算法，也不一定代表能万无一失通过笔试面试关，因为总 本文档使用 书栈(BookStack.CN) 构建 - 19 - 

20 .程序员如何准备面试中的算法 体说来，在一般的笔试面试中，70%基础+ 30%coding能力(含算法)，故如果做到了上文中的5个步 骤，还远远不够，最后，我推荐一份非算法的书单，以此为大家查漏补缺(不必全部看完，欢迎大家补 充)： 1. 《深入理解计算机系统》 2. W.Richard Stevens著的《TCP/IP详解三卷》，《UNIX网络编程二卷》，《UNIX环境高级编 程：第2版》，详见此豆瓣页面； 3. 你如果要面机器学习一类的岗位，建议看看相关的算法（如支持向量机通俗导论（理解SVM的三 层境界）），及老老实实补补数学基础，包括微积分、线性代数、概率论与数理统计（除了教 材，推荐一本《数理统计学简史》）、矩阵论（推荐《矩阵分析与应用》）等.. 最后望大家循序渐进，踏实前进，若实在觉得算法 & 编程太难，转产品、运营、测试、运维、前 端、设计都是不错的选择，因为虽然编程有趣，但不一定人人适合编程。 本文档使用 书栈(BookStack.CN) 构建 - 20 - 

21 .第一章 字符串 第一章 字符串 本文档使用 书栈(BookStack.CN) 构建 - 21 - 

22 .1.0 本章导读 1.0 本章导读 本章导读 本章导读 字符串相关的问题在各大互联网公司笔试面试中出现的频率极高，比如微软经典的单词翻转题：输 入“I am a student.”，则输出“student. a am I”。 本章重点介绍6个经典的字符串问题，分别是旋转字符串、字符串包含、字符串转换成整数、回文判 断、最长回文子串、字符串的全排列，这6个问题要么从暴力解法入手，然后逐步优化，要么多种思路 多种解法。 读完本章后会发现，好的思路都是在充分考虑到问题本身的特征的前提下，或巧用合适的数据结构， 或选择合适的算法降低时间复杂度（避免不必要的操作），或选用效率更高的算法。 本文档使用 书栈(BookStack.CN) 构建 - 22 - 

23 .1.1 旋转字符串 1.1 旋转字符串 1.1 旋转字符串 题目描述 分析与解法 解法一：暴力移位法 解法二：三步反转法 举一反三 1.1 旋转字符串 题目描述 给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面 的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成 此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。 分析与解法 解法一：暴力移位法 初看此题，可能最先想到的方法是按照题目所要求的，把需要移动的字符一个一个地移动到字符串的 尾部，如此我们可以实现一个函数 LeftShiftOne(char* s, int n) ，以完成移动一个字符到字符串尾 部的功能，代码如下所示： 1. void LeftShiftOne(char* s, int n) 2. { 3. char t = s[0]; //保存第一个字符 4. for (int i = 1; i < n; i++) 5. { 6. s[i - 1] = s[i]; 7. } 8. s[n - 1] = t; 9. } 因此，若要把字符串开头的m个字符移动到字符串的尾部，则可以如下操作： 1. void LeftRotateString(char* s, int n, int m) 2. { 3. while (m--) 4. { 本文档使用 书栈(BookStack.CN) 构建 - 23 - 

24 .1.1 旋转字符串 5. LeftShiftOne(s, n); 6. } 7. } 下面，我们来分析一下这种方法的时间复杂度和空间复杂度。 针对长度为n的字符串来说，假设需要移动m个字符到字符串的尾部，那么总共需要 mn 次操作，同时 设立一个变量保存第一个字符，如此，时间复杂度为O(m n)，空间复杂度为O(1)，空间复杂度符合 题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。 解法二：三步反转法 对于这个问题，换一个角度思考一下。 将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转 （如，X=”abc”，那么X^T=”cba”），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字 符串的反转问题。 例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可： 1. 首先将原字符串分为两个部分，即X:abc，Y:def； 2. 将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。 3. 反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反 转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。 如下图所示： 代码则可以这么写： 1. void ReverseString(char* s,int from,int to) 2. { 本文档使用 书栈(BookStack.CN) 构建 - 24 - 

25 .1.1 旋转字符串 3. while (from < to) 4. { 5. char t = s[from]; 6. s[from++] = s[to]; 7. s[to--] = t; 8. } 9. } 10. 11. void LeftRotateString(char* s,int n,int m) 12. { 13. m %= n; //若要左移动大于n位，那么和%n 是等价的 14. ReverseString(s, 0, m - 1); //反转[0..m - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba 15. ReverseString(s, m, n - 1); //反转[m..n - 1]，例如Y->Y^T，即 def->fed 16. ReverseString(s, 0, n - 1); //反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc。 17. } 这就是把字符串分为两个部分，先各自反转再整体反转的方法，时间复杂度为O(n)，空间复杂度为 O(1)，达到了题目的要求。 举一反三 1、链表翻转。给出一个链表和一个数k，比如，链表为1→2→3→4→5→6，k=2，则翻转后 2→1→6→5→4→3，若k=3，翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→6→5，用程序实现。 2、编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串 操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。 3、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以 空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输 出“student. a am I”。 本文档使用 书栈(BookStack.CN) 构建 - 25 - 

26 .1.2 字符串包含 1.2 字符串包含 字符串包含 题目描述 分析与解法 解法一 解法二 解法三 解法四 举一反三 字符串包含 题目描述 给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断 字符串B中所有字母是否都在字符串A里？ 为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B) 比如，如果是下面两个字符串： String 1：ABCD String 2：BAD 答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。 如果是下面两个字符串： String 1：ABCD String 2：BCE 答案是false，因为字符串String2里的E字母不在字符串String1里。 同时，如果string1：ABCD，string 2：AA，同样返回true。 分析与解法 本文档使用 书栈(BookStack.CN) 构建 - 26 - 

27 .1.2 字符串包含 题目描述虽长，但题意很明了，就是给定一长一短的两个字符串A，B，假设A长B短，要求判断B是否 包含在字符串A中。 初看似乎简单，但实现起来并不轻松，且如果面试官步步紧逼，一个一个否决你能想到的方法，要你 给出更好、最好的方案时，恐怕就要伤不少脑筋了。 解法一 判断string2中的字符是否在string1中?最直观也是最简单的思路是，针对string2中每一个字 符，逐个与string1中每个字符比较，看它是否在String1中。 代码可如下编写： 1. bool StringContain(string &a,string &b) 2. { 3. for (int i = 0; i < b.length(); ++i) { 4. int j; 5. for (j = 0; (j < a.length()) && (a[j] != b[i]); ++j) 6. ; 7. if (j >= a.length()) 8. { 9. return false; 10. } 11. } 12. return true; 13. } 假设n是字符串String1的长度，m是字符串String2的长度，那么此算法，需要O(n*m)次操作。显 然，时间开销太大，应该找到一种更好的办法。 解法二 如果允许排序的话，我们可以考虑下排序。比如可先对这两个字符串的字母进行排序，然后再同时对 两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的 线性扫描需要O(m+n)次操作。 关于排序方法，可采用最常用的快速排序，参考代码如下： 1. //注意A B中可能包含重复字符，所以注意A下标不要轻易移动。这种方法改变了字符串。如不想改变请自己复制 2. bool StringContain(string &a,string &b) 3. { 4. sort(a.begin(),a.end()); 5. sort(b.begin(),b.end()); 6. for (int pa = 0, pb = 0; pb < b.length();) 7. { 本文档使用 书栈(BookStack.CN) 构建 - 27 - 

28 .1.2 字符串包含 8. while ((pa < a.length()) && (a[pa] < b[pb])) 9. { 10. ++pa; 11. } 12. if ((pa >= a.length()) || (a[pa] > b[pb])) 13. { 14. return false; 15. } 16. //a[pa] == b[pb] 17. ++pb; 18. } 19. return true; 20. } 解法三 有没有比快速排序更好的方法呢？ 我们换一种角度思考本问题： 假设有一个仅由字母组成字串，让每个字母与一个素数对应，从2开始，往后类推，A对应2，B对应 3，C对应5，……。遍历第一个字串，把每个字母对应素数相乘。最终会得到一个整数。 利用上面字母和素数的对应关系，对应第二个字符串中的字母，然后轮询，用每个字母对应的素数除 前面得到的整数。如果结果有余数，说明结果为false。如果整个过程中没有余数，则说明第二个字 符串是第一个的子集了（判断是不是真子集，可以比较两个字符串对应的素数乘积，若相等则不是真 子集）。 思路总结如下： 1. 按照从小到大的顺序，用26个素数分别与字符’A’到’Z’一一对应。 2. 遍历长字符串，求得每个字符对应素数的乘积。 3. 遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。 4. 输出结果。 如前所述，算法的时间复杂度为O(m+n)的最好的情况为O(n)（遍历短的字符串的第一个数，与长字 符串素数的乘积相除，即出现余数，便可退出程序，返回false），n为长字串的长度，空间复杂度为 O(1)。 1. //此方法只有理论意义，因为整数乘积很大，有溢出风险 2. bool StringContain(string &a,string &b) 3. { 4. const int p[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101}; 5. int f = 1; 6. for (int i = 0; i < a.length(); ++i) 本文档使用 书栈(BookStack.CN) 构建 - 28 - 

29 .1.2 字符串包含 7. { 8. int x = p[a[i] - 'A']; 9. if (f % x) 10. { 11. f *= x; 12. } 13. } 14. for (int i = 0; i < b.length(); ++i) 15. { 16. int x = p[b[i] - 'A']; 17. if (f % x) 18. { 19. return false; 20. } 21. } 22. return true; 23. } 此种素数相乘的方法看似完美，但缺点是素数相乘的结果容易导致整数溢出。 解法四 如果面试官继续追问，还有没有更好的办法呢？计数排序？除了计数排序呢？ 事实上，可以先把长字符串a中的所有字符都放入一个Hashtable里，然后轮询短字符串b，看短字符 串b的每个字符是否都在Hashtable里，如果都存在，说明长字符串a包含短字符串b，否则，说明不 包含。 再进一步，我们可以对字符串A，用位运算（26bit整数表示)计算出一个“签名”，再用B中的字符到A 里面进行查找。 1. // “最好的方法”，时间复杂度O(n + m)，空间复杂度O(1) 2. bool StringContain(string &a,string &b) 3. { 4. int hash = 0; 5. for (int i = 0; i < a.length(); ++i) 6. { 7. hash |= (1 << (a[i] - 'A')); 8. } 9. for (int i = 0; i < b.length(); ++i) 10. { 11. if ((hash & (1 << (b[i] - 'A'))) == 0) 12. { 13. return false; 14. } 15. } 本文档使用 书栈(BookStack.CN) 构建 - 29 -