英文:
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 <= 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);
}
答案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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论