Leetcode 144 位1的个数 | 只出现一次的数字

1 题目191. 位1的个数给定一个正整数n编写一个函数获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数也被称为汉明重量。示例 1输入n 11输出3解释输入的二进制串1011中共有 3 个设置位。示例 2输入n 128输出1解释输入的二进制串10000000中共有 1 个设置位。示例 3输入n 2147483645输出30解释输入的二进制串1111111111111111111111111111101中共有 30 个设置位。提示1 n 231 - 12 代码实现cclass Solution { public: int hammingWeight(int n) { int ret 0 ; for (int i 0 ; i 32 ; i){ if (n (1 i )){ ret ; } } return ret ; } };js/** * param {number} n * return {number} */ var hammingWeight function(n) { let ret 0 ; for (let i 0 ; i 32 ; i){ if (n (1 i )){ ret ; } } return ret ; };思考我主要靠这题熟悉一下位运算的语法。题解第一步理解题目和整体框架这个函数的核心功能是统计一个 32 位无符号整数的二进制表示中数字 1 出现的次数汉明重量。我们先搭建最基础的类和函数框架// 定义一个解决方案类LeetCode 标准写法 class Solution { public: // 定义函数返回值是int类型参数n是要统计的32位整数 int hammingWeight(int n) { // 核心逻辑会写在这里 } };class SolutionLeetCode 固定的类名所有解题代码都放在这个类里。public函数的访问权限确保外部可以调用这个函数。int hammingWeight(int n)函数声明hammingWeight是函数名参数n是输入的整数返回值是 1 的个数整数。第二步初始化计数器接下来在函数内部定义一个变量用来记录 1 的个数class Solution { public: int hammingWeight(int n) { // 初始化计数器ret为0ret是result的缩写专门用来存1的个数 int ret 0 ; } };int ret 0;ret是计数器初始值必须为 0因为一开始还没统计到任何 1。第三步循环遍历 32 位二进制位因为题目明确是 32 位整数所以我们需要检查每一位从第 0 位到第 31 位class Solution { public: int hammingWeight(int n) { int ret 0 ; // 循环32次i从0到31对应二进制的第0位最低位到第31位最高位 for (int i 0 ; i 32 ; i){ // 每一位的检查逻辑写在这里 } } };for (int i 0 ; i 32 ; i)i 0从二进制最低位最右边开始检查。i 32因为是 32 位整数必须检查完所有位0~31 共 32 位。i每次检查下一位。第四步检查当前位是否为 1这是核心逻辑用位运算判断第i位是否为 1class Solution { public: int hammingWeight(int n) { int ret 0 ; for (int i 0 ; i 32 ; i){ // 关键位运算判断n的第i位是否为1 if (n (1 i )){ ret ; // 如果是1计数器加1 } } } };这里拆解两个关键位运算1 i把数字 1 向左移动i位生成一个 “只有第i位是 1其余位都是 0” 的数。比如i01 0 1二进制000...0001。比如i11 1 2二进制000...0010。比如i31 3 8二进制000...1000。n (1 i)按位与运算。只有当n的第i位是 1 时结果才不为 0否则结果为 0。举例如果n5二进制000...0101检查i05 1 0101 0001 0001 ≠ 0→ 第 0 位是 1ret加 1。检查i15 2 0101 0010 0000 0→ 第 1 位是 0不计数。检查i25 4 0101 0100 0100 ≠ 0→ 第 2 位是 1ret再加 1。第五步返回最终结果循环结束后ret就是 1 的总个数返回这个值class Solution { public: int hammingWeight(int n) { int ret 0 ; for (int i 0 ; i 32 ; i){ if (n (1 i )){ ret ; } } // 返回最终统计的1的个数 return ret ; } };完整代码 测试示例为了让你更直观理解我们加一个main函数测试#include iostream using namespace std; class Solution { public: int hammingWeight(int n) { int ret 0 ; for (int i 0 ; i 32 ; i){ if (n (1 i )){ ret ; } } return ret ; } }; int main() { Solution sol; // 测试用例1n5二进制0101预期结果2 int n1 5; cout n5的二进制中1的个数 sol.hammingWeight(n1) endl; // 测试用例2n0二进制全0预期结果0 int n2 0; cout n0的二进制中1的个数 sol.hammingWeight(n2) endl; // 测试用例3n3二进制0011预期结果2 int n3 3; cout n3的二进制中1的个数 sol.hammingWeight(n3) endl; return 0; }运行结果n5的二进制中1的个数2 n0的二进制中1的个数0 n3的二进制中1的个数2总结核心思路遍历 32 位整数的每一位用1 i定位第i位再用运算判断该位是否为 1统计总数。位运算关键1 i生成 “掩码”n 掩码仅保留第i位的数值非 0 则说明该位是 1。边界处理循环固定 32 次确保覆盖 32 位整数的所有位包括最高位的符号位。3 题目136. 只出现一次的数字给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。示例 1 输入nums [2,2,1]输出1示例 2 输入nums [4,1,2,1,2]输出4示例 3 输入nums [1]输出1提示1 nums.length 3 * 104-3 * 104 nums[i] 3 * 104除了某个元素只出现一次以外其余每个元素均出现两次。4 代码实现cclass Solution { public: int singleNumber(vectorint nums) { int ret 0 ; for (auto e : nums){ ret ^ e ;} return ret ; } };js/** * param {number[]} nums * return {number} */ var singleNumber function(nums) { let ret 0 ; for (const e of nums){ ret ^ e ; } return ret ; };思考泪目。25年7月用java提交过现在毫无印象了曾经还用java写算法hhh...不过这题和位运算有什么关系啥意思和0异或异或得到的是啥a和0异或得到的是a吧a再和a异或就是0所以说两轮异或得到0一轮异或得到本身也就是就出现过一次的数妙啊我看题解的我自己不会写的hhh。5 小结非常水的一节也不能如此说位运算主要是一个思路和语法看了就知道的办法。不过我也是才做位运算的解法还没做到难的。坚持加油