题解 | #牛群的数量计算#
牛群的数量计算
https://www.nowcoder.com/practice/dfafaa65a55040b3a4b65418db68949d?tpId=354&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D354
一、知识点:
二进制运算
二、文字分析:
代码的时间复杂度为O(log(n)),空间复杂度为O(log(n))。
在这个算法中,我们使用了一个辅助方法addBits(int bit1, int bit2, int carry)来实现两个二进制位的相加操作,而multiply(int n, int a)方法中没有使用加法运算。
三、编程语言:
java
四、正确代码:
public class Solution {
/**
* 计算所有牧场的牛的数量总和
* @param n 牧场的数量
* @param a 每个牧场的牛的数量
* @return 所有牧场的牛的数量总和
*/
public int multiply(int n, int a) {
int sum = 0;
int carry = 0; // 进位
while (n != 0) {
if ((n & 1) == 1) {
sum = addBits(sum, a, carry); // 将 n 和 a 的对应位相加
}
n = n >>> 1; // 向右移位,相当于 n 除以 2
a = a << 1; // 向左移位,相当于 a 乘以 2
}
return sum;
}
// 实现两个二进制位的相加,返回相加结果
private int addBits(int bit1, int bit2, int carry) {
if (bit2 == 0) {
return bit1 ^ carry; // 无进位相加
}
int sum = bit1 ^ bit2 ^ carry; // 无进位相加
int newCarry = (bit1 & bit2) | (bit1 & carry) | (bit2 & carry); // 计算新的进位
return addBits(sum, newCarry << 1, 0); // 递归调用,将新的进位和无进位相加的结果相加
}
}
查看23道真题和解析