使用Python编写程序以查找使目标数组的函数调用的最小数量
假设我们有以下函数定义:
def modify(arr, op, index):
if op == 0:
arr[index] += 1
if op == 1:
for i in range(len(arr)):
arr[i] *=2
我们必须找出需要多少次函数调用才能从相同大小的零数组中生成给定的数组nums?
所以,如果输入是nums = [1,5,3],那么输出将是7,因为最初所有元素都是0,[0,0,0]
- 在第一步中,将第二个元素增加1,因此数组为 [0,1,0]
-
将第二个元素加倍, 得到 [0,2,0]
-
增加第三个元素1,所以数组变为 [0,2,1]
-
将索引1到2之间的元素加倍,因此数组变为 [0,4,2]
-
将所有元素增加1 [此处共有三个操作]
因此需要进行3+4 = 7次操作。
要解决这个问题,我们将按照以下步骤进行−
- ans :=一个包含两个元素的数组,都是0
-
对于nums中的每个n,执行以下操作
- double := 0
-
当n为非零值时,执行以下操作
- 如果n为奇数,则
-
n := n/2的商数
-
double := double + 1
-
否则,
-
n := n – 1
-
ans[0] := ans[0] + 1
- 如果n为奇数,则
-
ans[1] := ans[1]和double中的最大值
-
返回ans的所有元素之和
让我们看下面的实现,以便更好地理解−
更多Python相关文章,请阅读:Python 教程
示例
def solve(nums):
ans = [0, 0]
for n in nums:
double = 0
while(n):
if not n%2:
n = n//2
double+=1
else:
n-=1
ans[0]+=1
ans[1] = max(ans[1], double)
return sum(ans)
nums = [1,5,3]
print(solve(nums))
输入
[1,5,3]
输出
7