在上一篇博客中有原有提到分享一下面试题，最近也是才能新公司入职没多久，忙着熟悉环境，加上前不久出去玩了一趟(顺便写了篇游记，感兴趣的可以看一看)。所以一直没时间整理博客，这段时间周末终于闲下来，就趁着周末就记录了几个面试过程中碰到的算法题。

本篇博客不打算介绍那些高逼格的算法(如winnow，bagging，ada boost等等)，就讲讲最近在面试过程中遇到的算法题以及面试的时候给出的答案(出场率比较高的算法题我都列出来了，其他的就不说了)。算法可以说是解决所有问题的基石。很多东西都可以转换为算法问题，学习算法最大的作用就是更清楚地了解了很多东西。正所谓是，知其然更知其所以然。很多人都觉得程序就是数据结构+算法+适当的注释。不学算法，那就不要学编程了。虽然说可能没这么夸张，因为实际上还是有很多小项目是不需要太多算法的，都是代码一个劲的往上叠加就行了。但是就算没那么夸张，但是作为一个程序员，逻辑思维就是算法的思路还是很重要的。---这段话是某公司一个面试官说的。

再次重申一下，这里只是列出一些最近遇到的算法面试题，拿出来给大家分享一下面试经历(仅是常见算法方面的经历，还有一些不常见的就懒得列举了，技术方向的不介绍)。还有就是我的答案。ps：无论是算法题还是答案都不具任何代表性也并非是正确答案，仅仅是我面试的时候给出的答案，只是分享而已。另外，对于我所列出的问题以及给出的答案，如果有园友有疑议或者是更好的解决办法，那就分享出来！ 写算法是一个非常过瘾的享受！

顺便说一嘴，因为有一次面试面试官是在伦敦，所以只能远程面试，我们是用collabedit，这个东东还是很受用的。 

----算法百科摘自百度百科(ps:不摘点介绍性的文字在这，直接开门见山的来题目。感觉有点duangduang的。性急的可以直接跳过此处！)

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

所有答案仅供参考，并非标准或者正确答案，只是在面试的时候给出的答案而已，所以欢迎大家给出更好的答案

所有答案都是面试的时候notepad写的，回来以后我没有double check，直接贴出了代码，其中有一部分我后面附加了图。如果大家有兴趣，我也建议大家可以先用notepad写写看，因为算法这种东西本身就是一个思路而已。没必要用vs。

//------------------------------------------------------------------------------ // <copyright file="Runner.cs" company="CNBlogs Corporation" owner="请叫我头头哥"> // Copyright (C) 2015-2016 All Rights Reserved </copyright> TestApp { using System; using System.Collections.Generic; using System.Text.RegularExpressions; class Runner { static void Main(string[] args) { int[] arr = { 3, 5, 6, 7, 8, 9, 14, 23, 45, 56, 63, 72, 87, 91, 92, 93, 95, 97, 98, 534, 555, 676, 878, 988, 1365 }; int number = 555; int result = Search(arr, number); Console.WriteLine(result); Console.ReadKey(); } Search(int[] arr, int number) { int result = 0; if (arr == null || arr.Length == 0 || number > arr[arr.Length - 1] || number < arr[0]) { result = -1; } else { result = Bisearch(arr.Length - 1, arr, number); } return result; } Bisearch(int endIndex, int[] arr, int number, int startIndex = 0) { int result = 0; if ((endIndex - startIndex) < 2) { for (int i = startIndex; i <= endIndex; i++) { if (arr[i] == number) { result = i; break; } else { result = -1; } } } else { if (arr[startIndex] <= number && number <= arr[(endIndex + startIndex) / 2]) { Bisearch((endIndex + startIndex) / 2, arr, number, startIndex); } else { Bisearch(endIndex, arr, number, (endIndex + startIndex) / 2 + 1); } } return result; } } }

关于这题我在面试回来的路上，构思了一下思路，大致是这样的：

当然，我这个肯定不是最好的solution。