百度2023秋招面试算法真题解析

文章正文
发布时间:2024-07-21 09:10

百度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,备注咨询

关注吴师兄,算法学习好轻松。

安可时刻

返回搜狐,查看更多

责任编辑: