学习笔记

Week8

位运算

XOR异或 ，相同为0，相异为1，也可理解为 "不进位加法"

x^0=x	  //0         即00000000...
x^1s =~x  //1s表示 =~0 即11111111...
x^(~x)=1s
x^x=0
    
temp=a^b
b=temp^b
a=temp^a
	=>3行右边一样的
a=a^b;
b=a^b;//b=a
a=a^b;//temp^a
a^b^c=a^(b^c)=(a^b)^c   // associative laws

指定位置的位运算（以下说的第n位，是从0开始）

1. 将最右边的n位清零：x&(~0<<n) 优先级~高于<<

2. 获取x的第n位值（0/1）:(x>>n)&1

3. 获取x的第n位的幂值：x&(1<<n)

4. 仅将第n位置为1：x|(1<<n)

5. 仅将第n位置为0：x&(~(1<<n))

6. 将x最高位至第n位（含）清零：x&((1<<n)-1) n皇后中有使用

实战位运算：

• 判断奇偶：(x&1)==1/0

• x>>1 ->x/2，mid=(left+right)>>1; 注意 不能mid=left+(right-left)>>1;加减乘除运算优先级都高于>>

• x&-x =>得到最低位的1

• x=x&(x-1)清零最低位的1，0&-1得0，若是2的幂次，则(x&x-1)==0为true注意，逻辑运算符高于&

• x&~x=>0

  		算术运算符（含移位）	逻辑比较	位运算	逻辑
  ++ --	* 取地址& 逻辑！ 按位反~	+-*/% >> <<	< <= > >=	&^|	&& || ?:

因此x&x-1 n>>i&1 or n&1<<i是可以的，但是if(n&1==0)是错误的，结果总是1==0，所以最好都加()

布隆过滤器

HashTable+拉链存储重复元素：所有元素占的空间，在哈希表里都要找相应内存的大小给存起来

而很多时候在工业级应用中，我们不需要存所有元素本身，而只需要存储 一个元素 在or不在 我的表里。

布隆过滤器：一个很长的二进制向量和一系列随机映射函数。可用于检索一个元素是否在一个集合中。（哈希表除了检索是否存在，还可以存额外信息）

优点：空间效率和查询时间都远超一般算法（模糊查询）

缺点：有一定误识别率和删除困难。

原理：可以将 x y z 的二进制位都存到向量内， 每个数都会被分配成几位，把x对应位置1就代表存入x。查询就是看目标在向量内转化成的几位数字是否都为1，都为1则目标存在。

但由于数据转化到向量内的位，可能有重叠，所以一个不存在于过滤器的词，有可能在向量内对应位已经被前面元素置为1，误判为存在，但是如果一个元素被判断不存在（不全为1），则必然100%不存在

所以布隆过滤器，可以过滤掉必然不在集合中的元素，相当于外面的一个快速查询的缓存，真正确定存在，还需要后面访问数据（一般就是数据库）的一个完整存储数据结构。

• 比特币网络

• 分布式系统（Map-Reduce)-Hadoop search engine

• Redis 缓存

• 垃圾邮件、评论等的过滤

LRU Cache

缓存，如斐波那契的记忆化搜索，也类似CPU的三级缓存，主要是越高速的缓存，容量越小，所以在使用满后，需要将不常用的内容置换出去，LRU Cache 就是Least Recently Used 最近最少使用算法

• 两要素：大小、替换策略

• HashTable+双向链表

• O(1) get(key)查询 O(1) put(key)修改、更新

还有一些LFU、LFRU都属于cache替换算法，与推荐系统有异曲同工之妙，根据使用频次和使用时间来预测新来的一个元素是老元素的概率是多少

排序算法

1. 比较累排序

   通过比较决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn) ，因此也称为非线性时间比较类排序。

