GoACM之Palindrome

收藏到CSDN网摘


回文数问题,也就是从左或者从右开始写,形式完全一样的数(或者叫对称数),例如909,21321这种.SPOJ的PALIN问题就是求大于给定数字的下一个回文数.

这个问题在处理时,有多种办法.
1. 可以用循环,不断+1,直到字符串表示的从左到右与从右到左完全相同;
2. 分析规律来处理原字符串.主要记录下这种办法.

要最终的结果是回文数,那么分别从头尾开始看,对应的数字两两都是相等的.
先看第一位,如果结尾数字大于第一位,那么最终的回文数,倒数第二位至少要+1,例如809,结果的倒数第二位肯定是比0大的最小整数1.因此解决思路就是:定义一个进位计数,如果前面第i个位置数字小于倒数第i个位置的数字,那么倒数第(i+1)位数字必须加1.值得注意的地方是,数字加1时要考虑9的进位问题,如果每个数字都是9,一直要进到最前面去,这时候由于前面的第1到第i个数字都被进位改变,因此倒数第1到倒数第i个已经匹配好的数字又需要重新匹配.好在python的整数范围非常大,而且字符串与数字的转换非常方便,因此只要截取第1位到倒数第(i-1)位,转为整数后加1即可.

一个要注意的地方是,python的string是immutable类型,虽然可以像list一样切片运算,但是不能inplace修改字符串的内容,也就是下面的操作时无效的:

s = 'abc' ; s[0] = 'c'
>> TypeError: 'str' object does not support item assignment

判断回文数的函数:

#! /usr/bin/env python
# coding=utf-8

def GetNextPalin(s):
    s = str(int(s)+1)
    slen = len(s)
    result = [int(c) for c in s]
    # process last digit
    prev = result[0]<result[-1] and 1 or 0
    # add 1 to the num except last digits
    result[-1] = result[0]
    result = [int(c) for c in str(int(''.join([str(c) for c in result[:-1]]))+prev)]+result[-1:]
    # prevent cases like 899, 49999
    # make sure the last digit is same as the first one
    prev = result[0]<result[-1] and 1 or 0
    result[-1] = result[0]
    # loop the others
    for i in range(1,slen/2):
        result = [int(c) for c in str(int(''.join([str(c) for c in result[:-i]]))+prev)]+result[-i:]
        if result[i]<result[-i-1]:
            result[i] += 1
            prev = 1
        else:
            prev = 0
        result[-i-1] = result[i]
    # odd length, process the center digit
    if slen%2!=0 and result[-1]==result[0]:
        result[slen/2] += prev
        result[slen/2] %= 10 # it may be 9, so only get the last digits
    # return result in string
    return ''.join([str(c) for c in result])

# test cases
print GetNextPalin('808')
print GetNextPalin('898')
print GetNextPalin('2133')
print GetNextPalin('48998')
print GetNextPalin('49888')
print GetNextPalin('79998')

测试结果:

818
909
2222
49094
49894
80008