1. Dotnet9首页
  2. .NET
  3. .NET相关

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

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

文章目录

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

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

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

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

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

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

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

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

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

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

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

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

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

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

020最新面试宝典带答案数据结构算法专题"
图一
020最新面试宝典带答案数据结构算法专题"
图二
020最新面试宝典带答案数据结构算法专题"
图九

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

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

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

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

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

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

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

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

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

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.如何使用递归实现字符串反转? 

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

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

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

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

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

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

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

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

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

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

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

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 可以直接添加到有序表中,则有序表和无序表可以如图所示:
020最新面试宝典带答案数据结构算法专题"
  • 向有序表中插入记录 1 时,同有序表中记录 3 进行比较,1<3,所以插入到记录 3 的左侧,如图所示:
020最新面试宝典带答案数据结构算法专题"
  • 向有序表插入记录 7 时,同有序表中记录 3 进行比较,3<7,所以插入到记录 3 的右侧,如图所示:
020最新面试宝典带答案数据结构算法专题"
  • 向有序表中插入记录 5 时,同有序表中记录 7 进行比较,5<7,同时 5>3,所以插入到 3 和 7 中间,如图所示:
020最新面试宝典带答案数据结构算法专题"
  • 向有序表插入记录 2 时,同有序表中记录 7进行比较,2<7,再同 5,3,1分别进行比较,最终确定 2 位于 1 和 3 中间,如图所示:
020最新面试宝典带答案数据结构算法专题"
  • 照此规律,依次将无序表中的记录 4,9 和 6插入到有序表中,如图所示:
020最新面试宝典带答案数据结构算法专题"

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

  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。

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

然后从最低位个位开始(从最次关键字开始),对所有数据的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;

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

除非注明,文章均由 Dotnet9 整理发布,欢迎转载。

转载请注明本文地址:https://dotnet9.com/9202.html

发表评论

登录后才能评论