2. 非比较类排序

   不通过比较来决定元素相对次序，可突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。缺点就是一般只能用于整形排序，且需要辅助用的额外空间（一般就是放到数组里统计每个数出现的次序）。

   	      交换排序	   冒泡排序
   					 快速排序
   					 
   		  插入排序	   简单插入排序
   		  			 希尔排序
   比较类：		  
   		  选择排序	   简单选择排序
   		  			 堆排序
   		  				
   		  归并排序	   两路归并排序
   		  			  多路归并排序
   
   			计数排序(稳定)
   非比较类排序：	桶排序 (稳定)
   			基数排序(稳定)
   

   排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
   冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
   快速排序	O(nlog2n)	O(n^2)	O(nlog2n)	O(nlog2n)	不稳定
   插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
   希尔排序	O(n^1.3)	O(n^2)	O(n)	O(1)	不稳定
   选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
   堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定
   归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定
   计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
   桶排序	O(n+k)	O(n^2)	O(n)	O(n+k)	稳定
   基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定

   3个nlog2n的算法要会手写

   十大经典排序算法

初级：O(n^2)

1. 冒泡排序 Bubble Sort

   嵌套循环，每次查看相邻元素，如果逆序，则交换（从后向前逐渐有序）

2. 选择排序 Selection Sort

   一般认为是冒泡排序的优化，因为只需要最值索引，不需要一直交换了。

   从前到后逐步构建有序序列，每次找最小值（arr[minIndex]），与已排好序部分（初始为空-1）的下一个位置交换

3. 插入排序 Insertion Sort

   从前到后逐步构建有序序列，对下一个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入(需要把已排序元素逐步向后挪位来提供空间)，具体实现一般用逐个比较后移，替代总是交换。由于可以在找到插入位置后提前终止循环，所以相对选择排序效率高一点，处理较为有序的数组时，效率甚至可高于nlogn

高级排序：O(nlog2n)

快速排序Quick Sort 分治

数组选取标杆pivot，将小元素放pivot左边，大元素放右，（此时，两子数组不一定有序，但值范围以pivot分隔）然后递归地对左右两边子数组继续快排；最终整个序列有序

正常数组prepend操作的时间复杂度是O(n)，但可以进行特殊优化到O(1)，方式是申请稍大一些的内存空间，然后在数组最开始预留一部分空间，然后prepend的操作则是把头下标前移一个位置即可。

重要 一个递归 一个partition(arr,l,r)

int partition(vector<int>& nums, int l, int r) {  
  swap(nums[rand() % (r - l +1) + l], nums[r]);//避免近乎有序数组的pivot始终集中于一端
  int v = nums[r];
  int i = l - 1;
  for (int j=l; j<r; j++) {
    if (nums[j] < v) {
      i++;
      swap(nums[i], nums[j]);//[l...i]<v
    }
  }

  swap(nums[i+1], nums[r]);
  return i+1;
}
void random_quicksort(vector<int>& nums, int l, int r) {
  if (l < r) {
    int p = partition(nums, l, r);
    random_quicksort(nums, l, p-1);
    random_quicksort(nums, p+1, r);
  }
}

//双路快速排序 区分<=  >=  避免大量重复元素集中于一端 退化成O(n^2)
int _partition2Ways(int arr[], int l, int r){
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    int v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        while( i <= r   && arr[i] < v )i ++;
        while( j >= l+1 && arr[j] > v )j --;
        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }
    swap( arr[l] , arr[j]);
    return j;
}

//3路快排  区分<  == > 避免2路的大量重复元素造成的交换,也能快速缩减递归区间
//[l+1...lt]<v  [lt+1...gt-1]=v  [i]=>[i+1]...  [gt...r]>v
void __quickSort3Ways(int arr[], int l, int r){
    // 对于小规模数组, 使用插入排序进行优化 不优化是 if(r<=l)return;
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    
	swap(arr[l], arr[l + rand() % (r - l + 1)]);
    
	int v = arr[l];
	int lt = l , gt = r+1;
	int i = l+1;
	while (i<gt) { //不主动缩小gt  gt全由左边交换过来 减少内部while个数
		 if (arr[i] < v) {
				swap(arr[i], arr[lt+1]);
				lt++; i++;
		 }else if(arr[i] > v) {				//< or >是先用[i]交换[lt+1...gt-1]两端之一
				swap(arr[i], arr[gt-1]);	//下一轮[i]仍需考察
				gt--;
		 }else {
				i++;
		 }
	}
	swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt-1);	//<v
    __quickSort3Ways(arr, gt, r);	//>v
}

归并排序 Merge Sort

1. 把长度为n的输入序列分为两个长度为n/2的子序列
2. 对这两个子序列分别采用归并排序
3. 将两个排好序的子序列合并成一个最终的排序序列

