小猪快跑，算法快刷(第一部分)

本篇是快刷《剑指Offer》的第一部分，涉及22道基础习题。

在文章的编排上，本人将每两道题目关联于一个球员名，这样做的目的是为了方便查询。第一部分选取的球员全部来自早些年的巴塞罗那俱乐部，他们未必曾经在同一时期的巴萨效力，但是却是本人在当时进行足球游戏的主力，这些球员名在本人的大脑查询的时间复杂度是O(1)。

梅西

梅西 -> 第一个只出现一次的字符
   \
    -> 连续子数组的最大和

第一个只出现一次的字符

这一题的关键在于字符换算为int类型，既有限，又有界。所以可以用一个最大界作为长度声明一个数组。这个数组相当于一个哈希表，将char字符转换为int类型相当于构造的一个index方法，每个槽位不再保存链表的头节点，而是保存index()到相同位置的元素的个数。

考虑鲁棒性应该进行判空指针操作，char默认’\u0000’，等价于(char)0。

连续子数组的最大和

这一题的关键在于用两个零时变量分别来记录当前数组和的值以及历史最大和的值，每当前进一个数，就要试着更新这两个零时变量。

同样需要进行判空指针的操作。

罗纳尔迪尼奥

罗纳尔迪尼奥 -> 数组中只出现一次的数字
   \
    -> 数字在排序数组中出现的次数

数组中只出现一次的数字

首先要了解题目给的条件，条件说一个整型数组里，除了两个数字，其它数字都出现了两次。要求时间复杂度是O(n)，空间复杂度是O(1)。

所以不能用梅西(1)题那种思路，因为这里的数字即无限，也无界。但是它奇怪的地方在于，不要求检出的数字都出现两次，所以可以考虑用异或运算。

比如现在有三个数：2，4，2。如果对它们进行异或，那么2^4^2返回的是4，所以如果将数组中所有的数字都异或一遍，最后输出就是两个只出现一次的数字异或的值。

两个数异或之后，相同位都是0，不相同位都是1，实际上不相同位可能有很多，但其实只需要观察一个位置，将这个位置称为不同位，这个位置如果再分别和这两个数异或，会出现不同的结果。

于是继续将第一遍异或的结果与整数数组的数字异或，观察上一步提到的不同位。由于大部分数字会再一次算两遍彼此“中和”，所以最后的得到的就是两个要求的数字。

数字在排序数组中出现的次数

题目可以简单描述为：已知一个排序数组，然后给出一个数字，输出该数字在数组中出现的次数。这题为了减小时间复杂度，可以先计算出给出的数字第一次出现在数组的索引，然后计算出最后一次出现在数组的索引，这样，最后只需要相减就可以了。

埃托奥

埃托奥 -> 两个链表的第一个公共节点
   \
    -> 最长不含重复字符的子字符串

两个链表的第一个公共节点

这个题目主要的问题是两个链表长度不一样，这样的话遍历的时候不好同步，解决的方式是让长度长的链表先“走两步”。这样能成功主要是利用了公共节点存在的特性，即公共节点在“Y”形交叉点往下就都是相同的部分了，只要两个链表遍历的起点到尾节点的距离相同，那么一旦进入“Y”形交叉点。两个链表就完全同步了。

最长不含重复字符的子字符串

这题的意思是输入一个字符串，求其最长不含重复字符的子字符串的长度。单从描述上来看，此题和连续子数组的最大和类似，而组成输入字符串的字符既有限，又有界，看来可以使用哈希表来解。与第一个只出现一次的字符不同的是，这里哈希表不需要保存字符出现的次数，而是保存在字符串中出现位置的索引(实际编码过程中，因为int数组的元素默认为0，所以对保存的索引稍微进行改动)。

哈维

哈维 -> 二叉树的深度 && 输入二叉树的根节点，判断该树是不是平衡二叉树
   \
    -> 把字符串转换成整数

二叉树的深度 && 输入二叉树的根节点，判断该树是不是平衡二叉树

树的深度用递归特别容易解决，要记得考虑根节点为null时，要返回0，这不仅为程序提供鲁棒性，还是递归的一个基础，通常来说，采用递归函数，要考虑是否产生调用栈爆棚以及是否进行了重复计算。

在判断一个二叉树是不是平衡二叉树时，可以先递归计算二叉树的深度，在计算中，设置一个全局标志位flag，起初值为true，然后添加代码判断左右深度差的绝对值是不是大于1，大于1表示不平衡，那就将flag设为false，递归的过程中只要有一次判断为false，那么flag就始终为false了，这也是为什么一开始将标志位设置为true的原因。

