Go程序员面试分类模拟题25

Go程序员面试分类模拟题25论述题1.

题目描述：

各种排序算法有什么优劣?正确答案：各种算法的性能见下表。算法性能对比排序方法最好时间平均时间最坏时间辅助存储（江南博哥）稳定性备注简单选择排序O(n2)O(n2)O(n2)O(1)不稳定n小时较好直接插入排序O(n)O(n2)O(n2)O(1)稳定大部分已有序时较好冒泡排序O(n)O(n2)O(n2)O(1)稳定n小时较好希尔排序O(n)O(nlogn)O(ns)1＜s＜2O(1)不稳定s是所选分组快速排序O(nlogn)O(nlogn)O(n2)O(logn)不稳定n大时较好堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定n大时较好归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定n大时较好

从该表中可以得到以下几个方面的结论：

(1)简单地说，所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，就称这种排序方法是稳定的，反之，就是非稳定的。例如：一组数排序前是a1，a2，a3，a4，a5，其中a2=a4，经过某种排序后a1，a2，a4，a3，a5，则说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1，a4，a2，a3，a5就不是稳定的了。各种排序算法中稳定的排序算法有直接插入排序、冒泡排序、归并排序，而不稳定的排序算法有希尔排序、快速排序、简单选择排序、堆排序。

(2)时间复杂度为O(n2)的排序算法有直接插入排序、冒泡排序、快速排序，简单选择排序；时间复杂性为O(nlogn)的排序算法有堆排序、归并排序。

(3)空间复杂度为O(1)的算法有单选择排序、直接插入排序、冒泡排序、希尔排序、堆排序；空间复杂杂度为O(n)的算法是归并排序；空间复杂度为O(logn)的算法是快速排序。

(4)虽然直接插入排序和冒泡排序的速度比较慢，但是当初始序列整体或局部有序时，这两种排序算法会有较好的效率。当初始序列整体或局部有序时，快速排序算法的效率会下降。当排序序列较小且不要求稳定性时，直接选择排序效率较好；要求稳定性时，冒泡排序效率较好。

除了以上这几种排序算法以外，还有位图排序、桶排序、基数排序等。每种排序算法都有其最佳适用场合，例如，当待排序数据规模巨大，而对内存大小又没有限制时，位图排序则是最高效的排序算法，所以，在选择使用排序算法的时候，一定要结合实际情况进行分析。[考点]各种排序算法有什么优劣

2.

题目描述：

给定两个单链表，链表的每个结点代表一位数，计算两个数的和。例如：输入链表(3-＞1-＞5)和链表(5-＞9-＞2)，输出：8-＞0-＞8，即513+295=808，注意个位数在链表头。正确答案：方法一：整数相加法

主要思路：分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单，但是有个非常大的缺点：当链表所代表的数很大的时候(超出了longint的表示范围)，就无法使用这种方法了。

方法二：链表相加法

主要思路：对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时还要记录结点相加后的进位。如下图所示：

使用这种方法需要注意如下几个问题：①每组结点进行相加后需要记录其是否有进位；②如果两个链表H1与H2的长度不同(长度分别为L1和L2，且L1＜L2)，当对链表的第L1位计算完成后，接下来只需要考虑链表L2剩余的结点的值(需要考虑进位)；③对链表所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1。实现代码如下：

packagemain

import(

"fmt"

."/isdamir/gotype"

//引入定义的数据结构

)

