1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int brokenCalc(int startValue, int target) {
        int steps = 0;
        while (target > startValue) {
            if (target % 2 == 1) {
                target += 1;
            } else {
                target /= 2;
            }
            steps += 1;
        }
        return steps + startValue - target;
    }
}

这道题也是想了半天. 从target到startValue好想一些. 如果target是奇数, 那么上一步一定是减去1来到了target, 不可能是乘上2来到了target, 因为任何整数乘2都是偶数. 如果target是偶数, 此时有两种情况, 一种是乘上2来到target, 一种是减去1来到了target, 如果减去1来到了target, 那么这个这个位置就是奇数, 因为奇数减去1才是偶数, 那奇数的话, 这个位置一定是它的上个位置减1来到的. 于是此时我们得到的是来到target分两种, 一种是乘2直接来到, 一种是连续减去两次1来到target. 假设连续减去两次1来的target的这个位置叫做x. 那么就是x - 2 == target. 那如何到达x的呢? 一样的道理, x是偶数, 因此可能是乘2直接来的, 可能是另一个位置y连续减去两次1来到x的. 假设是乘2来到x的, 这个位置我们假定为a, 也就是2a == x. 那为什么不让a先减去1, 再乘2, 也就是2(a - 1). 这样的话只需要两步直接到target, 毕竟x - 2 == 2a - 2 == target; 而不需要三步(a * 2再减去两步)到达target. 假定我们是减去两步来到x, 那么减去前的位置像我们之前说的就是y, 也就是y - 2 == x. 那么到y也是一样的道理, 乘2到或者减去2到y. 如果乘2到达y, 那么一样的道理, 为什么不在之前的位置先减去1再乘2呢? 这样直接到达x了. 如果是减去两步到达y的, 我们继续这样的逻辑推理(另一个z, 满足z - 2 == y. 到z也两种情况…). 但是不可能这个逻辑一直推理不停, 因为在大于target的某个位置, 我们肯定是从target以下的某个位置乘2蹦上来, 否则没办法超过target来往下减. 于是相当于是从某个位置乘2蹦到了target以上某个位置, 然后一路向下. 这样的话, 假设这个蹦之前的位置是d, 蹦后的位置是2d, 我们可以问一个问题就是为什么不让d减去1再乘2来到2d - 2的位置呢? 一样的道理, 为了来到2d - 4的位置, 为什么不先让d减去2再乘2呢? 下面六个格子即2d - 6, 为什么不让d减去3再乘2呢? 因此我们会发现如果是连续减去2来到了target, 那么这个减去2前的位置一定是target以下的某个位置乘2上来的. 否则一定会有更短的路线到达那里, 正如我上面说的. 那么一样的道理, 如果连续减去两格才能到target, 那为什么不在跳之前减去1再乘2, 这样直接到target.

到此我们得出结论, 如果target是偶数, 那么最后一步一定是乘2; 如果target是奇数, 最后一步一定是-1. 这样就可以了.

时间复杂度: O(log(target - startValue))
空间复杂度: O(1)