当前位置: 首页 > news >正文

位运算+leetcode(1)

基础

1.基础知识

 以下都是针对数字的二进制进行操作

  • >>  右移操作符
  • <<  左移操作符
  • ~   取反操作符
  •  &  有0就是0,全一才一
  •  |  有一才一 ,全0才0
  • ^  相同为0,相异为1

 异或( ^ )运算的规律

  1. a ^ 0 = a 
  2. a ^ a = 0
  3. a ^ b ^ c =a ^ (b ^ c)
 2.基础操作

1.给一个数n, 判断它的二进制表示中的第x位是0 还是 1

( n >> x ) & 1

2.给一个数n, 将它的二进制表示中的第x位是修改为1

n = n | (1<<x)

 3.给一个数n, 将它的二进制表示中的第x位是修改为0

 n = n & (~ (1<<x) )

4.提取一个数( n )二进制表示最右侧的 1

这个意思:将这个数二进制形式,其中从右往左出现的第一个数字1,给保留下来,其它的位的数统统赋值给 0

n & (-n) 得到的就是

-n 表示的就是:从右往左出现的第一个数字1,它的左边区域全部变成相反的

5.干掉一个数( n )二进制表示最右侧的 1

n & ( n-1 )

n-1 表示的是:从右往左出现的第一个数字1,它的右边(包括它本身)全部变成相反

 Leetcode刷题

题一:位1的个数

1. 链接

191. 位1的个数 - 力扣(LeetCode)

 2.思路

直接将这个数(二进制表示形式)从右往左每次干掉一个1,然后在更新这个数,同时去统计一下总共进行了几次

3. 代码
int hammingWeight(uint32_t n) {int count=0;while(n){n=n&(n-1);count++;}return count;
}

题二:比特位计数

1. 链接

338. 比特位计数 - 力扣(LeetCode)

2.思路

暴力方法

   遍历 n 个数,每次统计此次所对应的数二进制里有几个1(这个就是题目一),然后再放到数组里去

 动态规划

 arr为我们最终返回的那个数组名

 规律

  • 我们让 arr [0] = 0
  • 当数字为偶数时,此时该数字(n)所含一的个数与 n / 2这个数相等
  • 当数字为奇数时,此时这个数(n)所含一的个数等于 n-1这个所对应的再加上1
 3.代码
//暴力
class Solution {
public:vector<int> countBits(int n) {vector<int> arr(n+1);for(int i=1;i<=n;i++){int ret=0;while(i>0){i=i&(i-1);ret++;}arr[i]=ret;}return arr;}
};
//动态规划
class Solution {
public:vector<int> countBits(int n) {vector<int> arr(n + 1);for (int i = 1; i <= n; i++) {if (i % 2 != 0) {arr[i] = arr[i - 1] + 1;} else {arr[i] = arr[i / 2];}}return arr;}
};

题三:汉明距离

1. 链接

461. 汉明距离 - 力扣(LeetCode)

2. 思路
  • 首先找到二个数中最大的数,在对最大的数,进行除二,求出其二进制的位数
  • 定义一个变量count,当 ((x >> i) & 1) ! =  ((y >> i) & 1) 成立时,就让count++
  • ((x >> i) & 1) != ((y >> i) & 1) 这个是基础操作里的如何判断一个数第i位是否为 1

 3.代码
class Solution {
public:int hammingDistance(int x, int y) {int _max = max(x, y);int count = 0;while (_max) {_max = _max / 2;count++;}int lenSum = 0;for (int i = 0; i < count; i++) {if (((x >> i) & 1) != ((y >> i) & 1)) {lenSum++;}}return lenSum;}
};

题四:判断字符是否唯一

1.链接

面试题 01.01. 判定字符是否唯一 - 力扣(LeetCode)

2.思路

鸽巢原理:有n个巢,和n+1个鸽子,那么至少会有一个巢鸟的数量>1

astr 是字符串数组名

