dede无法一键更新网站,做网站营业执照经营范围怎么填写,抚州专业的企业网站建设公司,seo是什么意思怎么解决目录
1、 191. 位1的个数
2、 338. 比特位计数
3、 461. 汉明距离 4、136. 只出现一次的数字
5、 260. 只出现一次的数字 III
6、面试题 01.01. 判定字符是否唯一
7、 268. 丢失的数字
8、 371. 两整数之和
9、 137. 只出现一次的数字 II
10、面试题 17.19. 消失的两个…目录
1、 191. 位1的个数
2、 338. 比特位计数
3、 461. 汉明距离 4、136. 只出现一次的数字
5、 260. 只出现一次的数字 III
6、面试题 01.01. 判定字符是否唯一
7、 268. 丢失的数字
8、 371. 两整数之和
9、 137. 只出现一次的数字 II
10、面试题 17.19. 消失的两个数字 1.位运算常用操作 二进制左移一位 二进制右移一位~ 按位取反 有0则0| 有1则1^ 相同为0相异为1无进位相加
2.给一个数n,确定它的二进制表示中的第x位是0还是1
(nx)1或者n(1x)
3.将一个数n的二进制表示的第x位修改成1
n|(1x)
4.将一个数n的二进制表示的第x位修改成0
n(~(1x))
5.位图的思想
例如使用整形变量int的每一个二进制位进行记录
6.提取一个数(n)二进制表示中最右侧的1
n-n
7.干掉一个数(n)二进制表示中最右侧的1
n(n-1)
8.位运算的优先级
加括号解决
9.异或(^)运算的运算律
a^a0a^0aa^b^ca^(b^c)
1、 191. 位1的个数 思路干掉一个数(n)二进制表示中最右侧的1 n(n-1) class Solution {
public:int hammingWeight(uint32_t n) {int ret 0;while (n) {n (n - 1);ret;}return ret;}
};
2、 338. 比特位计数 class Solution {
public:vectorint countBits(int n) {vectorint a(n1);for (int i 0; i n; i) {int ret 0;int n i;while (n) {n (n - 1);ret;}a[i]ret;}return a;}
};
3、 461. 汉明距离 思路干掉一个数(n)二进制表示中最右侧的1 n(n-1) class Solution {
public:int hammingDistance(int x, int y) {int n x ^ y;int count 0;while (n) {n (n - 1);count;}return count;}
}; 4、136. 只出现一次的数字 class Solution {
public:int singleNumber(vectorint nums) {int v0;for(auto a:nums){v^a;}return v;}
};
5、 260. 只出现一次的数字 III class Solution {
public:vectorint singleNumber(vectorint nums) {int sum 0;for (int num : nums) {sum ^ num;}// 防止溢出int l (sum INT_MIN ? sum : sum (-sum));int num1 0, num2 0;for (int num : nums) {if (num l)num1 ^ num;elsenum2 ^ num;}return {num1, num2};}
}; 首先sum 是通过对数组中的所有元素进行异或操作得到的。由于其他元素都出现了两次所以异或操作会将相同的元素抵消掉最终得到的结果就是只出现一次的两个元素的异或值。 sum (-sum) 的作用是获取 sum 的最低位的 1 所对应的值。-sum 是 sum 的补码的负数它的二进制表示中只有最低位的 1 是相同的其他位都是相反的。通过与操作 sum (-sum)可以将 sum 的二进制表示中除了最低位的 1 以外的其他位都置为 0得到的结果就是最低位的 1 所对应的值。
这样l 就表示了只出现一次的两个元素在最低位的不同之处。在后续的循环中根据每个元素的最低位是否与 l 相同将元素分为两组分别进行异或操作最终得到的 num1 和 num2 就是只出现一次的两个元素。 需要注意的是由于 INT_MIN 的二进制表示中只有最高位是 1其他位都是 0所以在计算 l 的时候需要特殊处理 sum INT_MIN 的情况因为 -INT_MIN 会导致溢出以确保最低位的 1 能够正确地被提取出来。 INT_MIN 的二进制形式是一个以 1 开头后面跟着 31 个 0 的二进制数。在大多数平台上INT_MIN 的二进制表示为
10000000000000000000000000000000
这是一个带符号的 32 位整数最高位为 1表示负数其余位为 0。这是 int 类型能够表示的最小值。
6、面试题 01.01. 判定字符是否唯一 思路位图思想int类型变量有32个比特位选取26个比特位记录字母判断是否每个字母只出现一次。 class Solution {
public:bool isUnique(string astr) {if (astr.size() 26)return false;int bitmap 0;for (auto s : astr) {int i s - a;if ((bitmap i) 1 1)return false;elsebitmap | (1 i);}return true;}
};
7、 268. 丢失的数字 思路两次异或 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;}
};
8、 371. 两整数之和 class Solution {
public:int getSum(int a, int b) {while (b ! 0) {int ret a ^ b;unsigned int carry (unsigned int)(a b) 1;a ret;b carry;}return a;}
};
9、 137. 只出现一次的数字 II class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for (int i 0; i 32; i) {int sum 0;for (auto n : nums) {if (((n i) 1) 1)sum;}sum % 3;if (sum 1)ret | 1 i;}return ret;}
};
10、面试题 17.19. 消失的两个数字 class Solution {
public:vectorint missingTwo(vectorint nums) {int tmp 0;for (auto x : nums) {tmp ^ x;}for (int i 1; i nums.size() 2; i) {tmp ^ i;}int d 0;while (((tmp d) 1) ! 1) {d;}int a 0, b 0;for (auto x : nums) {if (((x d) 1) 1)a ^ x;elseb ^ x;}for (int i 1; i nums.size() 2; i) {if (((i d) 1) 1)a ^ i;elseb ^ i;}return {a, b};}
};
