题解 | #简单的变换#

一.题目描述 NC638简单的变换

给一个正整数n，如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。如果可以进行若干次操作后使得n等于0，返回需要操作的次数，如果无法将n变为变为0，返回-1。

二.算法一(数学)

我们可以从0开始反过来推导，首先要使n的最后值是0那么必然是$n-3=0n-3=0$n−3=0，不可能是由$n/3n/3$n/3得到的。那么$n-3=0n-3=0$n−3=0的上一步n必然是3的倍数，所以我们可以发现，如果给出的n不是3的倍数，那么必然不能通过操作将n变为0，所以直接返回-1。如果给出的数是3的倍数，那么我们就要根据奇偶来分情况讨论了，要是奇数就直接减去3，要是偶数就直接除以2，记录操作次数，返回最后的操作次数。 下面是完整代码：

class Solution {
public:
    int Numberofoperations(long long n) {
        int cn=0;//记录操作次数
        //不是3的倍数直接返回-1
        while(n%3!=0) return -1;
        while(n!=0){
            //分奇偶讨论
            if(n%2){
                n-=3;
            } else {
                n/=2;
            }
            cn++;
        }
        //返回操作次数
        return cn;
    }
};

时间复杂度：$O\left(logn\right)O(logn)$O(logn)因为交替对n除以2，所以时间复杂度可以实现$O\left(logn\right)O(logn)$O(logn)

空间复杂度：不需要额外空间，空间复杂度为$o\left(1\right)o(1)$o(1)。

三.算法二(暴力)

对于前面的数学方法我们可能第一想法不容易想出来，所以我们可以尝试去暴力实现，我们要知道，无论输入的n是多少对其的操作操作是确定的，因为其奇偶性是确定的，所以我们可以利用死循环去判断，看看是否在若干次操作后n的值是0，倘若在操作过程中存在n<0的情况发生，那么必然是不行了，直接返回-1了，下面是完整代码：

class Solution {
public:
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    int Numberofoperations(long long n) {
        int cn=0;//记录操作的次数
        while(1){//死循环
            //分奇偶来判断对数的操作
            if(n%2==1){
                n-=3;
            } else {
                n/=2;
            }
            cn++;
            if(n==0){
                return cn;
            } else if(n<0){//很显然不能将n变为0
               return -1;
            }
        }
    }
};

时间复杂度：$O\left(logn\right)O(logn)$O(logn)因为交替对n除以2，所以时间复杂度可以实现$O\left(logn\right)O(logn)$O(logn)

空间复杂度：不需要额外空间，空间复杂度为$o\left(1\right)o(1)$o(1)。