其他
OPPO校招面试算法真题解析
The following article is from 吴师兄学算法 Author 吴师兄
第一时间收到文章更新
已获得原公众号的授权转载
题目描述
小欧拿到了一个数组，她准备选择一个连续子数组，满足该连续子数组的所有元素乘积的2进制末尾至少有k个0。小红想知道，这个连续子数组的最短长度是多少？
输入描述
第一行输入两个正整数n和k。第二行输入n个正整数ai。
输出描述
一个整数，代表连续子数组的最短长度。如果不存在这样的子数组，输出-1。
示例一
输入
6 3
1 2 3 4 5 6
输出
3
说明
取[2,3,4]即可，2*3*4=24，其二进制为11000。
示例二
输入
6 4
2 2 2 1 4 8
输出
2
示例三
输入
5 1
1 1 1 1 1
输出
-1
解题思路
2进制末尾的0代表什么
实际上，如果一个数的二进制末尾存在k个0，说明这个数是2的k次方即2^k的倍数。
比如数字24，其二进制为11000，末尾存在3个0，说明24是2^3 = 8的倍数。
故题目可以简化为，找到最短的连续子数组，这个子数组的乘积是2的k次方即2^k的倍数。
子数组乘积与2的k次方的关系
由于对连续子数组的操作是相乘，只有包含质因数2的元素，才会对整个子数组的相乘结果造成影响。因此我们可以对数组中的每一个元素进行质因数分解，只考虑每个元素的质因数中2的个数，得到相应的数组nums_contain_2。
以原数组 nums = [1, 2, 3, 4, 5, 6]为例，我们可以得到每个元素的质因数中2的个数的数组nums_contain_2 = [0, 1, 0, 2, 0, 1]。
故问题可以进一步简化为，找到nums_contain_2的最短的连续子数组，该数组的和至少为k。这就是一个非常典型的滑动窗口问题了。
代码
# 题目：【不定滑窗】OPPO2023秋招提前批-小欧的区间取数
# 作者：闭着眼睛学数理化
# 算法：不定滑窗
# 答疑微信：od1336
from math import inf
# 计算数字num包含多少个质因数2的函数
def get_num_contain_2(num):
# 初始化个数为2
ans = 0
# 如果num可以整除2，持续循环
# 整除2，同时ans递增1
while(num % 2 == 0):
num //= 2
ans += 1
return ans
n, k = map(int, input().split())
nums = list(map(int, input().split()))
# 获得nums数组中每一个元素，包含质因数2的个数
nums_contain_2 = [get_num_contain_2(num) for num in nums]
# 初始化答案、滑窗中质因数2的个数、左指针
ans = inf
windows_contain_2 = 0
left = 0
for right, num in enumerate(nums_contain_2):
# A1
windows_contain_2 += num
# A2
if windows_contain_2 >= k:
while windows_contain_2 >= k:
windows_contain_2 -= nums_contain_2[left]
left += 1
# A3
ans = min(ans, right-left+2)
print(ans if ans != inf else -1)
前段时间面试了一些人，有这些槽点跟大家说说 面试官：try-catch 到底写在循环里面好，还是外面好？大部分人都会答错！ Go 面试题：string 是线程安全的吗？ 我不允许还有校招&社招党连这些HR黑话都听不懂！ 算法面试真题：完美走位