Leetcode2 有趣的数字(基础篇-下)

9.完美数

9.perfectNumber.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
9、对于一个正整数，如果它和除了它以外的所有正因子之和相等，则称这个数为完美数。
    现在，给定一个数N，判断它是否是完美数。如：28 = 1+2+4+7+14

解题思路：
    首先需要将这个数N的所有的因数找出来，拿到所有的因数相加，如果等于N，
    则说明是完美数，否则不是。这里有一个技巧：找到了一个因数，另一个也就找到了，
    除了1和它本身，是成对出现的。
    
    完美数，又称为完全数或完备数。自然中的第一个完美数是6，数字6也往往有着特殊的寓意。
据史料记载，最早开始研究完美数的人是公元前6世界的毕达哥拉斯。当时他已经找到了世上存在的两个完美数：
6和28，毕达哥拉斯曾说: 6象征着完美的婚姻以及健康和美丽，因为它是完整的，其所有因数的和等于它自身。除此之外，
一些《圣经》信仰者也认为6和28是上帝创造世界时所使用的基本数字，上帝创造世界花了6天，28天则是月亮绕地球一周的日数。
在我国古代文化中，数字6和28也被赋予了更多了含义，例如：与6有关的六畜、六谷、六常等，与28相关的二十八星宿等。
完美数仿佛有着神奇的魔力，在历史中总是有许多巧合与之相关。
    目前为止，到底存在多少个完美数依然是个谜，寻找完美数的过程并不十分轻松。到2013年2月6日，人们一共发现了48个完美数。
同样，完美数是十分稀有的，第13位完美数的长度就已经达到314位，之后完美数的长度则更加恐怖，据估计，
将第39位完美数使用4号字打印出来的长度有一本字典那么厚。自从人们发现完美数后，
众多数学家和数学爱好者都不知疲倦的寻找自然界中存在的完美数，这是一个艰苦的过程，直到计算机科学的发展，
对完美数的寻找效率才得到了质的提高。非常神奇的是，至今为止，所有找到的完美数都是偶数，尚无有奇完美数被发现。
'''

import math

def perfectNumber(N):
    if N <= 0:
        return False
    res = 0
    
    for i in range(1, int(math.sqrt(N)) + 1):
        if N % i == 0:
            res += i
            #剔除两个因子相同的情况
            if i * i != N:
                res += N / i
    #因为是成对出现，所以需要乘以2
    if res == N * 2:
        return True
    return False
print(perfectNumber(28))

'''
Output result：
    True
'''

'''
    查表法：在33550336以内的完美数只有五个：6、28、496、8128和33550336
'''

def checkPerfectNumber(N):
    return True if N in [6, 28, 496, 8128, 33550336] else False
print(checkPerfectNumber(8128))

'''
Output result：
    True
'''
复制代码

10.快乐数

10.happyNumber.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
10、对于一个正整数，每一次将该数替换为它每个位置上的平方和，然后重复这个过程直到这个数变为1，
也可能是无限循环但始终变不到1，如果可以变为1，那么这个数就是快乐数，否则就不是。
    例如：19是一个快乐数，证明如下：
    1^2 + 9^2 = 82
    8^2 + 2^2 = 64
    6^2 + 8^2 = 100
    1^2 + 0^2 + 0^2 = 1
    
    现在要求编写程序，求输入一个数N，判断其是否是一个快乐数。
'''

def happyNumber(N):
    #定义一个临时列表存放所有拆解的数字
    tmp = [N]
    while N != 1:
        #将输入的数转换为列表
        l = list((str(N)))
        res = 0
        for i in l:
            res += int(i) * int(i)
        #如果res在tmp中，终止循环，说明不是一个快乐数
        if res in tmp:
            return False
        tmp.append(res)
        N = res
    return True
print(happyNumber(91))

'''
Output result：
    True
'''
复制代码

11.顺次数

11.suitableNumber.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
11、定义顺次数为其每一位数字都比前一位数字大1的整数。例如123, 234, 345, 456等都是顺次数。
    现在，给定一个范围,例如[1000, 10000)，尝试编程查找其范围内的所有顺次数，并将其从小到大的组成列表返回。

解题思路：
    由于每一位比前一位大1，那最小是1，最大就是9。
'''

def suitableNumber(low, high):
    l = []
    #获取第一位，先从大到小排序，如：321，获取到第一位是1
    for num in range(1, 10):
        #获取从又到左前两位，根据如上就是：21，依次循环
        for j in range(num+1, 10):
            num = num * 10 + j
            if num <= high and num >= low:
                l.append(num)
    #从左往右，从小到大排序
    l.sort()
    return l
print(suitableNumber(1000, 10000))


'''
Output result：
    [1234, 2345, 3456, 4567, 5678, 6789]
