使用 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,做
如果n是奇数,那么
否则,
n:=n/2的商
双:=双+1
n:=n-1
ans[0]:=ans[0]+1
双:=0
当n非零时,做
ans[1]:=ans[1]和double的最大值
返回ans所有元素的总和
让我们看看以下实现以获得更好的理解-
示例
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