大家好,我是开车的阿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; } };