位运算(下)

int 32位

判断某一行是否是0或1 (num & 1 << i) === 0 ? 0 : 1 32位数范围是(2^-31)~(231)-1 为何要减1？因为负数对应的需要取反+1，最小数为(2^-31) 100000...000,取反后加1，要进位，最后还是100000...000,而正数的最大值是0111111...1,就是该值 对于正数 第一位为符号位+,值为正常的2次幂 对于负数 第一位为符号位-,对应十进制数的值是取反+1 -1 对应二进制数

>>(带符号右移，用1补位) 和 >>>（不带符号右移动，用0补位）

5的负数是-5 也可以～5+1（取反加一来表示-5）

为什么负数的值要取反+1，因为作者想走一套加法逻辑，让逻辑更快更简单，10-5 === 10+（-5） === 10+（～5+1）

最小负数的负数还是他本身 0的负数溢出还是0

num%m 相当于 num&(m-1) 示例： 27%8 27的二进制是11011 模8后结果应该是 00011 和&7的结果相同

什么是算法

1.有具体的问题 2.有设计解决问题的具体流程 3.有评价处理流程的量化指标

算法的分类： 分类非常的多，但是有个特别的分类 1.明确知道怎么算的流程 2.明确知道怎么尝试的流程

求1！+2！+3！。。。+N! 选择，冒泡，插入排序

第二节课 数据结构

数据结构：1.是数据存储，组织数据的方式 2.精心选择的数据结构可以带来更高的运行和存储效率 3.数据结构是很多算法进行的载体

两种大的数据结构：连续结构（数组）和跳转结构（单链表，二叉树，图） 连续结构是在内存中开辟一段连续的内存空间，当进行查询时非常快 跳转结构，除了保存自己的数据外还要保存指向下一个节点的指针，便于寻址，不便于删增数据 单链表有一个指针，二叉树保存两个下级节点指针，图保存一堆下级节点指针，便于增删数据，不便于寻址

前缀和数组

求一个数组中从下标l到r的累加和的函数，并且这个函数被系统的调用次数很频繁

两种思想进行： 思想一：维护一个二维数组，求得每个l到r的累加和，用的时候直接sum[l][r]来获取，适用于当数量不多时候，并且频繁的时候

思想二： 使用前缀和模式，维护一个一维累加和数组preSum，每位都是数组0-n的累加和，当获取l-r的累加时只要preSum[l]-preSum[r-1]即可，当r为0时，只需preSum[l]即可

Math.random

等概率的获取[0,1)的数,为什么是可以等概率呢？因为在计算机中精度是有限的，而在数学中是无法实现的

获取[0,n)的区间 Math.random()*n

获取[0,n)的整数区间 Math.floor(Math.random()*n)

获取[m,n)的区间 Math.random()*(n-m)+m

任意x，x属于[0,1),[0,x)出现的概率从x变成x的平方 Math.max(Math.random(),Math.random())

解释：因为max只有两次都得到[0,x)成立时，才能得到最终结果，所以[0,x)出现的概率从x变成x的平方

任意x，x属于[0,1),[0,x)出现的概率从x变成x的立方 Math.max(Math.random(),Math.max(Math.random(),Math.random()))

解释下Math.min(Math.random(),Math.random())返回的概率

当两次都得不到的[0,x)的概率是(1-x)的平方,所以得到的概率是1-Math.pow((1-x),2)

黑盒f函数返回1～5整形5个随机数，如何利用f函数返回1～7的整形7个随机数 第一步：函数s1(),使1～5个随机数等概率返回0，1两个随机数，1～5个随机数遇到1、2返回0，4、5返回1，遇到3的情况下就重做 第二步：函数s2(),1～7的整形减1返回0～6的整形 第三步：函数s3(),拼接0～6的整形，用s1()<<2+s1()<<1+s1()，三个二进制，返回0～7的等概率随机数，如果遇到7的情况下就从新执行，最终返回0～6的整形 第四步：函数s4(),s3()+1返回1～7的随机整形

