Open MiaoRain opened 4 years ago
大神笔记 https://github.com/algorithm006-class01/algorithm006-class01/issues/224#issue-566279035
哈希map和set map和set都分成两种，一种是有顺序，一种没有顺序。
对于有序map，内部元素通过key进行排序(a specific strict weak ordering criterion). 内部实现，二叉搜索树
对于无�序map(unordered_map)，访问速度快于有序map. 内部元素根据他们的哈希值组织成buckets（桶），可以直接根据key进行访问。
map容器重载了操作符[]和=, 使得键值对的设置更加符合直觉，也更加方便。
set和map类似，只不过只存放key，不存放value。
调用例子
std::unordered_map<string, string> hash_table; //定义 hash_table["张三"] = "年轻司机"; //设置key-value hash_table["李四"] = "老司机"; //设置key-value hash_table["张三"] ; //访问已有的结果 hash_table["王五"] ; //访问不存在的元素，会新建一个元素，内容为空 hash_table.count("张三"); //计数key hash_table.find("张三") ;// 查找，如果找不到则返回hash_table.end() 242:有效的字母异位词 注意审题，例如这道题目
什么异位词 是否大小写敏感 可能的解题方法
暴力求解1，排序，判断是否相同 暴力求解2，哈希表，比较每个字母出现频次 类似的题目:49题
1:两数之和 最大误区: 题目只做一遍
好习惯: 收藏比较好的代码，整理成代码库
树 树的结构用于满足人类需求，例如递归树，状态树，决策树
二叉树的遍历，前序，中序，后序，相对于根的位置
树的循环比较麻烦，递归是更好的实现。
二叉搜索树，空树也是
左子树的所有节点都小于根 右子树的所有节点都大于根 依次类推，也就是重复性来源 二叉搜索树 Demo，https://visualgo.net/zh/bst
常见操作
查询: O(log n) 插入: O(log n) 删除: O(log n): 如果是叶子节点，直接删除，如果不是，则找第一个大于待删除节点来替换掉要删除的节点。 最差的情况，退换成单链表
必须记住的代码
def preOrder(self, root): if root: self.traverse_path.append(root.val) self.preOrder(root.left) self.preOrder(root.right)
def inOrder(self, root): if root: self.inOrder(root.left) self.traverse_path(root.val) self.inOrder(root.right)
def postOrder(self, root): if root: self.postOrder(root.left) self.postOrder(root.right) self.traverse_path(root.val) 题目 一个误区: 递归本身不存在效率低，效率差的问题，只要你的程序本身没有写残。递归相对于非递归，就在于递归需要额外开栈，因此在深度非常高的情况下，可能会差一些。但是目前编译器存在尾递归优化，可以认为递归和循环一样的效率。
题目用遍历做都不难，只要理解中序，前序，和后续的含义，也就是前中后是相对于根节点。
递归 递归本质就是循环，通过函数体来循环。
根本原因是 汇编没有循环嵌套一说， 比较常见的情况，就是不断跳到之前写的函数命令，循环汇编之后会递归其实差不多。
一层一层下降落，然后一层一层回来
函数参数和全局参数会在递归过程中会发生变化
代码模版
public void recur(int level, int param) {
// terminator if (level > MAX_LEVEL) { // process result return; }
// process current logic process(level, param);
// drill down recur( level: level + 1, newParam);
// restore current status 核心部分
终止条件 当前层逻辑 下探下一层 (可选)清理当前环境 思维要点:
不要人肉递归， 不要尝试绘制递归树 找到最近最简的方法，将其拆解成可重复解决的问题（最近子问题） 数学归纳法思维 爬楼梯 在第三层的时候，不再是从头思考，而是从已有的结果出发，也就是从第二层和第三层出发
括号的生成 先思考参数应该如何设置，自顶向下编程
然后无脑写模版
第一种思路，先把所有可能都输出了，然后在return的时候，过滤结果
第二种思路，在中间过程中就把不合法的删除，规则是右括号小于等于左括号
为什么7行代码可以解决复杂的问题，因为人脑老是习惯暴力递归，而没有思考重复性。
验证二叉搜索树 方法1: 根据二叉搜索树定义
方法2: 中序遍历，输出有序数组
二叉树最大深度和最小深度 关键是叶子节点定义，最大深度肯定是探到底，因此最后的节点必然是叶子结点。但是对于最小深度，并不是最前面的节点就算是最小深度的节点了。比如下面这颗树，虽然9和20都算出来是2，但是20不符合要求，9才是需要的节点。
3
/ \ 9 20 / 15 因此都为空，返回+1，一个为空一个不为空，发挥不为空节点后续+1；
其他 Cpp的新的for循环: for( auto str:strs ).
新建容器vector的一种方法vect or vec(1, str), 结果是长度为1，默认为str的vector
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，
大神笔记 https://github.com/algorithm006-class01/algorithm006-class01/issues/224#issue-566279035
哈希map和set map和set都分成两种，一种是有顺序，一种没有顺序。
对于有序map，内部元素通过key进行排序(a specific strict weak ordering criterion). 内部实现，二叉搜索树
对于无�序map(unordered_map)，访问速度快于有序map. 内部元素根据他们的哈希值组织成buckets（桶），可以直接根据key进行访问。
map容器重载了操作符[]和=, 使得键值对的设置更加符合直觉，也更加方便。
set和map类似，只不过只存放key，不存放value。
调用例子
std::unordered_map<string, string> hash_table; //定义 hash_table["张三"] = "年轻司机"; //设置key-value hash_table["李四"] = "老司机"; //设置key-value hash_table["张三"] ; //访问已有的结果 hash_table["王五"] ; //访问不存在的元素，会新建一个元素，内容为空 hash_table.count("张三"); //计数key hash_table.find("张三") ;// 查找，如果找不到则返回hash_table.end() 242:有效的字母异位词 注意审题，例如这道题目
什么异位词 是否大小写敏感 可能的解题方法
暴力求解1，排序，判断是否相同 暴力求解2，哈希表，比较每个字母出现频次 类似的题目:49题
1:两数之和 最大误区: 题目只做一遍
好习惯: 收藏比较好的代码，整理成代码库
树 树的结构用于满足人类需求，例如递归树，状态树，决策树
二叉树的遍历，前序，中序，后序，相对于根的位置
树的循环比较麻烦，递归是更好的实现。
二叉搜索树，空树也是
左子树的所有节点都小于根 右子树的所有节点都大于根 依次类推，也就是重复性来源 二叉搜索树 Demo，https://visualgo.net/zh/bst
常见操作
查询: O(log n) 插入: O(log n) 删除: O(log n): 如果是叶子节点，直接删除，如果不是，则找第一个大于待删除节点来替换掉要删除的节点。 最差的情况，退换成单链表
必须记住的代码
def preOrder(self, root): if root: self.traverse_path.append(root.val) self.preOrder(root.left) self.preOrder(root.right)
def inOrder(self, root): if root: self.inOrder(root.left) self.traverse_path(root.val) self.inOrder(root.right)
def postOrder(self, root): if root: self.postOrder(root.left) self.postOrder(root.right) self.traverse_path(root.val) 题目 一个误区: 递归本身不存在效率低，效率差的问题，只要你的程序本身没有写残。递归相对于非递归，就在于递归需要额外开栈，因此在深度非常高的情况下，可能会差一些。但是目前编译器存在尾递归优化，可以认为递归和循环一样的效率。
题目用遍历做都不难，只要理解中序，前序，和后续的含义，也就是前中后是相对于根节点。
递归 递归本质就是循环，通过函数体来循环。
根本原因是 汇编没有循环嵌套一说， 比较常见的情况，就是不断跳到之前写的函数命令，循环汇编之后会递归其实差不多。
一层一层下降落，然后一层一层回来
函数参数和全局参数会在递归过程中会发生变化
代码模版
public void recur(int level, int param) {
// terminator if (level > MAX_LEVEL) { // process result return; }
// process current logic process(level, param);
// drill down recur( level: level + 1, newParam);
// restore current status 核心部分
终止条件 当前层逻辑 下探下一层 (可选)清理当前环境 思维要点:
不要人肉递归， 不要尝试绘制递归树 找到最近最简的方法，将其拆解成可重复解决的问题（最近子问题） 数学归纳法思维 爬楼梯 在第三层的时候，不再是从头思考，而是从已有的结果出发，也就是从第二层和第三层出发
括号的生成 先思考参数应该如何设置，自顶向下编程
然后无脑写模版
第一种思路，先把所有可能都输出了，然后在return的时候，过滤结果
第二种思路，在中间过程中就把不合法的删除，规则是右括号小于等于左括号
为什么7行代码可以解决复杂的问题，因为人脑老是习惯暴力递归，而没有思考重复性。
验证二叉搜索树 方法1: 根据二叉搜索树定义
方法2: 中序遍历，输出有序数组
二叉树最大深度和最小深度 关键是叶子节点定义，最大深度肯定是探到底，因此最后的节点必然是叶子结点。但是对于最小深度，并不是最前面的节点就算是最小深度的节点了。比如下面这颗树，虽然9和20都算出来是2，但是20不符合要求，9才是需要的节点。
/ \ 9 20 / 15 因此都为空，返回+1，一个为空一个不为空，发挥不为空节点后续+1；
其他 Cpp的新的for循环: for( auto str:strs ).
新建容器vector的一种方法vect or vec(1, str), 结果是长度为1，默认为str的vector
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，