funcAdd(h1*LNode,h2*LNode)*LNode{

if(h1==nil||h1.Next==nil){

returnh2

}

if(h2==nil||h2.Next==nil){

returnh1

}

c:=0

//记录进位

sum:=0

//记录两个结点相加的值

p1:=h1.Next

//遍历h1

p2:=h2.Next

//遍历h2

resultHead:=&LNode{}

//相加后链表头结点

p:=resultHead

//指向链表resultHead最后一个结点

forp1!=nil&&p2!=nil{

p.Next=&LNode{}

//指向新创建的存储相加和的结点

sum=p1.Data.(int)+p2.Data.(int)+c

p.Next.Data=sum%10

//两结点相加和

c=sum/10

//进位

p=p.Next

p1=p1.Next

p2=p2.Next

}

//链表h2比h1长，接下来只需要考虑h2剩余结点的值

ifp1==nil{

forp2!=nil{

p.Next=&LNode{}

//指向新创建的存储相加和的结点

sum=p2.Data.(int)+c

p.Next.Data=sum%10

//两结点相加和

c=sum/10/进位

p=p.Next

p2=p2.Next

}

}

//链表h1比h2长，接下来只需要考虑h1剩余结点的值

ifp2==nil{

forp1!=nil{

p.Next=&LNode{}

//指向新创建的存储相加和的结点

sum=p1.Data.(int)+c

p.Next.Data=sum%10

//两结点相加之和

c=sum/10//进位

p=p.Next

p1=p1.Next

}

}

ifc==1{

p.ext=&LNode{}

p.Next.Data=1

}

returnresultHead

}

funcmain(){

fmt.Println("链表相加")

l1,l2:=CreateNodeT()

PrintNode("Head1:",l1)

PrintNode("Head2:",l2)

addResult:=Add(l1,l2)

PrintNode("相加后:",addResult)

}

//创建链表

funcCreateNodeT()(l1*LNode,l2*LNode){

l1=&LNode{}

l2=&LNode{}

cur:=l1

fori:=1;i＜7;i++{

cur.Next=&LNode{}

cur.Next.Data=i+2

cur=cur.Next

}

cur=l2

fori:=9;i＞4;i--{

cur.Next=&LNode{}

cur.Next.Data=i

cur=cur.Next

}

return

}

程序的运行结果为

Head1：345678

Head2：98765

相加后：233339

运行结果分析：

前五位可以按照整数相加的方法依次从左到右进行计算，第五位7+5+1(进位)的值为3，进位为1。此时Head2已经遍历结束，由于Head1还有结点没有被遍历，所以，依次接着遍历Head1剩余的结点：8+1(进位)=9，没有进位。因此，运行代码可以得到上述结果。

算法性能分析：

由于这种方法需要对两个链表都进行遍历，因此，时间复杂度为O(n)，其中，n为较长的链表的长度，由于计算结果保存在一个新的链表中，因此，空间复杂度也为O(n)。[考点]如何计算两个单链表所代表的数之和

3.

题目描述

写一个方法，检查字符串是否是整数，如果是，返回其整数值。正确答案：整数分为负数与非负数，负数只有一种表示方法，而整数可以有两种表示方法。例如：-123，123，+123。因此，在判断字符串是否为整数的时候，需要把这几种问题都考虑到。下面主要介绍两种方法。

方法一：递归法

对于正数而言，例如123，可以看成12*10+3，而12又可以看成1*10+2。而-123可以看成(-12)*10-3，-12可以被看成(-1)*10-2。根据这个特点可以采用递归的方法来求解，可以首先根据字符串的第一个字符确定整数的正负，接着对字符串从右往左遍历，假设字符串为“c1c2c3…cn”，如果cn不是整数，那么这个字符串不能表示成整数；如果这个数是非负数(c1!=‘-’)，那么这个整数的值为“c1c2c3…cn-1”对应的整数值乘以10加上cn对应的整数值，如果这个数是负数(c1==‘-’)，那么这个整数的值为c1c2c3…cn-1对应的整数值乘以10减去cn对应的整数值。而求解子字符串“c1c2c3…cn-1”对应的整数的时候，可以用相同的方法来求解，因此可以采用递归的方法来求解。对于“+123”这种情况，可以首先去掉“+”，然后处理方法与“123”相同。由此可以得到递归表达式为：

c1==‘-’?toint(“c1c2c3…cn-1”)*10-(cn-'0')：toint(“c1c2c3…cn-1”)*10+(cn-'0')。

递归的结束条件为：当字符串长度为1时，直接返回字符对应的整数的值。实现代码如下：

packagemain

import(

"fmt"

."/isdamir/gotype"//引入定义的数据结构

)

varflagbool

