在Python中,通过将数字字符串拆分来计算我们可以创建值列表的方法的程序

在Python中,通过将数字字符串拆分来计算我们可以创建值列表的方法的程序

假设我们有一个字符串s。s包含从0-9的数字,我们还有另一个数字k。我们必须找出s可以表示为[1,k]中数字列表的不同方式的数量。如果答案非常大,则返回结果mod 10^9 + 7。

因此,如果输入像s =“3456”k = 500,则输出将为7,因为我们可以像[3,4,5,6],[34,5,6],[3,4,56],[3,45,6],[34,56],[345,6],[3,456]这样表示s。

要解决这个问题,我们将遵循以下步骤:

  • m: = 10 ^ 9 + 7

  • N:s的大小

  • dp:一个大小为(N + 1)的列表,并填充为0

  • dp [N]:= 1

  • for i in range N – 1 to 0,递减1,

    • curr_val:= 0

    • for j in range i to N,

      • curr_val:= curr_val * 10 +(s [j]作为数字)

      • 如果curr_val在1到k的范围内,

      • dp [i]:=(dp [i] + dp [j + 1])mod m

      • 否则,

      • 退出循环

  • 返回dp [0]

以下是更好的理解实现的示例-

示例

class Solution:
   def solve(self,s,k):
      m = 10 ** 9 + 7
      N = len(s)
      dp = [0] *(N + 1)
      dp [N] = 1
      for i in range(N-1,-1,-1):
         curr_val = 0
         for j in range(i,N):
            curr_val = curr_val * 10 + int(s [j])
            if 1 <= curr_val <= k:
               dp [i] =(dp [i] + dp [j + 1])%m
            else:
               break
      返回dp [0]
ob = Solution()
s = “3456”
k = 500
print(ob.solve(s,k))

输入

"3456",500

输出

7

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程