Leetcode挑战题——2 Keys Keyboard

电玩女神 2022-06-10 03:46 168阅读 0赞

2 Keys Keyboard

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1.  `Copy All`: You can copy all the characters present on the notepad (partial copy is not allowed).
2.  `Paste`: You can paste the characters which are copied last time.

Given a number `n`. You have to get exactly `n` 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get `n` 'A'.

Example 1:

Input: 3
    Output: 3
    Explanation:
    Intitally, we have one character 'A'.
    In step 1, we use Copy All operation.
    In step 2, we use Paste operation to get 'AA'.
    In step 3, we use Paste operation to get 'AAA'.

Note:

1.  The `n` will be in the range \[1, 1000\].

本题目大概意思是说：

2键键盘（我的理解就是复制和黏贴，哈哈……）

最初在记事本上只有一个字符“A”存在。每个步骤都可以在这个记事本上执行两个操作：

1.复制所有：你可以复制记事本上的所有字符（不允许部分拷贝）。

2.粘贴：你可以粘贴上次复制的字符。

给定一个数字N，你必须在记事本上执行n个A的最小步骤。输出得到n个A的最小步骤数。

例子:

> 输入：3
> 
> 输出：3
> 
> 分析：

> > 起初，我们有一个字符“A”。
> 
> > 在步骤1中，我们使用复制操作。
> 
> > 在步骤2中，我们使用粘贴操作获得“AA”。
> 
> > 在步骤3中，我们使用粘贴操作获得AAA。

注：

n在区间\[ 1, 1000 \]里。

我们现在来分析下题目，这个题目要我们求最小的步骤数，说明要得N个A可能有多种步骤数，比如6个A，可以5步或6步就可以得到了，但是

我们是要求最小的，所以得到的是5。

对于这类的算法题目，其实他们是有规律的，难点就是要找出他们的规律在是什么，找出他们的通项公式。

对于1个A，因为记事本本有就有一个A，所以最小步骤数为0，这是个特例；

对于除1以外的奇数，那就没有什么捷径更快地得出A，只能一次复制，N-1次黏贴了了，所以步骤数就是N了，这里需要的特别注意的是，这一类

可以开方的奇数，如9、25、625等等……，我们就需要先对他们分解因式，求出所有的质因数，如9=3\*3；625=5\*5\*5\*5,可以看出他们的质因数都

是一样的，所以他们的最小步骤数等于质因数\*质因数个数。即625的最小步骤数为5\*4=20,9的最小步骤数等于3\*2=6；

接下来，说下偶数。

其中，对于2的N次幂的数，如1是2的0次幂、2是2的一次幂、4是2的2次幂、8是2的3次幂……他们的通项公式为2^m,所以当我们求N个A

时（也就是N等于0、1、2、4、8……），他们的最小步骤数为2\*m。

剩余的偶数，也是该题最麻烦的地方，我们就要先列举一些这样的偶数，找规律，如下所示：

把他们都转换成2的m次幂（注意是2的最大次幂）乘以k的形式。

6=2^1\*3 => 最小步骤数等于2\*1+3=5（刚好等于我们刚出推论出来的5）

10=2^1\*5 => 最小步骤数等于2\*1+5=7（其实就等于5的步骤数再多两步，一步是在5的基础是进行复制，另外一步就是黏贴，现在就有10个A了）

12=2^2\*3 => 最小步骤数等于2\*2+3=7（原理同上）

14=2^1\*7 => 最小步骤数等于2\*1+7=9（原理同上）

18=2^1\*9 => 最小步骤数等于2\*1+9=11（原理同上）

等等……

通过上面的列举我们已经可以看出规律了，发现了他们的通项公式N=2^m+k,其中k为N的除1外的最小奇数因子，所以我们先求N的最小的奇数因子，

再对差取2的对数求出m，最后我们就可以求出最小步骤数了。

到现在为止，该题的题目已经被我们剖析得差不多了，拨开迷雾后，是不是觉得顿时豁然开朗，林暗花明又一村的感觉啊，哈哈……

好，直接上代码：

//运用函数嵌套，求出除了1外的最小奇数因子，先声明getMinOddFromAllFactorsNotOne，后声明getFactors，所以在getMinOddFromAllFactorsNotOne里面调用getFactors时，应写在getFactors声明的后面否则会报错，因为函数内部执行顺序是从上到下依次执行的,且此时的函数getFactors的作用域是局部的了。这里跟我们常规的写法不一样，平时顺序怎么写都可以,因为php是解释型语言，运行时，变量和函数都是先加载到内存。且函数的作用域是全局的，只要定义了，那么就可以在任意位置去调用它。
        
        //求一个正整数的质因数
        function getPrimeFactors($n) {
            if($n < 0 || gettype($n) != 'integer') return 'Parameter Error!';
            $result = array();
            for ($i = 2; $i <= $n; $i++) {//从最小的质数2开始循环
                while ($n <> $i) {
                    if ($n % $i == 0) {//如果$n<>$i，但n能被i整除，则把i放入数组
                        $result[] = $i;
                        $n /= $i;//用$n除以$i的商,作为新的正整数$n，重复执行
                    } else {//$n不能被$i整除，直接跳过，则用$i+1作为$i的值,
                        break;
                    }
                }
            }
            $result[] = $n;//如果这个质数恰等于$n，则说明分解质因数的过程已经结束，记得把最后一次的$n收集到数组里
            return $result;
        }
    
    
        // 除了能取以2为底的对数外的其他偶数情况，获得最小步骤数  
        function getMinNumberOfStepsForPartialEven($num){  
            //运用递归，利用引用做参数，求出因子；将array的引用传入函数，会将每一次递归产生的a添加到结果数组array里。  
            function getFactors($num,&$array = array()){  
                if($num % 2 == 0){  
                    $quotient = $num/2;  
                    $array[] = $quotient;  
                    getFactors($quotient,$array);  
                }  
                return $array;          
            }  
            $return_array = getFactors($num);//获得因子  
            $getMinOddFromAllFactorsNotOne = array_pop($return_array);//获得数组的最后一个元素，得到最小的非1奇数因子，即所求的最小因子  
            $value = $num/$getMinOddFromAllFactorsNotOne;//把传进来的数除以求出的因子  
            $exponent = log($value,2);//求以2为底$value的对数  
            return $exponent*2 + $getMinOddFromAllFactorsNotOne;  
        }  
      
        // 封装各种情况，获得每种情况的最小步骤数  
        function getMinNumberOfSteps($number){  
            $range = range(1,1000);  
            if(!in_array($number, $range,true)) return 'Parameter error!';// 只允许[1,1000]之间的整数  
            $log = log($number,2);  
            if($number % 2 != 0 && $number != 1){//除了1外的奇数  
                if(count(array_unique(getPrimeFactors($number)) == 1)){//表示该奇数可以求开方根,以为可以求开方根的数的质因数是一样的，对结果去重下，就只剩下一个数了
                    return array_sum(getPrimeFactors($number));
                }else{
                    return $number; 
                }
            }elseif(intval($log) == $log){// 可以取以2为底的对数时，注意：1也是满足这种情况的。  
                return $log*2;  
            }else{// 其他的偶数情况  
                return getMinNumberOfStepsForPartialEven($number);  
            }  
        }  
        echo getMinNumberOfSteps(18);

结果:

![Center][]

经过多次测试，均符合题意，得出正确的答案。如有不正确之处，希望各位批评指正，谢谢！

[Center]: /images/20220610/61be05e3052b4c25a8fc5b1c6f5041f2.png