美团实习笔试解析（go语言版）

写在前面

本菜鸡一go语言萌新，想着找点大厂实习提高自己，结果笔试都拉跨的一，基本都没做出来，笔试后再回看这些题真的还都不是很难，在这里做以总结。

说明

本次美团笔试共5道题，本菜鸡就记得前四道题目了，所以就重新写一下前四道，注意哦，笔试平台跟leetcode不一样，是要自己写包和输入输出的。

01川麻换牌

本题本质上是类似于找最大子集长度，属于简单题

输入 第一行 一个整数n(1 输入 第二行 n个空格隔开的整数数(1-200000) 表示具体可重集
输出 满足一个尽可能大的子集使得没有两个数是“连续”的(两数之差的绝对值不超过1)
样例输入

6
1 2 3 5 6 7

样例输出

4

package mainimport("bufio""fmt""os""sort""strconv"
)
func main() {var T intscanner := bufio.NewScanner(os.Stdin)scanner.Split(bufio.ScanWords)scanner.Scan()T, _ = strconv.Atoi(scanner.Text())//输入 其实用_,_=fmt.Scan(&T)就可以了nums := make([]int, T)for i := 0; i < T; i++ {var n intscanner.Scan()n, _ = strconv.Atoi(scanner.Text())nums[i] = n}sort.Ints(nums)//我们先对其排序if T<2{fmt.Println(T)}maxL:=1for i:=0;i<T;i++{ans:=[]int{}temp:=nums[i]ans=append(ans,nums[i])for j:=i+1;j<T;j++{if nums[j]>=temp+2{ans=append(ans,nums[j])temp=nums[j]}}if maxL<len(ans){maxL=len(ans)}}fmt.Println(maxL)
}

02最大字段和

本题跟leetcode.1330类似但也不完全相同，属于稍微中等题
翻转这个数组的连续一段(如{1,2,3,4,5,6}–>{1,2,5,4,3,6})一次，翻转之后最大子段和是多少

输入 第一行一个整数n(1-100000) 表示数组长度
输入 第二行n个空格隔开的整数数(-1000-1000) 表示具体数组
输出 一个整数，代表翻转之后所得的数组的最大字段和最大的值
样例输入

6
-1 3 -5 2 -1 3

样例输出

7

package mainimport ("bufio""fmt""os""strconv"
)func main() {var T intscanner := bufio.NewScanner(os.Stdin)scanner.Split(bufio.ScanWords)scanner.Scan()T, _ = strconv.Atoi(scanner.Text())nums := make([]int, T)for i := 0; i < T; i++ {var n intscanner.Scan()n, _ = strconv.Atoi(scanner.Text())nums[i] = n}if T==0{fmt.Println(0)}o,c:=nums[0],0ans:=[]int{}ans=append(ans,0)for i,n:=range nums{//最大子数组和if c>0{c+=n}else {c=n}if c>o{o=cans=append(ans,i)}}x:=ans[len(ans)-1]begin:=0for i:=x;i>=0;i--{if o==0{begin=i}o=o-nums[i]}begin++aa:=nums[:begin]bb:=nums[begin:x+1]cc:=nums[x:]fmt.Println(max(maxa(aa),maxa(cc))+maxa(bb))main()
}
func maxa(nums []int)int{if 0==len(nums){return 1}o,c:=nums[0],0for _,n:=range nums{if c>0{c+=n}else {c=n}if c>o{o=c}}return o
}func max(a,b int) int {if a>b{return a}return b
}

03切豆腐

看到标题大概就知道这是一个模拟题，属于题目长但理解之后就是简单题
小明切豆腐，每次都垂直于x,y,z轴切，每次切的长度是距离豆腐右上角那个点(或任意一个固定的点)的距离，求切开之后豆腐最大体积

输入 第一行 n,m 代表n为边长的立方体豆腐块 和一共切了m刀
输入 第二行 由x,y,z三种字母构成的m个字母 表示每次垂直于某个坐标轴切
输入 第三行 m个数字 表示每次切的距离右上角点的距离
输出 m行 每次切完之后最大豆腐块体积
样例输入

2 3
x y z
1 1 1

样例输出

4
2
1

package mainimport ("fmt""math"
)func main()  {var n,m int_,_=fmt.Scan(&n,&m)dao:=make([]string,m)for i:=0;i<m;i++{var d string_,_=fmt.Scan(&d)dao[i]=d}l:=make([]int,m)for i:=0;i<m;i++{var l0 int_,_=fmt.Scan(&l0)l[i]=l0}a:=nb:=nc:=nfor i:=0;i<m;i++{if dao[i]=="x"{a=maxxx(l[i], int(math.Abs(float64(a-l[i]))))fmt.Println(a*b*c)}else if dao[i]=="y"{b=maxxx(l[i], int(math.Abs(float64(b-l[i]))))fmt.Println(a*b*c)}else if dao[i]=="z"{c=maxxx(l[i],int(math.Abs(float64(c-l[i]))))fmt.Println(a*b*c)}}}
func maxxx(a,b int) int {if a>b{return a}return b
}

04查询区间和

这个题属于正常的中等题目难度，但是需要注意的是不能通过全排列暴力解题(别问我怎么知道的o(╥﹏╥)o)，因为可能会有5000！这样的数字。

给出一个长度为n的数组，进行m次数组上的区间操作，一个查询区间内数的和一个区间内所有数加上一个值
如果允许重新排列初始数组，则操作中所有查询区间的答案之和能达到多大
输入 有两个数n,m (1-n-5000)(1-m-500)代表数组长度和操作次数
输入 有n个数 代表初始数组中的元素
输入 m行形如1lr或2lrk，分别代表查询[l,r]的元素之和和将下标属于[l,r]的元素全部加上一个定值k。1-l-r-n,1-k-5000
输出 一个整数如果允许重新排列初始数组，则操作中所有查询区间的答案之和能达到多少

最终输出之和为9+16+17=42
样例输入

5 5
3 4 2 1 5
1 1 3
2 3 4 2
1 2 4
2 2 3 2
1 3 5

样例输出

42

package mainimport ("fmt""math""sort"
)func main() {var n, m int_, _ = fmt.Scan(&n, &m)num := make([]int, n)for i := 0; i < n; i++ {var x int_, _ = fmt.Scan(&x)num[i] = x}nums := make([][]int, n)for i := 0; i < m; i++ {flag := 0l, r, k := 0, 0, 0_, _ = fmt.Scan(&flag)if flag == 1 {_, _ = fmt.Scan(&l, &r)nums[i] = append(nums[i], flag, l, r)} else {_, _ = fmt.Scan(&l, &r, &k)nums[i] = append(nums[i], flag, l, r, k)}}diss0:=make(map[int]int,n)for i:=0;i<len(nums);i++{if nums[i][0]==1{for j:=nums[i][1]-1;j<nums[i][2];j++{diss0[j]++}}}//fmt.Println(diss)//map[0:1 1:2 2:3 3:2 4:1]cpnum:= make([]int, n)copy(cpnum,num)//fmt.Println(cp)//[3 4 2 1 5]sort.Ints(cpnum)//fmt.Println(cp)//[1 2 3 4 5]cpdiss:=[]int{}for _,v:=range diss0{cpdiss=append(cpdiss,v)}sort.Ints(cpdiss)//fmt.Println(cpdiss)//[1 1 2 2 3]finnum:=make([]int, n)tr:=0for i:=n-1;i>=0;i--{for id,v:=range diss0{if cpdiss[i]==v{finnum[id]=cpnum[i]tr=id//fmt.Println(diss0)}}diss0[tr]=math.MaxInt}//fmt.Println(finnum)//[2 3 5 4 1]diss:=make(map[int]int,n)for i:=0;i<len(nums);i++{if nums[i][0]==1{for j:=nums[i][1]-1;j<nums[i][2];j++{diss[j]++}}}cha:=0for i,v :=range diss{cha+=finnum[i]*v}//fmt.Println(cha)//32dissou:=make(map[int]int,n)disjia:=make(map[int]int,n)for i:=0;i<len(nums);i++{if nums[i][0]==1{for j:=nums[i][1]-1;j<nums[i][2];j++{dissou[j]++}//sum+=Sum(nums[i][1],nums[i][2],num)//fmt.Println(nums[i][1],nums[i][2])}else if nums[i][0]==2{for j:=nums[i][1]-1;j<nums[i][2];j++{disjia[j]+=(diss[j]-dissou[j])*nums[i][3]}}}//fmt.Println(disjia)//map[1:0 2:6 3:4]jia:=0for _,v:=range disjia{jia+=v}//fmt.Println(jia)//10finans:=jia+chafmt.Println(finans)
}

本题进行2操作的加法部分在整个流程中的总和是不变的，我们只用统计每个位置上进行查询的次数，最多查询的那一位放最大的值，同时动态更新加法部分，这样就没有问题了。

总结

本菜鸡是真的菜
后序和其他人交流的时候他们的表情都是：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！