algorithm - 需要删除的最小位数，留下一个可以被 8 整除的数字

Question

给定一个数n

我们必须找到最少删除其数字的次数才能找到数字是否可以被 8 整除？

e.g.
2156

这里需要的最小删除数是 1，因为从中删除 1 得到数字 256，它可以被 8 整除

256 ...Here  answer is 0 
12156    Here answer is 1
256111 here answer is 3

Answer 1

好吧，首先你需要知道只有最后 3 位数字除以 8 才能除以 8。仅当 4*x+2*y+z 除以 8 时，数字 xyz(x*10^2+y*10+z) 才能除以 8。所以我建议为每个可能的模块计算所有可能的长度为 2 的对乘以 8 .

例如，我们的号码等于:321321342。 z 等于 2。所以我们需要找到满足 (4*x+2*y)%8 = 6 的 (x,y) 对，因为 (4x+2y+z)%8 必须等于零。因此，我们构建了一个字典，其键为 (4x+2y)，值为 x 和 y 的一对索引 (i,j)。之后，您需要遍历所有可能的 z 值并取最小结果。算法将是 O(n^2) 复杂度

这是一些代码:

def solve(a):
        lst = digits(a)
        results = []
        d=collections.defaultdict(list)
        for i in range(1,len(lst)-1):
                    for j in range(i+1,len(lst)):
                            d[(4*lst[j]+2*lst[i])%8].append((i,j))
        for i in range(len(lst)-2):
            z = lst[i]
            if z%2==1:
                continue
            pairs = d[8-z]
            for k,v in pairs:
                if i>=k:
                    pass
                else:
                    results.append((i,k,v))
        return results

函数“solve”返回除以 8 的数组值的可能索引列表。

def solveNumberResult(number):
  result = solve(number)
  mn = result[0]
  for i,j,k in result:
    if sum(mn)>i+j+k:
        mn=(i,j,k)
  return i+(j-i-1)+(k-j-1)

获取求解函数的结果，然后找到最佳的数字删除数。

solveNumberResult(256111) =>3 
solveNumberResult(256)    =>0
solveNumberResult(2156)   =>1

希望，它有效