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

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

题目描述：

给定一个字符串数组，找出数组中最长的字符串，使其能由数组中其他的字符串组成。例如给定字符串数组{“test”，“tester”，“testert（江南博哥）est”，“testing”，“apple”，“seattle”，“banana”，“batting”，“ngcat”，“batti”，“bat”，“testingtester”，“testbattingcat”}。满足题目要求的字符串为“testbattingcat”，因为这个字符串可以由数组中的字符串“test”，“batti”和“ngcat”组成。正确答案：既然题目要求找最长的字符串，那么可以采用贪心的方法，首先对字符串由大到小进行排序，从最长的字符串开始查找，如果能由其他字符串组成，就是满足题目要求的字符串。接下来就需要考虑如何判断一个字符串能否由数组中其他的字符串组成，主要的思路为：找出字符串的所有可能的前缀，判断这个前缀是否在字符数组中，如果在，那么用相同的方法递归地判断除去前缀后的子串是否能由数组中其他的子串组成。

以题目中给的例子为例，首先对数组进行排序，排序后的结果为：{“testbattingcat”，“testingtester”，“testertest”，“testing”，“seattle”，“batting”，“tester”，“banana”，“apple”，“ngcat”，“batti”，“test”，“bat”}。首先取“testbattingcat”进行判断，具体步骤如下：

(1)分别取它的前缀“t”，“te”，“tes”都不在字符数组中，“test”在字符数组中。

(2)接着用相同的方法递归地判断剩余的子串“battingcat”，同理，“b”，“ba”都不在字符数组中，“bat”在字符数组中。

(3)接着判断“tingcat”，通过判断发现“tingcat”不能由字符数组中其他字符组成。因此，回到上一个递归调用的子串接着取字符串的前缀进行判断。

(4)回到上一个递归调用，待判断的字符串为“batcingcat”，当前比较到的前缀为“bat”，接着取其他可能的前缀“batt”，“battt”都不在字符数组中，“battti”在字符数组中。接着判断剩余子串“ngcat”。

(5)通过比较发现“ngcat”在字符数组中。因此，能由其他字符组成的最长字符串为“testbattingcat”。

实现代码如下：

packagemain

import(

"sort"

"fmt"

)

typeLongestWordstruct{

}

//判断字符串str是否在字符串数组中

func(p*LongestWord)find(strArr[]string,strstring)bool{

for_,v:=rangestrArr{

ifstr==v{

returntrue

}

}

retumfalse

}

//方法功能：判断字符串word是否能由数组strArray中的其他单词组成

//参数：word为待判断的后缀子串，length为待判断字符串的长度

func(p*LongestWord)isContain(strArr[]string,wordstring,lengthint)bool{

ll:=len(word)

//递归的结束条件，当字符串长度为0时，说明字符串已经遍历完了

ifll==0{

returntrue

}

//循环取字符串的所有前缀

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

//取到的子串为自己

ifi==length{

returnfalse

}

str:=string(word[0:i])

ifp.find(strArr,str){

//查找完字符串的前缀后，递归判断后面的子串能否由其他单词组成

ifp.isContain(strArr,string(word[i:]),length){

returntrue

}

}

}

returnfalse

}

//找出能由数组中其他字符串组成的最长字符串

func(p*LongestWord)GetLogestStr(strArr[]string)string{

//对字符串由大到小排序

sort.Slice(strArr,func(i,jint)bool{

returnlen(strArr[i])＞len(strArr[j])

})

//贪心地从最长的字符串开始判断

for_,v:=rangestrArr{

ifp.isContain(strArr,v,len(v)){

returnv

}

}

return""

}

funcmain(){

strArr:=[]string{"test","tester","testertest","testing","apple","seattle","banana","batting",

"ngcat","batti","bat","testingtester","testbattingcat"}

lw:=new(LongestWord)

logestStr:=lw.GetLogestStr(strArr)

iflogestStr==""{

fmt.Println("不存在这样的字符串")

}else{

fmt.Println("最长的字符串为:",logestStr)

}

}

程序的运行结果为

最长的字符串为：testbattingcat

算法性能分析：

