有效括号序列 思路： 由于需要进行括号匹配，由于对于最晚的进入的待匹配的括号是最早进行匹配的，所以符合后入先出的结构，所以用一个栈进行辅助 图解： 链接 代码： class Solution { public: //由于需要进行括号匹配，由于对于最晚的进入的待匹配的括号是最早进行匹配的 //所以符合后入先出的结构，所以用一个栈进行辅助 bool isValid(string s) { stack<char>s1; //遍历字符串，只要遇到左括号，就将其对应的右括号压入栈中，等待匹配 //之后如果遇...

包含min函数的栈 思路：（双栈法） 1.由于对于pop（）、top（）、push（）操作，直接用现有的stack中的这些操作就行，因为时间复杂度是O（1） 2.但是对于stack中现有的min函数，时间复杂度不是O（1） 3.所以可以通过另一个栈进行辅助记录栈1中的最小值，则栈2的栈顶元素就是栈1中的最小值 4.每次将插入栈1的元素与栈2的栈顶元素大小进行比较，将如果新的值小，就将该值压入栈2，否则就把栈2的栈顶元素本身压入栈中 代码： class Solution { public: //想在栈原先的结构中增加求min的函数，又要求时间复杂度是O（1） //对于pop()、top...

用两个栈实现队列 思路： 1.由于队列是先进先出的，然而栈是后进先出的 2.所以想要将入栈的元素模拟队列的结果，即先入的节点先出 3.则需要一个新的栈进行辅助，将栈1元素先压入栈2中，就实现了一次反转 4.此时栈2的栈顶的就是第一个元素，让这个元素出栈，就实现了先入先出 5.再将栈2中的元素再弹出压回栈1中 代码： class Solution { public: //对于插入，则直接将节点插入栈1中即可 void push(int node) { stack1.push(node); } //由于队列是先进先出的，但是栈是后进先出的...

和大于等于K的最短子数组 思路：（双指针） 1.先将右指针不断向右移动，直到区间的和大于等于k 2.当区间的长度大于等于k，就可以将左指针向右移动，不断取得最短的子数组的长度 代码： import java.util.*; public class Solution { //求和大于等于k的最短的子数组函数： //用双指针法：将左右指针最开始都指向数组的第一个元素 public int shortestSubarray (ArrayList<Integer> nums, int k) { int left=0,right=0...

序列化二叉树 知识点：二叉树递归 **递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。**而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。 思路：（递归） 序列化即将二叉树的节点值取出，放入一个字符串中，我们可以按照前序遍历的思路，遍历二叉树每个节点，并将节点值存储在字符串中，我们用‘#’表...

按之字形顺序打印二叉树 思路（双栈法）： 我们可以利用两个栈遍历这棵二叉树，第一个栈s1从根节点开始记录第一层，然后依次遍历两个栈，遍历第一个栈时遇到的子节点依次加入第二个栈s2中，即是第二层：而遍历第二个栈s2的时候因为是先进后出，因此就是逆序的，再将第二个栈s2的子节点依次加入第一个栈s1中：于是原本的逆序在第一个栈s1中又变回了正序，如果反复交替直到两个栈都空为止。 具体做法： step 1：首先判断二叉树是否为空，空树没有打印结果。 step 2：建立两个辅助栈，每次依次访问第一个栈s1与第二个栈s2，根节点先进入s1. step 3：依据依次访问的次序，s1必定记录的是奇...

按之字型顺序打印二叉树 图解： 链接 思路： 由于对于二叉树的分层打印，一般用队列进行维护 但是由于现在是按照之字形的顺序进行打印的，所以有些层需要在原先的顺序上进行反转 1.先判断树是否为空，如果为空，就直接返回 2.否则就创建一个队列进行维护 3.将每一层的节点都插入队列中，再将每一层的节点出队列 4.每一层的节点出队列的时候，需要将出队列的点存入一个一维数组中，并扩展其子节点，将子节点插入队列中 5.再去判断该层的节点是否遍历顺序是从右往左，如果是，就需要进行反转后插入二维数组中 代码： class Solution { public: //由于要将树进行之字形打印后存...

两个队列实现栈 思路： 由于对于队列是先进先出的结构，但是栈是后入先出的结构，所以可以用两个队列实现栈。 1.入栈操作就是将元素入队列1 2.出栈操作就是需要将队列1中的除了最后一个元素外的其他元素都移动到队列2中 3.再将队列1中的最后一个元素出栈，将队列2中的元素放回队列1中 4.获得栈顶元素就是获得队列1的队尾元素 5.判断栈是否为空就是判断队列1和队列2是否都为空 代码： class Solution { public: //将需要插入栈的元素插入队列1中即可 void push(int x){ q1.push(x); } ...

从上往下打印二叉树（用队列维护分层从左到右打印） 思路： 二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助： 因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一行节点，并在访问的时候依次把它们的子节点加入队列，那么它们的子节点也是从左到右的次序，且排在本行节点的后面，因此队列中出现的顺序正好也是从左到右，正好符合层次遍历的特点。 具体做法： step 1：首先判断二叉树是否为空，空树没有遍历结果。 step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它...

滑动窗口的最大值 思路： 用单调队列维护窗口中的元素的单调性 1.将序列中的每个元素都插入单调队列中，将小于需要插入的这个节点的数从队尾弹出 2.再将这个节点插入单调队列中 3.将超出窗口范围的队首节点从队首弹出队列 4.输出每个窗口中的第一个值就是这个窗口的最大值 单调队列的性质： 1.队首的元素永远是队列中最大或最小的元素，可以输出队首元素，不一定需要将队首元素弹出 2.只能从队尾插入元素，可以从队首和队尾弹出元素，单调队列实际是双端队列的一个典型应用，只是相比双端队列，单调队列只能从队尾插入，双端队列可以从队尾和队首插入元素 3.在队尾插入元素的时候，将大于或（小于）当前的元素弹...

设计LRU缓存 思路： 链接转载于https://blog.nowcoder.net/n/b279555a5cfd48f28fec790d96b0a1b9 代码： //双向链表的一个节点：包含该节点的值，对应map的索引，每个节点都有一个前驱指针和一个后驱指针 struct Node{ int key; int val; Node* pre; Node* next; //初始化 Node(int k, int v): key(k), val(v), pre(NULL), next(NULL){}; }; class Solution ...

旋转链表 思路： 1.先用一个hashmap将对应的下标和节点的值存起来 2.再遍历一遍链表，对原链表中的节点的值进行修改，根据下标查找对应的节点，将后面的k个节点进行平移到前面， 将前面的平移到后面（实际上是进行了修改） 3.注意取余操作 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public...

排序奇升偶降链表 思路： 1.先根据奇数位和偶数位的节点拆分为两个表 2.再将第二个表进行反转 3.最后将第一个表和第二表进行合并 代码： import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode Mergelist(ListNod...

给单链表加一： 思路： 1.先建立一个虚的头结点，将头结点连接到原链表的头结点 2.注意头结点的值要初始化为0！！！ 3.由于需要判断当前的节点的值是否需要加1，就需要知道后面的节点的值是否会产生进位 4.所以用递归的思想，先得到后面的节点的值 5.分为两种情况：如果后面没有节点，就表明该链表只有一个节点，所以将该节点的值加1就直接可以返回了 6.否则就将通过递归返回返回下一个节点的值，进行判断，如果下一个节点的值等于10，就将现在的节点的值加1，将后面的这个节点的值改为0 7.最后判断一下是否会产生一个最高位，如果虚节点的值不为0，就返回虚节点的值，否则就返回原先的链表的头结点 代码...