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