【位运算】--- 初阶题目赏析

2024-09-03 03:20
文章标签 题目 初阶 运算 赏析

本文主要是介绍【位运算】--- 初阶题目赏析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:       9ilk

(๑•́ ₃ •̀๑) 文章专栏:     算法Journey  


根据上一篇位运算的总结,我们来体会几道初阶题目。


🏠 判定字符是否唯一

📌 题目解析

判定字符是否唯一

  • s[i]中只包含小写字母。

📌 算法原理

✏️ 思路一:哈希表

利用哈希表对小写字母进行映射,如果遍历过程中出现已经映射的直接返回false,若遍历完之后都没有出现映射两次的则返回true。

时间复杂度:O(N) 

空间复杂度:O(N)

class Solution {
public:bool isUnique(string astr){bool flag = true;int arr[27] = { 0 };//数组模拟哈希表for (int i = 0; i < astr.size(); i++){char ch = astr[i];int pos = ch - 'a' + 1;arr[pos] ^= pos;if (!arr[pos]){flag = false;break;}}return flag;}
};

✏️ 思路二:位图思想

一个int有4个字节,也就是有32个bit。我们这里都是小写字母,只需要利用26个bit位进行映射就能判断是否出现过。利用位运算判断映射位置是否为1,为1则出现过返回false;为0则没出现过,将该位设置为1。

优化: 抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的"抽屉原理"。抽屉原理的一般含义为:"如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到到n个集合中去,其中必定有一个集合里至少有两个元素。"抽屉原理有时也被称为鸽巢原理。

由此我们可以得到,当字符串长度大于26时,一定会出现重复,字符串长度相当于抽屉,字符相当于苹果!

class Solution {
public:bool isUnique(string astr){if(astr.size()>26) //抽屉原理return false;int bitset = 0;for(auto& e : astr ){int pos = e - 'a';if((bitset >> pos )&1) //判断该位是否为1return false;bitset |=  (1 << pos);//设置为1   } return true;}
};

🏠 丢失的数字

📌 题目解析

丢失的数字

📌 算法原理

✏️ 思路一 :  高斯求和公式

知道了数组长度n,则原本数字总个数应该为n+1个.遍历一遍数组求和sum,由于高斯求和公式(等差数列公式),则我们可以求原本未缺失数字时的总和,减去sum就是缺失的数字。

参考代码:

class Solution {
public:int missingNumber(vector<int>& nums) {int size = nums.size() + 1;int count = (size*(size - 1)) / 2;cout << count <<endl;int sum = 0;for(auto e :nums){sum += e;}return count - sum;}
};

✏️ 思路二 : 异或运算

我们知道异或其中两条运算律是a^a=0和结合率,因此我们遍历一遍原来的数字,再遍历一遍缺失数组,最后得到的数就是缺失的数字,因为未缺失的在两次过程相当于出现两次,也就是会异或为0,最后只剩缺失的没有配对.

参考代码:

class Solution {
public:int missingNumber(vector<int>& nums) {  //思路:我们先将范围内的数异或再异或数组每一个数 最后得到的就是丢失的int ret = 0;int n = nums.size();for(int i = 0 ; i <= n ; i++){ret ^= i;} for(const auto& e : nums){ret ^= e;}return ret;}
};

🏠 两整数之和

📌 题目解析

两整数之和

📌 算法原理

我们前面说过按位与本质上是无进位相加。那多出来的进位信息在哪呢?其实按位与就能保存进位信息。那是因为如果两个数某个位上的数字都是1话,就需要进位,此时按位与得到的还是1,而如果两个数中有一位是0的话按位与就是0,因此通过按位与能很好的知道那一位进位,那一位不进位。

注:由于仅仅一次按位与只是提取到进位信息,重要的是不断地将进位信息用完,直到进位信息为0(进位信息用完)。因此我们需要不断地用进位信息进行无进位相加直到用完进位信息。同时要注意在进位的过程中也会产生进位。

参考代码:

class Solution {
public:int getSum(int a, int b){int next = (a & b) << 1; //进位信息 按位与之后再左移一位才是进位信息 因为进的位是给下一位的int ret = a ^ b;//无进位相加while (next){int del = next;next = (next & ret) << 1;ret ^= del; //用进位信息进行无进位相加}return ret;}
};

完。

这篇关于【位运算】--- 初阶题目赏析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131882

相关文章

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

【Java中的位运算和逻辑运算详解及其区别】

Java中的位运算和逻辑运算详解及其区别 在 Java 编程中,位运算和逻辑运算是常见的两种操作类型。位运算用于操作整数的二进制位,而逻辑运算则是处理布尔值 (boolean) 的运算。本文将详细讲解这两种运算及其主要区别,并给出相应示例。 应用场景了解 位运算和逻辑运算的设计初衷源自计算机底层硬件和逻辑运算的需求,它们分别针对不同的处理对象和场景。以下是它们设计的初始目的简介:

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

位运算:带带孩子吧,孩子很强的!

快速进制 在聊到位运算之前,不妨先简单过一遍二进制的东西。熟悉二进制和十进制的快速转换确实是掌握位运算的基础,因为位运算直接在二进制位上进行操作。如果不熟悉二进制表示,很难直观理解位运算的效果。 这里主要涉及二进制和十进制之间的互相转换。 十进制转二进制 十进制转二进制可以使用常见的 除2取余法 进行。每次将十进制除以2并记录所得余数,直到商为0,然后再将记录的余数 从下往上排列即

2024 年高教社杯全国大学生数学建模竞赛题目——2024 年高教社杯全国大学生数学建模竞赛题目的求解

2024 年高教社杯全国大学生数学建模竞赛题目 (请先阅读“ 全国大学生数学建模竞赛论文格式规范 ”) 2024 年高教社杯全国大学生数学建模竞赛题目 随着城市化进程的加快、机动车的快速普及, 以及人们活动范围的不断扩大,城市道 路交通拥堵问题日渐严重,即使在一些非中心城市,道路交通拥堵问题也成为影响地方经 济发展和百姓幸福感的一个“痛点”,是相关部门的棘手难题之一。 考虑一个拥有知名景区

JAVAEE初阶第七节(中)——物理原理与TCP_IP

系列文章目录 JAVAEE初阶第七节(中)——物理原理与TCP_IP 文章目录 系列文章目录JAVAEE初阶第七节(中)——物理原理与TCP_IP 一.应用层重点协议)1. DNS2 .NAT3. NAT IP转换过程 4 .NAPT5. NAT技术的缺陷6. HTTP/HTTPS7. 自定义协议 二. 传输层重点协议 1 .UDP协议 2.1.1 UDP协议端格式 2.1.2 UD