把字符串转换成整数

可以不断遍历字符串的每一位进行转换。这里要注意正负号的判断，正号可以强写，也可以不写，将判断是否有正负字符的存在和判断数字是正是负两个功能分别处理，方便厘清逻辑。

伊涅斯塔

伊涅斯塔 -> 二叉树的镜像
   \
    -> 二叉搜索树与双向链表

二叉树镜像

用递归就能解决问题，在递归子树之前会调用swap函数，该函数的计算不是一个重复计算。

二叉搜索树与双向链表

该题的要求是，不能创建任何新的节点，将二叉搜索树转换成一个排序的双向链表。在二叉搜索树中提到“排序”，首先想到的就是中序遍历，在递归中遵循“递归函数 -> 根 -> 函数”的模式。在函数之外设置两个参数head和tail，分别指向已经遍历出的链表解构的头节点和尾节点。在整个递归中，真正对head进行赋值只有一次，而通过不断向下递归，这个head最终指向的是搜索树中值最小的那个点。

难点在理解右子树和根节点的连接，实际在不停向下递归右子树的时候(convertNode(root.right))，最开始操作的是右子树中值最小的节点，该节点没有左子树，执行如下代码：

tail.right = root;
root.left = tail;
tail = root;

因为此时tail就是根节点，所以通过上面的代码根节点就和右子树值最小的节点产生了双向连接。

德科

德科 -> 二叉搜索树的第K个节点
   \
    -> 从上往下打印二叉树

二叉搜索树的第K个节点

递归中找准“全局变量”，对于全体递归中的单次实体，“全局变量”是有记忆的，是被共享的。所以k应该是一个“全局变量”，递归中不断增加的计数值也应该是一个“全局变量”。

从上往下打印二叉树

这题的要求是层次遍历，使用队列来实现，要考虑边界问题。

阿比达尔

阿比达尔 -> 二叉树中和为某一值的路径
   \
    -> 从尾到头打印链表

二叉树中和为某一值的路径

这题要求打印所有满足条件的路径，所以需要装列表的容器：List> lists，在添加的时候要注意列表深浅拷贝的问题。通过递归其实遍历了所有可能的路径，只不过中途一旦有满足条件的列表存在，就添加到列表容器中。

构造遍历的函数时，可以通过最小的模型来思考。

从尾到头打印链表

题目的意思如其名，栈和递归都可以很快实现这一题。

普约尔

普约尔 -> 二叉搜索树的后序遍历序列
   \
    -> 包含min函数的栈

二叉搜索树的后序遍历序列

需要注意的有两点，一是这一题假设了任意两个数字都互不相同，二是要考虑只有一个节点的树的情况。这题的思路是首先找到后序遍历的特点，即最后一个数字是根节点，除却最后一个元素，数组余下的元素分为两部分，一部分是左子树的点，且都小于根节点；另一部分是右子树的点，都大于根节点，只要不满足这种条件那么就不是二叉搜索树后序遍历的结果。

for (int i = head; i < tail; i++) {
    q = i;
    if (squence[i] > k) {
        break;
    }
}

for (int j = q; j < tail; j++) {
    if (squence[j] < k) {
        return false;
    }
}

一开始这样编写，可能会出现错误。比如输入4, 6, 7，q最终表示了一个小于k的元素的数组索引，在第二个for循环中会返回false。

包含min函数的栈

此题的难点在于可能存在多个相同值的元素，而且一旦推出一个最小值，可能会遇到复杂情况，比如次小值是多少，需要它的时候它能出现并顶上来？又比如存在多个和推出的元素一样值为最小值的元素，用什么机制来判断当前栈的最小值不需要更改？

实际编码中，要考虑栈为空的情况，在这种情况下，调用peek()会出现异常。push和pop都应该两个栈同步。

马奎斯

马奎斯 -> 重建二叉树
   \
    -> 丑数

重建二叉树

题目要求根据二叉树的前序和中序遍历的结果，重建二叉树。题目还假设这些遍历都不含重复的数字。

基本思路：前序遍历首先遍历出根节点，然后在中序遍历中找到值等于这个根节点的点，在中序遍历的序列中，此值之前的序列是根节点的左子树中序序列，此值之后的序列是根节点的右子树中序序列，根据这些线索又可以在前序序列中找到左子树的前序序列以及右子树的前序序列，接着就可以进行递归了。

这题的难点在于索引的计算，比如本人在实际编程中计算的索引见下列代码中函数的参数：

root.left = reConstructBinaryTree(l1, head01 + 1, head01 + temp - head02,
        l2, head02, temp - 1);
