字节笔试两道题
来源:3-7 更多和并查集相关的话题
旧日星光
2021-05-10 16:41:21
波波老师 我昨天参加了字节的内推笔试。 有两道题样例没有全部通过。请问下有没有什么更好的方法去实现
题1: 给定两个参数 N、K。 N代表输入的一个字符串的长度 这个字符串由0或者1组成 例如:10010011101 。K代表接下来的操作次数。 每次操作给定两个参数l和r 代表将这个由01组成的字符串 下标从l开始到r结束 的这段字符串0和1翻转,0变成1 1变成0.
如 给定字符串 10010 给定l=1 r=2 就变成 11110 。 求经过k此这样操作后 字符串会变成什么样。
我想到了记录每次操作的区间 如果k次操作后 这段区间被翻转偶数次 则不变 如果翻转奇数次 则翻转。但是没有想到怎么去记录这些区间操作的次数。
题2: 一共N个人玩吃鸡 他们从飞机上跳下来后 可以选择跟随一个人 成为他的跟随者。 一开始每个人都是自己的跟随者。给定参数N和K, N代表一共有多少人 如N = 4 则有编号为 :1 2 3 4 的四个人。K代表有K次操作,每次操作可输入两个参数 如: 1 2 代表编号为1的人跟随了编号为2的人。 问经过k次操作后 最大跟随者的数量。
例子如下:
人员:1 2 3 4
跟随:1 2 3 4
--》跟随操作 1 2
人员:1 2 3 4
跟随:2 2 3 4
--》跟随操作 3 4
人员:1 2 3 4
跟随:2 2 4 4
--》跟随操作 2 3
人员:1 2 3 4
跟随:4 4 4 4
最后输出4 代表最大跟随者数量一共是4个人。
我一开始觉得特别像并查集 但是并查集我记得不清楚就按照自己的想法暴力的去实现
这里边有个坑就是, A要去跟随B , 如果A原先跟随的是自己 就代表他原来可能是领头的 就有可能有其他人去跟随他 我就for循环 去查找谁跟随了A 并把所有跟随A的人全部改成跟随B。 但如果A不是跟随的自己 也就是他之前就跟随了别人 现在又改去跟随了B 就不需要for循环了 直接把A跟随的人改成B就行了。
最后再统计一遍谁拥有的跟随者最多 然后输出。 我感觉我实现的特别暴力,但是也没别的好想法了。
这回面试我被牛客网虐的体无完肤,第一次接触这种形式的做题方式,平时用idea根本不需要记方法名字 不需要记住很多细节,但是牛客网的编译器 什么都点不出来 导包我也不知道这个包在哪里,而且这种Scanner的方式 我第一次接触 直接懵逼了。 非常难受的笔试体验
1回答
1)
你的思路是正确的。我们需要一个方式,能够在一个区间快速地 +1,每次在 [l, r] 区间里 +1,最后看每个位置有过多少次翻转操作,偶数不变,奇数翻转。
区间更新,可以使用线段树。但是对这个问题来说,使用线段树麻烦了,使用差分数组更好。线段树做区间查询优势大,而这个问题不需要区间查询。差分数组这个课程没有介绍,以后有机会我可能会补充上。你可以在网上搜索一下“差分数组”,自学一下,非常非常简单的。
2)
标准的并查集,每个节点记录一下以这个节点为根的树有多少节点(sz)。
==========
补充一下:是的,牛客网上的问题,和 Leetcode 最大的区别是,需要自己写输入,而 Leetcode 上的问题数据已经准备好了,直接处理就好了。这一点了解了,可以简单熟悉一下基本的输入代码。
至于 IDE 的问题,我估计关键还是不适应。其实这两个问题,我简单想了一下,不管是差分数组还是并查集的实现,也不需要使用什么内置的数据结构(PriorityQueue,HashSet,HashMap 什么的。),使用 int[] 就够了。关键还是对算法和数据结构的考察。考区间操作和并查集,其实整体都算是偏难的问题了。。。
继续加油!:)
相似问题