payload: {"action":"created","issue":{"url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/458","repository_url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01","labels_url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/458/labels{/name}","comments_url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/458/comments","events_url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/458/events","html_url":"https://github.com/algorithm005-class01/algorithm005-class01/issues/458","id":541461814,"node_id":"MDU6SXNzdWU1NDE0NjE4MTQ=","number":458,"title":"【0144_week 02】周总结","user":{"login":"manajay","id":13750333,"node_id":"MDQ6VXNlcjEzNzUwMzMz","avatar_url":"https://avatars3.githubusercontent.com/u/13750333?v=4","gravatar_id":"","url":"https://api.github.com/users/manajay","html_url":"https://github.com/manajay","followers_url":"https://api.github.com/users/manajay/followers","following_url":"https://api.github.com/users/manajay/following{/other_user}","gists_url":"https://api.github.com/users/manajay/gists{/gist_id}","starred_url":"https://api.github.com/users/manajay/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/manajay/subscriptions","organizations_url":"https://api.github.com/users/manajay/orgs","repos_url":"https://api.github.com/users/manajay/repos","events_url":"https://api.github.com/users/manajay/events{/privacy}","received_events_url":"https://api.github.com/users/manajay/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2019-12-22T15:03:30Z","updated_at":"2019-12-22T15:13:42Z","closed_at":null,"author_association":"CONTRIBUTOR","body":"# Week 02 总结\r\n\r\n## 数据结构\r\n\r\n### 哈希表\r\n\r\n基于数组实现的快速查找数据结构, 这里说的基于数组是因为\r\n1. 主体存储使用的是数组实现, 不包含冲突解决的数据结构\r\n2. 无论哪种 hash 函数 都是要生成一个 int 索引值, 这样 取模 才能换算成索引, 才能根据索引定位值是实现 O(1) 的时间复杂度, 其他数据结构实现不了. \r\n\r\n哈希表的关键点:\r\n- 数组\r\n- hash 函数: 做 key 到 散列值 (然后处理成索引值)的 映射关系\r\n    - 散列值 是非负整数, 只有符合这个条件才能取模到索引\r\n    - 如果 key1 = key2 那么 hash(key1) 一定等于 hash(key2)\r\n    - 如果 key1 != key2 , 理想情况下, 我们要的是  hash(key1) !=  hash(key2), 但是因为 hash 冲突,导致有 hash(key1) 可能等于  hash(key2) 的情况\r\n- 冲突解决的方式\r\n    - 装载因子（load factor） 特别重要, 关系着冲突的概率, 性能的好坏\r\n        - Java中 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小\r\n    - 开放寻址 \r\n        - hash 计算后, 冲突则偏移索引再存储; 查找时 对比真正的 key \r\n        - 线性探测（Linear Probing）是最简单的一种; 这里有个问题, 我们在删除元素的时候, 不能简单的删除(因为可能是我们后删除的冲突元素, 防止查找为空,实际元素存在另一个偏移位置的问题), 怎么做的, 标记为删除, 查找时,遇到标记删除继续查找. \r\n        - 二次探测（Quadratic probing)\r\n        - 双重散列（Double hashing)\r\n        - 使用场景: 当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因\r\n    - 链表法\r\n        - 将冲突的元素保存为链表结构, 查询链表 对比 key; 优化查询效率可以使用红黑树, 即便退化也是 O(logn), 能抗击散列攻击\r\n        - 优点: 链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好\r\n        - 应用场景: 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表.\r\n        - HashMap 底层采用链表法来解决冲突, 在 JDK1.8 版本中，为了对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树\r\n\r\n冲突的原因解释: 可以用鸽巢理论或者抽屉理论来解释. \r\n最简单的解释方式是 用无限小的信息表示无限大的信息, 肯定是解释不了的. \r\n\r\n维护散列表性能的有效方式是适时降低装载因子, 动态扩容, 降低冲突概率. \r\n这会带来两个问题, ① 扩容会导致数据搬迁, 如果原本数量过大, 那么扩容的过程到使得该插入操作过满, 用户体验差, 也就是低效扩容, 解决这个问题是不一次性搬迁数据, 而是扩容一部分, 将老数据一点一点搬迁到新开辟空间, 这样查询虽然比不扩容要差一点(因为需要先查新空间再查旧空间), 但是比全部扩容要好太多. ② 扩容后发现大部分操作是删除操作, 有大量空间被浪费了, 如果内存紧张, 可以再缩容. \r\n\r\n\r\n问题1 关于 O(1) 经常会有一个设计题: \r\n支持O(1)时间增加，删除和随机选择操作的数据结构\r\n\r\n题解:\r\n对于 O(1)时间增加，删除 ,可以用 哈希表实现, 对于 随机选择, 可以用数组实现, 那么这种数据结构就可以用 **哈希表和数组** 组合实现\r\n\r\n问题2 工业级散列函数经常要解决的一个问题是: 处理散列攻击, 这种攻击是将一些hash值一致的数据提交服务器,导致散列退化, 查询效率降低到O(n), 使得服务器访问性能下降,从而达到DoS的目的\r\n解决方式:\r\n1. 散列函数不能太复杂, 降低运算量\r\n2. 散列值要尽量随机且均匀分布\r\n\r\n**Java** 之 `HashMap`\r\n\r\n```\r\nint hash(Object key) {\r\n    int h = key.hashCode()；\r\n    return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小\r\n}\r\n不同的对象其hashCode的 的计算方式不同 , 下面是 String的 \r\n\r\npublic int hashCode() {\r\n  int var1 = this.hash;\r\n  if(var1 == 0 && this.value.length > 0) {\r\n    char[] var2 = this.value;\r\n    for(int var3 = 0; var3 < this.value.length; ++var3) {\r\n      var1 = 31 * var1 + var2[var3];\r\n    }\r\n    this.hash = var1;\r\n  }\r\n  return var1;\r\n}\r\n```\r\n\r\n工业级散列表的要求:\r\n1. 快速查询, 增加, 删除\r\n2. 内存占用合理\r\n3. 性能稳定!!, 极端情况下, 也不会退化到不可接受的底部, 比如链表法优化红黑树\r\n\r\n设计时:\r\n1. 合适的散列函数\r\n2. 合适的装载因子, 以及动态扩容策略\r\n3. 合适的冲突解决方法\r\n\r\n开发中, 常用LRU 缓存功能, 是高频设计, 需要注意实现\r\n一般用 散列表 查找值是否存在, 用双向链表存储真正的数据\r\n\r\n散列函数与哈希函数\r\n\r\n### 树\r\n\r\n**树是一种非线性表**, 因为在某个节点分叉了, 但是注意树与图的区别, 树是无环的. \r\n根节点: 没有父节点的节点 \r\n叶子节点: 没有子节点的节点. \r\n深度: 根节点到叶子节点最大的层数 + 1, 起点是0 , 层数起点是 1\r\n高度: 深度相反的概念\r\n \r\n### 二叉树\r\n\r\n最简单的一种树, 子节点最多有两个, 左节点与右节点\r\n特殊的二叉树\r\n- 满二叉树: 除了叶子节点, 所有的节点都有左节点与右节点\r\n- 完全二叉树: 叶子节点都在最底下两层，最后一层的**叶子节点**都**靠左排列**，并且除了最后一层，其他层的节点个数都要达到**最大**. \r\n    - 它的特殊性在于: **顺序存储法**是`最节省内存`的方式, 也就是对于节点 i, `2*i` 是其左节点存储的位置, `2*i + 1` 是其右节点存储的问题. 数组存储的顺序类似节点层级遍历的顺序\r\n    - 堆其实就是一个完全二叉树,常用数组存储. 遇到类似堆的算法,就可以用数组构建\r\n\r\n树的遍历\r\n- 前序: 根左右 ; 算法: 递归 O(n)-O(n), 颜色标记, 栈\r\n- 中序: 左根右 ; 算法: 递归 O(n)-O(n), 颜色标记, 栈\r\n- 后续: 左右根 ; 算法: 递归 O(n)-O(n), 颜色标记, 栈 其中后序和前序基本一致, 直接用前序然后reverse就可\r\n- 层级: 按照树的level 遍历; 算法: queue 先进先出 \r\n\r\n### 二叉搜索树\r\n\r\n二叉搜索树的诞生原因: \r\n对于哈希表,能够快速的查找元素,删除元素, 插入元素. 但是对于近似值查找不太支持, **动态数据集合**的快速查找,删除与插入不太支持. \r\n\r\n先说二叉搜索树: 在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值. 算法题递归验证一个二叉搜索树\r\n\r\n**查找** : 从根节点出发, 根据特性比较值, 递归进行\r\n**插入** : 类似查找\r\n**删除** : 难度最大\r\n\r\n**特性** \r\n- 有序性: 中序遍历可以输出 二叉搜索树的有序序列, 经常会使用\r\n- 快速查找最大节点, 最小节点\r\n- 退化问题: 只有左子树或者右子树,可能退化到O(n)\r\n    - 为了避免退化, 也就有了平衡二叉树 (红黑树是其中一种), 其查找删除插入的复杂度为 O(logn) 这点其稳定性要强于散列表\r\n- 高度: 完全二叉树的高度小于等于 log2n\r\n\r\n重复二叉搜索树:\r\n- 实现一: 相同节点类比冲突解决方式, 使用链表存储\r\n- 实现二: 相同节点放在右子树 注意删除时遍历右子树的问题\r\n\r\n## 算法\r\n\r\n### 递归\r\n\r\n递归的三个条件\r\n1. 有重复子问题\r\n2. 子问题除了在规模上不同,求解思路一致\r\n3. 存在递归截止条件\r\n\r\n写代码的关键: 写出递归公式, 找到终止条件\r\n\r\n```\r\nf(n){\r\n    // 终止条件\r\n    if (n == 条件) return;\r\n    // 当前处理逻辑\r\n    ...\r\n    // 小规模后的递归调用\r\n    f(小于n的值) \r\n}\r\n```\r\n\r\n递归的误区:\r\n模拟机器去执行递归代码, 这样经常会懵逼卡死. 最后的办法是, 假设子问题已经解决 , 仅仅关心本层的问题 和 本层与子问题的关系即可. \r\n\r\n递归的问题:\r\n- 递归容易导致栈溢出, 因为函数调用需要程序压栈, 如果递归深度过大,容易超过栈的内存大小. \r\n    - 解决的办法: \r\n    - 限制深度, 返回次优解 \r\n    - 编写尾递归, 重用栈帧. 其实一般编译器会优化递归代码 \r\n    - 改写为非递归比如迭代法, 但是难度会大很多,  仅仅在需要优化的时候进行\r\n- 递归容易重复计算, 比如斐波那契或者爬楼梯\r\n\r\n递归的应用\r\n- DFS 深度优先搜索\r\n- 树的前中后序遍历\r\n- 函数调用栈维护\r\n\r\n### 树的递归\r\n\r\n```\r\n\r\nvoid preOrder(Node* root) {\r\n  if (root == null) return;\r\n  print root // 此处为伪代码，表示打印root节点\r\n  preOrder(root->left);\r\n  preOrder(root->right);\r\n}\r\n\r\nvoid inOrder(Node* root) {\r\n  if (root == null) return;\r\n  inOrder(root->left);\r\n  print root // 此处为伪代码，表示打印root节点\r\n  inOrder(root->right);\r\n}\r\n\r\nvoid postOrder(Node* root) {\r\n  if (root == null) return;\r\n  postOrder(root->left);\r\n  postOrder(root->right);\r\n  print root // 此处为伪代码，表示打印root节点\r\n}\r\n```\r\n\r\n\r\n- [二叉树的中序遍历 - 迭代法](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/)\r\n- [颜色标记法-一种通用且简明的树遍历方法](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/)\r\n\r\n### 最小公共祖先节点\r\n\r\n[淘宝面试题：有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先.有什么好算法呢？](https://www.zhihu.com/question/19957473)\r\n\r\n- Tarjan\r\n- 倍增\r\n- RMQ\r\n    - 欧拉序列\r\n    - [RMQ问题（ST表算法）](https://www.dazhuanlan.com/2019/08/23/5d5f57af7214c/)\r\n    - [一个RMQ问题的快速算法，以及区间众数](https://zhuanlan.zhihu.com/p/79423299)\r\n    - [Range Minimum Query (Square Root Decomposition and Sparse Table)](https://www.geeksforgeeks.org/range-minimum-query-for-static-array/)\r\n    - [RMQ和LCA在线算法](http://crisjk.site/2017/07/26/RMQ&LCA/)\r\n\r\n> 预处理\r\n\r\n- 设`a[i]`表示需要求区间最值的数列，`f[i][j]`表死从第i个数起连续`2^j`个数中的最大值。\r\n- 则很容易得到状态转移方程：``` f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]) ```\r\n\r\n根据动态迁移方程, 自底向上求解\r\n\r\n```\r\n 1 void rmq(int n)    //n为a序列的长度\r\n 2 {\r\n 3     for(int j=1;j<=20;j++)   //注意是外层循环j嵌套内层i循环\r\n 4     for(int i=1;i<=n;i++)\r\n 5     if(i+(1<<(j-1))-1<=n)\r\n 6     {\r\n 7         smin[i][j]=min(smin[i][j-1],smin[i+(1<<(j-1))][j-1]); //更新最小值\r\n 8         smax[i][j]=max(smax[i][j-1],smax[i+(1<<(j-1))][j-1]);//更新最大值\r\n 9     }\r\n10 }\r\n```\r\n\r\n## 思考题\r\n\r\n### 树的面试题解法一般都是递归，为什么？\r\n\r\n1. 递归写法简单直接\r\n2. 递归一般有编译器优化, 性能不一定差\r\n3. 易于维护, 工业应用稳定, 不会出现太大问题. "},"comment":{"url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/comments/568271552","html_url":"https://github.com/algorithm005-class01/algorithm005-class01/issues/458#issuecomment-568271552","issue_url":"https://api.github.com/repos/algorithm005-class01/algorithm005-class01/issues/458","id":568271552,"node_id":"MDEyOklzc3VlQ29tbWVudDU2ODI3MTU1Mg==","user":{"login":"javaxiaomangren","id":2129048,"node_id":"MDQ6VXNlcjIxMjkwNDg=","avatar_url":"https://avatars2.githubusercontent.com/u/2129048?v=4","gravatar_id":"","url":"https://api.github.com/users/javaxiaomangren","html_url":"https://github.com/javaxiaomangren","followers_url":"https://api.github.com/users/javaxiaomangren/followers","following_url":"https://api.github.com/users/javaxiaomangren/following{/other_user}","gists_url":"https://api.github.com/users/javaxiaomangren/gists{/gist_id}","starred_url":"https://api.github.com/users/javaxiaomangren/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/javaxiaomangren/subscriptions","organizations_url":"https://api.github.com/users/javaxiaomangren/orgs","repos_url":"https://api.github.com/users/javaxiaomangren/repos","events_url":"https://api.github.com/users/javaxiaomangren/events{/privacy}","received_events_url":"https://api.github.com/users/javaxiaomangren/received_events","type":"User","site_admin":false},"created_at":"2019-12-22T15:13:42Z","updated_at":"2019-12-22T15:13:42Z","author_association":"NONE","body":"总结很棒👍"}}
other: {"actor":{"display_login":"javaxiaomangren"}}