root.right = reConstructBinaryTree(l1, head01 + temp - head02 + 1, tail01,
        l2, temp + 1, tail02);

再就是鲁棒性也要考虑，除了对输入的参数进行鲁棒性，输入的两个数组如果不满足分别为某一二叉树的前序遍历和后序遍历时，也要及时返回null：

for (int i = head02; i <= tail02; i++) {
    if (l1[head01] == l2[i]) {
        temp = i;
        break;
    } else if (i == tail01) {
        return null;
    }
}

丑数

丑数可以表示为 2^a * 3^b * 5^c，其中a、b、c为大于等于0的整数。现在求从小到大第1500个丑数。出题者的意图是希望找到一个时间复杂度较小的解题方法。对于已经排好的丑数序列来说，每新增加一个丑数，就是之前的某个已排好位置的丑数的2、3或5倍。将它们互相比较，取其中最小的一个数字安排进序列中。

阿尔维斯

阿尔维斯 -> 按之字形顺序打印二叉树
   \
    -> 栈的压入、弹出序列

按之字形顺序打印二叉树

     10
   /    \
  6     14
 / \   /  \
4   8 12  16

假设现在有一二叉树如上图，按之字形打印就是说打印出[[10], [14, 6], [4, 8, 12, 16]]。

一种解题思路：此解题思路也是本人采用的思路，用两个栈分别存储二叉树的奇数层和偶数层。因为栈是LIFO，所以pop出存奇数层栈的node后，对其求左子树和右子树，并按此顺序依次压入偶数层栈；pop出存偶数层栈的node后，对其求右子树和左子树，并按此顺序依次压入奇数层栈；如此往复遍历完树的全部的节点。

此题的有一些小坑需要注意，比如：

• null被压入栈后，栈并不为空，所以两个栈交替压入之前要检测node是否为null；
• 考虑到外层while的判断条件和内层遍历奇数层的while的判断条件相同，本人打草稿的时候，直接使用遍历奇数层的while内嵌一个遍历偶数层的while，如果测试样例小(比如三层)，则不会发现错误；
• 给程序网站编写提交的时候，只有一个指向null的node指针时要求返回[]，list要注意深浅拷贝，以及每次声明新的list应该在while之外；

栈的压入、弹出序列

这个题是一道判断题，给出两个整数序列s1和s2，序列s1表示栈的压入顺序，判断序列s2是否为序列s1的弹出顺序。

由于输入是不会回退的，本人以输入的步进来构造for循环语句，基本的逻辑如下：

• 如果栈为空或者peek()的值不是s2当前应该弹出的值，那么就不停push()输入序列的值，直到该值等于s2当前应该弹出的值，如果遍历完s1序列的值仍然没有等于s2当前应该弹出的值，则返回false，说明序列s2不是序列s1的弹出顺序；
• 如果peek()的值就是s2当前弹出的值，则对栈进行pop()，将指向s2当前值的索引j加1，指向下一位，由于这一步没有进行push()操作，而每次for循环指向输入序列s1的索引i都会自动加1，所以，在这一步还要对i进行减1的操作；
• 当for循环结束后，理想的状态是j的大小等于s2的长度，这样就说明序列s2是序列s1的弹出顺序，否则结论相反。

这里需要注意的是鲁棒性，要考虑数组的null和空，s1和s2长度不相等的情况等；另外，本程序for循环里设置的是i <= s1.length，由于本人把pop()迭代的逻辑一并也写在for循环中，i即使==s1.length，也并不代表程序就返回false。

巴尔德斯

巴尔德斯 -> 二进制中1的个数
   \
    -> 旋转数组的最小数字

二进制中1的个数

这个题的意思是：一个整数可以用二进制表示，实现一个函数计算这个二进制表示的形式由多少个1组成。

用位运算巧妙算法的原理是：假设一个数字二进制表示的形式存在多个1，最小位置的1存在两种可能情况，一种是自己处在个位；另一种是自己不处在个位，后面全部都是0。本人以1000举例，当减去一个1后，变成0111，此时两者相与就变成0000，通过这种方法不断削减1。

旋转数组的最小数字

这题的关键在于鲁棒性测试，题目给出的是一个递增的数组，并没有限定数组的元素不能重复，假设存在一个数组[1, 0, 1, 1, 1]，旋转后就变成了[1, 1, 1, 0, 1]，那么只能通过顺序查找的方式找出最小的元素，而不能采用二分查找。

小结

这套阵容在《剑指Offer》里攻守平衡，看看下一套阵容能否与之匹敌。