题目
这天小明正在学数数。他突然发现有些正整数的形状像一座“山”,比如 123565321 、 145541 ,它们左右对称(回文)且数位上的数字先单调不减,后单调不增。小明数了很久也没有数完,他想让你告诉他在区间[2022,2022222022]中有多少个数的形状像一座“山”。
可以分为两步去进行判断,写一个判断回文的方法,写一个判断是否递增的方法。
判断回文
判断回文其实在StringBuilder就有现成的方法可以使用一下,
StringBuilder内有一个reverse()的方法可以将stringBuilder进行一个反转,
只需要将数字int变为一个String和一个StringBuilder,将StringBuilder进行反转之后与String进行一下比较
这里可以直接使用链式编程,反转之后需要进行toString不然不能正常调用equals方法去比较
public static boolean isPalindrome(int num) { String snumString = "" + num; StringBuilder stringBuilder = new StringBuilder(snumString); return stringBuilder.reverse().toString().equals(snumString); }
判断递增
为了减少运算的时间,我们可以将判断递增再递减,改为判断为 是回文再判断前面递增即可。
判断递增最快就是数组,我们可以将这个数字的每一位拆为数组的每一个元素
这里可以用很快速的一个办法,先将int变为String再变为字符数组
char[] chs = ("" + num).toCharArray();
因为要确认一个中间值,去对半判断,要知道前一半有多少,需要先判断是奇数还是偶数,如果是奇数个的话,最后要判断的个数为len/2+1,偶数的话就是len/2
int mid; if (len%2 == 0) { mid = len / 2; }else { mid = len / 2 + 1; }
如果简单一点点
int mid = (len & 1) == 0 ? len >> 1 : (len >> 1) + 1
len & 1 之后,除了最后一位,前面全是0.最后一位如果本来就是1,那么这个数一定为奇数,因为只有最后一位会影响奇偶性,前面都是2的某次方,一定为偶数。
len >> 1 就相当于除以2
之后就是遍历去判断是否递增。
那么全部代码就是
public static void main(String[] args) { int cnt = 0; for (int i = 2022; i <=2022222022 ; i++) { if (isPalindrome(i) && isMonotonous(i)) { cnt++; System.out.println(cnt);//看到进度 } } System.out.println(cnt); } // 判断回文 public static boolean isPalindrome(int num) { String snumString = "" + num; StringBuilder stringBuilder = new StringBuilder(snumString); return stringBuilder.reverse().toString().equals(snumString); } // 判断递增不减 public static boolean isMonotonous(int num) { char[] chs = ("" + num).toCharArray(); int len = chs.length; //int mid = (len & 1) == 0 ? len >> 1 : (len >> 1) + 1;//判断是奇数还是偶数 int mid; if (len%2 == 0) { mid = len / 2; }else { mid = len / 2 + 1; } for (int i = 0; i < mid - 1; i++) { if (chs[i] > chs[i + 1]) { return false; } } return true; }
那么大概不到一分钟就可以跑完所有的