注:答案均以红色字体标注!答案仅供参考!为提供学员的实操性! 此处答案均以截图提供!希望学员能以实操理解!
文章目录
一.数组专题 (要求:尽量不要使用系统框架提供的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 个元素,分别与前面的元素进行比较。当大于前面的元素时,可以直接进入已排好序的部分;当小于前面的元素时,需要把这个元素拿出来,将前面的元素后移一位,继续与前面的元素相比,直到比较完数组的第 1 个元素或者出现一个元素小于我们拿出来的这个元素,这时停止比较、移动,直接把这个元素放到当时的空位上;
- 一直重复步骤 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;
两个减操作一个加操作,执行的先后顺序不一样,其原理也稍微有些区别,但根本原理是一样滴。
除非注明,文章均由 Dotnet9 整理发布,欢迎转载。
转载请注明:
作者:Dotnet9
链接:https://dotnet9.com/9202.html
来源:Dotnet9
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。