“将数字转换为1的最小操作次数”

huangapple go评论44阅读模式
英文:

Minimum operations to convert number to 1

问题

给定一个数字 N 和一个数字 K,找到将 N 转换为 1 的最小操作次数。
允许的操作有:

  • 减去 1
  • 除以 2(最多 K 次)

这是我的代码,但它不能正确运行。

private int getMinRounds(int N, int K, int memo[]) 
{ 
    if(N <= 1) return 0;
    if (memo[N] != -1) return memo[N];
    
    int rounds;
    if ((N%2) == 0 && K > 0) {
        rounds = 1 + Math.min(getMinRounds(N-1, K, memo), getMinRounds(N/2, K-1, memo));
    }else {
        rounds = 1 + getMinRounds(N-1, K, memo);
    }
    memo[N] = rounds; 
    return rounds; 
}

private int solution(int N, int K) 
{ 
    int memo[] = new int[N + 1];
    Arrays.fill(memo, -1);
    return getMinRounds(N, K, memo); 
}
英文:

Given a number N and number K, find minimum number of operations to convert N to 1.
allowed operations:

  • subtract 1
  • divide by 2 (at most K times)

here is my code but it is not working correctly.

  private int getMinRounds(int N, int K, int memo[]) 
  { 
  	if(N &lt;= 1) return 0;
  	if (memo[N] != -1) return memo[N];
      
      int rounds;
      if ((N%2) == 0 &amp;&amp; K &gt; 0) {
          rounds = 1 + Math.min(getMinRounds(N-1, K, memo), getMinRounds(N/2, K-1, memo));
      }else {
      	rounds = 1 + getMinRounds(N-1, K, memo);
      }
      memo[N] = rounds; 
      return rounds; 
  }

  private int solution(int N, int K) 
  { 
      int memo[] = new int[N + 1];
      Arrays.fill(memo, -1);
      return getMinRounds(N, K, memo); 
  } 

答案1

得分: 0

贪婪法应该足以解决这个问题。数字越大,最好的方法是已经将其除以2,因此你不需要思考“现在除以2还是将除法保留以备将来使用?”。你能够分割的数字越大,对你来说就越好,因为你越应该将其分割。

int solve(int n, int k) {
    if (n == 1) return 0;
    if (k == 0) return n - 1;
    if (n % 2 == 0) return 1 + solve(n / 2, k - 1);
    return 1 + solve(n - 1, k);
}

复杂度:O(log(n))


输出 solve(n, k)

solve(1, 1) = 0
solve(2, 2) = 1
solve(3, 3) = 2
solve(4, 0) = 3
solve(5, 1) = 3
solve(6, 2) = 3
solve(7, 3) = 4
solve(8, 0) = 7
solve(9, 1) = 5
solve(10, 2) = 4
英文:

A greedy aproach should be enough to solve this problem. The bigger the number is, the best it is to divide it by 2 already, so you don't need to think "is it better to divide now or store the division for later?". The bigger the number you can divide is, the best for you it will be to divide it.

int solve (int n, int k){
    if(n == 1) return 0;
    if(k == 0) return n - 1;
    if(n % 2 == 0) return 1 + solve(n / 2, k - 1);
    return 1 + solve(n - 1, k);
}

Complexity: O(log(n))


OUTPUTS solve(n, k)

solve(1, 1) = 0
solve(2, 2) = 1
solve(3, 3) = 2
solve(4, 0) = 3
solve(5, 1) = 3
solve(6, 2) = 3
solve(7, 3) = 4
solve(8, 0) = 7
solve(9, 1) = 5
solve(10, 2) = 4

huangapple
  • 本文由 发表于 2020年7月30日 07:35:02
  • 转载请务必保留本文链接:https://go.coder-hub.com/63164012.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定