有点像快排的逆向，因为快排是先大块有序，再小块有序，最后整体有序

归并是递归地向下（固定地）二分为更小的子数组，再自底向上，将小数组合并为有序的大数组，最后整体有序

不同于快排随机选择标定点可能造成分割层级很高，两侧不平衡，归并是固定的二分

重要函数merge 如题目“合并两个有序链表”,在O(n)时间内可解决，对数组一般很难原地归并，需要开一个等长区间。记住3段式，3个while，先见森林，再见树木

void mergeSort(vector<int> &nums, int left, int right) {
	if (left >= right) return;
	
	int mid = left + (right - left) / 2;
	mergeSort(nums, left, mid);
	mergeSort(nums, mid+1, right);
	
	merge(nums, left, mid, right);
}
//[left ... mid] [mid+1 ... right]
void merge(vector<int> &nums, int left, int mid, int right) {
	vector<int> tmp(right-left+1);
	int i = left, j = mid+1, k = 0;
	
	while (i <= mid && j <= right) {	//在一方越过边界后退出，然后查看是否另一方还有元素
		tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
	}
	while (i <= mid)   tmp[k++] = nums[i++];
	while (j <= right) tmp[k++] = nums[j++];
	
	for (i = left, k = 0; i <= right;) nums[i++] = tmp[k++];//往回赋值
}

//----------------------一个for循环也比较明晰-------------------------------
//	对arr[l...mid] 和 arr[mid+1...r]归并
	vector<int> aux(r-l+1);
    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){
        if( i > mid ){  	// 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }
if 可以合并为  if(j>r || aux[i-l] < aux[j-l])使用成员大数组aux可以更简洁

归并：先排序左右子数组，然后合并两个有序子数组

快排：先调配出左右子数组，然后对左右子数组再分别排序（分治）

堆排序 Heap Sort

堆插入 O(logN),取最大/小值O(1)

1. 数组元素依次建立小顶堆（堆顶是最小值）
2. 依次取堆顶，并删除

特殊排序O(n)

• 计数排序（Counting Sort）

  要求数据必须是有确定范围的整数，将输入值转化为键存储在额外开辟的数组空间中；然后依次把计数>1的填充回原数组（因为数组索引必然是有序的，逐个取出也必然有序）

• 桶排序 （Bucket Sort）

  计数排序的升级，即不是一个值对应一个索引，而是一个值区间，对应一个桶，如两位数排序，桶0~9，以10位上的数字判定放入哪个桶，桶内再排序

  原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或以递归方式继续使用桶排序）

• 基数排序（Radix Sort）

  按照低位先排序，然后收集（收集就是赋值回原数组）；再按照高位排序，然后再收集；以此类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。好处是如对于0-99999的数，仍可以只用0~9，缺点就是只能对整形使用了。

逆序对（i<j且nums[i]>nums[j]）可以用归并排序，也可以用堆，

题目

逆序对，翻转对问题

逆序对的数量可以衡量数据的有序程度，如完全逆序，逆序对的数量是(n-1)+(n-2)+...+1=n(n-1)/2（所以一般用long long防止整形溢出）

1. 暴力法：枚举起点与后面逐个比较O(n^2)

2. 归并排序

3. 树状数组

一般用归并，归并的重点在于向上合并逐渐有序，每两个子数组合并时即可计数到逆序对，而题目逆序对是指总的逆序对个数 ，因此进行一遍归并排序，即可得到总的逆序对个数，而暴力法在求总逆序对个数时，也求了每个元素的逆序对，因此更慢。

全且在合并的时候，没有漏统计和重复统计，因此是mutual exclusive互斥的，completely exhaustive完全详尽的，所以是可行解。

int mergeSort(vector<int> nums,int l,int r){
	if(l>=r)return 0;
	int mid = l + (r-l)/2;
	int cnt = mergeSort(nums,l,mid)+mergeSort(nums,mid+1,r);
    for(int i = l,j=mid+1;i<=mid;i++){
        while(j<=r && nums[i]/2.0 >nums[j])j++; //避免溢出 也可以2LL*nums[j]
        cnt +=(j-mid-1);//不含j;因为是左右有序的，所以j不用重置
    }
    sort(nums.begin()+l,nums.begin()+r);
    return cnt;
}