黑盒f函数返回的0，1两个数是不等概率的，如何变成等概率的返回0，1？ 假设返回0的概率是p，则返回1的概率是1-p f()<<1+f() 当返回00(Math.pow(p,2)->重做)，11(Math.pow(1-p,2)->重做)，01（p*(1-p)->返回0），10（p*(1-p)->返回1）

function y(){
    let ant = 0;
    do{
        ant = f();
    }while(ant===f()); //如果第一次执行和第二次执行的结果相同，则重新执行
    return ant;
}

对数器

调整bug使用，可以随意控制样本大小，生成随机样本，自己做比对的机器，遇到不确定的代码或者有问题的代码，不要自己干想，做一个对数器找到bug位置

第三节课

二分法

二分法，在有序数组中找到num docs/pages/算法/技巧/二分法/二分法.js

有序数组中找到>=num最左侧位置

有序数组中找到<=num最右侧位置

局部最小值问题(未练习)

时间复杂度

常熟性操作 O(1)

操作时间是固定时间的操作 比如说1+1和100万+100万 其底层都是两个32位数相加，无区别 比如说数组寻址arr[1]和arr[100万]是相同的

时间复杂度(最差情况)

例：冒泡排序 从0～N-1上对每个相邻的数进行比对，如果后面的比前面的大就交换，最终N-1位置为第一次比对后最大的数，然后从0～N-2上继续比对

所以复杂度是 N<第一次比对的次数>+(N-1)<第二次比对的次数>+(N-2)+...0 <--等差数列求和 最终演变为 a*Mat.pow(N,2)+bn+c ，由于算法只关心高阶项，所以时间复杂度是O(n的平方)

为何只保留最高阶？ 因为时间复杂度是衡量当数据量趋近于无穷大时，速度的变化曲线，当数据量很大时低阶项基本上影响很小

二分法的时间复杂度logN（可以反置想Math.pow(2,?)=总数量N）

常见的时间复杂度 O(1)<O(logN)<O(N)<O(N*logN)<O(Math.pow(N,2))<O(Math.pow(N,K))<O(Math.pow(2,N))<O(Math.pow(k,N))<O(N!)

动态数组（JAVA）

固定数组：长度固定不变的数组 动态数组：在固定数组中如果固定数组的长度不够用，则创建一个新的扩容一倍的数组，把老数组中的数据迁移进去

由于动态数组扩容后需要将原来的数据迁移进去，第一次迁移1个，第二次迁移2个，第三次迁移4个 所以迁移代价时1+2+4+8+16+...+N <--等比数列 最终时间复杂度是O(N)，某一步扩容（O(N)/N）均摊下来相当于O(1)

哈希表（key-value表）和有序表

js中的对象是基于哈希表结构的，而哈希表的查找时间复杂度为O(1)，所以很多人喜欢用对象来做映射，减少遍历循环 哈希表不管存储了多少数据，增删改查都是比较大的常数时间O(1) java中的哈希操作

Hash<String,String> map1 = new HasMap<>()
map1.put("姓名","小明") //增
map1.get("姓名") //查询
map1.containKey("姓名") //查询
map1.put("姓名","小红") //修改
map1.remove("姓名") //删除

key按值传递的哈希表，key存储的是数据本身 key按引用传递的哈希表，key存储的是引用的内存地址

有序表 O(logN) 有序表有哈希表相同的操作，但是比哈希表强大，会自动排好序

TreeMap<Integer,String> TreeMap1 = new TreeMap<>()
TreeMap1.put(3,"小明") //增
TreeMap1.put(1,"小红") //增
TreeMap1.put(5,"小绿") //增
TreeMap1.get(1) //查询
TreeMap1.containKey(1) //查询
TreeMap1.put(1,"小白") //修改
TreeMap1.remove(1) //删除

TreeMap1.firstKey() //获取最小key的值 ：小红
TreeMap1.lastKey() //获取最大key的值 ：小绿
TreeMap1.floorKey(5) //获取key<=5的值 ：小绿
TreeMap1.ceilKey(2) //获取key>=2的值 ：小明

第四节课

单链表和双列表