funcstrToIntSub(arr[]rune,lengthint)int{

iflength＞1{

if!IsNumber(arr[len(arr)-1]){

fmt.Println("不是数字")

flag=false

return-1

}

ifarr[0]=='-'{

returnstrToIntSub(arr,length-1)*10-int(arr[length-1]-'0')

}else{

returnstrToIntSub(arr,length-1)*10+int(arr[length-1]-'0')

}

}else{

ifarr[0]=='-'{

return0

}else{

if!IsNumber(arr[0]){

fmt.Println("不是数字")

flag=false

return-1

}

returnint(arr[0]-'0')

}

}

}

funcstrToInt(sstring)int{

arr:=[]rune(s)

flag=true

ifarr[0]=='+'{

returnstrToIntSub(arr[1:],len(arr)-1)

}else{

returnstrToIntSub(arr,len(arr))

}

}

funcmain(){

fmt.Println("方法一")

printResult("-543")

printResult("543")

printResult("+543")

printResult("++43")

}

funcprintResult(sstring){

re:=strToInt(s)

ifflag{

fmt.Println(re)

}

}

程序的运行结果为

-543

543

543

不是数字

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此，时间复杂度为O(n)(其中，n是字符串的长度)。

方法二：非递归法

首先通过第一个字符的值确定整数的正负性，然后去掉符号位，把后面的字符串当作正数来处理，处理完成后再根据正负性返回正确的结果。实现方法为从左到右遍历字符串计算整数的值，以“123”为例，遍历到‘1’的时候结果为1，遍历到‘2’的时候结果为1*10+2=12，遍历到‘3’的时候结果为12*10+3=123。其本质思路与方法一类似，根据这个思路实现代码如下：

packagemain

import(

"fmt"

."/isdamir/gotype"

//引入定义的数据结构

)

vatflagbool

funcstrToInt2(strstring)int{

arr:=[]rune(str)

flag=true

res:=0

//是否是负数

i:=0

minus:=false

ifarr[i]=='-'{

minus-true

i++

}

ifarr[i]-='+'{

i++

}

for;i＜len(arr);i++{

ifIsNumber(arr[i]){

res=res*10+int(arr[i]-'0')

}else{

flag=false

fmt.Println("不是数字")

return-1

}

}

ifminus{

return-res

}else{

returnres

}

}

funcmain(){

fmt.Println("方法二")

printResult2("-543")

printResult2("543")

printResult2("+543")

printResult2("++43")

}

funcprintResult2(sstring){

re:=strToInt2(s)

ifflag{

fmt.Println(re)

}

}

算法性能分析：

由于这种方法只对字符串进行了一次遍历，因此，算法的时间复杂度为O(n)(其中，n是指字符串的长度)。但是由于方法一采用了递归法，而递归法需要大量的函数调用，也就有大量的压栈与弹栈操作(函数调用都是通过压栈与弹栈操作来完成的)。因此，虽然这两个方法有相同的时间复杂度，但是方法二的运行速度会比方法一更快，效率更高。[考点]如何判断字符串是否是整数

4.

题目描述：

找出两个字符串的最长公共子串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。正确答案：对于这道题而言，最容易想到的方法就是采用蛮力的方法，假设字符串s1与s2的长度分别为len1和len2(假设len1＞=len2)，首先可以找出s2的所有可能的子串，然后判断这些子串是否也是s1的子串，通过这种方法可以非常容易地找出两个字符串的最长子串。当然，这种方法的效率是非常低下的，主要原因为：s2中的大部分字符需要与s1进行很多次的比较。那么是否有更好的方法来降低比较的次数呢?下面介绍两种通过减少比较次数从而降低时间复杂度的方法。

方法一：动态规划法

通过把中间的比较结果记录下来，从而可以避免字符的重复比较。主要思路如下：

首先定义二元函数f(i，j)：表示分别以s1[i]，s2[j]结尾的公共子串的长度，显然，f(0，j)=0(j＞=0)，f(i，0)=0(i＞=0)，那么，对于f(i+1，j+1)而言，则有如下两种取值：

(1)f(i+1，j+1)=0，当str1[i+1]!=str2[j+1]时。

(2)f(i+1，j+1)=f(i，j)+1，当str1[i+1]==str2[j+1]时。

根据这个公式可以计算出f(i，j)(0=＜i＜=len(s1)，0=＜j＜=len(s2))所有的值，从而可以找出最长的子串，如下图所示：

