位运算

单词长度的最大乘积 原题链接：https://leetcode.cn/problems/aseY1I/ 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 1234567891011121314151617181920212223242526class Solution {public: bool have_same_char(string str1, string str2) { for (char c = 'a'; c <= 'z'; ++c) { int flag1 = 0; int flag2 = 0; for (int i = 0; i < str1.size(); ++i) if (str1[i] == c) {flag1 = 1; break;} for (int i = 0; i < str2.size(); ++i) if (str2[i] == c) {flag2 = 1; break;} if (flag1 && flag2) return true; } return false; } int maxProduct(vector<string>& words) { int max = 0; for (int i = 0; i < words.size(); ++i) { for (int j = i; j < words.size(); ++j) { int temp = words[i].size() * words[j].size() ...

二进制中1的个数 AcWing801.二进制中1的个数 求n的第k位数字: n >> k & 1 返回n的最后一位1：lowbit(n) = n & -n 1234567891011121314151617181920#include<iostream>using namespace std;int lowbit(int x) { return x & -x;}int main() { int n; scanf("%d", &n); while (n--) { int x; int res = 0; scanf("%d", &x); while (x) { x -= lowbit(x);//每次减去x的最后一位1 res++; } printf("%d", res); } return 0;}

只出现一次的数字 原题链接：https://leetcode.cn/problems/WGki4K/description/ 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 1.暴力法1234567891011121314151617class Solution {public: int singleNumber(vector<int> &nums) { vector<int> ans = nums; sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); for (int i = 0; i < ans.size(); ++i) { int count = 0; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == ans[i]) count++; if (count > 1) break; } if (count == 1) return ans[i]; } return -1; }}; 2.哈希法哈希法：哈希映射统计数组中每个元素的出现次数，在统计完成后，遍历哈希映射即可找出只出现一次的元素。 12345678910111213141516class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; unordered_map<int, int> unmap; for (int num : nums) unmap[num]++; pair<i ...

前n个数字二进制中1的个数 原题链接：https://leetcode.cn/problems/w3tCBm/ 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。 1.一般思路12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int x = i; int count = 0; while (x) { if (x % 2 == 1) count++; x /= 2; } ans.push_back(count); } return ans; }}; 2.位运算12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int count = 0; int x = i; while (x != 0) { count++; x = x & (x - 1); } ans.push_back(count); } return ans; }}; 3.动态规划对于所有的数字，只有奇数和偶数两种： 奇数：二进制表示中，奇数一定比前面那个偶数多一 ...

二进制加法 原题链接：https://leetcode.cn/problems/JFETK5/ 位运算是将数字用二进制形式表示之后，对每位上0或1的运算，二进制及其位运算是现代计算机科学的基石， 位运算种类：非~、与&、或|、异或^、左移<<、右移>> 按位与&：对应二进制位上，a与b必须同时为真 按位或|：对应二进制进位上，a与b有一边为真即可 异或运算^：对应二进制位上，相同则为0，不同则为1（逆运算首先满足交换律） 关于异或运算的补充： 异或运算是逆运算：由 a ^ b = c 可得 c ^ a = b； c ^ b = a； 相同的数异或运算为0：n ^ n = 0 ; 任何数与0异或运算值不变：0 ^ n = n； 问：在文件中有一堆整数，每一次数都出现了两次，其中有一个值只出现了一次，如何快速找到只出现一次的这个数的值？ 答：利用异或运算解决，将所有整数互相异或，最后得到的值即为只出现一次的值 左移 m << n ：二进制数整 m 左移n 位 右移 m >> n：二进制数整 m 右移 n 位 运算 按位与& 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1 按位或| 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1 按位异或^ 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0 1.数制转换主要思路：将输入的二进制转换为10进制，使用10进制进行运算，将得到的结果转化回二进制即可。 存在问题：outside the range of representable values of type ‘int’，将int类型改为long long 无法存储， 1234567891011121314151617181920212223242526272829303132333435class Solution {public: string _ ...

整数除法 原题链接：https://leetcode.cn/problems/xoh6Oh/ 编程语言可能会提供占据不同内存空间的整数类型，每种类型能表示的整数范围不同， 无符号整数无论二进制表示的最高位是0还是1，其都表示一个正数，32位整数的范围为 ~ 。由于整数范围的限制，如果计算结果超出了范围，就会产生溢出。产生溢出时运行不会出错，但是计算结果可能会出乎意料。 1.减法主要思路：为了求得dividend/divisor，可以不断的从dividend里减去divisor，当不能再减去更多的divisor时，循环执行的次数就是商 存在问题： 当除数很大时，减法操作执行的次数就会很多，导致程序超时，如 没有考虑除数与被除数，在32位int数据类型的范围溢出问题 没有考虑除法结果，在32位int数据类型的范围溢出问题 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.减法的优化主要思路： 当被除数大于除数时，继续比较判断被除数是否大于除数的2倍，如果是则继续判断是否大于除数的4倍、8倍、… 倍， 如果被除数最多大于除数的 倍，则将被除数减去除数的 倍，然后将剩余的被除数重复前面的步骤（由于每次 ...

只出现一次的数字 原题链接：https://leetcode.cn/problems/single-number/description/ 给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 1.位运算1234567891011//异或运算 ^=class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++i) { ans ^= nums[i]; } return ans; }}; 0 ^ x = x x ^ x = 0 异或满足交换律 2.暴力枚举1234567891011121314//暴力双层for循环 ---- 超出时间限制class Solution {public: int singleNumber(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) { int flag = 1; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == nums[i] && i != j) flag = 0; } if (flag) return nums[i]; } return -1; }}; 3.常见位运算的操作 得到右数第 k 位值：(x >> k) & 1 把右数第 k 位值置1：x | (1 << k) 把右数第 k 位值取反：x ...