OPPO校招面试算法真题解析

文章预览

来自公众号： 吴师兄学算法 题目描述 小欧拿到了一个数组，她准备选择一个连续子数组，满足该连续子数组的所有元素乘积的 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 的倍数。 故题目可以简化为， 找到最短的连续子数组，这 ………………………………