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

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

题目描述：

把一个含有N个元素的数组循环右移k(k是正数)位，要求时间复杂度为O(n)，且只允许使用两个附加变量。正确答案：由于有空间复杂度的要求，（江南博哥）因此，只能在原数组中就地进行右移。

方法一：蛮力法

蛮力法也是最简单的方法，题目中需要将数组元素循环右移k位，只需要每次将数组中的元素右移一位，循环k次即可。例如，假设原数组为abcd1234，那么，按照此种方式，具体移动过程如下：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

此种方法也很容易写出代码。示例代码如下：

packagemain

import(

"fmt"

)

funcrightShiftl(arr[]int,kint){

ifarr==nil{

fmt.Println("参数不合法")

return

}

ll:=len(arr)

fork!=0{

k--

tmp:=arr[ll-1]

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

arr[i]=arr[i-1]

}

art[0]=tmp

}

}

funcmain(){

arr:=[]int{1,2,3,4,5,6,7,8}

rightShift1(arr,4)

fmt.Println("方法1")

for_,v:=rangearr{

fmt.Print(v,"")

}

}

程序的运行结果为

56781234

以上方法虽然可以实现数组的循环右移，但是由于每移动一次，其时间复杂度就为O(n)，所以，移动k次，其总的时间复杂度为O(k*n)，0＜k＜n，与题目要求的O(n)不符合，需要继续往下探索。

对于上述代码，需要考虑到，k不一定小于n，有可能等于n，也有可能大于n。当k＞n时，右移k-n之后的数组序列跟右移k位的结果一样，所以，当k＞n时，右移k位与右移k'(其中k'=k%n)位等价，根据以上分析，相对完备的代码如下：

funcrightShift2(arr[]int,kint){

ifarr==nil{

fmt.Println("参数不合法")

return

}

ll:=len(arr)

k%=ll

fork!=0{

k--

t:=arr[ll-1]

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

arr[i]=arr[i-1]

}

arr[0]=t

}

}

算法性能分析：

上例中，算法的时间复杂度为O(n2)，与k值无关，但时间复杂度仍然太高，是否还有其他更好的方法呢?

仔细分析上面的方法，不难发现，上述方法的移动采取的是一步一步移动的方式，可是问题是，题目中已经告知了需要移动的位数为k，为什么不能一步到位呢?

方法二：空间换时间法

通常情况下，以空间换时间往往能够降低时间复杂度，本题也不例外。

首先定义一个辅助数组T，把数组A的第n-k+1到N位数组中的元素存储到辅助数组T中，然后再把数组A中的第1到n-k位数组元素存储到辅助数组T中，然后将数组T中的元素复制回数组A，这样就完成了数组的循环右移，此时的时间复杂度为O(n)。

虽然时间复杂度满足要求，但是空间复杂度却提高了，由于需要创建一个新的数组，所以，此时的空间复杂度为O(n)，鉴于此，还可以对此方法继续优化。

方法三：翻转法

把数组看成由两段组成的，记为XY。左旋转相当于要把数组XY变成YX。先在数组上定义一种翻转的操作，就是翻转数组中数字的先后顺序。把X翻转后记为XT。显然有(XT)T=X。

首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是期待的结果。

回到原来的题目。要做的仅仅是把数组分成两段，再定义一个翻转子数组的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。

对于数组序列A={123456}，如何实现对其循环右移2位的功能呢?将数组A分成两个部分：A[0～n-k-1]和A[n-k～n-1]，将这两个部分分别翻转，然后放在一起再翻转(反序)。具体是这样的：

(1)翻转12341：123456---＞432156。

(2)翻转56：432156---＞432165。

(3)翻转432165：432165---＞561234。

示例代码如下：

funcreverse(arr[]int,start,endint){

forstart＜end{

tmp:=arr[start]

arr[start]=arr[end]

arr[end]=tmp

start++

end--

}

}

funcrightShift3(arr[]int,kint){

ifarr==nil{

fmt.Println("参数不合法")

return

}

ll:=len(arr)

k%=ll

reverse(arr,0,ll-k-1)

reverse(arr,ll-k,ll-1)

reverse(arr,0,ll-1)

}

算法性能分析：

此时的时间复杂度为O(n)。主要是完成翻转(逆序)操作，并且只用了一个辅助空间。[考点]如何对数组进行循环移位

2.

题目描述：

