算法通关面试40讲

如何学好数据结构？
- 精通一个领域
  - 切碎知识点
  - 刻意练习：
    - 练习缺陷，弱点地方（练字）----不爽，枯燥，不舒服的地方----坚持，心里没底的　　
  - 反馈　　　　
    - 主动反馈：看看高手怎么写代码的（自己去找）
    - 被动反馈：高手教你（别人教你）
时间复杂度和空间复杂度
- 斐波拉契数量o(2^n)----用递归很明显不是最好的
- 主定律：二分查找。二叉树变量，排序，快排
LeetCode
- 寻求反馈
数组
- 连续的存储区域　　
- 插入,删除O（n）,查询O(1)
链表--改善数组的插入和删除的时间复杂度
- 插入和删除O(1),查询O(n)
- 双链表
- 面试题：反转链表
- 面试题：两两反转
- 面试题：判断是否有环
  - 2个指针，1个一次走一步，1个一次走两步，相遇就有环---龟兔赛跑法
  - set 判重复　　　
栈--先入后出
- 插入和删除O(1),查找O(n)
- 面试题：给定一个只包含大中小括号的字符串，判断括号是否合法
  - a.左括号---push
  - b.右括号---peek栈顶--pop元素
  - c.堆栈必须是空的　　
  - 时间O(n),空间O（n）
- 面试题：只用栈实现队列
  - 输入栈：push
  - 输出栈:pop,peek　　
  - 倒腾顺序　
- 面试题：只用队列实现栈
  - 与上面相反，也是两个队列倒腾顺序　　　　　　　　
队列---先入先出　
- 插入和删除O(1),查找O(n)
- 优先队列
  - 堆实现
    - 二叉最小堆　　
    - 面试题：实时判断数据流中第K大的元素
      - 1.保存K个最大值
      - 优先队列--小顶堆保存K个数据，比他小就弃了，比他大就加入堆弃掉它
    - 面试题：滑动窗口最大值
      - 优先队列--大顶堆--维护堆，结果是堆顶元素
      - 双端队列---最左边的最大，左边比他小的全部删除，右边比他小的保留　　
  - 二叉搜索树实现　　
映射map---字典
- 解决哈希碰撞
- 哈希实现map---无序
  - python本身是hashmap　　
- 树实现map---有序　　
- 面试题：有效字母异位词
  - ①---排序--遍历O（nlogn）
  - ②---map计字母的出现次数---比较map----O（n）　　
- 面试题：两数之和　
  - ①--2个循环暴力破解
  - ②--set解决---枚举x,查询target-x是否存在set--每次删除x---O(n)
- 面试题：三数之和
  - ①---3层循环暴力破解
  - ②---暴力循环破解2次，set查询1次　
  - ③---排序---枚举A，去掉A变成两数之和查找---其实③=②　　
  - ④---排序--枚举A，用两个指针夹逼　
集合set
- 哈希或树实现　　　
树和图
- 链表如果存在两个next就变成了二叉树
- 如果树的子节点能指回去，指向父节点或其他节点就变成了图
- 链表是特殊化的树，树是特殊化的图　　
- 二叉搜索树--有序二叉树，左子树小于根节点，右子树大于根节点
  - 防止退化成链表--只有左子树的情况
    - Java，c++实现的二叉树都是红黑树
- 面试题：判断一个树是否是二叉排序树
  - ①---中序遍历---升序就是二叉排序树--每次保留前继节点即可
  - ②---递归查询---左子树最大值，右子树最小值，跟根节点比较
- 面试题：最小公共祖先
  - 1.找父亲节点，找到最早出现重合的父亲结点
  - 2.找到节点1路径1，找到节点2的路径2，然后找最迟重合的父节点　　　
- 二叉树的遍历
  - 前中后序遍历
递归--循环
分治
- 面试题：计算x的N次方
  - ①--调库函数
  - ②--傻乘
  - ③---分一半--只需要计算一半--同理　
    - 非递归
