本来这篇文章标题我想起成《关于 vector 的两个小坑》，后来想想，其实也不算是坑，还是自己对原理性的东西理解的没做那么透彻。工作中遇到的很多问题，后来归根到底都是基础不牢靠。

我是 2015 年参加校招，这个过程可谓是一波三折。先是比较顺利地拿到了阿里的实习 offer，然后在快要转正的时候被通知「拥抱变化」，接着在腾讯和小公司的 offer 之间抉择，然而选择了小公司之后又被毁约三方协议，最后重新申请腾讯 offer 成功。

读了《C++ 的门门道道 | 技术头条》这篇文章之后有很多共鸣，可以说是近期看过的最好的技术 tips 文章了。按照这篇文章里面讲到的几点，结合工作上实际遇到的问题，我也来说一下我的感受。

工作上有大量协议采用 Google Protocol Buffer，关于 Protobuf 的简单介绍可以看 IBM 的《Google Protocol Buffer 的使用和原理》这篇介绍。简单来说，Protobuf 的优点是（相比 XML）更小、更快、更简单，同时可以向后兼容。缺点的话，对我日常工作影响比较大的就是可读性较差，因为 Protobuf 压缩的时候会做序列化，生...

核心的思路是：既然要达到O(n)的复杂度，那么就要保持窗口内的最大值在窗口边界上。达到这个效果的方法就是滤掉窗口中没用的元素。维护一个双向队列，队列保存数组的下标，每当有新元素进入队列时，从队尾开始，删掉连续的比新元素小的元素，然后将其插入到队列末尾。之所以可以这样删掉元素是基于：这些元素永远都不会...

显然在平时使用中，ArrayList<Integer>()和new ArrayList<String>()是完全不同的类型，但是在这里，程序却的的确确会输出true。

Scrapy是Python非常有名的爬虫框架，框架本身已经为爬虫性能做了很多优化：多线程、整合xpath和图片专用管道等等，开发人员只要专注在功能需求上。

用Java暴力是可以过的，思路也很简单：补充完成之后的回文串中心必定在原字符串中，所以原字符串以第一个字符为起点必然存在至少一个回文串（长度可以为1），那么任务就变为找到原字符串中以第一个字符为起点最长的回文串，找到之后剩下的工作就是把剩余部分的翻转补充到原字符串头部即可。

由于之前没有没法过相关功能的经验，一开始来真不知道从哪里入手。当然，这个解决，google一下立马就发现了ffmpeg，网上讲解用Java+ffmpeg来进行视频转换的文章也不在少数，我主要参考的这篇文章。

DouBanReader是一个自动根据你的豆瓣读书标记生成读书报告的脚本。适用对象是像我这种豆瓣读书的重度用户，会在豆瓣上标记自己读过的每一本书，并且会很负责地打分与写review。对于这样的用户，这个项目可以帮你一键生成读书报告，并且格式化成MarkDown格式，之后你再发布到各大博客平台或者自己转成其他格式（HTML，PDF...

典型的动态规划题。维护一个二维数组dungeon，dungeon[i][j]表示从第i行第j出发到终点所需要的最低血量（包含当前位置的消耗），最低血量不大于1。

要求连续元素的最大差值，那必然要排序，但是又要求在O(n)的复杂度内完成，自然就想到了桶排序。维护left和right两个数组，left[i]表示第i个桶的最左端元素，right[i]表示第i个桶的最右端点元素。除最后一个桶之外，每个桶都是前闭后开，最后一个桶是前闭后闭。当元素落到相应的桶内就更新相应桶的最左最右元素值，当所...

其实直接遍历也是可以也可以AC，但是更加优化的解法应该是采用二分查找的思想。如果中间值比起点大就收缩起点，如果中间值比终点大就收缩终点，直到收缩到起点和终点相邻，也就是找到了翻转的部分。这里需要注意的是，数组可能是没有翻转过的，所以mid的初值赋0。

题目本身不难，一次AC可能有点困难，因为要考虑的东西还是挺多的。两层循环，外层遍历所以点，内层遍历外层点之后的所有点，同时在内层循环用一个HashMap来保存每个斜率对应的，这样在内存循环中，斜率相同就代表是在同一条直线上了。这里要注意的有两点：

