2020最新面试宝典带答案数据结构算法专题

注：答案均以红色字体标注！答案仅供参考！为提供学员的实操性! 此处答案均以截图提供！希望学员能以实操理解！

一．数组专题 （要求：尽量不要使用系统框架提供的Api;自己设计)

1.在一个给定的从1到100的整型数组中，如何快速找到缺失的数字？

2.如何找到一个给定的整型数组中的重复数字？

3.在一个未排序的整型数组中，如何找到最大和最小的数字？

4.在一个整型数组中，如何找到一个所有成对的数字，满足它们的和等于一个给定的数字？

5.如果一个数组包含多个重复元素，如何找到这些重复的数字？

6. 用C# 实现从一个给定数组中删除重复元素？

7. 如何利用快速排序对一个整型数组进行排序？

8.如何从一个数组中删除重复元素？

9.用 C#如何 实现数组反转？

二、字符串编程问题：（要求：尽量不要使用系统框架提供的Api;自己设计）

1.如何输出字符串中的重复字符？

2.如何判断两个字符串是否互为回文？

3.如何从字符串中输出第一个不重复字符？

static void Main(string[] args)
        {
            string str = "ABCDCBAbbb";
            var index = FirstUniqChar(str);
            var charStr= str[index];
        }

        public static int FirstUniqChar(String s)
        {
            char[] temp = s.ToCharArray();
            int length = temp.Length;
            int j, i;
            int result = 0;
            for (i = 0; i < length; i++)
            {
                for (j = 0; j < length; j++)
                {
                    if (i == j) { continue; }
                    if (temp[i] == temp[j])
                    {
                        break;
                    }
                }
                if (j == length)
                {
                    result = i;
                    break;
                }
            }
            if (i == length)
            {
                result = -1;
            }
            return result;
        }

4.如何使用递归实现字符串反转? 

5.如何检查字符仅包含数字字符？

6.如何在字符串中找到重复字符？

7.如何计算给定字符传中特定字符出现的次数？

8.如何找到一个字符串的全排列？

9.在不使用任何库方法的情况下如何反转给定语句中的单词？

10.如何判断两个字符串是否互为旋转？

/// <summary>
        ///a="cdab"，b="abcd"，返回true； 
        ///a="1ab2"，b="ab12"，返回false；
        ///a="2ab1"，b="ab12"，返回true。
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            string a = "cdab";
            string b = "abcd";
            var aResult = IsRotation2(a, b); 
            a = "1ab2"; b = "ab12"; // 返回false；
            var bResult = IsRotation2(a, b);
        }

        public static bool IsRotation2(String a, String b)
        {
            if (a == null || b == null || a.Length != b.Length)
            {
                return false;
            }
            String b2 = b + b;
            return IndexOf(b2, a, 0) > -1;
        }

        private static int IndexOf(String b2, String a, int index)
        {
            char[] source = b2.ToCharArray();
            char[] target = a.ToCharArray();
            return Func(source, 0, source.Length, target, 0, target.Length, index);
        }

        private static int Func(char[] source, int sourceOffset, int sourceCount,
                            char[] target, int targetOffset, int targetCount,
                            int fromIndex)
        {
            if (fromIndex >= sourceCount)
            {
                return (targetCount == 0 ? sourceCount : -1);
            }
            if (fromIndex < 0)
            {
                fromIndex = 0;
            }
            if (targetCount == 0)
            {
                return fromIndex;
            }
            char first = target[targetOffset];
            int max = sourceOffset + (sourceCount - targetCount);

            for (int i = sourceOffset + fromIndex; i <= max; i++)
            {
                if (source[i] != first)
                {
                    while (++i <= max && source[i] != first) ;
                }

                if (i <= max)
                {
                    int j = i + 1;
                    int end = j + targetCount - 1;
                    for (int k = targetOffset + 1; j < end && source[j]
                            == target[k]; j++, k++) ;

                    if (j == end)
                    {
                        return i - sourceOffset;
                    }
                }
            }
            return -1;
        }

三、编程面试杂项问题：（要求：尽量不要使用系统框架提供的Api;自己设计）

1.冒泡排序是如何实现的?

答：

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

2.你如何实现插入排序算法？

答：

插入排序实际上把待排序的数列分为了两部分，一部分已排好序，另一部分待排序。我们下面还是以一组实际数据为例进行讲解。例如采用直接插入排序算法将无序表{3,1,7,5,2,4,9,6}进行升序排序的过程为：

• 首先考虑记录 3 ，由于插入排序刚开始，有序表中没有任何记录，所以 3 可以直接添加到有序表中，则有序表和无序表可以如图所示：

• 向有序表中插入记录 1 时，同有序表中记录 3 进行比较，1<3，所以插入到记录 3 的左侧，如图所示：

• 向有序表插入记录 7 时，同有序表中记录 3 进行比较，3<7，所以插入到记录 3 的右侧，如图所示：

• 向有序表中插入记录 5 时，同有序表中记录 7 进行比较，5<7，同时 5>3，所以插入到 3 和 7 中间，如图所示：