通过上图所示的计算结果可以求出最长公共子串的长度max与最长子串结尾字符在字符数组中的位置maxI，由这两个值就可以唯一确定一个最长公共子串为“cad”，这个子串在数组中的起始下标为：maxI-max=3，子串长度为max=3。实现代码如下：

packagemain

import(

"bytes"

"fmt"

)

//方法功能：获取两个字符串的最长公共字串

//输入参数：str1和str2为指向字符的指针

funcgetMaxSubStr(str1,str2string)string{

len1:=len(str1)

len2:=len(str2)

varbufbytes.Buffer

maxI:=0

//用来记录最长公共字串最后一个字符的位置

max:=0

//申请新的空间来记录公共字串长度信息

M:=make([][]int,len1+1)

fori,_:=rangeM{

M[i]=make([]int,len2+1)

}

//通过利用递归公式填写新建的二维数组(公共字串的长度信息)

fori:=1;i＜len1+1;i++{

forj:=1;j＜len2+1;j++{

ifstr1[i-1]==str2[j-1]{

M[i][j]=M[i-1][j-1]+1

ifM[i][j]＞max{

max=M[i][j]

maxI=i

}

}else{

M[i][j]=0

}

}

}

fori:=maxI-max;i＜maxI;i++{

buf.WriteByte(str1[i])

}

returnbur.String()

}

funcmain(){

str1:="abccade"

str2:="dgcadde"

fmt.Println("动态规划法")

fmt.Printin(getMaxSubStr(str1,str2))

}

程序的运行结果为

cad

算法性能分析：

由于这种方法使用了二重循环分别遍历两个字符数组，因此，时间复杂度为O(m*n)(其中，m和n分别为两个字符串的长度)，此外，由于这种方法申请了一个m*n的二维数组，因此，算法的空间复杂度也为O(m+n)。很显然，这种方法的主要缺点为申请了m*n个额外的存储空间。

方法二：滑动比较法

如下图所示，这种方法的主要思路为：保持s1的位置不变，然后移动s2，接着比较它们重叠的字符串的公共子串(记录最大的公共子串的长度maxLen，以及最长公共子串在s1中结束的位置maxLenEnd1)，在移动的过程中，如果当前重叠子串的长度大于maxLen，则更新maxLen为当前重叠子串的长度。最后通过maxLen和maxLenEnd1就可以找出它们最长的公共子串。实现方法如下图所示：

v如上图所示，这两个字符串的最长公共子串为“bc”，实现代码如下：

packagemain

import(

"bytes"

"fmt"

)

funcgetMaxSubStr2(str1,str2string)string{

len1:=len(str1)

len2:=len(str2)

varbufbytes.Buffer

maxLen:=0

maxLenEnd1:=0

fori:=0;i＜len1+len2;i++{

s1begin:=0

s2begin:=0

tmpMaxLne:=0

ifi＜len1{

s1begin=len1-i

}else{

s2begin=i-len1

}

j:=0

forj=0;(s1begin+j＜len1)&&(s2begin+j＜len2);j++{

ifstr1[s1begin+j]==str2[s2begin+j]{

tmpMaxLne++

}else{

iftmpMaxLne＞maxLen{

maxLen=tmpMaxLne

maxLenEnd1=s1begin+j

)else{

tmpMaxLne=0

}

}

}

iftmpMaxLen＞maxLen{

maxLen=tmpMaxLne

maxLenEnd1=s1begin+j

}

}

fori:=maxLenEnd1-maxLen;i＜maxLenEnd1;i++{

buf.WriteByte(str1[i])

}

returnbuf.String()

}

funcmain(){

str1:="abccade"

str2:="dgcadde"

fmt.Println("滑动比较法")

fmt.Println(getMaxSubStr2(str1,str2))

}

算法性能分析：

这种方法用双重循环来实现，外层循环的次数为m+n(其中，m和n分别为两个字符串的长度)，内层循环最多执行n次，算法的时间复杂度为O((m+n)*n)，此外，这种方法只使用了几个临时变量，因此，算法的空间复杂度为O(1)。[考点]如何求两个字符串的最长公共子串

5.

题目描述：

有N个磁盘，每个磁盘大小为D[i]