如果一个正整数的十进制表示(没有前导零)是一个回文字符串(一个前后读取相同的字符串)，那么它就是回文。例如，数字5, 77, 363, 4884, 11111, 12121和349943都是回文。
如果一个整数范围包含偶数个回文，那么它就是一个有趣的范围。范围 [L, R]且L <= R的定义为从L到R(包括):(L, L+1, L+2，……，R-1, R)的整数序列。L和R是这个范围的第一个和最后一个数字。
如果L <=L1 <= R1 <=R1 > =R，那么范围[L1, R1]就是[L, R]的子集合。你的工作是确定有多少有趣的[L, R]子集。
- 数据保证结果在int范围，不会溢出
您在真实的面试中是否遇到过这个题？
样例
样例 1:
输入 : L = 1, R = 2
输出 : 1
样例 2:
输入 : L = 1, R = 7
输出 : 12
样例 3:
输入 : L = 87, R = 88 输出 : 1
我的解法：
class Solution:
"""
@param L: A positive integer
@param R: A positive integer
@return: the number of interesting subranges of [L,R]
"""
def PalindromicRanges(self, L, R):
# test
ans = 0
dp = [0]*(R-L+2)
for i in range(L, R+1):
if self.is_palindrom(str(i)):
dp[i-L+1] = dp[i-L]+1
else:
dp[i-L+1] = dp[i-L]
for i in range(L, R+1):
for j in range(i, R+1):
if (dp[j-L+1]-dp[i-L]) % 2 == 0:
ans += 1
return ans
def is_palindrom(self, s):
i, j = 0, len(s)-1
while i < j:
if s[i] != s[j]: return False
i += 1
j -= 1
return True
参考代码：
class Solution:
"""
@param L: A positive integer
@param R: A positive integer
@return: the number of interesting subranges of [L,R]
"""
def PalindromicRanges(self, L, R):
# test
count = 0
len = R - L + 2
record = [0] * len
for offset in range(len-1):
record[offset+1] = record[offset]
if self.IsPalindromic(L + offset):
record[offset+1] += 1
for left in range(0, len-1):
for right in range(left+1, len):
temp = record[right] - record[left]
if temp % 2 == 0:
count += 1
return count
def IsPalindromic(self, number):
str_ = str(number)
start, end = 0, len(str_) - 1
while start < end:
if str_[start] == str_[end]:
start += 1
end -= 1
else:
return False
return True
值得学习的地方：L + offset的处理，比我写得优雅。