位运算
leetcode191. 位1的个数
法一:巧用n&(n-1)
法二:逐位判断
leetcode231. 2 的幂
法一:二进制的表示
leetcode371. 两整数之和
法一:位运算
leetcode136. 只出现一次的数字
法一:位运算
leetcode137. 只出现一次的数字 II
法一:有限状态自动机
法二:遍历统计
leetcode191. 位1的个数
191. 位1的个数https://leetcode.cn/problems/number-of-1-bits/
法一:巧用n&(n-1)
public class Method01 {public int hammingWeight(int n) {int count = 0; // 初始化计数器,用于记录'1'的数量// 当 n 不为 0 时继续循环while (n != 0) {n &= (n - 1); // 将 n 最右边的 '1' 置为 '0'count++; // 计数器加一}return count; // 返回汉明重量}
}
法二:逐位判断
public class Method02 {public int hammingWeight(int n) {int count = 0; // 初始化计数器,用于记录'1'的数量// 当 n 不为 0 时继续循环while (n != 0) {count += n & 1; // 通过与运算获取 n 最右边的位,如果为 1 则 count 加 1n >>= 1; // 右移 n,准备检查下一个位}return count; // 返回汉明重量}
}
leetcode231. 2 的幂
231. 2 的幂https://leetcode.cn/problems/power-of-two/
法一:二进制的表示
public class Method01 {public boolean isPowerOfTwo(int n) {// 检查 n 是否小于或等于 0, 如果是则不是 2 的幂if (n <= 0) {return false;}// 检查 n 是否为 2 的幂,使用位与运算:2 的幂具有唯一一个 '1' 位return (n & (n - 1)) == 0;}
}
leetcode371. 两整数之和
371. 两整数之和https://leetcode.cn/problems/sum-of-two-integers/
法一:位运算
public class Method01 {public int getSum(int a, int b) {int c = 0; // 初始化 c,用于存储进位// 当 b 不为 0 时,继续进行加法运算while (b != 0) {c = a & b; // 计算进位部分,使用位与运算a = a ^ b; // 计算和部分,不考虑进位,使用位异或运算b = c << 1; // 将进位左移一位,以便加到下一高位}return a; // 返回最终的和}
}
leetcode136. 只出现一次的数字
136. 只出现一次的数字https://leetcode.cn/problems/single-number/
法一:位运算
public class Method01 {public int singleNumber(int[] nums) {int a = 0; // 初始化变量a为0,用于存储结果// 遍历数组中的每一个数字for (int i = 0; i < nums.length; i++) {a = a ^ nums[i]; // 使用异或运算更新a}// 返回只出现一次的数字return a;}
}
leetcode137. 只出现一次的数字 II
137. 只出现一次的数字 IIhttps://leetcode.cn/problems/single-number-ii/
法一:有限状态自动机
public class Method01 {// 方法:找到只出现一次的数字,其他数字均出现三次public int singleNumber(int[] nums) {// 初始化:ones 表示当前只出现一次的数字的位状态int ones = 0;// 初始化:twos 表示当前出现两次的数字的位状态int twos = 0;// 遍历输入数组中的每个数字for (int num : nums) {// 更新 ones:在 num 还未在 twos 中的情况下更新// 具体逻辑为:ones = (ones ^ num) 仅在 num 不在 twosones = ones ^ num & ~twos;// 更新 twos:在 num 还未在 ones 中的情况下更新// 具体逻辑为:twos = (twos ^ num) 仅在 num 不在 onestwos = twos ^ num & ~ones;}// 返回结果:ones 中存储的就是只出现一次的数字return ones;}
}
法二:遍历统计
public class Method02 {// 方法:找到只出现一次的数字,其他数字均出现三次public int singleNumber(int[] nums) {// 创建一个数组 counts,用于统计每个位上 1 的出现次数int[] counts = new int[32];// 遍历输入数组中的每个数字for (int num : nums) {// 对 32 位整数的每一位进行统计for (int j = 0; j < 32; j++) {// 将当前位 (num & 1) 加入 counts 中对应的计数counts[j] += num & 1;// 右移 num,继续处理下一位num >>= 1;}}// 初始化结果 resint res = 0;// 定义 m 为 3,表示我们将考虑出现次数对 3 取模int m = 3;// 处理 counts 数组,将结果构造到 res 中for (int i = 0; i < 32; i++) {// 左移 res,为下一位腾出空间res <<= 1;// 将 counts 中对应位的出现次数对 3 取模,添加到 resres |= counts[31 - i] % m;}// 返回结果,res 中现在存储的是只出现一次的数字return res;}
}