LRU Cache 数据结构用列表。get()和set()方法就不多讲，重要的是遇到下两种情况： 元素被访问过，要将其放到列表头部，实现函数：moveToHead(Node node) 元素个数达到最大值，删除尾部元素，实现函数：removeTail() 同时为了快速选中元素，就采用HashMap<Integer, Node>来保存键值。 {代码...}

树的前序和后序遍历是树相关算法的基本。就不多加解释了，直接上代码。 Binary Tree Preorder Traversal {代码...} Binary Tree Postorder Traversal {代码...}

递归，基本属于暴力求解。但是纯暴力应该是过不了的，参考网上的办法，增加了一个unmatch集合，类型是HashSet，用来存放那些已经被验证过无法匹配的字符串，这样可以剪掉很多分支。

节点中需要拷贝的两个引用是next和random。next引用比较好拷贝，相当直接复制普通列表。而对于random则需要目标节点已存在才比较容易些拷贝代码，采用的办法就是构造一个HashMap，其中key是原节点，value是拷贝节点，在拷贝random引用的过程中，直接用map.get(node.random)来获取相应的目标节点即可。

Candy 双向爬坡。从左到右爬一边，再从右到左爬一边。再累加所有值即可。 {代码...}

动态规划。维护一个boolean[][] isPalindrome二维数组，isPalindrome[i][j]表示s.substring(i, j)是否为回文串。递推公式：检查s.charAt(begin)和s.charAt(end)是否相等，如果相等就检查isPalindrome[begin + 1][end - 1]的值，也就是对一个isPalindrome[begin][end]的赋值复杂度是O(1)。另外维护一个numOfCuts数组，num...

那么这种『显然要遍历所有元素，但是却只给了O(n)的复杂度』，这样就想到了HashMap。把数组中的每个元素都放入一个HashMap中为key，value为boolean类型，表示该元素有没有访问过。然后，对于数组中的每个元素，要是没有被访问过，就对其进行计数——往前遍历及往后遍历，直到下一个元素不存在于表中为止。那么这样就保证了...

动态规划+深度优先搜索。把大问题（求整棵树的路径最大值）拆分成小问题（每颗子树的路径最大值），递推公式为：当前树的路径最大值=max(左子树的路径最大值, 右子树的路径最大值)+当前根节点的值。以此来推出最后全树的最大路径值。

树的广度优先搜索题。记录下每一层的节点总个数，然后根据广度优先搜索的原则进行遍历，将非null节点都加入到队列中，对于同一层中的节点，将其next指向队列中的下一个节点即可。

动态规划题。先用二维动态规划的思路解释下：设match是动态规划表，其中match[i][j]表示S.substring(0, i)对T.substring(0, j)有几种组成方式，递推公式为：

一旦有两个位置的节点被交换了，那么中序遍历就会出现有两个：Node[i] > Node[i + 1]其中i是错误位置，Node[j] < Node[j - 1]其中j是错误位置，遵循这个规律，找到相应的Node[i]和Node[j]对其进行交换（只交换val值）即可。

动态规划题。用一个二维（也可以简化成一维的）boolean数组match[i][j]来表示str3.substring(0, i + j)能不能由str1.substring(0, i)和str2.substring(0, j)组成，递推公式：

提前检验的内容就是检验两个字符串的内容是否相同，这个内容是否相同指的是：两个字符串所包含的字符种类和每种字符出现的个数是否相同，如果这个不同就可以直接返回，不需要执行接下来的代码。

这一题的核心算法其实和Largest Rectangle in Histogram一样，对每一行都求出每个元素对应的高度，这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积，那么这个问题就变成了Largest Rectangle in Histogram，用相同的方法求解就行了。总结来说就是对矩阵中的每一行，执行一遍Largest Rectangle in His...

这道题目有一个规则要掌握：当图形处在上升期时（height[i] < height[i + 1]），其实是不用计算面积的，因为在这种情况下再往前移动一格（i -> i + 1）所能得到的面积必然更大；当图形处在下降期时（height[i] > height[i + 1]），就要开始计算当前矩形的面积了，但是这个时候只知道右端点，如何知道左端点在哪...

扩充窗口：将窗口的右端点尽力向右扩展，直至到包含所有标准表中的字符（窗口中的每个有效字符的数量大于等于标准表中对应字符的数量），一旦窗口中的有效字符的总数达到字典字符串的长度，就停止扩充。