请教一道算法题（答题加米）

联氢人 发表于 2019-9-27 06:51
感觉是greedy吧
倒推，当N%4!=0的时候必然是-1，当N%4==0的时候如果乘法次数还没到上线，反证法可得此处/4 ...

可以展开说一下，为什么贪心法的时间复杂度是log（n）吗？

这是我的code，欢迎大家批评指正 :)
class Solution {
    public int solution(int N, int x) {
     int ans = 0;
         while(N != 1){
                 if(N%4 == 0 && x >0 ){
                        N = N/4;
                        x--;
                        ans++;          
                 }
                 if(N%4 != 0 || x == 0){
                         N --;
                         ans++;
                 }
                 
         }

      return ans;
    }
  }

小水 发表于 2019-10-3 02:17
可以展开说一下，为什么贪心法的时间复杂度是log（n）吗？

准确来说是O(min(log(N), X))
因为如果X范围比较松的话，greedy倒推的下降速度是至多每四次操作N->N/4，算下来就是上限是O(4log_4(N))也就是O(logN); 如果X范围比较紧的话操作次数会限制为4X

联氢人 发表于 2019-10-3 05:22
准确来说是O(min(log(N), X))
因为如果X范围比较松的话，greedy倒推的下降速度是至多每四次操作N->N/4， ...

谢谢大神解答！方便帮我看一眼code写的对不对或者需要怎样优化吗？
class Solution {
    public int solution(int N, int x) {
     int ans = 0;
         while(N != 1){
                 if(N%4 == 0 && x >0 ){
                        N = N/4;
                        x--;
                        ans++;         
                 }
                 if(N%4 != 0 || x == 0){
                         N --;
                         ans++;
                 }           
         }
      return ans;
    }
  }

小水 发表于 2019-10-3 07:33
谢谢大神解答！方便帮我看一眼code写的对不对或者需要怎样优化吗？
class Solution {
    public int s ...

思路基本是对的呀，优化的话可以把while里面改成N!=1 && x>0 （if条件相应改掉），返回ans + N - 1，这样可以减少一些不必要的循环次数（意思就是X=0的时候反正剩下的都要用加来做，那就没必要再一步一步加了直接把剩余的所有次数都加起来就好了）

当然更fancy的写法很可能也有，不过我个人喜欢写比较基础的写法（这样被面试的时候讲起来好讲也相对容易debug）

另外大神实在不敢当，我自己也是个刷题找工作的刚毕业的学生hhhh，一起努力~

我的java code
  *4 越靠后用越好，所以先判断能不能/4.
public class test {    public static void main(String[] args) {
        int N = 128;
        int count = 0;
        int x = 2;
        while(N > 1){
            if(x == 0){
                count +=  N - 1;
                break;
            }
            while(N > 1 && N % 4 != 0 ){
                N--;
                count++;
            }
            while(N > 1 && N % 4 == 0 && x > 0){
                N = N / 4;
                x--;
                count++;
            }
        }
        System.out.println(count);
    }
}