当前位置：首页 > news >正文

解决leetcode第3850题.统计结果等于k的序列数目

news 2026/5/12 1:54:11

3850.统计结果等于K的序列数目

难度：困难

问题描述：

给你一个整数数组nums和一个整数k。

从初始值val=1开始，从左到右处理nums。在每个下标i处，你必须恰好选择以下操作之一：

将val乘以nums[i]。

将val除以nums[i]。

保持val不变。

在处理完所有元素后，当且仅当val的最终有理数值恰好等于k时，才认为val等于k。

返回生成val==k的不同选择序列的数量。

注意：除法是有理数除法（精确除法），而不是整数除法。例如，2/4=1/2。

示例1:

输入:nums=[2,3,2],k=6

输出:2

解释:

以下2个不同的选择序列导致val==k：

序列对nums[0]的操作对nums[1]的操作对nums[2]的操作最终val

1 乘法：val=1*2=2 乘法：val=2*3=6 保持val不变 6

2 保持val不变乘法：val=1*3=3 乘法：val=3*2=6 6

示例2:

输入:nums=[4,6,3],k=2

输出:2

解释:

以下2个不同的选择序列导致val==k：

序列对nums[0]的操作对nums[1]的操作对nums[2]的操作最终val

1 乘法：val=1*4=4 除法：val=4/6=2/3 乘法：val=(2/3)*3=2 2

2 保持val不变乘法：val=1*6=6 除法：val=6/3=2 2

示例3:

输入:nums=[1,5],k=1

输出:3

解释:

以下3个不同的选择序列导致val==k：

序列对nums[0]的操作对nums[1]的操作最终val

1 乘法：val=1*1=1 保持val不变 1

2 除法：val=1/1=1 保持val不变 1

3 保持val不变保持val不变 1

提示:

1<=nums.length<=19

1<=nums[i]<=6

1<=k<=10**15

问题分析：

对于元素个数为n的整数序列nums，其元素是固定不变的，生成val==k的不同选择序列，实际上是对这些元素使用*、/和保持不变形成各种操作序列，为此，约定对于*、/和保持不变三种操作，对应使用字符*、/和.来表示。对整数序列nums中每一个元素进行操作，首先应找出对各种元素进行可能操作的序列，然后再来判断这些操作结果是不是等于k，如果等于k，则统计val==k的记数器记数，并输出这种操作序列，最后再把记数器的值输出即可。

程序如下：

#对于n个元素的数组，每个元素都要进行三种处理*/.中的一种处理(其中.表示保持不变），共有多少种处理排列组合 def get_all_list(n): if n == 1: return ['.', '/', '*'] else: b = get_all_list(n - 1) t = [] for i in b: c = '.' + i t.append(c) c = '/' + i t.append(c) c = '*' + i t.append(c) return t #对于一次处理，返回处理结果，s表示一次处理，如*3、/2或者.5等等，val表示处理结果 def analysis_str(s,val): if s[0]=='.': return val else: val=eval(str(val)+s) return val #根据nums数组和操作符s生成操作序列 def create_operate_array(nums,s): t=list(zip(s,nums)) c=list(i[0]+str(i[1]) for i in t) return c #检查操作序列的操作结果是否等k def check_operate_array_result(operate_array,k): m=[] n=[] for i in operate_array: if i[0]=='*': m.append(i) else: n.append(i) m.extend(n) val=1 for i in m: val=analysis_str(i,val) return val==k #主程序 nums=eval(input('pls input nums=')) k=int(input('pls input k=')) n=len(nums) operate_array=get_all_list(n) c=0 for i in operate_array: val=1 operate_number_array = create_operate_array(nums,i) if check_operate_array_result(operate_number_array, k): print('操作序列：',operate_number_array) c += 1 print('不同选择序列数量为：',c)