茶叶网站flash模板免费下载,青海城乡建设厅网站,济南市住房和城乡建设部网站,正阳县网站建设文章目录 C 位运算详解#xff1a;基础题解与思维分析前言第一章#xff1a;位运算基础应用1.1 判断字符是否唯一#xff08;easy#xff09;解法#xff08;位图的思想#xff09;C 代码实现易错点提示时间复杂度和空间复杂度 1.2 丢失的数字#xff08;easy#xff0… 文章目录 C 位运算详解基础题解与思维分析前言第一章位运算基础应用1.1 判断字符是否唯一easy解法位图的思想C 代码实现易错点提示时间复杂度和空间复杂度 1.2 丢失的数字easy解法位运算C 代码实现易错点提示时间复杂度和空间复杂度 1.3 两整数之和medium解法位运算C 代码实现易错点提示时间复杂度和空间复杂度为什么选择无符号类型来防止溢出 1.4 只出现一次的数字 IImedium解法比特位计数C 代码实现易错点提示时间复杂度和空间复杂度 1.5 消失的两个数字hard解法位运算 lowbitC 代码实现易错点提示时间复杂度和空间复杂度 写在最后 C 位运算详解基础题解与思维分析 欢迎讨论如有疑问或见解欢迎在评论区留言互动。 点赞、收藏与分享如觉得这篇文章对您有帮助请点赞、收藏并分享 分享给更多人欢迎分享给更多对 C 感兴趣的朋友一起学习位运算的基础与进阶 前言 在算法的世界里位运算是一门精妙的技艺简洁而高效似微风拂水看似无声却能激起阵阵涟漪。位运算将每一位的状态变换化作算法中的魔法使得复杂问题得以在比特的碰撞间被轻松解构。它是一种微观的语言却能支撑起宏观的世界它的每一次与或非移仿佛是对数据世界的精确雕琢将代码的力量发挥到极致。 本篇文章意在带你走进位运算的世界细数其中蕴含的算法之美。从最基础的字符判定到丢失数字的找回从无进位加法的实现到位图的优化每一道题目都是对位运算逻辑的深层探索。我们会一步步揭开位运算的面纱透过 C 语言的语法与语义看见算法设计中隐藏的巧思与哲理。 愿这篇文章不仅能成为你算法学习中的指南更能启发你在每一道“位”的转动中感受代码的力量与数学的纯粹。让我们以最细微的单位为起点探寻算法的浩瀚宇宙在这片二进制的旷野中找到属于你的算法之道。 第一章位运算基础应用
1.1 判断字符是否唯一easy
题目链接面试题 01.01. 判定字符是否唯一
题目描述
实现一个算法确定一个字符串 s 的所有字符是否全都不同。
示例 1
输入s leetcode输出false
示例 2
输入s abc输出true
提示
0 len(s) 100s[i] 仅包含小写字母如果不使用额外的数据结构会很加分。 解法位图的思想
算法思路
利用「位图」的思想每一个「比特位」代表一个「字符」一个 int 类型的变量的 32 位足够表示所有的小写字母。在位图中如果一个比特位是 0表示这个字符没有出现过如果一个比特位是 1表示该字符出现过。
因此我们可以使用一个「整数」来充当「哈希表」 字符映射每个字符的出现与否可以映射到一个 bitMap 中的比特位上。 位运算操作 检测检测字符是否已经出现过使用 ((bitMap i) 1) 1 来检查第 i 位。添加字符使用 bitMap | 1 i 将字符加入到 bitMap 中。 鸽巢原理优化当字符串长度超过 26 时必定有重复字符可以直接返回 false。 C 代码实现
class Solution {
public:bool isUnique(string astr) {// 利用鸽巢原理来做的优化if (astr.size() 26) return false;int bitMap 0;for (auto ch : astr) {int i ch - a;// 先判断字符是否已经出现过if (((bitMap i) 1) 1) return false;// 把当前字符加入到位图中bitMap | 1 i;}return true;}
};易错点提示 位图的初始化与处理 bitMap 初始值为 0保证所有比特位均为 0即所有字符均未出现。 鸽巢原理优化 如果 s 的长度超过 26必定有重复字符可以直接返回 false减少不必要的遍历。 按位判断与添加 通过位移和按位或操作确保每个字符的状态准确记录在位图中。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是字符串的长度需要遍历字符串一次。空间复杂度O(1)仅使用一个 int 来存储位图。 1.2 丢失的数字easy
题目链接268. 丢失的数字
题目描述
给定⼀个包含 [0, n] 中 n 个数的数组 nums 找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1
输入nums [3,0,1]输出2解释n 3因为有 3 个数字所以所有的数字都在范围 [0,3] 内。2 是丢失的数字因为它没有出现在 nums 中。
示例 2
输入nums [0,1]输出2解释n 2因为有 2 个数字所以所有的数字都在范围 [0,2] 内。2 是丢失的数字因为它没有出现在 nums 中。
示例 3
输入nums [9,6,4,2,3,5,7,0,1]输出8解释n 9因为有 9 个数字所以所有的数字都在范围 [0,9] 内。8 是丢失的数字因为它没有出现在 nums 中。
示例 4
输入nums [0]输出1解释n 1因为有 1 个数字所以所有的数字都在范围 [0,1] 内。1 是丢失的数字因为它没有出现在 nums 中。
提示
n nums.length1 n 10^40 nums[i] nnums 中的所有数字都独⼊无二
进阶你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题 解法位运算
算法思路
设数组的大小为 n 那么缺失之前的数就是 [0, n] 数组中是在 [0, n] 中缺失一个数形成的序列。 如果我们把数组中的所有数以及 [0, n] 中的所有数全部「异或」在一起那么根据「异或」运算的「消消乐」规律最终的异或结果应该就是缺失的数。 C 代码实现
class Solution {
public:int missingNumber(vectorint nums) {int ret 0;for(auto x : nums) ret ^ x;for(int i 0; i nums.size(); i) ret ^ i;return ret;}
};易错点提示 理解异或运算 异或运算具有自反性和交换性任何数与自己异或的结果为 0任何数与 0 异或的结果为该数本身。 边界条件处理 确保遍历过程中正确处理所有范围内的数字。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是数组的长度需要遍历数组两次。空间复杂度O(1)仅使用一个整数变量来存储异或结果。 1.3 两整数之和medium
题目链接371. 两整数之和
题目描述
给你两个整数 a 和 b不使用运算符 和 -计算并返回两整数之和。
示例 1
输入a 1, b 2输出3
示例 2
输入a 2, b 3输出5
提示
-1000 a, b 1000 解法位运算
算法思路
异或 ^ 运算本质是「无进位加法」用于计算 a 和 b 在不考虑进位的情况下的和。按位与 操作用于计算 a 和 b 的进位部分左移一位后表示将进位加到下一位。不断更新 a 为无进位和b 为进位值重复以上步骤直到 b 变为 0表示没有进位了a 就是最终的加法结果。 C 代码实现
class Solution {
public:int getSum(int a, int b) {while(b ! 0){int x a ^ b; // 先算出无进位相加的结果unsigned int carry (unsigned int)(a b) 1; // 算出进位a x;b carry;}return a;}
};易错点提示 理解位运算的含义 异或运算 a ^ b 可以有效地计算无进位相加的部分而按位与 a b 运算可以确定需要进位的部分。将进位部分左移一位表示加到更高一位上这与常规加法的进位规则是一致的。 为什么使用无符号整数类型 题目限制的 a 和 b 范围-1000 到 1000实际上不会超出 int 范围因此在很多编译环境中即使使用 int 类型通常也可以通过测试。但为了编写健壮的代码尤其是处理可能的极值或边界情况时推荐在位运算加法中使用 unsigned int 来处理进位值。原因是 在 C 中带符号整数int在左移时若超过其表示范围可能导致未定义行为。而 unsigned int 在左移超过范围时则会进行模 (2^{32}) 运算这样可以保证结果在范围内“循环”。这种处理方式可以确保即使位运算结果溢出程序仍然能够稳定地获得正确的结果。 确保循环终止条件 注意循环条件 b ! 0确保在进位为 0 时停止。此时a 已经包含了最终的结果。 时间复杂度和空间复杂度
时间复杂度O(1)因为在 32 位系统上位运算的次数是有限的与输入值的大小无关。空间复杂度O(1)只使用了常数空间来存储中间变量。 为什么选择无符号类型来防止溢出
在 C 中带符号整数在超出范围时的行为是未定义的而无符号整数超出范围时会自动取模。选择 unsigned int 能够确保即使溢出程序也会得到一个稳定的结果。例如a 0x40000000 和 b 0x40000000即 1073741824在左移后超出 int 范围时unsigned int 可以保证结果循环到范围内而不会产生未定义行为。
这种方法不仅适用于该题目也是一种编写健壮的位运算代码的好习惯。 1.4 只出现一次的数字 IImedium
题目链接137. 只出现一次的数字 II
题目描述
给你一个整数数组 nums除某个元素仅出现一次外其余每个元素都恰出现三次。请你找出并返回那个只出现了唯一一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
示例 1
输入nums [2,2,3,2]输出3
示例 2
输入nums [0,1,0,1,0,1,99]输出99
提示
1 nums.length 3 * 10^4-2^31 nums[i] 2^31 - 1nums 中除某个元素仅出现一次外其余每个元素都恰出现三次。 解法比特位计数
算法思路
设要找的数为 ret。由于整个数组中需要找的元素只出现了一次其余的数都出现三次因此我们可以根据所有数的某一特定位的总和 % 3 的结果快速定位到 ret 的某个特定位上的值是 0 还是 1。通过 ret 的每一个比特位上的值就可以将 ret 还原出来。 C 代码实现
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(int i 0; i 32; i) // 依次去修改 ret 中的每一位{int sum 0;for(int x : nums) // 计算 nums 中所有的数的第 i 位的和if(((x i) 1) 1)sum;sum % 3;if(sum 1) ret | 1 i;}return ret;}
};易错点提示 理解比特位计数的原理 需要关注每一位的计数并确保只针对出现一次的数的比特位进行处理。 循环的边界条件 确保循环遍历每一位时处理负数时的位运算没有产生意外结果。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是数组的长度需要遍历数组多次但每次遍历都只针对 32 位。空间复杂度O(1)仅使用常量空间来存储 ret 和 sum。 1.5 消失的两个数字hard
题目链接面试题 17.19. 消失的两个数字
题目描述
给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗 以任意顺序返回这两个数字均可。
示例 1
输入[1]输出[2,3]
示例 2
输入[2,3]输出[1,4]
提示
nums.length 30000 解法位运算 lowbit
算法思路
该问题可以看作是 268. 丢失的数字 与 260. 只出现一次的数字 III 的组合问题。本题的核心在于利用异或操作与 lowbit 方法进行高效分组。通过以下步骤找到缺失的两个数字 初始异或操作 将 nums 数组中所有数与 [1, n 2] 区间内的所有数依次异或。由于异或的特点相同的数字异或结果为 0最后会得到 tmp其值是两个缺失数字的异或结果 a ^ b。此时 tmp 不为 0因为 a 和 b 是不同的数字必然有某一位不同。 使用 lowbit 找到分组位 利用 lowbit获取 tmp 最低为 1 的位找到 tmp 中的一个不为 0 的比特位 diff。该位能区分两个缺失的数字因为 a 和 b 在这一位上必然不同。 计算 diff 的方法为 diff tmp -tmp它提取 tmp 的最低有效位。 根据 diff 进行分组异或 通过 diff 位对所有数字进行分组将数组 nums 和 [1, n2] 中的所有数根据 diff 位的不同分成两组分别对每组进行异或 如果某数字在 diff 位上为 1则将其与 b 异或否则将其与 a 异或。 由于其他成对出现的数字会在分组后各自抵消最终 a 和 b 的值就是这两个消失的数字。 C 代码实现
class Solution {
public:vectorint missingTwo(vectorint nums) {// 1. 将所有的数异或在一起得到 a ^ bint tmp 0;for (int x : nums) tmp ^ x;for (int i 1; i nums.size() 2; i) tmp ^ i;// 2. 使用 lowbit 找到 a 和 b 中最低不同的位int diff tmp -tmp; // 利用 lowbit 找到第一个不同的比特位// 3. 根据 diff 位的不同将所有的数划分为两类并异或int a 0, b 0;for (int x : nums)if (x diff) b ^ x;else a ^ x;for (int i 1; i nums.size() 2; i)if (i diff) b ^ i;else a ^ i;return {a, b};}
};易错点提示 理解 lowbit 的用途 lowbit 方法可以快速获取一个整数的最低为 1 的比特位确保我们能高效地将两个缺失数字分开处理。这一步骤相当于找到了这两个数字的“区分特征”。 分组后的异或逻辑 使用 diff 位对所有数字进行分组后对每组进行异或操作。因为其他成对出现的数字在每组中互相抵消最后保留的即为两个只出现一次的数字。 确保正确处理 diff 位的计算和分组条件 diff tmp -tmp 提取了 tmp 的最低有效位第一个不为 0 的位。这一位能够保证 a 和 b 被正确分组因此在进行分组异或时要格外注意 diff 的使用。 时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是数组的长度需遍历所有数字一次。空间复杂度O(1)只使用常量空间来存储临时变量。 写在最后 位运算是算法世界中的点滴星辰看似细微却拥有改变全局的力量。在 C 中位运算不仅仅是逻辑符号的堆叠而是通过对每一个比特的操控使得代码在有限的资源中发挥出无限的效能。从基础的字符判定到复杂的加法运算位运算用简洁的方式诠释了算法的本质——那是一种近乎哲学的简约主义以最小的构件描绘出最大的问题解决空间。 微观的位运算如涓涓细流涓滴不息却汇成了庞大而稳定的算法结构。我们在加法中找到无进位的神奇在查找中看到消消乐的奥秘在位图中读出数据压缩的智慧。每一道位运算的题目都是对代码效率的深思每一个解法的背后都是对数学美感的致敬。 数之深位之微若能在这片无声的数字原野中找到心中的算法之道便是对这门艺术的最高赞礼。愿位运算的精妙启发你在算法的道路上不断前行不断探索在这无垠的计算世界中找到属于你的高峰与星辰。 以上就是关于【优选算法篇】微位至简数之恢宏——解构 C 位运算中的理与美的内容啦各位大佬有什么问题欢迎在评论区指正或者私信我也是可以的啦您的支持是我创作的最大动力❤️
