欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 美食 > 算法训练-位运算

算法训练-位运算

2025/3/16 20:25:09 来源:https://blog.csdn.net/2403_85375987/article/details/144315649  浏览:    关键词:算法训练-位运算

位运算

leetcode191. 位1的个数

法一:巧用n&(n-1)

法二:逐位判断

leetcode231. 2 的幂

法一:二进制的表示

leetcode371. 两整数之和

法一:位运算

leetcode136. 只出现一次的数字

法一:位运算

leetcode137. 只出现一次的数字 II

法一:有限状态自动机

法二:遍历统计


leetcode191. 位1的个数

191. 位1的个数icon-default.png?t=O83Ahttps://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 的幂icon-default.png?t=O83Ahttps://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. 两整数之和icon-default.png?t=O83Ahttps://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. 只出现一次的数字icon-default.png?t=O83Ahttps://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. 只出现一次的数字 IIicon-default.png?t=O83Ahttps://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;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词