最近在准备面试的时候，特意的留意了一下算法，现在越来越多的公司在面试的时候，很看重算法能力。这篇文章，算是自己在阅读《剑指offer》后的一点点心得吧。
数组 哈希表
数组的哈希表算是最简单的两种数据结构了。这两种数据结构有一个非常重要的特点，就是可以通过O(1)的时间复杂度，找到某个值。
如何理解这个O(1)呢？就是如果我希望找到长度为n的数组array的下标为k的值，那我直接引用array[k]就可以找到它，这个查找的速度和array的大小n没有关系。这就是O(1)的时间复杂度。
如果需要遍历一遍数组才能找到想要的值，则时间复杂度就是O(n)了，如果需要遍历两遍，则时间复杂度是O(n^2)。提到了时间复杂度，就不得不提提空间复杂度。时间和空间总是此消彼长的，我们做优化的时候，经常根据实际的项目要求，用时间换空间，或用空间换时间。如果真的能同时降低时间复杂度和空间复杂度，那真的是非常好的算法了。
对于数组和哈希表具有O(1)时间复杂度的查找特性，我们经常可以通过辅助数组或哈希表的方法，达到空间复杂度换时间复杂度的目的。比如如果一个算法，需要O(n2)的时间复杂度，和O(1)的空间复杂度，那么我们在优化的时候，一个基本的思路，就是能否通过一个辅助的数组或哈希表，即O(n)的空间复杂度，将时间复杂度从O(n2)降为O(n)。
数组中，最常见的算法题，就是各种排序了，我觉得我们至少要清楚快速排序法，以及冒泡排序法能最基本的排序算法。很多数组类型的问题，都可以通过这种问题衍生。
字符串
和数组最接近的数据结构，也是和实际项目息息相关的，大概就是字符串了。这类问题通俗易懂，又可以考察数组和指针的基本用法，很多面试题的解答思路也非常巧妙，因此这部分内容是不容忽视的。
比如《剑指offer》中的面试题5
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如，输入"We are happy."，则输出"We%20are%20happy."
对于任何题目，我们首先要考虑异常情况，一个优秀的解答，一定要具备正确性，以及鲁棒性。正确性是最基本的要求，也就是说输入和输出在正常的情况下是满足条件的，而鲁棒性就要求对异常的考虑了。实际上在实际工作中，对异常情况的考虑，也是非常重要的。
对于这道问题，首先需要考虑的就是，如果输入是null，应该如何处理？是否可以改变原有字符串，还是输出新的字符串？按照题目要求，字符串的长度将变大，是否输出的空间足够容纳这些字符串？
假如我们考虑可以破坏原有的数据，那么可以设计如下的函数
int replaceSpace(char* src, int length)；
这里，src为源字符串，以及最后输出的字符串，length是src的大小，返回值设置为int类型，可以返回输出的字符串的大小，特别的，如果是-1可以认为是转换失败。
转换的思路，有两种，一种是从头到尾的遍历，将字符串替换为%20，这种方法，每次遇到空格的时候，都要插入新的字符，并且将后面的所有字符都往后依次挪位，这样的做法，没有用额外的存储空间，因此空间复杂度为O(n)，而由于需要遍历一遍字符串，并且在每次遍历的时候，都有可能向后移动所有的字符，因此是一个双重循环，因此时间复杂度为O(n2)。
当然我们会考虑优化的方案，是否可以将时间复杂度降为O(n)呢，我们想到可以从尾向前遍历数组，我们首先可以遍历一遍字符串，找到空格的个数，从而计算出最终的字符串的长度，在这里，由于遍历了一遍字符串，因此时间复杂度为O(n)，确认了最终的字符串长度后，我们可以定义两个指针，一个指向源字符串的尾部，另一个指向最终字符串的尾部，将源尾部的字符不断的拷贝到最终尾部，如果遇到空格，则替换为%20，这样，当两个尾指针相等时，循环结束。这样的拷贝，也用了O(n)的时间复杂度。因此总共用了O(n) + O(n)的时间复杂度，实际上还是O(n)。因为O(n) + O(n)和O(n)是同阶的。
这样，我们通过O(n)的时间复杂度，以及O(1)的空间复杂度，完成了这个空格的转换。在这道题中，我们运用了两个指针的技巧，这个技巧非常常用，我们在后面的算法中还会遇到类似的解决思路。
另一道我觉得非常好的题目，是面试题17
题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999.
这个题看似很简单，实际上确是暗藏陷阱。这种看似简单的题目，就是很容易理解题目的含义，我们更要特别留意，找到题目中可能存在的陷阱。对于这种类型的题目，如果不仔细思考，找到关键，就很容易上当。这类问题是典型的数字和字符串相结合的问题，一个直观的方案，就是找到n位最大树，即10n - 1，然后从1开始打印，一直到这个最大的数。看起来道理完全讲的通，似乎很完美的解决思路，却已经在不知不觉中掉入了出题人的陷阱。
你找到的那个数10n - 1，真的可以用计算机的数字来描述吗？简单的用int可以吗？显然不可以，因为n可以很大，则10n - 1就是一个更大的数，显然完全可以超出int的范围。当没有一个合适的整型结构可以容纳任意大的数字的时候，我们就要考虑万能的字符串了。不管多大的数，我们当然都可以通过字符串来承载，这里就涉及到一个问题，就是如何完成一个字符串表示的数字的累加？实际上这也不难，我们只要模拟数字的每一位相加，并且进位就可以了。
这种字符串和整数相结合的题目，可以很好的考察对字符串以及数字的理解，类似的题目，比如输入一个整数，转换成字符串，这些看似简单的题目，实际上都暗藏杀机，需要仔细的考虑清楚，不要掉入陷阱。
再和大家分享一道题，是面试题19
题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和”ab*ac*a”匹配，但与"aa.a"和"ab*a"均不匹配。
正则匹配是一个非常重要的领域，在实际应用中也非常复杂。这个题目挑选了正则匹配中的两个典型符号'*'以及'.'，实际上已经大大化简了正则匹配的难度。虽然已经化简了难度，但对于没有接触过正则表达式的同学，还是比较复杂，尤其是'*’，由于'*'是和它上一个字符强关联的，可以是零个或多个，所以组合起来情况比较复杂。
这个题目的另一个特点是，题目本身构成了子问题。比如，判断aaa和a.a是否匹配，则可以将问题转换为，首字母a和a匹配，然后判断剩余的字符串是否匹配，也就是aa和.a是否匹配，这样，问题转换成了子问题。满足这种条件的问题，我们往往可以采用递归的思想对题目进行解答。
确定了通过递归方法的解题思路，我们再继续分析具体的思路，也就是如何将问题转换为子问题。我觉得递归问题有两个要点，一个就是终止判断，另一个就是将问题分解为子问题。
我们可以做如下的设计
bool isMatch(char* src, char* pattern);
其中src为输入的字符串，而pattern为输入的正则表达式，返回值是bool类型，表明是否匹配。解任何问题，首先就是要做异常处理，比如当src或者pattern为null的时候，我们应该判断匹配还是不匹配？这点我们可以和面试官交流。
异常情况处理完毕了，我们就要考虑递归问题的终止条件了，实际上终止条件有两种，其一是*src == '\0' && *pattern == '\0'，这种情况下，表明src和pattern都成功的匹配到了最后，因此是match的，返回true。另一种情况是*src != '\0' && *pattern == '\0'，也就是说src还没有走到最后，但是pattern已经走到了最后，这种情况下，显然两者是不匹配的，直接返回false。
说到这里，可能有的同学会想，如果*src == '\0' && *pattern != '\0'的情况是否也是递归的终止条件呢？这种情况下，src已经走到最后，但是pattern还没有走完，那么在这种情况下，我们可以判断两者是否匹配吗？答案是不一定。比如""和"a*"，字符串已经走到最后，但是pattern还有后面的"a*"，在这种情况下，两者也是匹配的，因为'*'可以表示零个前面的字符，也就是说"a*"也可以理解为""。因此在这种情况下，我们是不能轻易下结论的。因此，我们在分析问题的时候，一定要找到递归终止的真正条件，对于一些伪终止条件，我们要有自己的判断。
解决完异常处理，以及递归的终止判断，最后要做的就是找到转换为子问题的方法。前面已经分析过，如果有'*'的时候，情况就比较复杂，因此我们可以分类讨论。首先，就是如果src[1] != '*'的情况，在这种情况下，比较容易处理，就是要判断(*src == *pattern) || (*pattern == '.' && *src != '\0')，这里的判断就是两个字符是否相等，或者pattern为'.'的情况，因为'.'在正则表达式中可以代表所有的字符。如果两者相等，我们就将问题转换为了子问题，即isMatch(++src, ++pattern)，我们成功的将src和pattern各往后推进了一位，问题转换为了子问题。如果上面的判断不相等，说明不匹配，直接返回false。
最后，处理最复杂的情况，也就是src[1] == '*'的情况，实际上这种情况下，也可以转换为子问题，考虑到'*'可代表0个前面的字符，问题可以转换为isMatch(src, pattern + 2)。另外，考虑到'*'还可以代表多个前面的字符，问题还可以转换为isMatch(++src, pattern)，这样，这两种情况完全覆盖了'*'的含义，因此问题也成功的转换为了子问题。
于是我们做了异常处理，做了递归的终止处理，并且可以将问题转换为子问题。有了这三部曲，这个问题就可以圆满的解决了。
网友评论