题目

定义何为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;
    }

总结

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