已知随机数生成函数rand7()能产生的随机数是整数1～7的均匀分布，如何构造rand10()函数，使其产生的随机数是整数1～10的均匀分布。正确答案：要保证rand10()产生的随机数是整数1～10的均匀分布，可以构造一个1～10*n的均匀分布的随机整数区间(n为任何正整数)。假设x是这个1～10*n区间上的一个随机数，那么x%10+1就是均匀分布在1～10区间上的整数。

根据题意，rand7()函数返回1到7的随机数，那么rand7()-1则得到一个离散整数集合，该集合为{0，1，2，3，4，5，6}，该集合中每个整数的出现概率都为1/7。那么(rand7()-1)*7得到另一个离散整数集合A，该集合元素为7的整数倍，即A={0，7，14，21，28，35，42}，其中，每个整数的出现概率也都为1/7。而由于rand7()得到的集合B={1，2，3，4，5，6，7}，其中每个整数出现的概率也为1/7。显然集合A与集合B中任何两个元素和组合可以与1～49之间的一个整数一一对应，即1～49之间的任何一个数，可以唯一地确定A和B中两个元素的一种组合方式，这个结论反过来也成立。由于集合A和集合B中元素可以看成是独立事件，根据独立事件的概率公式P(AB)=P(A)P(B)，得到每个组合的概率是1/7*1/7=1/49。因此，(rand7()-1)*7+rand7()生成的整数均匀分布在1～49之间，而且，每个数的概率都是1/49。

所以，(rand7()-1)*7+rand7()可以构造出均匀分布在1～49的随机数，为了将49种组合映射为1～10之间的10种随机数，就需要进行截断了，即将41～49这样的随机数剔除掉，得到的数1～40仍然是均匀分布在1～40的，这是因为每个数都可以看成一个独立事件。由1～40区间上的一个随机数x，可以得到x%10+1就是均匀分布在1～10区间上的整数。

程序代码如下：

packagemain

import(

"time"

"math"

"math/rand"

"fmt"

)

//产生的随机数是整数1～7的均匀分布

funcrand7()int{

rand,Seed(time.Now().UnixNano())

returnrand.Intn(7)

}

//产生的随机数是整数1～10的均匀分布

funcrand10()int{

x:=math.MaxInt32

forx＞40{

x=(rand7())*7+rand7()

}

rcturnx%10+1

}

funcmain(){

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

fmt.PrintIn(rand10())

}

}

程序的运行结果为

610818638107[考点]如何根据已知随机数生成函数计算新的随机数

3.

题目描述：

如何把一个有序整数数组放到二叉树中?正确答案：如果要把一个有序的整数数组放到二叉树中，那么所构造出来的二叉树必定也是一棵有序的二叉树。鉴于此，实现思路为：取数组的中间元素作为根结点，将数组分成左右两部分，对数组的两部分用递归的方法分别构建左右子树。如下图所示。

如上图所示，首先取数组的中间结点6作为二叉树的根结点，把数组分成左右两部分，然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建，例如，对于左半部分子数组，取中间结点3作为树的根结点，再把孩子数组分成左右两部分。依此类推，就可以完成二叉树的构建，实现代码如下：

packagemain

import(

"fmt"

."/isdamir/gotype"

//引入定义的数据结构

)

funcarrayToTree(arr[]int,startint,endint)*BNode{

varroot*BNode

ifend＞=start{

root=NewBNode()

mid:=(start+end+1)/2

//树的根结点为数组中间的元素

root.Data=arr[mid]

//递归的用左半部分数组构造root的左子树

root.LeftChild=arrayToTree(arr,start,mid-1)

//递归的用右半部分数组构造root的右子树

root.RightChild=arrayToTree(arr,mid+1,end)

}

returnroot

}

funcmain(){

data:=[]int{1,2,3,4,5,6,7,8,9,10}

fmt.Println("数组:",data)

root:=arrayToTree(data,O,len(data)-1)

fmt.Print("转换成树的中序遍历为:")

PrintTreeMidOrder(root)

fmt.Println()

}

程序的运行结果为

数组：12345678910

转换成树的中序遍历为：12345678910

算法性能分析：

由于这种方法只遍历了一次数组，因此，算法的时间复杂度为O(n)，其中，N表示的是数组长度。[考点]如何把一个有序整数数组放到二叉树中

4.

题目描述：

设计一个算法，判断给定的一个数n是否是某个数的平方，不能使用开方运算。例如16就满足条件，因为它是4的平方；而15则不满足条件，因为不存在一个数使得其平方值为15。正确答案：方法一：直接计算法

