力扣hot100-->位运算

news/2024/11/2 8:22:06/

目录

位运算

1. 136. 只出现一次的数字

2. 338. 比特位计数

3. 461. 汉明距离


位运算

1. 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
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> count;  // 创建一个哈希表来计数

        // 遍历数组,统计每个数字的出现次数
        for (int i = 0; i < nums.size(); i++) {
            count[nums[i]]++;
        }

        // 查找唯一出现一次的数字
        for (int i = 0; i < nums.size(); i++) {
            if (count[nums[i]] == 1) {
                return nums[i];  // 返回该数字
            }
        }

        return 0;  // 如果没有找到,返回0
    }
};
 

解释:

// 位运算

// 异或运算的性质

// 1.任何数和0做异或运算,结果仍是原来的数

// 2.任何数和自己异或结果是0

// 3.异或运算满足交换律和结合律 

2. 338. 比特位计数

简单

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示:

  • 0 <= n <= 105

// 位运算
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> result;  // 用于存储每个数字的位1个数

        // 遍历从 0 到 n 的每个数字
        for (int i = 0; i <= n; ++i) {
            int count = 0;  // 计数器,初始化为 0
            int num = i;    // 复制当前数字

            // 计算 num 的位1的个数
            while (num > 0) {
                if (num & 1) {  // 检查最低位是否为1
                    ++count;    // 如果是1,则计数器加1
                }
                num = num >> 1;  // 右移一位,处理下一个位
            }
            result.push_back(count);  // 将计数结果添加到结果向量中
        }
        return result;  // 返回包含每个数字位1个数的向量
    }
};

3. 461. 汉明距离

简单

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

示例 1:

输入:x = 1, y = 4
输出:2
解释:
1   (0 0 0 1)
4   (0 1 0 0)↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2:

输入:x = 3, y = 1
输出:1

提示:

  • 0 <= x, y <= 231 - 1

// 方法1. 内置位计数功能
class Solution {
public:
    int hammingDistance(int x, int y) {
        // 计算 x 和 y 的异或结果,然后使用内置函数 __builtin_popcount 统计结果中 1 的个数
        return __builtin_popcount(x ^ y);
    }
};

// 位运算
//方法 2. 移位实现位计数
class Solution {
public:
    int hammingDistance(int x, int y) {
        int s = x ^ y;  // 计算 x 和 y 的异或,得到不同位的结果
        int ret = 0;    // 初始化计数器,用于记录不同位的个数

        // 逐位检查异或结果,统计其中的 1 的个数
        while (s) {
            ret += s & 1;  // 检查最低位是否为 1,若是,则计数加 1
            s >>= 1;       // 将 s 右移一位,处理下一个位
        }

        return ret;  // 返回不同位的总数(汉明距离)
    }
};

解释:

 x ^ y 是位运算中的异或操作。它的结果是将 xy 的每一位进行比较,若对应的两位相同则结果为 0,若不同则结果为 1。例如:x=5,y=3,则x ^ y结果如下:

   0101  (5)
^  0011  (3)
--------
   0110  (6)
 


http://www.ppmy.cn/news/1543811.html

相关文章

【Nginx系列】Nginx 中的`proxy_set_header`指令:Host 字段的区别与联系

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

pycharm小游戏飞机射击

导入pygame模块 下载成功 图片略显粗糙 python 复制 import pygame import random # 初始化 pygame pygame.init() # 屏幕大小 SCREEN_WIDTH 800 SCREEN_HEIGHT 600 # 颜色 WHITE (255, 255, 255) BLACK (0, 0, 0) GREEN (0, 255, 0) RED (255, 0, 0) # 飞机速度 P…

8.3.2 前向分步算法与 AdaBoost

由前向分步算法可以推导出 AdaBoost&#xff0c;用定理叙述这一关系。   定理 8.3  AdaBoost 算法是前向分步加法算法的特例。 这时&#xff0c;模型是由基本分类器组成的加法模型&#xff0c;损失函数是指数函数。   证明 前向分步算法学习的正加法模型&#xff0c;当基…

自动驾驶---理想汽车智驾进展

1 背景 自媒体---“电车通”从2024年初开始推出智能化评测相关栏目&#xff0c;尤其是针对智能驾驶这一功能做了大量的实测工作&#xff1b;根据综合表现&#xff0c;给测试车型给出了能够直观展示其能力的评分。当评测的对象达到一定数量后&#xff0c;对整个国内车市智驾能力…

小张求职记二:完善简历

金色的夕阳将校园染上一层温暖的橘色&#xff0c;操场上&#xff0c;足球队员们挥洒着汗水&#xff0c;欢笑声在空气中回荡&#xff0c;远处的图书馆里&#xff0c;学生们埋头苦读&#xff0c;偶尔传出翻书的声音。一切都是那么美好&#xff0c;仿佛时间都静止在了这美好的时刻…

红队-shodan搜索引擎篇

如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 一.shodan原理与功能的介绍 Shodan Search Engine 它是专门搜网络设备的,只要联网的,只要有IP地址的都可以称为网络设备 1.shodan&#x…

从0攒一个分布大数据/人工智能/数据库 处理引擎

以下各组件部署方式&#xff1a;嵌入模式 vs 独立服务模式 组件选型&#xff1a; 分布式网络通信: brpc, zmq ...分布式高可靠存储用于存元信息: zk, etcd, braft分布式状态保存用于存储数据: memory/disk storage(shuffle,sort): rocksdbpartition_manage单机计算引擎: Grap…

ICPC区域赛成都站【赛后回顾+总结】

传送门 前言赛后总结赛后回顾赛后感悟 前言 首先&#xff0c;这是本人本赛季第一场XCPC区域赛&#xff0c;也是本人算竞生涯中第一场XCPC区域赛&#xff08;之前只打过邀请赛和省赛&#xff09;。 赛后总结 然后赛后总结一下&#xff1a;我队天崩开局&#xff0c;我队出师不利…