林重笑

20.有效的括号文章：4. 有效的括号 题目：20. 有效的括号 视频：栈的拿手好戏！| LeetCode：20. 有效的括号_哔哩哔哩_bilibili 用栈来解决的经典问题。 不匹配的场景有三种： ​ 数量、类型、顺序 剪枝：如果字符串为奇数，则一定有不匹配的括号，直接返回多余即可。 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(')'); else if(s.charAt(i) == &# ...

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

KMP算法原理：帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili 构造前缀表 解决字符串匹配的问题 ​ 前缀表（ 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 && s[i] != s[j+1] ) j = next[j] ​ 3.前后缀相同：需要同时向后移动 i 和 j ，还需要将j （前缀的长度）赋给next[i]，因为next[i] 要记录相同前后缀的长度，if (s[i] == s[j+1])j++; next[i]=j 使用next数组来做匹配 ...

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]; ...

454.四数相加II文章：6. 四数相加II 题目：454. 四数相加 II 视频：学透哈希表，map使用有技巧！LeetCode：454.四数相加II_哔哩哔哩_bilibili 该题出现的元素数值有可能很大，不适合用数组作为解题 -> set \ map 要统计是否出现过，还需要存出现了多少次，且去重 -> 使用 map key：两数组相加的值 | value： 数值出现了多少次 注意事项：用于返回计数的count 在遇到有符合题目要求的组合时应该 += value ！ Java实现 123456789101112131415161718class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { HashMap<Integer,Integer> map = new HashMap<>(); int res = 0; for(in ...

哈希表理论基础文章：1. 哈希表理论基础 哈希表是根据关键码的值而直接进行访问的数据结构 直白来讲，数组就是一张哈希表 哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。 一般解决的问题：一般哈希表都是用来快速判断一个元素是否出现在集合里。 哈希函数哈希函数，把学生的姓名直接映射为哈希表上的索引，然后可以通过查询索引下标，就可以快速知道这位同学是否在这所学校里了。 哈希函数，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转换为不同的数值，这样就可以把学生名字映射为哈希表上的索引数字了。 如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？ 此时为了保证映射出来的索引数值都落在哈希表上，我们会再次对数值做一个取模的操作，就让我们保证了学生姓名一定可以映射到哈希表上。 如果学生数量大于哈希表的大小怎么办？此时就算哈希函数计算的再均匀，也避免不了会有几个学生的名字 同时映射到哈希表同一个索引下标的位置。 接下来哈希碰撞登场 哈希碰撞学生姓名都映射到了同一个索引下标的位置，这一现象叫 ...

【数组】 数组是存放在连续内存空间上的相同类型数据的集合； 数组下标都是从0开始的； 数组内存空间的地址是连续的； 因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，难免要移动其元素的地址； 数组的元素是不能删的，只能覆盖； 常见的解题方法： 二分法 ： 循环不变量，左闭右开，左闭右闭 双指针法（快慢指针）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作 滑动窗口：主要理解滑动窗口如何移动窗口的起始位置，达到动态更新窗口的大小，从而得出长度最小的符合条件的长度。 精妙之处在于根据当前子序列的大小的情况，不断调节子序列的起始位置。从而降低时间复杂度 模拟行为：螺旋数组再一次介绍了循环不变量原则， 【链表】 种类：单链表，双链表，循环链表 存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。 增删改查的方式： 数组和链表在不同场景的性能分析 常见方法： 虚拟头结点： 链表的一大问题就是操作当前节点必须要找到前一个节点才能操作。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题 链 ...

两两交换链表中的节点文章：代码随想录 (programmercarl.com) 题目：24. 两两交换链表中的节点 视频：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili（尊嘟讲的很好，可以去看看！） 奇数节点：最后会多出来一个节点，但是因为没有多出来的节点可以和其交换，所以我们不交换最后一个节点 偶数节点：两两交换即可 【思路】 虚拟头结点 我们当前操作的指针，一定要指向我们要反转的两个节点的前一个节点 cur 指向2，然后2指向1，1再指向3，拉直链表之后，即完成了节点12的交换 遍历的终止条件一定要清楚！ 进行两两交换的逻辑一定要清楚 Java实现 123456789101112131415161718class Solution { public ListNode swapPairs(ListNode head) { //虚拟头结点 ListNode dummyNode = new ListNode(0); dummyNode.next = he ...

文章：4. 翻转链表.url 链表链表是一种通过指针串联在一起的线性结构，每个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思） 链表的入口节点称为链表的头节点也就是head。 链表类型单链表上面定义的就是单链表 双链表单链表中的指针域只能指向节点的下一个节点。 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。 双链表既可以向前查询也可以向后查询。 循环链表循环链表，链表首尾相连。 可以用来解决约瑟夫环问题。 链表的存储方式数组是在内存中连续分布的，但是链表在内存中不是连续分布的。 链表通过指针域的指针链接在内存中的各个节点，所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。 链表的定义12345struct ListNode{ int val; //节点上存储的元素 ListNode *next; //指向下一个节点的指针 ListNode(int x): val(x),next(NULL){} //节点的 ...

双指针4. 有序数组的平方 1234567891011121314151617181920212223class Solution { public int[] sortedSquares(int[] nums) { if(nums.length ==1){ nums[0]=nums[0]*nums[0]; return nums; } int right =nums.length-1; int[]arr = new int[right+1]; //1.刚开始直接在原数组上面进行修改发现偶数长度的数组无法正确返回 //2.一开始没有正确理解双指针的含义，将j和right混淆惹 //i和j分别为左右指针，right为数组的下标，并new了一个新数组进行排序返回 for(int i =0,j = nums.length-1;i<=j;){ if(nums[i]*nums[i] < nums[j]*nums[j]){ ...