由于不能使用开方运算，因此最直接的方法就是计算平方。主要思路为：对1到n的每个数i，计算它的平方m，如果m＜n，则继续遍历下一个值(i+1)，如果m==n，那么说明n是m的平方，如果m＞n，那么说明n不能表示成某个数的平方。实现代码如下：

packagemain

import(

"fmt"

)

//判断一个自然数是否是某个数的平方

funcisPower1(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

returnfalse

}

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

m:=i*i

if(m==n){

returntrue

}elseif(m＞n){

returnfalse

}

}

returnfalse

}

funcmain(){

n1:=15

n2:=16

fret.Println("方法一")

ifisPower1(n1){

fmt.Println(n1,"是某个自然数的平方")

}else{

fmt.Println(n1,"不是某个自然数的平方")

}

if(isPower1(n2)){

fmt.Println(n2,"是某个自然数的平方")

}else{

fmt.Println(n2,"不是某个自然数的平方")

}

}

程序的运行结果为

15不是某个自然数的平方

16是某个自然数的平方

由于这种方法只需要从1遍历到n^0.5就可以得出结果，因此算法的时间复杂度为O(n^0.5)。

方法二：二分查找法

与方法一类似，这种方法的主要思路还是查找从1～n的数字中，是否存在一个数m，使得m的平方为n。只不过在查找的过程中使用的是二分查找的方法。具体思路为：首先判断mid=(1+n)/2的平方power与m的大小，如果power＞m，那么说明在[1，mid-1]区间继续查找，否则在[mid+1，n]区间继续查找。

实现代码如下：

funcisPower2(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

returnfalse

}

low:=0

high:=n

forlow＜high{

mid:=(low+high)

power:=mid*mid

ifpower＞n{//大于则在小的范围找

high=mid-1

}elseifpower＜n{//小于则在大的范围找

low=mid+1

}else{

returntrue

}

}

returnfalse

}

算法性能分析

由于这种方法使用了二分查找的方法，因此，时间复杂度为O(logn)，其中，n为数的大小。

方法三：减法运算法

通过对平方数进行分析发现有如下规律：

(n+1)^2=n^2+2n+1=(n-1)^2+(2*(n-1)+1)+2*n+1=…=1+(2*1+1)+(2*2+1)+…+(2*n+1)。通过上述公式可以发现，这些项构成了一个公差为2的等差数列的和。由此可以得到如下的解决方法：对n依次减1，3，5，7…，如果相减后的值大于0，则继续减下一项；如果相减的后的值等于0，则说明n是某个数的平方；如果相减的值小于0，则说明n不是某个数的平方。根据这个思路，代码实现如下：

funcisPower3(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

returnfalse

}

minus:=1

forn＞0{

n=n-minus

//n是某个数的平方

if(n==0){

returntrue

//n不是某个数的平方

}elseifn＜0{

returnfalse

//每次减数都加2

}else{

minus+=2

}

}

returnfalse

}

算法性能分析

这种方法的时间复杂度仍然为O(n^0.5)。由于方法一使用的是乘法操作，这种方法采用的是减法操作，因此，这种方法的执行效率比方法一更高。[考点]如何判断一个自然数是否是某个数的平方

5.

题目描述：

判断一个字符串是否包含重复字符。例如：“good”就包含重复字符‘o’，而“abc”就不包含重复字符。正确答案：方法一：蛮力法

最简单的方法就是把这个字符串看作一个字符数组，对该数组使用双重循环进行遍历，即对每个字符都将这个字符与其后面所有的字符进行比较，如果能找到相同的字符，则说明字符串包含有重复的字符。

实现代码如下：

packagemain

import(

"fmt"

)

//判断字符串中是否有相同的字符

funcisDup(strstring)bool{

fori:=0;i＜len(str);i++{

forj:=i+1;j＜len(str);j++{

ifstr[i]==str[j]{

returntrue

}

}

}

returnfalse

}

funcmain(){

str:="GOOD"

fmt.Println("方法一")

if(isDup(str)){

fmt.Println(str,"中有重复字符")

}else{

fmt.Println(str,"中没有重复字符")

}

}

程序的运行结果为

GOOD中有重复字符

算法性能分析：

由于这种方法使用了双重循环对字符数组进行了遍历，因此，算法的时间复杂度为O(N^2)(其中，N是指字符串的长度)。

方法二：空间换时间

在算法中经常会采用空间换时间的方法。对于这个问题，也可以采取这种方法。其主要思路如下：由于常见的字符只有256个，可以假设这道题涉及的字符串中不同的字符个数最多为256个，那么可以申请一个大小为256的int类型数组来记录每个字符出现的次数，初始化都为0，把这个字符的