单链表：值+一条next指针 双链表：值+一条next指针+一条last指针

经典题目： 给定一个单链表的头head,完成链表逆序调整 给定一个双链表的头head,完成链表逆序调整

队列和栈都是我们想要实现的功能，并不是基础的数据结构 用单链表实现队列功能（先进先出） 实现 isEmpty()<是否为空> size()<有多少节点> offer()<加入节点> poll()<弹出节点> peek()<此时要弹出的节点是什么>

用单链表实现栈功能（后进先出） 实现 isEmpty()<是否为空> size()<有多少节点> push()<加入节点> pop()<弹出节点>

用双链表结构实现双端队列 实现 shift() unshift() push() pop() 且每次操作都是O(1)

链表问题面试考察细心度，如果没过，会降低印象分

题1:给定一个单链表的head节点和一个正数k，实现k个节点的小组内部逆序调整，如果最后一个组不够k个，则不进行调整

题2:将两个链表相加

题3:给定两个有序列表的头节点head，返回合并后的大链表，要求依然有序

第五节

位图 bitmap

假如说要存储从0到31的32个数，如果用hashSet存储，在java中一个int占用4bit,共要占用 32*4 = 128bit 如果用位图，一个int代表32位（4bit），则可以表示32个数，仅仅用4bit便可解决

如果想表示更大的数比如说0～1023，我们可以准备一个整形的数组，用1024/32 = 32，我们分配一个32长度的整形数组，便可表示

位图的功能

位图可以做出一个集合，如果数字的范围是确定的，就可以用位图来收集数据，来表示数字是否存在

位图的好处

可以极大的压缩空间

位图的实现

用位运算实现 + - * /

异或运算(^)<相同是0，不同为1>，就是无进位相加 0110110 ^ 1110111 —————————— 1000001

a+b=a^b+a&b<<1

解释 a+b = a和b的无进位相加 + a和b的进位信息 46+20 46=》0101110 20=》0010100 a^b： 0101110 ^ 0010100 —————————— 0111010

0101110

& 0010100 —————————— 0000100 <<1 0001000

a+b=a^b+a&b<<1 假设a1 = a^b b1 = a&b<<1 a+b = a1^b1+a1&b1<<1 假设a2 = a1^b1 b2 = a1&b1<<1 a+b = a1^b1+a1&b1<<1 = a2^b2+a2&b2<<1 直到a和b的进位信息为0时，得到最终结果

代码为...

/

第六节

比较器

arr.sort(function(a,b){ //如果返回负数，则a排在前 //如果返回正数，则b排在前 //如果返回0，则不动 if(a>b){ return 1 }else if(a < b){ return -1 }else{ return 0 } })

合并k个升序链表

二叉树的基本

面对所有的树的算法，一定要看成左子树，右子树操作，然后再左子树，右子树操作

先序 头左右，先打印头节点，再打印所有的左树，再次打印所有的右树，依次类推 中序 左头右 后序 左右头

先序中序后序（以头的位置区分记忆）

实现先中后需要递归序（递归重点是宏观调度）

function f(Node){
    if(!Node.value) return null;
    //console.log("打印放在此处为先序",Node.value)
    f(Node.left)
     //console.log("打印放在此处为中序",Node.value)
    f(Node.right)
     //console.log("打印放在此处为后序",Node.value)
}

递归序是指走过的全部过程 假如说我们有个二叉树，头节点是1，左树是2，右树是3，则递归序为：1 2 2 2 1 3 3 3 1，任何节点都会到达3次 所以，如果在访问第一次到达节点时便是先序，第二次到达时中序，第三次到达是后序

练习： 1.有两颗独立树，一个是p,一个是q，如果p和q的结构完全相同，称之为相等 2.判断一颗树是否是镜面树 3.返回一颗树的最大深度 4.用先序数组和中序数组重建一颗树

第七节

实现广度优先遍历

用队列实现， 1）拿出当前的size 2）弹出节点，并插入节点的子节点

第八节

归并排序

递归版本和非递归版本

快速排序

单端快排，双端快排，非递归版本