网站策划书内容,柳州网站建设psn118,河北网站seo优化,广东微信网站建设哪家专业问题描述 这天小明正在学数数。 他突然发现有些整数的形状像一座“山”#xff0c;比123565321、145541#xff0c;它们左右对称#xff08;回文#xff09;且数位上的数字先单调不减#xff0c;后单调不增。 小朋数了很久也没有数完#xff0c;他想让你告诉他在区间[202…问题描述 这天小明正在学数数。 他突然发现有些整数的形状像一座“山”比123565321、145541它们左右对称回文且数位上的数字先单调不减后单调不增。 小朋数了很久也没有数完他想让你告诉他在区间[2022,2022222022]中有多少个数的形状像一座“山”。 思路解答
首先暴力求解会超时至少10分钟参考他人运行时间
所以必须找捷径
山形数字条件有两个一个是回文一个是单调性
对于回文因为是对称的类似照镜子所以我们只需要对一半数字考虑单调性
对于区间[2022,2022222022]中的数我们只需要考虑到区间[2222,199999991],所以对半区间是[22,19999]
代码如下
#左闭右开区间
for s in range(22, 20000): s str(s)flag True#判断单调性for i in range(len(s)-1):if s[i] s[i1]:flag Falsebreakif flag:count 1
注意
这段代码只考虑了山形数的位数是偶数的情况例如233256788765而没有12321这种
所以对于山形数位数为奇数时我们需要再分析
例如12221取前两位12奇数位的数有12221、12321、12421、12521、12621、12721、12821、12921【2~9即9-21个加1是因为2本身也是可以满足条件的】即有10-2(奇数位上的数字)个
对于区间奇数位是从5位11111开始到9位999999999结束所以遍历的区间为[11,9999]
代码如下
#左闭右开区间
for s in range(11, 10000): s str(s)flag True#判断单调性for i in range(len(s)-1):if s[i] s[i1]:flag Falsebreakif flag:count 10 - int(s[i1])
完整代码
import os
import syscount 0
for s in range(22, 20000): # 位数为偶数s str(s)flag Truefor i in range(len(s)-1):if s[i] s[i1]:flag Falsebreakif flag:count 1
for s in range(11, 10000): # 位数为奇数s str(s)flag Truefor i in range(len(s)-1):if s[i] s[i1]:flag Falsebreakif flag:count 10 - int(s[i1])
print(count)
最后结果3138