- 面试题：求众数
  - ①---循环枚举+循环计算
  - ②---map,元素：count
  - ③--sort---找重复的次数　　　
贪心算法
- 在问题求解时，总是做出在当前看来最好的选择
- 问题能分成子问题来解决，子问题的最优解能递推到全局问题的最优解
- 贪心问题解决不了，就用动态规划解决---多找几种解
- 面试题：买卖股票的最佳时机
  - ①--深度优先的搜索---
  - ②---贪心算法--后一天比前一天高就买进，第二天卖出
  - ③---动态规划--0股和1股都记录下来---解决问题比贪心算法严谨
广度优先搜索：在状态集中寻找特定节点
- 增加一个是否已经访问的集合
深度优先算法：
- 迷宫的走法
- 面试题：二叉树的层次遍历　
  - ①---广度优先--level加入queue
  - ②---深度优先--记住level
- 面试题：二叉树的最大深度和最小深度　
  - 广度优先---记住深度--最后的深度就是最大深度--第一次到达的叶子节点就是最小深度
  - 深度优先---看是否是叶子节点，根据叶子节点的更新max和min　　
- 面试题：生成括号
  - ①---数学归纳法
  - ②---递归搜索，深度优先搜索，填格子，在判断是否合法
  - ③---改进--加入剪枝，局部不合法，左右都只能放三个　
剪枝：搜索中用到的优化策略
- 可能没办法覆盖到全部可能，根据优胜劣汰去淘汰不可能的分支
- 面试题：N皇后问题　　
  - ①--深度优先DFS--每层枚举Q的位置--枚举第二层的位置，2次循环
    - 暴力
    - 剪枝--数组缓存--已经处理过的进行标记x+y是一个常数(撇)，x-y是一个常数(啦)进行剪枝---空间换时间
- 面试题：数独游戏
  - ①--枚举1-9，循环
  - ②--剪枝--枚举选项比较少的空格--预处理找出空格子里的可选数，从可选数从少到多进行循环
  - ③--跳舞链表
二分查找：
- 面试题：求平方根
  - ①---枚举逼近+二分查找
  - ②---牛顿迭代法---求切线
字典树
- 用边存，叶子节点是单词--跟你你输入的单词，查找以你输入单词为前缀的所有词
- 面试题：实现字典树
- 面试题：单词搜索
  - ①--深度优先搜索DFS
  - ②--形成字典树--然后找出所有的候选词--得到结果　
  - 　　
  - 　　　
位运算
- 面试题：为1的数
  - 　　　　
  - ①---%2---count++
  - ②---x&(x-1)---消掉最后的1---count++　
    - 　　　　
- 面试题：是不是2的指数
  - ①--%2
  - ②--log2
  - ③--x!=0 x&x-1=0
- 面试题：N皇后
动态规划---动态递推
- 　　　　　　　
- 记忆化：加一个缓存
- 从小向大递推　
- 面试题：爬楼梯
  - ①--回溯
  - ②--动态规划　
- 面试题：三角形最小路径
  - ①--动态规划--递推
  - ②--回溯
- 面试题：乘积最大子序列
  - 必须连在一起
  - ①：暴力求解
  - ②：动态规划递推
- 面试题：最长上升子序列
  - ①“---暴力求解
  - ②---到第i个元素的最大上升子序列。然后以此递推---动态规划
- 面试题：零钱兑换
  - 　
  - 跟上台阶一样
- 面试题：编辑距离
  - 　　　　
  - ①---动态规划--状态前I个字符，替换前J个字符　　　　
并查集
- 　　　
- 面试题：岛屿的个数
  - 1.染色，遍历节点找出1，染色其周围的节点变成0　　
  -

课程总结

　　　　　　
模板
- 递归模板
  - 　　　　
- DFS--递归写法
  - 　　　　
- BFS
  - 　　　　
- 二分查找
  - 　　　　
- 动态规划模板
  - 　　　
- 位运算
  - 　　　
- 练习
  - 　　
- 面试
  - 　　　　
- 面试--探讨和交流，别当做是老师　　
最后：三分学，七分练