百度2023秋招面试算法真题解析
2023-09-17 20:41
发布于：河北省
大家好，我是吴师兄，关注我，每天更新大厂最新笔试题解析。
题目描述
小红有一个长度为n的排列，她可以选择两个位置，然后交换两个位置的数。
她想知道能否通过最多一次交换，使得存在一个连续子段，是长度为k的排列。
排列是指一个长度为 len 的整数数组，数组中包含1到len的每个数，且每个数只出现一次。
输入描述
第一行两个整数n,k，表示排列长度和连续子段长度。
第二行n个整数a1, a2, ..., an，表示排列。
1 <= k <= n <= 10^5
输出描述
如果能够通过最多一次交换，存在一个连续子段是排列，输出YES，并输出交换的位置:先输出一个整数x (0 <= x <= 1)，然后输出x行，每行两个整数u, v，表示交换位置u, v (u < v)
否则输出NO。
示例输入5 3
1 2 3 4 5
输出YES
0
解题思路
本题看似很复杂，实际上由于我们要找的是一个固定长度为k的滑动窗口，因此可以直接使用固定滑窗的方法来解答。
一个长度为k的排列，其中一定包含的是1到k一共k个数，由于最多可以交换一次，我们可以允许固定滑窗中包含至多一个大于k的数。故我们可以构建一个哈希表dic，用于储存滑窗中所有大于k的数以及其下标，如果在滑动过程中，发现dic的长度小于等于1，则说明此时固定滑窗只包含至多一个大于k的数，这个数可以通过与其他的某个数进行交换，来使得该滑窗变成一个长度为k的排列。
滑窗三问
Q1：对于每一个右指针right所指的元素right_num，做什么操作？
Q2：什么时候要令左指针left右移？对于left所指的元素left_num，要做什么操作？
Q3：什么时候进行ans的更新？如何更新？
滑窗三答
A1：若right_num大于k，则将其下标right计入哈希表dic中，即dic[right_num] = right
A2：在固定滑窗中，left始终为right-N。若left_num大于k，则需要将其在dic中所储存键值对删除，即del dic[left]。
A3：当发现len(dic) <= 1时，说明此时此时固定滑窗可以至多一次交换，使得该滑窗变成一个长度为k的排列。此时退出循环，寻找窗口中缺失的那个数的下标。
注意在更新答案时，存在一种极为特殊的情况需要判断：
当len(dic) == 1，且left恰好指向的是窗口中大于k的数，right+1恰好指向的是需要交换的数，那么窗口[left+1，right+1]是可以不通过交换就构建长度为k的排列的，所以此时应该输出交换次数为0。
代码# 大厂算法训练营添加微信：278166530
# 根据dic的情况，获取答案的函数
defget_ans(nums, dic, right, k):
x, first, second = 0, 0, 0
# 若dic长度为0，说明此时固定滑窗就是一个长度为k的排列
# 交换次数x为0，无需做任何修改。
# 若dic长度为1，需要做以下判断
iflen(dic) == 1:
# 第一个数字的位置，为dic中唯一一个键值对的value
first = list(dic.values)[0]
# 长度为k的排列的和可以用等差数列求和公式获得，记为A
# 固定窗口的和可以直接计算，记为B
# 窗口中多出来的数字，记为C
# 窗口中缺失的数字num_miss，为A-(B-C)
num_miss = (1+k)*k//2- sum(nums[right-k+1:right+1]) + list(dic.keys)[0]
# 找到num_miss在nums中的下标
second = nums.index(num_miss)
# 特殊情况判断：
# 若此时second的位置在窗口右边界right的下一个位置right+1
# 同时first的位置在窗口左边界right-k+1的位置
# 说明下一个窗口可以无需进行交换，就可以获得长度为k的排列
ifsecond == right+1andfirst == right-k+1:
x = 0
else:
x = 1
returnx, first, second
n, k = map(int, input.split)
nums = list(map(int, input.split))
# 初始化交换次数为任意一个大于1的数
x = 2
# 构建哈希表，储存固定滑窗中，所有大于k的元素的下标
dic = {num: i fori, num inenumerate(nums[:k]) ifnum > k}
# 若第一个固定滑窗就满足题意，则直接获得答案
iflen(dic) <= 1:
# 第一个窗口的有边界right = k-1
x, first, second = get_ans(nums, dic, k-1, k)
else:
forright, right_num inenumerate(nums[k:], k):
# A1
ifright_num > k:
dic[right_num] = right
# A2
left = right - k
left_num = nums[left]
ifleft_num > k:
deldic[left_num]
# A3
iflen(dic) <= 1:
x, first, second = get_ans(nums, dic, right, k)
break
# 根据最终得到的x的结果，输出答案
ifx <= 1:
print("YES")
ifx == 1:
print(1)
# 先输出小的位置，再输出大的位置
iffirst > second:
first, second = second, first
print("{} {}".format(first, second))
else:
print(0)
else:
print("NO")
最后，欢迎想要刷题进大厂的小伙伴加入吴师兄的大厂算法训练营。
很多编程零基础的同学在第一天的学习中，一口气刷了 5 题！
图片
有的同学每天记录自己的学习笔记。
吴师兄全职 24 小时在线，和其他两个老师一起随时解答你的疑惑，让你少走弯路。
图片
已经服务了上千学员，广受好评。
每周直播细致的讲解和答疑，帮助你学的更扎实一些。
想要咨询吴师兄大厂算法训练营的同学可以添加微信：278166530，备注咨询。
关注吴师兄，算法学习好轻松。
安可时刻
责任编辑：
