林重笑

二叉树理论基础文章：1. 二叉树理论基础 视频：关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩_bilibili 种类满二叉树定义：如果一颗二叉树上只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。 深度为k，节点数：2^k-1 除了底层以外，从左到右其他地方都是满的，是完全二叉树 完全二叉树定义：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含 1 ~ 2^(h-1)个节点。 优先级队列->堆 是完全二叉树，同时保证父子节点的顺序关系。 二叉搜索树前面介绍的数都是没有数值的，而二叉搜索树是有数值的。 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树 平衡二叉搜索树性质：它是一棵空树或它的左右两个子树的高度的绝对值不超过1，并且左右两个子 ...

代码随想录训练营第十三天 | 滑动窗口最大值&&前K个高频元素&&总结 239.滑动窗口最大值文章：7. 滑动窗口最 大值 题目：239. 滑动窗口最大值 视频：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili 难点在于：如何求滑动窗口里面的最大值。 【思路】 滑动窗口很像一个队列。 单调队列。维护队列里面的元素单调递增或单调递减。 因此我们采用Deque进行处理：著需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。 1.pop(value)： 如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。 2.push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到（while）push元素的数值小于等于队列入口元素的数值为止。 保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。 pop() push() getMaxValue() Java实现 1234 ...

代码随想录训练营第十一天 | 栈与队列02 20.有效的括号文章：4. 有效的括号 题目：20. 有效的括号 视频：栈的拿手好戏！| LeetCode：20. 有效的括号_哔哩哔哩_bilibili 用栈来解决的经典问题。 栈的函数： push/pop/peek 不匹配的场景有三种： ​ 数量、类型、顺序 剪枝：如果字符串为奇数，则一定有不匹配的括号，直接返回多余即可。 Java实现 1234567891011121314class Solution { public boolean isValid(String s) { if(s.length()%2 ==1 )return false; Stack<Character> stack = new Stack<>(); for(int i = 0 ; i < s.length();i++){ if(s.charAt(i) == '(')stack.push( ...

代码随想录训练营第十天 | 栈与队列 栈与队列理论基础队列是先进先出，栈是先进后出 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是我们可以控制使用哪种容器来实现栈的功能） 我们常用的SGL STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。 栈提供push和pop接口，所有元素必须符合先进后出的规则，所以栈不提供走访功能，也不提供迭代器。不像set或者map提供迭代器iterator来遍历所有元素。 deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。 232.用栈实现队列文章：2. 用栈实现队列 题目：232. 用栈实现队列 视频：栈的基本操作！ | LeetCode：232.用栈实现队列_哔哩哔哩_bilibili 使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。pop() – 从队列首部移除元素。peek() – 返回队列首部的元素。empty() – 返回队列是否为空。 【思路】 队列：先入先出 栈，需要借助另一个栈。关键在于如何模拟出栈的顺序，需要两个栈，一个输入栈， ...

KMP算法作用：应用在字符串匹配上。 主要思想：当出现字符串不匹配的时候，可以知道一部分之前已匹配的文本内容，可以利用这些信息避免从头再去匹配。 原理：帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili 什么是前缀表（next数组）前缀表：用来回退的，记录了模式串和主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配。记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀 构造前缀表 解决字符串匹配的问题 ​ 前缀表（ next / prefix ）: 记录下标 i 之前（包括 i ）的字符串中，有多大长度的相同前缀后缀。 当字符不匹配时，就要跳到最长相等的前缀 的后面 构造next数组 ​ 1.初始化前缀表： j为前缀末尾位置 i为后缀末尾位置 j = 0;next[j] = j ;而i的初始化为for(int i = 1 ; i < s.length() ; i++ )，如果s[i] 和 s[j+1]不同，就要找j+1前一个元素在next数组里的值。（就是next[j]） ​ 2.前后缀不相同：j要回退回去， if ( j > 0 &a ...

KMP算法作用：应用在字符串匹配上。 主要思想：当出现字符串不匹配的时候，可以知道一部分之前已匹配的文本内容，可以利用这些信息避免从头再去匹配。 原理：帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili 什么是前缀表（next数组）前缀表：用来回退的，记录了模式串和主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配。记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀 构造前缀表 解决字符串匹配的问题 ​ 前缀表（ next / prefix ）: 记录下标 i 之前（包括 i ）的字符串中，有多大长度的相同前缀后缀。 当字符不匹配时，就要跳到最长相等的前缀 的后面 构造next数组 ​ 1.初始化前缀表： j为前缀末尾位置 i为后缀末尾位置 j = 0;next[j] = j ;而i的初始化为for(int i = 1 ; i < s.length() ; i++ )，如果s[i] 和 s[j+1]不同，就要找j+1前一个元素在next数组里的值。（就是next[j]） ​ 2.前后缀不相同：j要回退回去， if ( j > 0 &a ...

344.反转字符串文章：代码随想录 (programmercarl.com) 题目：字符串基础操作！ | LeetCode：344.反转字符串_哔哩哔哩_bilibili 视频：344. 反转字符串 【思路】 方法：双指针法 如果题目的实现逻辑为库函数的话，尽量手写。 swap函数的实现逻辑： ​ swap可以有两种实现。 ​ 一种就是常见的交换数值： 123int tmp = s[i];s[i] = s[j];s[j] = tmp; ​ 一种就是通过位运算： 123s[i] ^= s[j];s[j] ^= s[i];s[i] ^= s[j]; Java实现 1234567891011class Solution { public void reverseString(char[] s) { int j = s.length-1; for(int i = 0 ; i < s.length/2;i++){ char t = s[i]; s[i] = s[j]; ...

两数之和文章：5. 两数之和 题目：1. 两数之和 【思路】 Java 12345678910111213141516class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer,Integer> map = new HashMap<>(); int[]res = new int[2]; for(int i = 0;i< nums.length;i++){ int t = target-nums[i]; if(map.containsKey(t)){ res[1] = i; res[0] = map.get(t); break; } map.put(nums[i],i); ...

哈希表理论基础哈希表 根据关键码的值而进行直接访问的数据结构 哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。 一般哈希表都是用来快速判断一个元素是否出现在集合里。 哈希函数哈希函数，将学生的姓名直接映射味哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。 哈希函数，通过hashcode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转换为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。 如果hashCode得到的数值大于哈希表的大小，我们将会再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上。 为了避免多个hashCode映射到哈希表同一个索引下标的位置，我们需要哈希碰撞。 哈希碰撞拉链法索引1的位置发生了冲突，发生冲突的元素都被存储在链表中，这样我们就可以通过索引找到了。 拉链法：要选择 适当的哈希表的大小，这样既不会因为数组控制而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。 线性探测法一定要保证tableSize大于dataSize，我们需要依靠哈希表中的空位 ...

24.两两交换链表中的节点文章：5. 两两交换链表中的节点 题目：24. 两两交换链表中的节点 【思路】 虚拟头结点 Java 1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapPairs(ListNode head) { //虚拟头结点 L ...