广州市增城区建设局网站是什么北京网站关键词优化推荐

广州市增城区建设局网站是什么,北京网站关键词优化推荐,网站宣传用了最字,wordpress 标题 插件位运算的总结 基础位运算 左移 右移 ~ 按位取反 按位与#xff1a;有0则0 | 按位或#xff1a;有1则1 ^ 按位异或#xff1a;相同为0#xff0c;相异为1/无进位相加 位运算的优先级#xff1a;不需要记#xff0c;根据自己…位运算的总结基础位运算 左移 右移 ~ 按位取反 按位与有0则0 | 按位或有1则1 ^ 按位异或相同为0相异为1/无进位相加位运算的优先级不需要记根据自己的要求加上括号给一个数n确定它的二进制表示中的第 x 位是 0 还是 1如果要将0移动到最低位应该向右移动2位也就是下标位那么如何确定第x位是0还是1将 n 向右移动 x 位在1根据运算的规则有0则0同1则1。若第x位是0010若第x位是1111。公式表示为(n x) 1将一个数 n 的二进制表示的第 x 位修改成 1假设要将0修改成1仅需将0 | 1即可根据 | 运算规则有1则1同0则0。如何让指定比特位的0 | 1呢将1左移x位与n按位或即可。1数字的其它比特位都是0n的其它比特位与0异或不会被改变。公式表示n | (1 x)将一个数 n 的二进制表示的第 x 位修改成0假设要将1修改成0但是不影响 n 的其它比特位应该怎么办让修改位按位与0其它位按位与1即可。怎么获取到这么一个数11…………0111仅需将1左移 x 位再取反即可即 ~(1 x)。公式n ~(1 x)位图思想位图思想本质就是 hash 表只是我们见到的 hash 表大多都是数组使用一个变量的二进制位来记录信息。比特位为0/1各自表示一种信息。位图离不开上述提到的三种操作。提取一个数 n 的二进制表示中最右侧的 1仅需将 n -n即可-n 的二进制表示是 ~n 1~n:1001010111~n1:1001011000。将 1001011000 与 n 的二进制表示一对比发现以最右侧的1为分界点右侧没有改变左边取反。那么将 n ~n运算规则有0则0同1则1。以最右侧的1的左边都是相反的那么后都为0因此后最右侧的1就被提取出来了。公式n -n将一个数 n 的二进制表示中最右侧的 1 变成 0公式n (n-1)n 0110101000 n-10110100111n – 1 操作就是将以最右侧的 1 为分界点右侧取反包含分界点1左侧不改变。此时 n-1 n运算规则有0则0同1则1。n-1 n 0110100000这样就将最右侧的1变成0了异或运算的运算律a ^ 0 a a ^ a 0 a ^ b ^ c a ^ (b ^ c)算法题目题目1191. 位1的个数 - 力扣LeetCode题目分析给定一个正整数n编写一个函数获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数也被称为汉明重量。题目示例示例 1输入n 11输出3解释输入的二进制串1011中共有 3 个设置位。示例 2输入n 128输出1解释输入的二进制串10000000中共有 1 个设置位。示例 3输入n 2147483645输出30解释输入的二进制串1111111111111111111111111111101中共有 30 个设置位。算法原理题目要求找 n 二进制表示中 1 的个数转化思路也就是 n 的二进制表示中能有几个 1 变成 0即n (n-1)有几个1n (n-1)就可以执行几次。代码实现class Solution { public: int hammingWeight(int n) { // 计数器 int count 0; while(n) { // 将1变成0,有几个1就循环几次 n (n - 1); count; } return count; } };题目2338. 比特位计数 - 力扣LeetCode题目分析给你一个整数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] 中每个数的二进制表示 1 的个数。代码实现class Solution { public: vectorint countBits(int n) { // 返回值 vectorint ret(n 1); for(int i 0; i n; i) { // 统计i中1的个数 int count 0; int k i; while(k) { k (k-1); count; } ret[i] count; } return ret; } };题目3461. 汉明距离 - 力扣LeetCode题目分析两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。给你两个整数x和y计算并返回它们之间的汉明距离。题目示例示例 1输入x 1, y 4输出2解释1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。示例 2输入x 3, y 1输出1算法原理先将两个数的二进制表示存储起来在依次比较相同的比特位上的元素是否相等。如何获取一个数的二进制表示的 x 位比特位(n x) 1。代码实现class Solution { public: int hammingDistance(int x, int y) { int arr1[32] { 0 }; int arr2[32] { 0 }; // 将 x,y 的二进制位存储起来 for(int i 0; i 32; i) { // 获取x,y的每一个二进制位 arr1[i] (x i) 1; arr2[i] (y i) 1; } // 计数器 int count 0; // 比较不同 for(int i 0; i 32; i) { if(arr1[i] ! arr2[i]) { count; } } return count; } };题目4136. 只出现一次的数字 - 力扣LeetCode题目分析给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。题目示例示例 1 输入nums [2,2,1]输出1示例 2 输入nums [4,1,2,1,2]输出4示例 3 输入nums [1]输出1算法原理使用异或运算的规则a^a 00^a a。将 nums 数组中所有的元素异或在一起最终的结果就是数组中只出现一次的数字。代码实现class Solution { public: int singleNumber(vectorint nums) { int ret 0; for(auto e : nums) { ret ^ e; } return ret; } };题目5260. 只出现一次的数字 III - 力扣LeetCode题目分析给你一个整数数组nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。线性时间复杂度说明时间复杂度为O(N)只使用常量额外空间说明空间复杂度为O(1)。题目示例示例 1输入nums [1,2,1,3,2,5]输出[3,5]解释[5, 3] 也是有效的答案。示例 2输入nums [-1,0]输出[-1,0]示例 3输入nums [0,1]输出[1,0]算法原理本道题和上一道题的思路一致但是这道题nums数组中有两个只出现一次的数字因此我们需要将nums数组分成两部分每一部分都有一个只出现一次的数字。分组的依据的是什么根据nums数字所有元素异或得到结果 all获取all的二进制表示中最右边为1的比特位 bitmap让 bitmap 与 nums 中元素按位与为 1 的分成一组为 0 的分成一组。代码实现class Solution { public: vectorint singleNumber(vectorint nums) { // long 类型防止溢出 long all 0; for(auto e : nums) { all ^ e; } // 获取all中的最低位的1即最右边比特位为1 // long 类型防止溢出 long lowbit all (-all); // 分组 int nums1 0, nums2 0; for(auto e : nums) { // 在分组的过程中就开始异或 if(e lowbit) { nums1 ^ e; } else { nums2 ^ e; } } return {nums1, nums2}; } };题目6面试题 01.01. 判定字符是否唯一 - 力扣LeetCode题目分析实现一个算法确定一个字符串s的所有字符是否全都不同。题目示例示例 1输入:s leetcode输出:false示例 2输入:s abc输出:true限制0 len(s) 100s[i]仅包含小写字母如果你不使用额外的数据结构会很加分。算法原理解法1hash表遍历字符串判断遍历到的字符是否存在 hash 表中如果不存在则加入hash表继续向后遍历如果存在直接返回 false。解法2位图单独的 int 变量就有32位比特位从右向左依次表示 a,b,c,……。仅需使用 0~25 位比特位就可以表示26个英文字母了。其中 0 表示没有出现过1 表示出现过使用位图思想来替代数据结构hash。主要操作是查询某位比特位是否为1和将某个比特位修改成1。优化点根据双指针算法处提到的鸽巢原理一个有26个英文字母如果字符串的长度大于26那么字符串中一定存在相同的字符。代码实现class Solution { public: bool isUnique(string astr) { // 求字符串的长度 int len astr.length(); // 小优化 if(len 26) { return false; } // 使用位图思想 int bitmap 0; for(auto ch : astr) { int index ch - a; // 判断第 index 位是否为 1即是否存在 // 存在返回false if(((bitmap index) 1) 1) { return false; } // 不存在将第index比特位变成1 bitmap | (1 index); } return true; } };题目7268. 丢失的数字 - 力扣LeetCode题目分析给定一个包含[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中。提示n nums.length1 n 1040 nums[i] nnums中的所有数字都独一无二算法原理解法1hash表创建一个 n 1大小的hash表遍历 nums 数组将 nums 中的元素加入到hash表中最终看哪个位置的元素个数为0那么那个下标就是目标值。解法2求和使用等差数列的求和公式计算出从0~n的和再依次减去整个nums的元素和最终的结果就是目标值。解法3利用位运算创建一个 n 1大小的数组将创建的数组与 num s数组全部异或在一起最终结果就是目标值。使用第三种解法来解决问题。代码实现class Solution { public: int missingNumber(vectorint nums) { // 返回值 int ret 0; // 将 nums 数组中的元素异或在一起 for(auto e : nums) { ret ^ e; } // 再将ret与[0,n]异或 for(int i 0; i nums.size(); i) { ret ^ i; } return ret; } };题目8371. 两整数之和 - 力扣LeetCode题目分析给你两个整数a和b不使用运算符和-计算并返回两整数之和。题目示例示例 1输入a 1, b 2输出3示例 2输入a 2, b 3输出5算法原理题目要求不能使用加法和减法大概率就是使用位运算。这里使用异或运算在前文提到过异或运算规则无进位相加。找到异或运算的进位即可。例13 28 41无进位相加的结果要找到进位需要思考什么时候会出现进位。当1^1时才会进位即1,1是11,0和0,1是0这不就是 运算吗因此找进位的时候ab。但是我们找到只是会进位的位置进位是向左进位的因此 ab 再左移一位即可。接下来再重复上面的操作即将 a^b 看作 a(ab)1 看作 b。最终的进位仍然存在因此还需要重复的操作。最终进位变成0即b 0时终止操作。因此使用位运算作加法运算不断重复a^b 和 ab1。代码实现class Solution { public: int getSum(int a, int b) { // 进位 ab1 如果不等于0就一直需要重复 // (a ^ b)操作和(ab 1)操作 while(b ! 0) { int c a ^ b; // 无进位结果 int d (a b) 1; // 进位 a c; b d; } // 最终结果就是a return a; } };题目9137. 只出现一次的数字 II - 力扣LeetCode题目分析给你一个整数数组nums除某个元素仅出现一次外其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。题目示例示例 1输入nums [2,2,3,2]输出3示例 2输入nums [0,1,0,1,0,1,99]输出99算法原理使用位图来解决这道问题。nums数组中每一个元素都是整型所有元素的任意比特位之和可能出现以下四种情况3n 个003n 个013n 个103n 个11第n位比特位之和为 3n 个00那么第 n 位比特位的总和是0第n位比特位之和为 3n 个01那么第 n 位比特位的总和是1第n位比特位之和为 3n 个10那么第 n 位比特位的总和是3n第n位比特位之和位 3n 个11那么第 n 位比特位的总和是3n1再将这些比特位总和%3则3n个00 - 0 % 3 03n个01 - 1 % 3 13n个10 - 3n % 3 03n个11 - 1 % 3 1%3后的结果与前面的结果相呼应3n 后面加的数字是只出现一次的数的比特位。如果只出现一次的数的比特位为 0那么所有比特位加起来模3仍然等于0如果只出现一次的数的比特位为 1那么所有比特位加起来模3仍然等于1具体步骤将 nums 数组中所有元素的第 i 位加起来再模上3如果为0那么返回值 ret 的第 i 位比特位不变如果为1那么返回值 ret 的第 i 位比特位变成1。题目再继续扩展如果一个数只出现一次其余数出现了 k 次那么模的就是 k。代码实现class Solution { public: int singleNumber(vectorint nums) { // 返回值 int ret 0; // 依次修改ret的每一位比特位 for(int i 0; i 32; i) { // 记录nums数组的所有元素的第i位比特位之和 int sum 0; for(auto e : nums) { // 获取 e 的第i位比特位 sum ((e i) 1); } // 若 sum % 3 1,ret的第i位比特位变成1 if(sum % 3 1) { ret | (1 i); } } return ret; } };题目10面试题 17.19. 消失的两个数字 - 力扣LeetCode题目分析给定一个数组包含从 1 到 N 所有的整数但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗以任意顺序返回这两个数字均可。题目示例示例 1输入[1]输出[2,3]示例 2输入[2,3]输出[1,4]算法分析这道题可以转换成《只出现一次的数字III》《丢失的数字》即找到 nums 数组和 1~n2 序列中只出现一次的数字将 nums 数组和 1~n2 序列看成一个整体那么这道题就转化成了在这个整体中只出现一次的两个数字。在解决《只出现一次的数字III》问题中将 nums 所有的元素都异或在一起接着再根据 bitmap 变量进行分组bitmap 就是异或结果中最右边为1的比特位。为什么要根据它来作为分组条件整体中的元素与 bitmap 异或的结果只有两种 1 和 0如此就可以将整体序列分成两组。这两组异或的结果就是返回值。代码实现class Solution { public: vectorint missingTwo(vectorint nums) { // 整体序列的异或结果 long all 0; for(auto e : nums) { all ^ e; } for(int i 1; i nums.size() 2; i) { all ^ i; } // 获取bitmap,即all中最右边为1的比特位 long bitmap all (-all); // 分组 int nums1 0, nums2 0; for(auto e : nums) { if(e bitmap) { nums1 ^ e; } else { nums2 ^ e; } } for(int i 1; i nums.size() 2; i) { if(i bitmap) { nums1 ^ i; } else { nums2 ^ i; } } return {nums1, nums2}; } };