专栏名称: 算法与数据结构
算法与数据结构知识、资源分享
目录
相关文章推荐
算法与数据结构  ·  OPPO校招面试算法真题解析 ·  昨天  
算法爱好者  ·  30+ 年前的 Win 3.1 ... ·  2 天前  
九章算法  ·  senior地狱模式上岸,亲测有效的SD ... ·  1 周前  
51好读  ›  专栏  ›  算法与数据结构

OPPO校招面试算法真题解析

算法与数据结构  · 公众号  · 算法  · 2024-11-05 11:00

正文

来自公众号:吴师兄学算法

题目描述

小欧拿到了一个数组,她准备选择一个连续子数组,满足该连续子数组的所有元素乘积的2进制末尾至少有k0。小红想知道,这个连续子数组的最短长度是多少?

输入描述

第一行输入两个正整数nk。第二行输入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代表什么

实际上,如果一个数的二进制末尾存在k0,说明这个数是2k次方即2^k的倍数。

比如数字24,其二进制为11000,末尾存在30,说明242^3 = 8的倍数。

故题目可以简化为,找到最短的连续子数组,这个子数组的乘积是2k次方即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)

---END---