OPPO校招面试算法真题解析

将 脚本之家 设为“星标⭐”
第一时间收到文章更新

来源公众号：吴师兄学算法  ID：CXYxiaowu

已获得原公众号的授权转载

题目描述

小欧拿到了一个数组，她准备选择一个连续子数组，满足该连续子数组的所有元素乘积的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)

  推荐阅读：