题解 | #简单的变换#

题意整理

给定正整数n，如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。
如果n等于0，返回之前变换次数，如果无法变为0，返回-1。

方法一（模拟）

1.解题思路

用一个死循环，模拟n的值变换的过程。
如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。
如果n小于0，说明不可能再变为0，因为无论是减去3，还是变为n/2，都无法将一个负数变为0或正数。所以直接返回-1。如果n等于0，记录最终变为0时总共执行的变换次数，并返回。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    public int Numberofoperations (long n) {
        int cnt=0;
        //无限循环
        for(;;){
            //如果是奇数，减去3
            if(n%2==1){
                n=n-3;
            }
            //如果是偶数，变为原来一半
            else{
                n=n/2;
            }
            //计数加1
            cnt++;
            //如果为0，直接返回计数
            if(n==0){
                return cnt;
            }
            //如果小于0，说明无法变为0了，直接返回-1
            if(n<0){
                return -1;
            }

        }
    }
}

3.复杂度分析

时间复杂度：只有当n是3的倍数时，n经过一定变换，才能变为0，在变换的过程中，一种情况是奇偶交替变换，也就是要么执行减3操作，要么变为原来一半。另一种情况是一直为偶数，执行减半操作，最后变为3时，执行减3操作变为0。所以整体的时间复杂度为 $O(log_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。

方法二（数学）

1.解题思路

简单分析：

由于n只有两种变换方式，减去3或者变为原来一半，要想变为0，最后一步要从从3变为0，要么从0变为0，显然不能从0变为0，所以如果能变为0，最后一定是从3变换而来，而3一定是从3的倍数变换而来。为什么呢？通过执行变换的逆操作，加3或者乘以2，无论选则哪一种方式，最后的结果仍然是3的倍数，所以3一定是从3的倍数变换而来。

基本步骤：

如果不是3的倍数，直接返回-1。
如果n是奇数，将其减去3；如果n是偶数，将其变为n/2。并记录变换次数。
返回变换次数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n long长整型 
     * @return int整型
     */
    public int Numberofoperations (long n) {
        int cnt=0;
        //如果不是3的倍数，直接返回-1
        if(n%3!=0) return -1;
        while(n!=0){
            //如果n是奇数，减去3
            if(n%2==1){
                n=n-3;
            }
            //如果n是偶数，变为原来一半
            else{
                n=n/2;
            }
            //计数加1
            cnt++;
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：分析与方法一相同，时间复杂度为 $O(log_2n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。