找出最接近的对称数字

[编程题]找出最接近的对称数字

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

输入一个正整数的字符串，输出与它最接近的对称数字(不包括它自己)的字符串

注1: 输入字符串的长度最多不会超过18

注2: 当大于输入数字和小于输入数字的对称数字与输入数字距离相同时，取小的数字作为答案

输入描述:

输入为一个正整数的字符串

输出描述:

输出为与输入数字最接近的对称数字(不包括输入本身)的字符串

示例1

输入

输出

算法知识视频讲解

Python

TimeMac

找出几个候选答案然后比较差值（最多为4个）

长度为1，#长度为1，直接减一返回
开头为1，9~~9为一个候选答案例：100001，答案为99999
开头为9，10~~01为一个候选答案例：99999，答案为100001
如果本身对称，则把最中间的一个（或两个）位数减（如果0则加）一
例：123321，答案为122221
例：120021，答案为121121
如果不对称：
-把前半部分逆序替换掉后半部分例：1223，答案为1221

-把最中间的一个（或两个）位数加一例：1291，答案为1331，而非1221

-把最中间的一个（或两个）位数减一例：1800，答案为1771，而非1881

额外的，在这里测试用例比较少，有些情况并未测试出来。如果本身不对称直接把前半部分逆序替换掉后半部分也是能通过的。但不严谨。希望添加测试用例。

例：9，答案为8（没有单个数的测试用例）

例：1291，答案为1331，而非1221

例：1800，答案为1771，而非1881

while True:
    try:
        string = input()
        length = len(string)

        if length == 1:                         # 长度为1，直接减一
            print(str(int(string) - 1))
        else:
            candidate = []                      # 候选字答案
            if string[0] == '1':                # 开头为1，9**9可能为候选字
                candidate.append('9' * (length - 1))
            elif string[0] == '9':              # 开头为9，10**01可能为候选字
                candidate.append('1' + '0' * (length - 1) + '1')
            if string == string[::-1]:          # 如果本身对称，则把最中间的一个（或两个）位数减（如果0则加）一
                temp = list(string)
                if temp[length // 2] == '0':
                    temp[length // 2] = temp[(length - 1) // 2] = '1'
                else:
                    char = str(int(temp[length // 2]) - 1)
                    temp[length // 2] = temp[(length - 1) // 2] = char
                candidate.append(''.join(temp))
            else:                               # 不对称，把前半部分逆序替换掉后半部分
                temp = list(string[:(length // 2)] + string[:((length + 1) // 2)][::-1])
                candidate.append(''.join(temp))
                if temp[length // 2] == '0':    # 最中间为0，只能加一
                    temp[length // 2] = temp[(length - 1) // 2] = '1'
                    candidate.append(''.join(temp))
                elif temp[length // 2] == '9':  # 最中间为9，只能减一
                    temp[length // 2] = temp[(length - 1) // 2] = '8'
                    candidate.append(''.join(temp))
                else:                           # 加一和减一都加入候选答案
                    char = int(temp[length // 2])
                    temp[length // 2] = temp[(length - 1) // 2] = str(char + 1)
                    candidate.append(''.join(temp))
                    temp[length // 2] = temp[(length - 1) // 2] = str(char - 1)
                    candidate.append(''.join(temp))
            candidate = sorted(list(map(int, candidate)))
            string = int(string)
            diff = string                       # 保存差值
            for num in candidate:               # 在候选答案里选择差值最小的最小数（前面已排序）
                if abs(string - num) < diff:
                    result = num
                    diff = abs(string - num)
            print(result)


    except Exception:
        break

编辑于 2019-03-29 10:38:21 回复(0)