BAT实习内推笔试卷（第场）.PDFVIP

NOWCODER.COM ⽜客⽹-中国最⼤IT笔试/⾯试题库 BAT实习内推笔试卷 （第⼆场） ⼀. 编程题 1. 给定⼀个单链表的头部节点head ，链表⻓度为N。 如果N为偶数，那么前N/2个节点算作左半 ，后N/2个 节点算作右半 ； 如果N为奇数，那么前N/2个节点算作左半 ，后N/2+1个节点算作右半 ； 左半 从左到 右依次记为L1-L2-... ，右半 从左到右依次记为R1-R2-...。请将单链表调整成L1-R1-L2-R2-...的样 ⼦。 例如： 1-2-3-4 调整后：1-3-2-4 1-2-3-4-5 调整后：1-3-2-4-5 要求：如果链表⻓度为 N ，时间复杂度请达到O(N) ，额外空间复杂度请达到O(1) 2. 给定⼀个路径数组paths ，表⽰⼀张图。 paths[i]==j代表城市i连向城市j ，如果paths[i]==i表⽰i城市是⾸都，⼀张图⾥只会有⼀个⾸都，不会有分图且 图中除了⾸都指向⾃⼰之外不会有环； 例如：paths={9 1 4 9 0 4 8 9 0 1} 由这个数组表⽰的图如下图所⽰。 城市1是⾸都所以距离为0 ；离⾸都距离为1的城市只有城市9 ；离⾸都距离为2的城市有城市0 ，3 ，7 ；离⾸都 距离为3的城市有城市4 ，8 ；离⾸都距离为4的城市有城市2 ，5 ，6 ； 所以，距离为0的城市有1座；距离为1 的城市有1座；距离为2的城市有3座；距离为3的城市有2座；距离为4的城市有3座；那么统计数组为numArr= { 1 1 3 2 3 0 0 0 0 0} ，numArr[i]==j代表距离为i的城市有j座； 要求实现⼀个void类型的函数，输⼊⼀个路径数 组paths ，直接在原数组上调整，使之变为numArr数组。 paths={9 1 4 9 0 4 8 9 0 1} ，函数处理后，paths= { 1 1 3 2 3 0 0 0 0 0} 。 要求：如果paths⻓度为N ，时间复杂度为O(N) ，额外空间复杂度为O(1) ； 3. 给定⼀个⻓度为N的整型数组arr ，可以划分成左右两个部分： 左部分arr[0..K] ，右部分arr[K+1..arr.length- 1] ，K可以取值的范围是[0 arr.length-2] 求这么多划分⽅案中，左部分中的最⼤值减去右部分最⼤值的绝对 ⽜客出品- NOWCODER.COM ⽜客⽹-中国最⼤IT笔试/⾯试题库 值，最⼤是多少？ 例如： [2 7 3 1 1] 当左部分为[2 7] ，右部分为[3 1 1]时，左部分中的最⼤值减去右部分最 ⼤值的绝对值为4; 当左部分为[2 7 3] ，右部分为[1 1]时，左部分中的最⼤值减去右部分最⼤值的绝对值为6; 最后返回的结果为6。 注意：如果数组的⻓度为N ，请尽量做到时间复杂度O(N) ，额外空间复杂度O(1) 技术QQ群：379386529 微博：/nowcoder 微信 登录⽜客⺴，参与以上题⺫讨论，查看更多笔试⾯试题 ⽜客出品-