'''
复制代码

12.进步数

12.progressNumber.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
12、进步数是顺次数的一种扩展，如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是1，
那么这个数就是一个进步数。例如：321是一个进步数，而421不是。
    现在，给定一个范围，尝试编程查找其范围内的所有进步数，并将其由小到大的组成列表返回。
'''

def progressNumber(low, high):
    #存放所有进步数
    l = [0]
    #将所有筛选出来的进步数存放到res中
    res = []
    #定义一个指针
    p = 0
    #将0这个特殊的进步数添加进去
    if low <= 0:
        res.append(0)
    #将一位数的进步数筛选出来
    while l[-1] < 9:
        l.append(l[-1] + 1)
        if l[-1] >= low and l[-1] <= high:
            res.append([-1])
    while l[-1] < high:
        current = l[p]
        if current == 0:
            p += 1
            continue
        #两位以上步阶数进行判断，如果倒数第一位为边界0的话，只能比它大
        if str(current)[-1] == "0":
            nex = current * 10 + int(str(current)[-1]) + 1
            l.append(nex)
            if nex >= low and nex <= high:
                res.append(nex)
        #如果倒数第一位为边界9的话，只能比它小
        elif str(current)[-1] == "9":
            nex = current * 10 + int(str(current)[-1]) - 1
            l.append(nex)
            if nex >= low and nex <= high:
                res.append(nex)
        #如果都没有满足，说明边界在2-8之间
        else:
            nexLeft = current * 10 + int(str(current)[-1]) - 1
            nexRight = current * 10 + int(str(current)[-1]) + 1
            l.append(nexLeft)
            l.append(nexRight)
            if nexLeft >= low and nexLeft <= high:
                res.append(nexLeft)
            if nexRight >= low and nexRight <= high:
                res.append(nexRight)
            p += 1
    return res
print(progressNumber(10,15))

'''
Output result：
    [10, 12]
'''

复制代码

13.中心对称数

13.center_symmeter_num.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
13、中心对称数定义：一个数字旋转180度之后看起来依旧相同的数字。例如：数字69旋转
180度之后依然为69，则数字69是一个中心对称数。
    现在，输入一个任意的字符串形式的数字，要求通过编程判断它是否是中心对称数。
'''

def func(num):
    #数字0-9建立映射关系
    dic = {"0":"0", "1":"1", "2":"-1", "3":"-1", "4":"-1", "5":"-1", "6":"9", "7":"-1", "8":"8", "9":"6"}
    l = []
    for i in num:
        if dic[i] == "-1":
            return False
        #每次插入到第一个元素位置，自动逆序
        l.insert(0, dic[i])
    return  num == "".join(l)

print(func("96"))

'''
Output result：
    True
'''
复制代码

14.寻找中心对称数

14.search_center_symmeter_Num.py：

#!/usr/bin/python
# Env: python3
# Rewrite by afei_0and1

'''
14、在上一篇中已经知道中心对称数是一个数字旋转180度之后看起来依旧相同的数字。
    现在，要求通过编程找到长度为N的所有中心对称数。例如：N等于2时，所有中心对称数为：
    ”11“、”69“、”88“和”96“。
中心对称数特性：
（1）中心对称数如果是奇数位的，那么最中间的数一定是：0、1、8这三个数字中的一个。因为只有
这三个数字旋转180度后依然与自身相等。并且从中心开始向两边扩展的话，两边的数字一定是成对出现的。
即：00、11、88、69和96这5对数字。
（2）如果是偶数位的，则从左向右与从右向左依次取到的数字一定是成对的。
'''

S = ['0', '1', '8']  #N=1时中心对称数
D = ["00", "11", "88", "69", "96"]  #双位两边扩展
d = ["11", "88", "69", "96"]  #N=2时中心对称数

def func(l, N):
    res = []
    #双位判断
    if N > 1:
        for i in D:
            for item in l:
                tmp = list(item)
                tmp.insert(len(tmp) // 2, i)
                res.append("".join(tmp))
        if res == []:
            res = d
        return func(res, N - 2)
    #奇数位判断
    if N == 1:
        for i in S:
            for item in l:
                tmp = list(item)
                tmp.insert(len(tmp) // 2, i)
                res.append("".join(tmp))
        if res == []:
            res = S
        return func(res, N - 1)
    return  l

print(func([], 3))

'''
Output result：
    ['101', '808', '609', '906', '111', '818', '619', '916', '181', '888', '689', '986']
'''
复制代码

更多Leetcode：blog.csdn.net/qq_41490561…