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

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

题目描述：

单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在?（江南博哥）正确答案：方法一：蛮力法

定义一个Set用来存放结点的引用，并将其初始化为空，从链表的头结点开始向后遍历，每遍历到一个结点就判断Set中是否引用这个结点，如果没有，说明这个结点是第一次访问，还没有形成环，那么将这个引用结点添加到指针Set中去。如果在Set中找到了同样的结点，那么说明这个结点已经被访问过了，于是就形成了环。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

方法二：快慢指针遍历法

定义两个指针fast(快)与slow(慢)，二者的初始值都指向链表头，指针slow每次前进一步，指针fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，如果快指针等于慢指针，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表。[考点]如何检测一个较大的单链表是否有环

2.

题目描述：

如何把十进制数(long型)分别以二进制和十六进制形式输出?正确答案：由于十进制数本质上还是以二进制的方式来存储的，在实现的时候可以把十进制数看成二进制的格式，通过移位的方式计算出每一位的值。为了方便起见，下面以byte类型的数为例介绍实现方法，假如现在要把十进制数7以二进制的形式来输出，由于7的二进制的表示为00000111，计算第6位二进制码是0还是1的方法为：首先把这个值左移6位得到11000000，然后再右移7位，得到00000001，移位后得到的值就是第6位二进制码的值。由此可以得出如下计算方法：假设十进制数对应的二进制数的长度为binNum，那么计算十进制数n的第i位二进制码值的公式为n＜＜i＞＞binNum-1。通过这种计算方法可以得到每一位的值，然后把对应的值存储在字符数组中即可。

上面介绍的方法使用的是移位操作，虽然效率比较高，但是难以理解。下面介绍一种简单的转换为十六进制的方法。可以使用类似于十进制转二进制的方法。把十进制的数对16求余数。得到的结果就是十六进制的最后一位，然后把这个十进制数除以16，用得到的数继续使用相同的方法计算其他的位数。需要注意的是对于十六进制10～15需要转换为A～F。示例代码如下：

packagemare

import(

"bytes"

"fmt"

)

funcintToBinary(nint)string{

ifn＜0{

fmt.Println("不支持负数")

return""

}

hexNum:=8*8;//二进制的位数(long占8个字节)

varpBinarybytes.Buffer

fori:=0;i＜hexNum;i++{

//先左移i位把pBinary[i]移到最高位，然后右移hexNum-1位把pBinary[i]移到最后一位

tmpBinary:=(n＜＜uint(i))＞＞(uint(hexNum)-1)

if(tmpBinary==0){

pBinary.WriteRune('0')

}else{

pBinary.WriteRune('1')

}

}

returnpBinary.String()

}

funcintToHex(sint)string{

hex:=""

remainder:=0

fors!=0{

remainder=s%16

if(remainder＜10){

hex=string(remainder+'0')+hex

}else{

hex=string(remainder-10+'A')+hex

}

s=s＞＞4

}

returnhex

}

funcmain(){

fmt.Println("10的二进制输出为:",intToBinary(10))

fmt.Println("10的十六进制输出为:",intToHex(10))

}

程序的运行结果为

10的二进制输出为：0000000000000000000000000000000000000000000000000000000000001010

10的十六进制输出为：A[考点]如何把十进制数(long型)分别以二进制和十六进制形式输出

3.

题目描述：

不使用^操作实现异或运算。正确答案：最简单的方法是遍历两个整数的所有的位，如果两个数的某一位相等，那么结果中这一位的值为0，否则结果中这一位的值为1，实现代码如下：

packagemain

import(

"strconv"

"fmt"

)

//获取x与y异或的结果

funcxor1(x,yint)int{

BITS:=strconv.IntSize//以具体平台为例

res:=0

varxoredBitint

fori:=BITS-1;i＞=0;i--{

/*获取x与y当前的bit值*/

b1:=(x&(1＜＜uint(i)))＞0

b2:=(y&(1＜＜uint(i)))＞0

/*只有这两位都是1或0的时候结果为0*/

if(b1=b2){

xoredBit=0

}else{

xoredBit=1

}

res＜＜=1

res|=xoredBit

}

returnres

}

funcmain(){

fmt.Println("方法一")

fmt.Println(xor1(3,5))

}

程序的运行结果为

6

下面介绍另外一种更加简便的实现方法：x^y=(x|y)&(～x|～y)，其中x|y表示如果在x或y中的bit为1，那么结果的这一个bit的值也为1，显然这个结果包括三部分：这个bit只有在x中为1，只有在y中为1，在x和y中都为1，要在这个基础上计算出异或的结果，显然要去掉第三种情况，也就是说去掉在x和y中都为1的情况，而当一个bit在x和y中都为1的时候“～x|～y”的值为0，因此(x|y)&(～x|～y)的值等于x^y。实现代码如下：

funcxor2(x,yint)int{

return(x|y)&(^x|^y)//这里是golang的取反语法，不是异或

}

算法性能分析：

这种方法的时间复杂度为O(n)。[考点]如何不使用^操作实现异或运算

4.

题目描述：

有N个磁盘，每个磁盘大小为D[i](i=0…N-1)，现在要在这N个磁盘上"顺序分配"M个分区，每个分区大小为P[j](j=0…M-1)，顺序分配的意思是：分配一个分区P[j]时，如果当前磁盘剩余空间足够，则在当前磁盘分配；如果不够，则尝试下一个磁盘，直到找到一个磁盘D[i+k]可以容纳该分区，分配下一个分区P[j+1]时，则从当前磁盘D[i+k]的剩余空间开始分配，不在使用D[i+k]之前磁盘未分配的空间，如果这M个分区不能在这N个磁盘完全分配，则认为分配失败，请实现函数，isallocable判断给定N个磁盘(数组D)和M个分区(数组P)，是否会出现分配失败的情况?举例：磁盘为[120，120，120]，分区为[60，60，80，20，80]可分配，如果为[60，80，80，20，80]，则分配失败。正确答案：本题的主要思路如下：对所有的分区进行遍历，同时用一个变量dIndex记录上次分配磁盘的下标，初始化为0；对于每个分区，从上次分配的磁盘开始继续分配，如果没有足够的空间，则顺序找其他的磁盘，直到找到合适的磁盘为止，进行分配；如果找不到合适的磁盘，则分配失败，实现代码如下：

packagemain

import(

"fmt"

)

funcisAllocable(d,p[]int)bool{

//磁盘分区下标

dIndex:=0

for_,v:=rangep{

//找到符合条件的磁盘

fordIndex＜len(d)&&v＞d[dlndex]{

dIndex++

}

//没有可用的磁盘

ifdIndex＞=len(d){

returnfalse

}

//给分区分配磁盘

d[dIndex]-=v

}

returntrue

}

funcmain(){

//磁盘

d:=[]int{120,120,120}

//分区

p:=[]int{60,60,80,20,80}

ifisAllocable(d,p){

fmt.Println("分配成功")

)else{

fmt.Println("分配失败")

}

}

程序的运行结果为

分配成功

算法性能分析：

这种方法使用了双重循环，因此，时间复杂度为O(mn)。[考点]如何对磁盘分区

5.

题目描述：

找出两个字符串的最长公共子串，例如字符串“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{

s