排序的时间复杂度为O(nlogn)，假设单词的长度为m，那么有m种前缀，判断一个单词是否在数组中的时间复杂度为O(mn)，由于总共有n个字符串，因此，判断所需的时间复杂度为O(m*n2)。因此，总的时间复杂度为O(nlogn+m*n2)。当n比较大的时候，时间复杂度为O(n2)。[考点]如何找到由其他单词组成的最长单词

2.

题目描述：

用递归的方式实现一个求字符串中连续出现相同字符的最大值，例如字符串“aaabbcc”中连续出现字符‘a’的最大值为3，字符串“abbc”中连续出现字符‘b’的最大值为2。正确答案：如果不要求采用递归的方法，那么算法的实现就非常简单，只需要在遍历字符串的时候定义两个额外的变量curMaxLen与maxLen，分别记录与当前遍历的字符重复的连续字符的个数和遍历到目前为止找到的最长的连续重复字符的个数。在遍历的时候，如果相邻的字符相等，则执行curMaxLen+1；否则，更新最长连续重复字符的个数，即maxLen=max(curMaxLen，maxLen)，由于碰到了新的字符，因此，curMaxLen=1。

题目要求用递归的方法来实现，通过对非递归方法进行分析可以知道，在遍历字符串的时候，curMaxLen与maxLen是最重要的两个变量，那么在进行递归调用的时候，通过传入两个额外的参数(curMaxLen与maxLen)就可以采用与非递归方法类似的方法来实现，实现代码如下：

packagemain

import(

"fmt"

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

)

funcgetMaxDupChar(sstring,startIndex,curMaxLen,maxLenint)int{

//字符串遍历结束，返回最长连续重复字符串的长度

ifstartIndex==len(s)-1{

returnMax(curMaxLen,maxLen)

}

//如果两个连续的字符相等，则在递归调用的时候把当前最长串的长度加1

ifs[startIndex]==s[startIndex+1]{

returngetMaxDupChar(s,startIndex+1,curMaxLen+1,maxLen)

}else{

//两个连续的子串不相等，求出最长串(max(curMaxLen,maxLen))，

//当前连续重复字符串的长度变为1

returngetMaxDupChar(s,startIndex+1,1,Max(curMaxLen,maxLen))

}

}

funcmain(){

fmt.Println("abbc的最长连续重复子串长度为:",getMaxDupChar("abbc",0,0,1))

fmt.Println("aaabbcc的最长连续重复子串长度为:",getMaxDupChar("aaabbcc",0,0,1))

}

程序的运行结果为

abbc的最长连续重复子串长度为：2

aaabbcc的最长连续重复子串长度为：3

算法性能分析：

由于这种方法对字符串进行了一次遍历，因此，算法的时间复杂度为O(n)。这种方法也没有申请额外的存储空间。[考点]如何统计字符串中连续重复字符的个数

3.

题目描述：

假设L=＜a1，a2，…，an＞是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=＜aK1，ak2，…，akm＞，其中，k1＜k2＜…＜km且aK1＜ak2＜…＜akm。求最大的m值。正确答案：方法一：最长公共子串法

对序列L=＜a1，a2，…，an＞按递增进行排序得到序列LO=＜b1，b2，…，bn＞。显然，L与LO的最长公共子序列就是L的最长递增子序列。因此，可以使用求公共子序列的方法来求解。

方法二：动态规划法

由于以第i个元素为结尾的最长递增子序列只与以第i-1个元素为结尾的最长递增子序列有关，因此，本题可以采用动态规划的方法来解决。下面首先介绍动态规划方法中的核心内容递归表达式的求解。

以第i个元素为结尾的最长递增子序列的取值有两种可能：

(1)1，当第i个元素单独作为一个子串(L[i]＜=L[i-1])。

(2)以第i-1个元素为结尾的最长递增子序列加1(L[i]＞L[i-1])。

由此可以得到如下的递归表达式：假设maxLen[i]表示以第i个元素为结尾的最长递增字序列，那么

(1)maxLen[i]=max{1,maxLen[j]+1),j＜iandL[j]＜L[i]

(2)maxLen[0]=1

根据这个递归表达式可以非常容易地写出实现的代码如下：

packagemain

import(

"fmt"

)

