---

题目

定义何为step sum？
比如680，680 + 68 + 6 = 754，680的step sum叫754
给定一个正数num，判断它是不是某个数的step sum

解题思路

一个数X它的步骤和叫甲,一个数Y它的步骤和叫乙。
我首先有一个推论,如果Y>X,它的步骤和乙只可能大于甲。

二分
如果中间数的步骤和小于目标,则在1-mid中进行二分
如果中间数的二分和大于目标,则在mid+1-target进行二分
如果你二分都没有了,也没得到7268,说明这个7268不是任何数的步骤和
这个思想传统来自一个名词叫单调性,就往单调性上靠,给你提升了一点点单调性的敏感度

代码

	public static boolean isStepSum(int stepSum) {
		int L = 0;
		int R = stepSum;
		int M = 0;
		int cur = 0;
		while (L <= R) {
			M = L + ((R - L) >> 1);
			cur = stepSum(M);
			if (cur == stepSum) {
				return true;
			} else if (cur < stepSum) {
				L = M + 1;
			} else {
				R = M - 1;
			}
		}
		return false;
	}

	public static int stepSum(int num) {
		int sum = 0;
		while (num != 0) {
			sum += num;
			num /= 10;
		}
		return sum;
	}
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

总结

我们首先使用打表法来找出如果X大于Y,则X的步骤和也大于Y的步骤和这个结论
有了这个结论后,我们发现了其中的单调性,我们就可以使用二分了