解决leetcode第3883题统计满足数位和数组的非递减数组数目

3883.统计满足数位和数组的非递减数组数目难度困难问题描述给你一个长度为n的整数数组digitSum。如果一个长度为n的数组arr满足以下条件则认为它是有效的0arr[i]5000它是非递减的。arr[i]的数位和等于digitSum[i]。返回一个整数表示不同的有效数组的数量。由于答案可能很大请将其对1097取模后返回。如果一个数组的每个元素都大于或等于它的前一个元素如果存在则称该数组是非递减的。示例1输入digitSum[25,1]输出6解释数位和为25的数字有799、889、898、979、988和997。数位和为1且可以出现在这些值之后同时保持数组非递减的唯一数字是1000。因此有效数组为[799,1000]、[889,1000]、[898,1000]、[979,1000]、[988,1000]和[997,1000]。因此答案是6。示例2输入digitSum[1]输出4解释有效数组为[1]、[10]、[100]和[1000]。因此答案是4。示例3输入digitSum[2,49,23]输出0解释在范围[0,5000]内没有数位和为49的整数。因此答案是0。提示1digitSum.length10000digitSum[i]50问题分析一种做法是先把digits数组中的数字分解成数字和数组的形式比如digits[1,2]可以把组成数字和为1和2的所有数字找出构成一个数组[[1, 10, 100, 1000],[2, 11, 20, 101, 110, 200, 1001, 1010, 1100, 2000]]然后从[1, 10, 100, 1000]和[2, 11, 20, 101, 110, 200, 1001, 1010, 1100, 2000]中找出所有的非递减排列如果后面还有数字和排列则可以把这次的非递减排列的最后一个数字提取出来形成一个数组然后用其中的元素与后面的数字和排列中的数字依次进行比较从而可以构成新的非递减排列元素直到得到最终结果。程序如下#对于给定的整数n找出在【05000】中数位和等于n的所有整数并以列表形式返回 def get_digits(n): digits[] for i in range(0, 5001): t list(str(i)) s sum(list(map(int, t))) if s n: digits.append(i) return digits #将两个数组能够组成的所有非递减排列找出并返回其中a为上一次生成的b为新的数组 def get_all_non_decreasing_order_from_two_arrays(a,b): t [] clist(i[-1] for i in a) mlen(a) nlen(b) for i in range(m): for j in range(n): if c[i]b[j]: da[i][b[j]] t.append(d) return t # 主程序 digitsumeval(input(pls input digitsum)) nlen(digitsum) t[] for i in digitsum: t.append(get_digits(i)) templist([x] for x in t[0]) for i in range(1,n): atemp bt[i] tempget_all_non_decreasing_order_from_two_arrays(a,b) print(不同有效数组如下) for i in range(1,len(temp)1): sstr(temp[i-1]) if i%50: print({:20}.format(s),end\n) else: print({:20}.format(s),end ) print(f\n共有不同有效数组共{len(temp)%(10**97)}个)运行实例一pls input digitsum[2,3]不同有效数组如下[2, 3] [2, 12] [2, 21] [2, 30] [2, 102][2, 111] [2, 120] [2, 201] [2, 210] [2, 300][2, 1002] [2, 1011] [2, 1020] [2, 1101] [2, 1110][2, 1200] [2, 2001] [2, 2010] [2, 2100] [2, 3000][11, 12] [11, 21] [11, 30] [11, 102] [11, 111][11, 120] [11, 201] [11, 210] [11, 300] [11, 1002][11, 1011] [11, 1020] [11, 1101] [11, 1110] [11, 1200][11, 2001] [11, 2010] [11, 2100] [11, 3000] [20, 21][20, 30] [20, 102] [20, 111] [20, 120] [20, 201][20, 210] [20, 300] [20, 1002] [20, 1011] [20, 1020][20, 1101] [20, 1110] [20, 1200] [20, 2001] [20, 2010][20, 2100] [20, 3000] [101, 102] [101, 111] [101, 120][101, 201] [101, 210] [101, 300] [101, 1002] [101, 1011][101, 1020] [101, 1101] [101, 1110] [101, 1200] [101, 2001][101, 2010] [101, 2100] [101, 3000] [110, 111] [110, 120][110, 201] [110, 210] [110, 300] [110, 1002] [110, 1011][110, 1020] [110, 1101] [110, 1110] [110, 1200] [110, 2001][110, 2010] [110, 2100] [110, 3000] [200, 201] [200, 210][200, 300] [200, 1002] [200, 1011] [200, 1020] [200, 1101][200, 1110] [200, 1200] [200, 2001] [200, 2010] [200, 2100][200, 3000] [1001, 1002] [1001, 1011] [1001, 1020] [1001, 1101][1001, 1110] [1001, 1200] [1001, 2001] [1001, 2010] [1001, 2100][1001, 3000] [1010, 1011] [1010, 1020] [1010, 1101] [1010, 1110][1010, 1200] [1010, 2001] [1010, 2010] [1010, 2100] [1010, 3000][1100, 1101] [1100, 1110] [1100, 1200] [1100, 2001] [1100, 2010][1100, 2100] [1100, 3000] [2000, 2001] [2000, 2010] [2000, 2100][2000, 3000]共有不同有效数组共131个运行实例二pls input digitsum[2]不同有效数组如下[2] [11] [20] [101] [110][200] [1001] [1010] [1100] [2000]共有不同有效数组共10个运行实例三pls input digitsum[25,2]不同有效数组如下[799, 1001] [799, 1010] [799, 1100] [799, 2000] [889, 1001][889, 1010] [889, 1100] [889, 2000] [898, 1001] [898, 1010][898, 1100] [898, 2000] [979, 1001] [979, 1010] [979, 1100][979, 2000] [988, 1001] [988, 1010] [988, 1100] [988, 2000][997, 1001] [997, 1010] [997, 1100] [997, 2000] [1699, 2000][1789, 2000] [1798, 2000] [1879, 2000] [1888, 2000] [1897, 2000][1969, 2000] [1978, 2000] [1987, 2000] [1996, 2000]共有不同有效数组共34个