funcgetMaxAscendingLen(strstring)int{

maxLen:=make([]int,len(str))

maxAcsendingLen:=1

fori,_:=rangestr{

maxLen[i]=1

forj:=0;j＜i;j++{

ifstr[j]＜str[i]&&maxLen[j]＞maxLen[i]-1{

maxLen[i]=maxLen[j]+1

maxAcsendingLen=maxLen[i]

}

}

}

returnmaxAcsendingLen

}

funcmain(){

fmt.Println("最长递增子序列的长度为:",getMaxAscendingLen("xbcdza"))

}

程序的运行结果为

xbcdza最长递增子序列的长度为：4

算法性能分析：

由于这种方法用双重循环来实现，因此，这种方法的时间复杂度为O(n2)，此外由于这种方法还使用了n个额外的存储空间，因此，空间复杂度为O(n)。[考点]如何求最长递增子序列的长度

4.

题目描述：

给定一个字符串，找出这个字符串中最长的重复子串，比如给定字符串“banana”，子字符串“ana”出现2次，因此最长的重复子串为“ana”。正确答案：由于题目要求最长重复子串，显然可以先求出所有的子串，然后通过比较各子串是否相等从而求出最长公共子串，具体的思路为：首先找出长度为n-1的所有子串，判断是否有相等的子串，如果有相等的子串，那么就找到了最长的公共子串；否则找出长度为n-2的子串继续判断是否有相等的子串，依次类推直到找到相同的子串或遍历到长度为1的子串为止，这种方法的思路比较简单，但是算法复杂度较高。下面介绍一种效率更高的算法：后缀数组法。

后缀数组是一个字符串的所有后缀的排序数组。后缀是指从某个位置i开始到整个串末尾结束的一个子串。字符串r的从第i个字符开始的后缀表示为Suffix(i)，也就是Suffix(i)=r[i..len(r)]。例如：字符串“banana”的所有后缀如下：

所以“banana”的后缀数组为：{5，3，1，0，4，2}。由此可以把找字符串的重复子串的问题转换为从后缀排序数组中，通过对比相邻的两个子串的公共串的长度找出最长的公共串的问题。在上例中3:ana与1:anana的最长公共子串为ana。这也就是这个字符串的最常公共子串。实现代码如下：

packagemain

import(

"sort"

"fmt"

)

//找出最长的公共子串的长度

funcmaxPrefix(s1,s2string)int{

i:=0

fori＜len(s1)&&i＜len(s2){

ifs1[i]==s2[i]{

i++

}else{

break

}

}

returni

}

//获取最长的公共子串

funcgetMaxCommonStr(txtstring)string{

n:=len(txt)

//用来存储后缀数组

suffixes:=make([]string,n)

longestSubStrLen:=0

varlongestSubStrstring

//获取到后缀数组

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

suffixes[i]=txt[i:]

}

sort.Strings(suffixes)

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

tmp:=maxPrefix(suffixes[i],suffixes[i-1])

iftmp＞longestSubStrLen{

longestSubStrLen=tmp

longestSubStr=(suffixes[i])[0:i+1]

}

}

returnlongestSubStr

}

funcmain(){

txt:="banana"

fmt.Println("最长的公共子串为",getMaxCommonStr(txt))

}

算法性能分析：

这种方法在生成后缀数组的复杂度为O(n)，排序的算法复杂度为O(nlogn*n)，最后比较相邻字符串的操作的时间复杂度为O(n)，所以，算法的时间复杂度为O(nlogn*n)。此外，由于申请了长度为n的额外的存储空间，因此空间复杂度为O(n)。[考点]求一个串中出现的第一个最长重复子串

5.

题目描述：

给定一个字符串，求串中字典序最大的子序列。字典序最大的子序列是这样构造的：给定字符串a0a1…an-1，首先在字符串a0a1…an-1找到值最大的字符ai，然后在剩余的字符串ai+1…an-1中找到值最大的字符aj，然后在剩余的aj+1…an-1中找到值最大的字符ak…直到字符串的长度为0，则aiajak…即为答案。正确答案：方法一：顺序遍历法

最直观的思路就是首先遍历一次字符串，找出最大的字符ai，接着从ai开始遍历再找出最大的字符，依此类推直到字符串长度为0。