用数组来模拟哈希表

  • 由于只含有小写字母,那么只要开辟一个数组长度为26的就可以
  • 如果字符串的长度大于26,那么则就返回 false(鸽巢原理
  • 当字符串的长度小于26,这里的映射关系是 astr[i] - 'a'
  • 先让此刻的字符进入哈希表,再去判断该字符在哈希表中位置的值是否大于1
  • 若大于1,则返回 false,否则,就继续循环

 用一个整数来模拟位图

  • 一个整数是4个字节,一个字节是8个比特位,那么就是有36位比特位
  • 由于只含有小写字母,那么一个整数就够用
  • 如果字符串的长度大于26,那么则就返回 false(鸽巢原理
  • 定义一个整数biteMap,并初始化为0(保证此刻biteMap的二进制位都为0,为了方便后面判断 )
  • 再去遍历这个 astr 字符串,先判断该字符在位图所在位置是否为1,
  • 若为1,则返回false
  • 若不为1,则将该字符在位图所在位置修改为1,在继续循环。
  • 若能将这个循环结束,那么则就返回true
 3.代码

法一 哈希表:

//哈希表
class Solution {
public:bool isUnique(string astr) {int hash[26] = {0};for (int i = 0; i < astr.size(); i++) {hash[astr[i] - 'a']++;if(hash[astr[i] - 'a']>1)return false;}return true;}
};

法二 位图: 

//位图
class Solution {
public:bool isUnique(string astr) {if (astr.size() > 26)return false;int biteMap = 0;for (auto ch : astr) {int i = ch - 'a';if (((biteMap >> i) & 1) == 1)return false;biteMap = biteMap | (1 << i);}return true;}
};

相关文章:

位运算+leetcode(1)

基础 1.基础知识 以下都是针对数字的二进制进行操作 >> 右移操作符<< 左移操作符~ 取反操作符 & 有0就是0&#xff0c;全一才一 | 有一才一 &#xff0c;全0才0^ 相同为0&#xff0c;相异为1 异或( ^ )运算的规律 a ^ 0 a a ^ a 0a ^ b ^ c a ^ (b …...

如何在 JavaScript 中比较两个日期 – 技术、方法和最佳实践

在 JavaScript 中&#xff0c;您可以使用 date 对象有效地处理应用程序中的日期、时间和时区。 Date 对象可帮助您有效地操作数据、处理各种与日期相关的任务&#xff0c;并在创建实际应用程序时执行一些计算。 &#xff08;本文内容参考&#xff1a;java567.com&#xff09;…...

【More Effective C++】条款17:考虑使用lazy evaluation

含义&#xff1a;将计算拖延到必须计算的时候&#xff0c;以下为4个场景 优点&#xff1a;避免不必要的计算&#xff0c;节省成本 缺点&#xff1a; 管理复杂性&#xff1a;可能会增加代码复杂性&#xff0c;特别是在多线程环境中需要正确处理同步和并发问题。性能开销&…...

深入探索Pandas读写XML文件的完整指南与实战read_xml、to_xml【第79篇—读写XML文件】

深入探索Pandas读写XML文件的完整指南与实战read_xml、to_xml XML&#xff08;eXtensible Markup Language&#xff09;是一种常见的数据交换格式&#xff0c;广泛应用于各种应用程序和领域。在数据处理中&#xff0c;Pandas是一个强大的工具&#xff0c;它提供了read_xml和to…...

如何在我们的模型中使用Beam search

在上一篇文章中我们具体探讨了Beam search的思想以及Beam search的大致工作流程。根据对Beam search的大致流程我们已经清楚了&#xff0c;在这我们来具体实现一下Beam search并应用在我们的seq2seq任务中。 1. python中的堆&#xff08;heapq&#xff09; 堆是一种特殊的树形…...

PKI - 借助Nginx 实现Https 服务端单向认证、服务端客户端双向认证

文章目录 Openssl操系统默认的CA证书的公钥位置Nginx Https 自签证书1. 生成自签名证书和私钥2. 配置 Nginx 使用 HTTPS3. 重启 Nginx 服务4. 直接访问5. 不验证证书直接访问6. 使用server.crt作为ca证书验证服务端解决方法1&#xff1a;使用 --resolve 参数进行请求域名解析解…...

WebSocket原理详解

目录 1.引言 1.1.使用HTTP不断轮询 1.2.长轮询 2.websocket 2.1.概述 2.2.websocket建立过程 2.3.抓包分析 2.4.websocket的消息格式 3.使用场景 4.总结 1.引言 平时我们打开网页&#xff0c;比如购物网站某宝。都是点一下列表商品&#xff0c;跳转一下网页就到了商品…...

在面试中如何回复擅长vue还是react

当面试官问及这个问题的时候&#xff0c;我们需要思考面试官是否是在乎你是掌握vue还是react吗&#xff1f;&#xff1f;&#xff1f; 在大前端的一个环境下&#xff0c;当前又有AI人工智能的加持辅助&#xff0c;我们是不是要去思考企业在进行前端岗位人员需求的时候&#xf…...

使用Vue.js输出一个hello world

导入vue.js <script src"https://cdn.jsdelivr.net/npm/vue2/dist/vue.js"></script> 创建一个标签 <div id"app">{{message}}</div> 接管标签内容&#xff0c;创建vue实例 <script type"text/javascript">va…...

15 ABC基于状态机的按键消抖原理与状态转移图

1. 基于状态机的按键消抖 1.1 什么是按键&#xff1f; 从按键结构图10-1可知&#xff0c;按键按下时&#xff0c;接点&#xff08;端子&#xff09;与导线接通&#xff0c;松开时&#xff0c;由于弹簧的反作用力&#xff0c;接点&#xff08;端子&#xff09;与导线断开。 从…...

λ-矩阵的多项式展开

原文链接 定义. 对于 m n m \times n mn 的 λ \lambda λ-矩阵 A ( λ ) [ a 11 ( λ ) . . . a 1 n ( λ ) ⋮ ⋮ a m 1 ( λ ) . . . a m n ( λ ) ] \mathbf{A}(\lambda)\begin{bmatrix} a_{11}(\lambda) & ... & a_{1n}(\lambda)\\ \vdots & & \vdo…...

如何在PDF 文件中删除页面?

查看不同的工具以及解释如何在 Windows、Android、macOS 和 iOS 上从 PDF 删除页面的步骤&#xff1a; PDF 是最难处理的文件格式之一。曾经有一段时间&#xff0c;除了阅读之外&#xff0c;无法用 PDF 做任何事情。但是今天&#xff0c;有许多应用程序和工具可以让您用它们做…...

蓝桥杯官网填空题(质数拆分)

问题描述 将 2022 拆分成不同的质数的和&#xff0c;请问最多拆分成几个&#xff1f; 答案提交 本题为一道结果填空的题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将结果输出即可。 运行限制 import java.util.Scanner;public class Main {static int …...

【数据结构】二叉树的顺序结构及链式结构

目录 1.树的概念及结构 1.1树的概念 1.2树的相关概念 ​编辑 1.3树的表示 1.4树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 2.二叉树概念及结构 2.1二叉树的概念 2.2现实中的二叉树 ​编辑 2.3特殊的二叉树 2.4二叉树的性质 2.5二叉树的存储结…...

海外IP代理:解锁网络边界的实战利器

文章目录 引言&#xff1a;正文&#xff1a;一、Roxlabs全球IP代理服务概览特点&#xff1a;覆盖范围&#xff1a;住宅IP真实性&#xff1a;性价比&#xff1a;在网络数据采集中的重要性&#xff1a; 二、实战应用案例一&#xff1a;跨境电商竞品分析步骤介绍&#xff1a;代码示…...

如何写好一个简历

如何编写求职简历 论Java程序员求职中简历的重要性 好简历的作用 在求职过程中&#xff0c;一份好的简历是非常重要的&#xff0c;它甚至可以直接决定能否被面试官认可。一份出色或者说是成功的个人简历&#xff0c;最根本的作用是能让看这份简历的人产生一定要见你的强烈愿…...

【AutoML】AutoKeras 进行 RNN 循环神经网络训练

由于最近这些天都在人工审查之前的哪些问答数据&#xff0c;所以迟迟都没有更新 AutoKeras 的训练结果。现在那部分数据都已经整理好了&#xff0c;20w 的数据最后能够使用的高质量数据只剩下 2k。这 2k 的数据已经经过数据校验并且对部分问题的提问方式和答案内容进行了不改变…...

H12-821_74

74.在某路由器上查看LSP&#xff0c;看到如下结果&#xff1a; A.发送目标地址为3.3.3.3的数据包时&#xff0c;打上标签1026&#xff0c;然后发送。 B.发送目标地址为4.4.4.4的数据包时&#xff0c;不打标签直接发送。 C.当路由器收到标签为1024的数据包&#xff0c;将把标签…...

有趣儿的组件(HTML/CSS)

分享几个炫酷的组件&#xff0c;起飞~~ 评论区留爪&#xff0c;继续分享哦~ 文章目录 1. 按钮2. 输入3. 工具提示4. 单选按钮5. 加载中 1. 按钮 HTML&#xff1a; <button id"btn">Button</button>CSS&#xff1a; button {padding: 10px 20px;text-tr…...

1、深度学习环境配置相关下载地址整理(cuda、cudnn、torch、miniconda、pycharm、torchvision等)

一、深度学习环境配置相关&#xff1a; 1、cuda&#xff1a;https://developer.nvidia.com/cuda-toolkit-archive 2、cudnn&#xff1a;https://developer.nvidia.com/rdp/cudnn-archive 4、miniconda&#xff1a;https://mirrors.tuna.tsinghua.edu.cn/anaconda/miniconda/?C…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...