• 向有序表插入记录 2 时，同有序表中记录 7进行比较，2<7，再同 5，3，1分别进行比较，最终确定 2 位于 1 和 3 中间，如图所示：

• 照此规律，依次将无序表中的记录 4，9 和 6插入到有序表中，如图所示：

接下来我们总结一下直接插入排序的整个执行过程：

1. 首先需要明确待排序的数列由两部分组成，一部分是已排好序的部分，另一部分是待排序的部分；
2. 接着我们每次选择待排序的部分的第 1 个元素，分别与前面的元素进行比较。当大于前面的元素时，可以直接进入已排好序的部分；当小于前面的元素时，需要把这个元素拿出来，将前面的元素后移一位，继续与前面的元素相比，直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素，这时停止比较、移动，直接把这个元素放到当时的空位上；
3. 一直重复步骤 2，当待排序的部分已经没有元素可进行插入时，停止操作，当前的数列为已排好序的数列。

3.合并排序算法是如何实现的？

答：算法思想：用分治策略实现对n个元素进行排序。将待排序元素分成大小相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。

4.桶排序算法是如何实现的？

答：

桶排序也是一种排序算法，它的基本原理就是：将一组待排序的数组，按照某种映射规则分配到有限数量的桶中，桶中的记录值再按照某种排序规则排序，最后将这些有限数量的桶中的记录值合并，即得到排序后的数组。

有以下几个步骤的思路：

桶数量的确定。假设待排序记录数是N，桶数是k，一般可根据k^2=N来确定桶的数量。

映射规则。在桶数量确定的情况下，要确定映射规则，使得从待排序数组中依次取出的记录值，能够判定其分配到角标为几的桶中。假设待排序的记录值是array[i]，那么根据映射规则，必然能够找到某个桶B[j]，记录值array[i]就是B[j]中的一个元素。

每个桶内记录值的排序。可以使用快速排序，也可以使用插入排序，如果待排序的记录值是整数，甚至可以使用集合类自带的排序方法。

所有不为空的桶的记录值合并，形成最终排序后的有序数组。

5.计数排序算法是如何实现的？

答：

计数排序对输入的数据有附加的限制条件：

1、输入的线性表的元素属于有限偏序集S；

2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)。

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上。

假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：

1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；

2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。

6.基数排序算法是如何实现的？

答：

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：                

135、242、192、93、345、11、24、19

我们将每个数值的个位，十位，百位分成三个关键字，例如：

135 -> k1(个位)=5  ，k2(十位)=3 ，k3(百位)=1。

然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。

(11)、(242、192)、(93)、(24)、(135、345)、(19)（从最次关键字开始排序，忽略百位与十位，按照个位上的数字分配）

再对上面的序列接着进行针对k2的桶分配，输出序列为：

(11、19)、(24)、(135)、(242、345)、(192、93)（参考最次关键字来排序第二次关键字，忽略百位与个位，按照十位上的数字分配）

最后针对k3的桶分配，输出序列为：

(011、019、024、093)、(135、192)、(242)、(345)（参考第二次关键字来排序最高关键字，忽略十位与个位，按照百位上的数字分配）

排序完毕。

7.在不使用第三个变量的前提下如何交换两个数？

答：

例如题目：a=10,b=15，将a / b的值互换。

通常我们的做法是（尤其是在学习阶段）：定义一个新的变量，借助它完成交换。代码如下：

      int a,b;

      a=10; b=15;

      int t;

      t=a; a=b; b=t;

      这种算法易于理解，特别适合帮助初学者了解计算机程序的特点，是赋值语句的经典应用。在实际软件开发当中，此算法简单明了，不会产生歧义，便于程序员之间的交流，一般情况下碰到交换变量值的问题，都应采用此算法（以下称为标准算法）。

上面的算法最大的缺点就是需要借助一个临时变量。那么不借助临时变量可以实现交换吗？答案是肯定的！

      1） 算术运算

      简单来说，就是通过普通的+和-运算来实现。代码如下：

      int a,b;

      a=10;b=12;

      a=b-a; //a=2;b=12

      b=b-a; //a=2;b=10

      a=b+a; //a=10;b=10

      通过以上运算，a和b中的值就进行了交换。表面上看起来很简单，但是不容易想到，尤其是在习惯标准算法之后。

      它的原理是：把a、b看做数轴上的点，围绕两点间的距离来进行计算。

      具体过程：第一句“a=b-a”求出ab两点的距离，并且将其保存在a中；第二句“b=b-a”求出a到原点的距离（b到原点的距离与ab两点距离之差），并且将其保存在b中；第三句“a=b+a”求出b到原点的距离（a到原点距离与ab两点距离之和），并且将其保存在a中。完成交换。

      此算法与标准算法相比，多了三个计算的过程，但是没有借助临时变量。（以下称为算术算法）

      该算法还可以这样做：

      int a,b;

      a=10;b=12;

      a=a+b=22;

      b=a-b=10;

      a=a-b=12;

      两个减操作一个加操作，执行的先后顺序不一样，其原理也稍微有些区别，但根本原理是一样滴。