以”acbdxmng”为例，首先对字符串遍历一遍找出最大的字符‘x’，接着从‘m’开始遍历找出最大的字符‘n’，然后从‘g’开始遍历找到最大的字符为‘g’，因此“acbdxmng”的最大子序列为“xng”。实现代码如下：

packagemain

import(

"fmt"

)

//求串中字典序最大的子序列

funcgetLargestSub(strstring)string{

ll:=len(str)

largestSub:=make([]byte,ll+1)

k:=0

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

largestSub[k]=str[i]

fofj:=i+1;j＜ll;j++{

//找出第i个字符后面最大的字符放到largestSub[k]中

ifstr[j]＞largestSub[k]{

largestSub[k]=str[j]

i=j

}

}

k++

}

returnstring(largestSub[0:k])

}

funcmain()(

s:="acbdxmng"

result:=getLargestSub(s)

ifresult==""{

fmt.Println("字符串为空")

}else{

fmt.Println(result)

}

}

程序的运行结果为

xng

算法性能分析：

这种方法在最坏的情况下(字符串中的字符按降序排列)，时间复杂度为O(n2)；在最好的情况下(字符串中的字符按升序排列)，时间复杂度为O(n)。此外这种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O(n)。

方法二：逆序遍历法

通过对上述运行结果进行分析，发现an-1一定在所求的子串中，接着逆序遍历字符串，大于或等于an-1的字符也一定在子串中，依次类推，一直往前遍历，只要遍历到的字符大于或等于子串首字符时，就把这个字符加到子串首。由于这种方法首先找到的是子串的最后一个字符，最后找到的是子串的第一个字符，因此，在实现的时候首先按照找到字符的顺序把找到的字符保存到数组中，最后再对字符数组进行逆序从而得到要求的字符。以"acbdxmng"为例，首先，字符串的最后一个字符‘g’一定在子串中，接着逆向遍历找到大于等于‘g’的字符‘n’加入到子串中“gn”(子串的首字符为‘n’)，接着继续逆向遍历找到大于或等于‘n’的字符‘x’加入到子串中“gnx”，接着继续遍历，没有找到比‘x’大的字符。最后对子串“gnx”逆序得到"xng”。实现代码如下：

packagemain

import(

"fmt"

)

funcgetLargestSub2(txtstring)string{

ll:=len(txt)

largestSub:==make([]byte,ll+1)

//最后一个字符一定在子串中

largestSub[0]=txt[ll-1]

i:=ll-2

j:=0

//逆序遍历字符串

for;i＞=0;i--{

iftxt[i]＞=largestSub[j]{

j++

largestSub[j]=txt[i]

}

}

largestSub[j+1]=''

//对子串进行逆序遍历

fori=0;i＜j;i,j=i+1,j-1{

trap:=largestSub[i]

largestSub[i]=largestSub[j]

largestSub[j]=tmp

}

returnstring(largestSub)

}

funcmain(){

s:="acbdxmng"

fmt.Println("逆序遍历法")

result:=getLargestSub2(s)

ifresult==""{

fmt.Println("字符串为空")

}else{

fmt.Println(result)

}

}

算法性能分析：

这种方法只需要对字符串遍历一次，因此，时间复杂度为O(n)。此外，这种方法需要申请n+1个额外的存储空间，因此，空间复杂度为O(n)。[考点]如何求解字符串中字典序最大的子序列

6.

题目描述：

给定一个能判断一个单词是否为另一个单词的子字符串的方法，记为isSubstring。如何判断s2是否能通过旋转s1得到(只能使用一次isSubstring方法)。例如：“waterbottle”可以通过字符串“erbottlewat”旋转得到。正确答案：如果题目没有对isString使用的限制，可以通过求出s2进行旋转的所有组合，然后与s1进行比较。但是这种方法的时间复杂度比较高。通过对字符串旋转进行仔细分析，发现对字符串s1进行旋转得到的字符串一定是s1s1的子串。因此可以通过判断s2是否是s1s1的子串来判断s2能够通过旋转s1得到。例如：s1=“waterbottle”，那么s1s1=“waterbottlewaterbottle”，显然s2是s1s1的子串。因此s2能通过旋转s1得到。实现代码如下：

packagemain

import(

"s