0248：中心对称数 III（★★）

2015-09-05 约 563 字预计阅读 2 分钟次阅读

力扣第 248 题

题目

给定两个字符串 low 和 high 表示两个整数 low 和 high ，其中 low <= high ，返回范围 [low, high] 内的 「中心对称数」总数。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:

输入: low = "50", high = "100"
输出: 3

示例 2:

输入: low = "0", high = "0"
输出: 1

提示:

1 <= low.length, high.length <= 15
low 和 high 只包含数字
low <= high
low and high 不包含任何前导零，除了零本身。

分析

令 cal(s) 返回 [0,s] 范围的对称数
- s 长度 m，则所有长度<m 的对称数都 <s，令 f[n] 代表长度<=n的对称数个数，可以递推得到
- 再考虑长度 m 的数，考虑 s 的前一半（包括中心）t
- 先考虑第一位就比 t 小的数，后面的数可以任取（只要保证是对称数）
- 然后考虑第一位和 t 相同，第二位比 t 小的数，同理统计
- 依此类推，需要注意两点
  - 假如某位不是对称数字，直接退出
  - 非中心数可以选择 0,1,6,8,9，中心数只能选择 0,1,8
- 最后再判断前一半和 t 完全相同的对称数是否小于 s 即可
结果就是 cal(high)-cal(low)，如果 low 是对称数，再加 1 即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


f,g = [0]*16,[0]*16
g[0] = 1
f[1] = g[1] = 3
for i in range(2,16):
    f[i] = f[i-1]+g[i-2]*4
    g[i] = g[i-2]*5

A = [0,1,6,8,9]
B = [0,1,8]
d = dict(zip('01689','01986'))

def gen(s):
    return ''.join([d.get(c,'*') for c in s][::-1])

def cal(s):
    m = len(s)
    q,r = divmod(m,2)
    res = f[m-1]
    for i in range(q):
        x = int(s[i])
        w = bisect_left(A,x)
        res += (w if i else w-1)*pow(5,q-1-i)*pow(3,r)
        if x not in A:
            return res
    if r:
        x = int(s[q])
        res += bisect_left(B,x)
        res += x in B and s[:q+r]+gen(s[:q])<=s
    else:
        x = int(s[q-1])
        res += s[:q]+gen(s[:q])<=s
    return res

class Solution:
    def strobogrammaticInRange(self, low: str, high: str) -> int:
        return cal(high)-cal(low)+(gen(low)==low)

目录

0248：中心对称数 III（★★）

题目

分析

解答