幸运数字

[编程题]幸运数字

热度指数：2989 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小雅同学认为6,8是她的幸运数字,而其他数字均不是,一个幸运数是指在十进制表示下只含有幸运数字的数。给定你一个区间（a,b）a和b之间（其中包括a和b幸）运数的个数。

输入描述:

输入两个整数a和b，a的取值范围在1和1000000000之间（其中包括1和1000000000），b的取值范围在a和1000000000之间（其中包括a和1000000000）。

输出描述:

返回a和b之间的幸运数个数，如果入参不合法，请输出-1

示例1

输入

1 10

输出

说明

6,8,6666,88888,6668888,68686688均为幸运数字，当a=1，b=10函数返回值为2。

算法知识视频讲解

Python

TimeMac

#这个代码比较乱，但可以顺序输出结果。已AC
while True:
    try:
        a, b = map(int, input().split())
        if 1 <= a <= 1000000000 and a <= b <= 1000000000:
            res = [0]         #保存幸运数个数
            temp = list(str(a))
                 
            #找出范围内最小的幸运数
            for i in range(len(temp)):
                if temp[i] == '6' or temp[i] == '8':
                    continue
                if temp[i] == '9':
                    temp[i] = '6'
                    for j in range(i - 1, -1, -1):
                        if temp[j] == '6':
                            temp[j] = '8'
                            break
                    else:
                        temp.insert(0, '6')
                elif temp[i] == '7':
                    temp[i] = '8'
                else:
                    temp[i] = '6'
                temp[i + 1: len(temp)] = ['6'] * (len(temp) - (i + 1))
                break
           #此时temp保存着最小的幸运数十进制位数的数组            

            #递归查找结果函数
            def pathThrought(index):
                if index == len(temp) - 1:
                    nowNum = int(''.join(temp))     #此时得到一个幸运数
                    if nowNum <= b:
                        res[0] += 1                 #可在此处输出nowNum
                        if temp[-1] == '6' and nowNum + 2 <= b:
                            res[0] += 1             #nowNum + 2也为一个幸运数
                else:
                    pathThrought(index + 1) #进来的时候temp[index]为6，递归一次
                    temp[index] = '8'       
                    pathThrought(index + 1) #置为8再递归一次
                    temp[index] = '6'       #赋值回去6
            
            #调用递归的过程
            while int(''.join(temp)) <= b:
                pathThrought(len(temp) - 1)
                for i in range(len(temp) - 2, -1, -1): #从末尾位数开始
                    if temp[i] == '8':       #当前位数不能再增大，跳过
                        continue
                    temp[i] = '8'            #本为6，增大为8，然后将右边位数置为6
                    temp[i + 1:] = ['6'] * (len(temp) - i - 1)
                    if int(''.join(temp)) > b:
                        break
                    pathThrought(i + 1)        #进行递归
                
                temp = ['6'] * (len(temp) + 1) #当前位数循环结束，增加位数继续
            print(res[0])

        else:   # a > b的情况
            print(-1)
    except ValueError:  #参数不正确的情况
        print(-1)
    except Exception:
        break

编辑于 2019-03-27 23:43:08 回复(0)