与回文数相关的解题思路和题目示例。
回文数的重点是把握回文数的根,也就是回文数的左半部分,因为右半部分可以通过左半部分镜像来得到,比如回文数123321的根是123。
注意,以123为根的回文数不止有一个,而是有两个,分别是123321和12321,这也就说明,同一个根在长度为奇数和偶数情况下各自对应一个回文数。
回文数可以通过根来简化构造和判断,通过回文数的根可以解决下面这类的问题:
- 判断N位的回文数一共有几个
- 从小到大构造全部N位的回文数(或者说找出第n个长度为N的回文数)
- 找出全部小于x的回文数
假设回文数的长度为N
,则根的长度为root_len = (N / 2) + (N % 2)
,根的范围是[pow(10, root_len-1), pow(10, root_len))
,参考以下示例:
偶数长度示例:
- 回文数长度为6。
- 根的长度为3,根的范围是[100, 1000)。
- 回文数从小到大的顺序为:100001,101101,102201,103301,... 999999。
奇数长度示例:
- 回文数长度为5。
- 根的长度为3,根的范围是[100, 1000)。
- 回文数从小到大的顺序为:10001,10101,10201,10301,99999。
题目示例:
- 5253. 找到指定长度的回文数 - 力扣(LeetCode)
思路:根据回文数长度可以确定根的长度,从而得到根的范围,对于每个查询,如果超出了根的范围,直接返回-1,如果未超出,则先求出对应的根,再直接构造对应的回文数。