位运算
位运算符号
| 含义 | 运算符 | 示例 |
|---|---|---|
| 左移 | << | 0011 ->0110 |
| 右移 | >> | 0110 -> 0011 |
| 按位或 | | | 0011 | 1011 ->1011 |
| 按位与 | & | 0011|1011 -> 0011 |
| 按位取反 | ~ | 0011->1100 |
| 按位异或(不同为1) | ^ | 0011^1011 -> 1000 |
异或(XOR): 不进位加法，高阶操作（记住就好）
x^0 = x;
x^1s = ~x; // 1s= ~ 0, 表示全为1
x^(~x) = 1s;
x^x = 0;
c = a ^b; a^c=b;b^c=a //两数 交换
a^b^c=a^(b^c)=(a^b)^c; //交换律
任意的对二进制数的部分位进行 清零，置一，移动操作
- 清零x的最右边n位:
x&(~0<<n) - 获取x的第n位置:
(x>>n)&1 - 获取x的第n位的幂值:
x&(1<<(n-1)) - 仅将第n位替换为1:
x|(1<<n) - 仅将第n为替换为0:
x&(~(1<<n)) - 将x最高位至第n位(含)清零:
x&((1<<n)-1) - 将第n位到第0位(含)清零:
x&(~((1<<(n+1))-1))
实战要点，常用技巧
- 奇偶判断:
(x&1) - 除2:
x>>1 - 清零最低位:
(x&(x-1)) - 得到最低位的1:
x&-x - 清零:
x&~x=0
补充知识，原码、反码和补码
原码是二进制的原始表示，例如+2是000..010, -2是100...010
在涉及到负数的运算时，不能直接用负数的原码表示， 例如0010 + 1010 = 1100(-4的原码), 而不是0。
因此负数在运算时会用到它的补码，也就是负数的反码加一，反码指的是除符号位外按位取反，也就是1010 -> 1101(反码)-> 1110(补码)。另外规定正数的反码，补码都和原码相同。
于是，实际运算是正数的补码和负数的补码进行相加, 即 0010 + 1110 = 0000
实战题目
191. 位1的个数: x & (x-1) 不断打掉最右边的1
231. 2的幂: x & (x-1)直接打掉最右边的1，看是否为0
190. 颠倒二进制位: 答案每次先左移一位，然后把原数字的右边第一位加入到答案中，接着原数字右移，循环32次
338. 比特位计数: DP方程为 res[i] = res[i & (i-1)]
重点题目，利用位运算处理N皇后问题，分别是51. N皇后和52. N皇后 II
以4皇后，8位整型为例讲解里面的位运算。一开始初始化: row, cols, pie,na都是 00000000
下面语句的目的是获取可以放皇后的位置(二进制表示的1)
bits = (~(cols | pie | na)) & ((1 << n) — 1) # 得到当前所有的空位
~(cols | pie | na) 按位或，然后按位取反，也就是先得到所有1占据的位置，接着把1变为0，把0变成1，这里结果就是11111111.
((1 << n) — 1) 首先将00000001左移n位(n=4), 得到 00010000, 然后-1得到00001111,
将两者按位与，就得到00001111。1就是可以放皇后的位置。
注意，如果没有& ((1 << n) — 1)操作，就无法清空高位部分的1。
下面语句的目的是获取最低位的1，也就是0000111(1)
p = bits & —bits # 取到最低位的1
bits是00001111, -bits是10001111, 但是在运算过程中, -bits会以补码形式出现，也就是11110001, 因此实际是00001111 & 11110001 = 00000001
下面的语句是在bits中p的位置上放上皇后， 00001111 - 00000001 = 00001110
bits = bits - p # 表示在p位置上放入皇后
# 或
bits = bits & (bits — 1) # 也就是把最后一位变为0
递归一层，在原来的位置上加上p, 对于左下角要左移，右下角要右移(不需要再考虑数组的边界了)
self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)
于是新的row, cols, pie, na是 00000001, 00000001, 00000010, 00000000. (是原来棋盘的镜像翻转)
接着计算bits, 就是 00001100, 只剩下两个位置可以放皇后了。
感想: 之前看到位运算相关知识点的时候，一般我都会直接跳过，觉得我以后也用不上。但在八皇后问题中，位运算绝对是最优选择，位的左移和右移能够自动处理使用数组会出现的边界判断问题，同时也比使用set更加节约空间。八皇后所需要的复杂位运算只有三个而已，就是最高位到第n清零，获取最后一位1的位置和打掉最后一位的1。
布隆过滤器
哈希表是一个没有误差的数据结构，包括了元素的所有信息。
布隆过滤器是一个很长的二进制向量和一些列随机的映射函数组成。
优点：空间效率和查询效率极高
缺点：删除困难，且存在会情况
布隆过滤器是一个存在误差的数据结构，如果布隆过滤器返回不存在，那么百分百不存在。但是如果返回存在，那么未必真的有该元素。
布隆过滤的意义是高效缓存，如果查不到，就不需要继续查询数据库，如果查到了，我们才考虑去检索数据库。
案例：
- 比特币网络
- 分布式系统
- 使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
代码实现案例:
LRU缓存
缓存两个要素：大小，替换策略。缓存的大小通常是有限的，因此需要将缓存外更重要的东西替换到缓存中
替换算法：LRU(最近最少使用)，以哈希表+双链表实现， O(1)查询和O(1)的查询和更新
[图片上传失败...(image-4cb8df-1584940239942)]
面试的时候，介绍LRU是什么，它的三个API是什么？
实现方式有两种：
- 有序字典 （简单）
- 哈希表 + 双向链表（复杂）
Python提供了有序词典（根据插入顺序进行存放元素），Java提供了LinkedHashMap 链式的哈希表都可以用于实现第一种策略。C++的map是以红黑树进行存放元素，因此顺序是基于key,value对。
排序
分为比较类排序和非比较排序
表格中快排时间复杂度描述不当，快排是原地排序方法，不用额外申请空间。
一定要看的三篇文章：
看完动画发现，归并排序始终很稳定，而快排则和数据集关系很大（可以通过随机化标杆来优化），简单排序某些时候表现效果好于高级排序算法。由于快排平均情况能够达到O(n log n), 且是原地排序，是大部分程序标准库的第一选择。
初级排序: 插入排序，选择排序和冒泡排序
高级排序:
- 快速排序(分治): 数组取标杆(pivot), 将小元素放在pivot左边，大元素放在pivot放在右侧
- 归并排序(分治): 需要额外空间。
- 快排和归并具有相似性，但步骤相反，归并是排序左右子数组然后合并，快排是分开左右数组，然后对左右数组排序
- 堆排序: 先建立小顶堆（C++的优先队列），然后以此取出元素
特殊排序（要求数据都是整型，因此使用范围有限）
- 计数排序: 要求输入数据必须是有确定范围（例如成绩）
- 桶排序: 假设输入数据均匀分布，然后将数组分到优先数量的同，每个桶单独排序。 桶排序可以是计数排序的升级
- 基数排序: 先排个位，再排十位，再排百位
242. 有效的字母异位词：排序比较即可
56. 合并区间: 高频，看排序+一次扫描 逐行解释好理解 python3
493. 翻转对: 面试的时候需要注意逆序对，归并排序
如果是普通的逆序对，在归并排序的合并步骤时，检查顺序
如果arr[i] > arr[j] (i <j) 就说明存在一个逆序对， 此外如果左侧元素还没有使用完，就说明存在左侧元素存在比较大的情况，还需要统计。
对于重要翻转对，C++实现如下， 排序部分直接调用了自带的排序方法，导致时间复杂度从 n log(n) 变为, n log(n) log(n)
class Solution {
public:
int reversePairs(vector<int>& nums) {
return mergeSort(nums, 0, nums.size() -1);
}
//s: start, e: end
int mergeSort(vector<int>& nums, int s, int e){
if ( s >= e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for (int i = s, j = mid + 1; i <= mid; i++){
while ( j <= e && nums[i] / 2.0 > nums[j]) j++;
cnt += j - (mid+1);
}
sort(nums.begin()+s, nums.begin()+e+1);
return cnt;
}
};
程序分为三个部分:
- 一分为二，分别统计左右区间内的重要翻转对
- 然后统计，左右两个区间之间的重要翻转对
- 最后对左右区间合并（可以偷懒调用系统sort）
PS: 1244题目是会员才能做
其他
构造函数与成员初始化器列表: 初始化列表对成员变量初始化, 初始化列表比构造函数先执行
struct S {
int n;
S(int); // 构造函数声明
S() : n(7) {} // 构造函数定义。
// ": n(7)" 为初始化器列表
// ": n(7) {}" 为函数体
};
S::S(int x) : n{x} {} // 构造函数定义。": n{x}" 为初始化器列表
int main()
{
S s; // 调用 S::S()
S s2(10); // 调用 S::S(int)
}
