大家好,我是开车的阿Q,自动驾驶的时代已经到来,没时间解释了,快和阿Q一起上车。作为自动驾驶系统工程师,必须要有最好的C++基础,让我们来一起刷题吧。
这道题目仍然考察位运算,但与之前的不同之处在于,现在有些牛的标识被错误地标记了三次,而只有一头牛的标识只出现了一次。我们需要找出那个只出现了一次的牛的标识。
思路如下:
我们可以利用位运算的思想来解决这个问题。假设每个标识的二进制表示共有32位(int类型的特点),对于每一位的1的个数,如果出现了3次,那么对3取余后应该为0,而对于只出现一次的牛,剩余的余数就是1。
具体步骤如下:
- 初始化一个长度为32的数组count,用于记录每一位上1的个数。
- 遍历nums数组,对于每个数,将其与1左移后的结果进行与运算,来统计每一位上1的个数,并更新到count数组中。
- 遍历count数组,对每一位上1的个数取余数,得到只出现一次的牛的标识在该位上的值。
- 根据得到的二进制值,计算出只出现一次的牛的标识。
下面是用C++实现的完整代码:
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int singleNumberII(vector<int>& nums) {
int count[32] = {0}; // 用于记录每一位上1的个数
for (int num : nums) {
for (int i = 0; i < 32; i++) {
// 统计当前位上1的个数
count[i] += (num >> i) & 1;
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
// 对每一位上1的个数取余数,得到只出现一次的牛的标识在该位上的值
result |= (count[i] % 3) << i;
}
return result;
}
};

京公网安备 11010502036488号