算法宝典1——Java版本（此系列持续更新，这篇文章有20道）（有题目的跳转链接）（此份宝典包含了链表、栈、队列、二叉树的算法题）

注：由于字数的限制，我打算把算法宝典做成一个系列，一篇文章就20题！！！

目录

一、链表的算法题（目前10道）

1. 移除链表元素（力扣；思路：前后指针）

2. 反转一个单链表 （力扣；思路：头插法）

3. 链表的中间结点（力扣；思路：快慢指针）

4. 链表中倒数第k个结点（牛客网；思路：①快慢指针、②倒数第几个与步数的关系）

5. 合并两个有序链表（力扣）

6. 链表分割（牛客网）

7. 相交链表（力扣）

8.  链表的回文结构（牛客网）

9.  环形链表（力扣；思路：快慢指针、数学追击问题）

10.  环形链表 II（力扣；思路：快慢指针、数学追击问题★★★☆☆）

二、栈的算法题（目前4道）

1. 有效的括号（力扣）

2. 逆波兰表达式求值（力扣）

3. 栈的压入、弹出序列（牛客网）

4.  最小栈（力扣）

三、队列的算法题（目前3道）

1. 设计循环队列（力扣）

2. 用队列实现栈（力扣）

3. 用栈实现队列（力扣）

四、二叉树的算法题（目前3道） 

1. 相同的树（力扣）

2. 另一棵树的子树（力扣）

3. 翻转二叉树（力扣）

一、链表的算法题（目前10道）

1. 移除链表元素（力扣；思路：前后指针）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/remove-linked-list-elements/description/

题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：

ed126bc284fa4e21a28ee2a67bd42bbe.png

代码：

/*** 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 removeElements(ListNode head, int val) {if(head == null){return null;}ListNode prev = head;ListNode cur = head.next;while(cur != null){if(cur.val == val){prev.next = cur.next;cur = cur.next;}else{cur = cur.next;prev = prev.next;}}//最后处理第一个节点if(head.val == val){head = head.next;}return head;}}

运行结果：

e9600f94041a4a6faab8188fc48ed21e.png

时间复杂度和空间复杂度：

（1）时间复杂度：O(N)；（2）空间复杂度：O(1)

2. 反转一个单链表 （力扣；思路：头插法）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-linked-list/description/

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：

d60d3af6c8704f86ba3f33535e674250.png

代码： 

/*** 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 reverseList(ListNode head) {//特殊情况一：如果链表为空，就不需要返回if(head == null){return null;}//特殊情况二：只有一个节点if(head.next == null){return head;}ListNode cur = head.next;//把第二个节点地址保存起来head.next = null;//到时第一个节点的next肯定为空，在这里就可以提前改了//进入循环，开始进行头插法while(cur != null){ListNode curNext = cur.next;//保存cur指向的节点cur.next = head;//将第一个节点的地址赋值给cur.nexthead = cur;cur = curNext;}return head;}
}

运行结果：

da607258f141437ba49ed38bb427e9a6.png

时间复杂度和空间复杂度：

（1）时间复杂度：O(N)；空间复杂度：O(1)

3. 链表的中间结点（力扣；思路：快慢指针）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-linked-list/description/

题目：思路给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

思路：

23501745df9f4ef48f3b1a9ce2b5a968.png

代码： 

/*** 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 middleNode(ListNode head) {//特殊情况：如果只有一个结点if(head.next == null){return head;}ListNode quick = head;//快指针ListNode slow = head;//慢指针//有两种条件都成立表示快指针不走了，（1）quick为空 （2）quick.next为空while(quick != null && quick.next != null){quick = quick.next.next;slow = slow.next;}return slow;}
}

运行结果：

a0152355dc99421099a201c1f351cf82.png

时间复杂度和空间复杂度：

（1）时间复杂度：O(N)；（2）空间复杂度：O(1)

4. 链表中倒数第k个结点（牛客网；思路：①快慢指针、②倒数第几个与步数的关系）

题目跳转链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking题目：输入一个链表，输出该链表中倒数第k个结点。

思路：

1caa2144c9794d0ea1761e571db651e6.png

代码： 

思路一：

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head, int k) {//输入值是否正确的判断if(k <= 0 || head == null){return null;}ListNode quick = head;ListNode slow = head;//先让quick走k - 1步while (k - 1 != 0){quick = quick.next;if(quick == null){return null;}k--;}//快慢指针一起走while(quick.next != null){quick = quick.next;slow = slow.next;}return slow;}
}

思路二：

    public ListNode findKthToTail2(int k) {//输入值是否正确的判断if(k <= 0 || head == null){return null;}int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}int i = count - k;cur = head;if(i < 0){return null;}while(i > 0){cur = cur.next;i--;}return cur;}

运行结果：

804065225d0d4c5fb7bacc1db417990d.png

时间复杂度和空间复杂度：

（1）时间复杂度：O(N)；（2）空间复杂度：O(1)

5. 合并两个有序链表（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：

7d4ffc8fe062452aa74b5217aa7ff812.png

代码： 

    //合并两个升序链表，有问题public ListNode mergeTwoLists(ListNode list1, ListNode list2){//处理空表的情况if(list1 == null && list2 !=null){return list2;}else if(list1 != null && list2 == null){return list1;}else if(list1 == null&&list2 == null){return null;}//创建两个地址引用，指向两个链表的首元素结点ListNode cur1 = list1;ListNode cur2 = list2;ListNode cur3 = null;//始终指向新链表的终端结点//创建一个newList引用ListNode newList = null;if (cur1.val <= cur2.val){newList = cur1;cur1 = cur1.next;cur3 = newList;}else if(cur1.val >= cur2.val){newList = cur2;cur2 = cur2.next;cur3 = newList;}//开始比较while(cur1 != null && cur2 != null ){if(cur1.val <= cur2.val){cur3.next = cur1;cur3 = cur3.next;cur1 = cur1.next;}else if(cur1.val > cur2.val){cur3.next = cur2;cur3 = cur3.next;cur2 = cur2.next;}}//当cur1 == null或cur2 == null时，意味着已经到链表的结尾，此时还需要将没有连接上的链表（cur1或cur2）连接接上cur3.next = null;if(cur1 != null){cur3.next = cur1;}if(cur2 != null){cur3.next = cur2;}return newList;}

运行结果：

ce1ef861c2ef420a8c4f3b09d2f37d80.png

6. 链表分割（牛客网）

题目跳转链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：

b51b92ae44ce47a3b9f5141ab4eb7281.png

代码： 


/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code here//把整个链表看成两部分，创建四个引用来分别指向这两部分ListNode bs = null;//小于x部分的起始引用ListNode be = null;//小于x部分的终端引用ListNode as = null;//大于或等于x部分的起始引用ListNode ae = null;//大于或等于x部分的终端引用ListNode cur = pHead;//开始循环while(cur != null){//有两种可能性，小于x或者大于等于xif(cur.val < x){//这部分也有两种情况，①当bs和be都为空，②bs不会空if(bs == null){bs = cur;be = cur;}else{be.next = cur;be = be.next;}}else{if(as == null){as = cur;ae = cur;}else{ae.next = cur;ae = ae.next;}}cur = cur.next;}//有可能不会同时存在小于x和大于等于x的数据if(bs == null){return as;}//特殊情况：如果第一段不为空be.next = as;//如果第二段为空if(as != null){ae.next = null;}return bs;}
}

运行结果：

f5ac474b27be4c8daccd8d71d9f80587.png

7. 相交链表（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/intersection-of-two-linked-lists/description/题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路：

783265d812214c179bf5e2a855833421.png

代码： 

    public MySinglelist.ListNode getIntersectionNode(MySinglelist.ListNode headA, MySinglelist.ListNode headB) {int lenA = 0;//用来记录长度int lenB = 0;MySinglelist.ListNode pl = headA;MySinglelist.ListNode ps = headB;//计算pl和ps的链表长度while(pl != null){lenA++;pl = pl.next;}while (ps != null){lenB++;ps = ps.next;}//1. len一定是一个正数  2.pl指向的链表一定是最长的  ps 指向的链表一定是最短的pl = headA;ps = headB;//计算彼此之间的差值int len = lenA - lenB;if(len < 0){pl = headB;ps = headA;len = lenB - lenA;}//先让长度多的链表先走len步while(len != 0){pl = pl.next;len--;}//开始找相交的节点while(pl != ps){ps = ps.next;pl = pl.next;}//pl == ps/* if(pl == null) {return null;}*/return pl;}

运行结果：

43040a123a13462f9f5a6f65b13d731d.png

8.  链表的回文结构（牛客网）

题目跳转链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

思路：

定义快慢指针：

（1）找到中间结点

（2）翻转慢指针到快指针部分的结点

（3）首尾互相判断是否符合回文结构

代码： 

    public boolean chkPalindrome(ListNode head) {if(head == null){return false;}if(head.next == null){return true;}// write code here//先定义快慢指针ListNode quick = head;ListNode slow = head;//1. 找中间结点while(quick != null && quick.next != null){quick = quick.next.next;slow = slow.next;}//2. 翻转ListNode cur = slow.next;while(cur != null){ListNode curNext = cur.next;//先记录下来后一个结点cur.next = slow;//实现翻转slow = cur;//保存上一个结点的地址cur = curNext;//找到下一个结点}//3.开始判断cur = head;while(cur != slow){//如果不是不相等，返回falseif(cur.val != slow.val){return false;}//判断偶数的情况：if(cur.next == slow){return true;}cur = cur.next;slow = slow.next;}return true;}

运行结果：

ee73ea872379449095990d7f548dc1a3.png

9.  环形链表（力扣；思路：快慢指针、数学追击问题）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle/description/题目：给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：

378a0c7c403c40eab57d7af7e1610047.png

代码： 

    //判断链表是否有环//第一种写法public boolean hasCycle() {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return false;}//第二种写法public boolean hasCycle2() {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if(fast  == null || fast.next == null){return false;}return true;}

运行结果：

878a5c809c0e44ff8b8c02251a47fbe5.png

【扩展问题】

  • 为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

  • 快指针一次走3步，走4步，...n步行吗？

2141faa24f3e41a0bdb74883804c7102.png

10.  环形链表 II（力扣；思路：快慢指针、数学追击问题★★★☆☆）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/linked-list-cycle-ii/题目：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路：

23cb4ad07e7d4fd2b72a60f5902d5db4.png

代码： 

public ListNode detectCycle() {//找到相遇点ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if(fast  == null || fast.next == null){return null;}//slow指针从头走slow = head;//fast指针从相遇点开始走//因为X = （N - 1）C + Ywhile (fast != slow){fast = fast.next;slow = slow.next;}return fast;}

运行结果：

a230f288c4cc44bd8dd1394a3502b486.png

二、栈的算法题（目前4道）

1. 有效的括号（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/valid-parentheses/题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

思路：

代码： 

    public static boolean isValid(String s) {//创建一个栈来存储括号Stack<Character> stack = new Stack<>();//用for循环进行拆分Stringfor (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);//如果字符是左括号就入栈if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch);} else {//如果字符是右括号就执行else//如果栈是空的，就意味着右括号之前没有左括号if (stack.empty()) {return false;}//先看下栈顶元素是不是满足条件的左括号char ch2 = stack.peek();//进行匹配if (ch == ')' && ch2 == '(' || ch == '}' && ch2 == '{'  || ch == ']' && ch2 == '['){//满足条件，栈顶的左括号跳出stack.pop();}else{return false;//如果不满足条件，返回false}}}//假设右括号都匹配完了，还是有左括号加入，也就是栈不为空if(!stack.empty()){return false;}return true;}

运行结果：

2. 逆波兰表达式求值（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/evaluate-reverse-polish-notation/题目：给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

思路：

代码： 

    public int evalRPN(String[] tokens) {//首先创建一个栈Stack<Integer> stack = new Stack<>();//遍历数组for(String x : tokens){if (!isOperation(x)){//如果不是操作符就压入栈stack.push(Integer.parseInt(x));//解析字符串}else{//如果遍历到操作符//弹出两个数int num2 = stack.pop();//作为右操作数int num1 = stack.pop();//作为左操作数switch (x){case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;}}}//最后弹出最后一个数，就可以得到结果了return stack.pop();}//判断传入的字符是不是操作数private boolean isOperation(String x){if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")){return true;}return false;}

运行结果：

3. 栈的压入、弹出序列（牛客网）

题目跳转链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

思路：此题的思路比较简单，就不作图了，代码的注释有写哈哈哈。

代码： 

    public boolean IsPopOrder (int[] pushV, int[] popV) {//pushV 和 popV 的元素数量都一致// write code here//首先创建一个栈Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0;i < pushV.length;i++){stack.push(pushV[i]);//这段代码要注意异常的抛出，得先知道栈不为空，才可以跳出栈顶元素while(j < popV.length && !stack.empty() && stack.peek().equals(popV[j])  ){stack.pop();j++;}}return stack.empty();//如果stack为空了，就是栈内没元素了，都匹配上了}

运行结果：

4.  最小栈（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/min-stack/题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

思路：

虽然内部是用了两个栈，但是在外部看就是一个栈！

代码： 

public class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;//初始化两个栈public MinStack() {stack = new Stack<>();minStack = new Stack<>();}//压栈public void push(int val) {//先压入普通栈stack.push(val);//如果最小栈为空，直接压入最小栈进行维护if(minStack.empty()){minStack.push(val);}else{//如果最小栈有值，那么就看看如今想压入栈的元素与栈顶元素的大小//栈顶元素是在minStack中最小的元素，也是stack中最小的元素if (val <= minStack.peek()){minStack.push(val);}}}//出栈public void pop() {if(!stack.empty()){Integer val = stack.pop();//取出stack的栈顶元素//如果stack的栈顶元素是minStack栈顶元素的，那么minStack的栈顶元素也要取出if(val.equals(minStack.peek())){//这里必须用equals，因为Integer在元数据区中只有-128~127minStack.pop();}}}//查看栈顶元素public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

运行结果：

三、队列的算法题（目前3道）

1. 设计循环队列（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/design-circular-queue/

题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

思路：

循环队列两个特殊的状态：队空和队满(rear的情况和front类似)。 由图3-5可以看出，循环队列必须损失一个存储空间，如果空白处也存入元素，则队满的条件也成了front==rear,即和队空条件相同，那么就无法区分队空和队满了

(1)三个状态

1)队空状态:qu.rear==qu.front。

2)队满状态:(qu.rear+1)%maxSizequ == front。

3)长度（多少个元素）:(rear-front+maxsize)%maxsize；防止rear-front为负，所以要加maxsize

(2)两个操作

1)元素x进队操作(移动队尾指针)。

qu.rear=(qu.rear+1)%maxSize;qu.data[qu.rear]=x;

2)元素x出队操作(移动队首指针)。

qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];

队首指针指向的位置不能有数据！！！

代码：

//循环队列
public class MyCircularQueue {private int elem[];private int front;//表示队列的头private int rear;//表示队列的尾//创建循环队列public MyCircularQueue(int k) {//如果是浪费空间，这里必须多加一个1this.elem = new int[k + 1];}//判断队列是否为满public boolean isFull() {return (rear + 1) % elem.length == front;}//入队列public boolean enQueue(int value) {//1. 检查是否队列是满的if (isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}//出队列public boolean deQueue() {//队列为空if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}//得到队头元素public int Front() {if (isEmpty()) {return -1;}return elem[front];}//得到队尾元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length - 1 : rear-1;return elem[index];}//判读队列是否为空public boolean isEmpty() {return front == rear;}
}

运行结果：

2. 用队列实现栈（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/implement-stack-using-queues/

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

代码：


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;public class MyStack2 {//需要两个队列才能模拟栈private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack2() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else {qu1.offer(x);}}public int pop() {if(empty()){return -1;//两个队列都为空，意味着当前的栈为空}if(!qu1.isEmpty()){int size = qu1.size();for(int i = 0;i < size - 1;i++){int val = qu1.poll();qu2.offer(val);}return qu1.poll();}else{int size = qu2.size();for(int i = 0;i<size - 1;i++){int val = qu2.poll();qu1.offer(val);}return qu2.poll();}}public int top() {if(empty()){return -1;}int val = 0;if(!qu1.isEmpty()){int size = qu1.size();for(int i = 0;i < size;i++){val = qu1.poll();qu2.offer(val);}return val;}else{int size = qu2.size();for(int i = 0;i < size;i++){val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

运行结果：

3. 用栈实现队列（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/implement-queue-using-stacks/题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路：

代码：

import java.util.Stack;public class MyQueue2 {//创建两个栈private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue2() {s1 = new Stack<>();s2 = new Stack<>();}//入队public void push(int x) {s1.push(x);}//出队public int pop() {//栈空判断if(empty()){return -1;}if(s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.pop();}//返回队头结点public int peek() {//栈空判断if(empty()){return -1;}if(s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.empty() && s2.empty();}
}

运行结果：

四、二叉树的算法题（目前3道） 

1. 相同的树（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/same-tree/

题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1：

输入：p = [1,2,3]，q = [1,2,3]

输出：true

示例2：

输入：p = [1,2]，q = [1,null,2]

输出：false

示例3：

输入：p = [1,2,1]，q = [1,1,2]

输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

思路：

代码：

    //判断两棵树是否相同public boolean isSameTree(TreeNode p, TreeNode q) {//如果p还有结点，q没有结点，证明两棵树的子树就不相同了，反之亦然if(p != null && q == null || p == null && q != null){return false;}//要么都为null，要么都不为nullif(p == null && q == null){return true;}//如果两个结点的数值不一样就返回falseif(p.val != q.val){return false;}return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);}

运行结果：

2. 另一棵树的子树（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/subtree-of-another-tree/

题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例1：

输入：root = [3,4,5,1,2]，subRoot = [4,1,2]

输出：true 

示例2：

输入：root = [3,4,5,1,2,null,null,null,null,0]，subRoot = [4,1,2]

输出：false

提示：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104

思路：

代码：

    //判断两棵树是否相同public boolean isSameTree(TreeNode p, TreeNode q) {//如果p还有结点，q没有结点，证明两棵树的子树就不相同了，反之亦然if(p == null && q != null || p != null && q == null){return false;}//要么都为null，要么都不为nullif(p == null && q == null){return true;}//如果两个结点的数值不一样就返回falseif(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null || subRoot == null){return false;}if(isSameTree(root,subRoot))//从当前结点开始return true;if(isSubtree(root.left,subRoot))//从左子树的根结点开始return true;if(isSubtree(root.right,subRoot))//从右子树的根结点开始return true;return false;}

运行结果：

3. 翻转二叉树（力扣）

题目跳转链接icon-default.png?t=N7T8https://leetcode.cn/problems/invert-binary-tree/题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：

（1）先将父亲结点交换

（2）再将子树结点交换

（3）然后递归下去

代码：

    //翻转二叉树public TreeNode invertTree(TreeNode root) {//如果为空树，返回nullif(root == null){return null;}//进行交换TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);//翻转左子树invertTree(root.right);//翻转右子树return root;}

运行结果：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/135280.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

宋浩概率论笔记（六）样本与统计量

宋浩概率论笔记（六）样本与统计量

参数估计的入门章节&#xff0c;为后面的参数估计与假设检验铺垫基础&#xff0c;难点在于背诵公式&#xff0c;此外对于统计量的理解一定要清晰——本质是多个随机变量复合而成的函数~
阅读更多...
ARM接口编程—Interrupt(exynos 4412平台)

ARM接口编程—Interrupt(exynos 4412平台)

CPU与硬件的交互方式 轮询 CPU执行程序时不断地询问硬件是否需要其服务&#xff0c;若需要则给予其服务&#xff0c;若不需要一段时间后再次询问&#xff0c;周而复始中断 CPU执行程序时若硬件需要其服务&#xff0c;对应的硬件给CPU发送中断信号&#xff0c;CPU接收到中断信号…
阅读更多...
MySQL常用函数集锦 --- 字符串|数值|日期|流程函数总结

MySQL常用函数集锦 --- 字符串|数值|日期|流程函数总结

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【MySQL学习专栏】&#x1f388; 本专栏旨在分享学习MySQL的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 目录 一、字符…
阅读更多...
在c#中使用CancellationToken取消任务

在c#中使用CancellationToken取消任务

目录 &#x1f680;介绍&#xff1a; &#x1f424;简单举例 &#x1f680;IsCancellationRequested &#x1f680;ThrowIfCancellationRequested &#x1f424;在控制器中使用 &#x1f680;通过异步方法的参数使用cancellationToken &#x1f680;api结合ThrowIfCancel…
阅读更多...
js创建动态key的对象ES6和ES5的方法

js创建动态key的对象ES6和ES5的方法

前提&#xff1a; 有个场景&#xff0c;循环数组&#xff0c;根据每一项的值&#xff0c;往一个数组中push一个新对象&#xff0c;对象的key不同要从数组中获取 情况解析&#xff1a;push没有什么问题&#xff0c;问题就是创建一个动态key的对象。下面就说一下如何以参数为key…
阅读更多...
第二证券股票分析：什么是赛道股和题材股？

第二证券股票分析：什么是赛道股和题材股？

赛道股和题材股是两种经常被出资者关注的股票类型。赛道股是指代表着产业趋势和未来增加方向的上市公司股票&#xff0c;例如新能源汽车、5G通信等。题材股则是针对商场上的某些抢手事情或话题而产生的股票炒作。那么赛道股和题材股有哪些不同之处&#xff1f;在进行这类出资时…
阅读更多...
Claude 使用指南 | 可与GPT-4媲美的语言模型

Claude 使用指南 | 可与GPT-4媲美的语言模型

本文全程干货&#xff0c;让你轻松使用上claude&#xff0c;这也是目前体验cluade的唯一途径&#xff01;废话不多说&#xff0c;直接上教程&#xff0c;cluade的能力不逊于GPT4&#xff0c;号称是ChatGPT4.0最强竞品。相对Chatgpt来说&#xff0c;Claude不仅是完全免费的&…
阅读更多...
贝叶斯分位数回归、lasso和自适应lasso贝叶斯分位数回归分析免疫球蛋白、前列腺癌数据...

贝叶斯分位数回归、lasso和自适应lasso贝叶斯分位数回归分析免疫球蛋白、前列腺癌数据...

原文链接&#xff1a;http://tecdat.cn/?p22702 贝叶斯回归分位数在最近的文献中受到广泛关注&#xff0c;本文实现了贝叶斯系数估计和回归分位数&#xff08;RQ&#xff09;中的变量选择&#xff0c;带有lasso和自适应lasso惩罚的贝叶斯&#xff08;点击文末“阅读原文”获取…
阅读更多...
服务器迁移：无缝过渡指南

服务器迁移：无缝过渡指南

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…
阅读更多...
笔记01：第一行Python

笔记01：第一行Python

NameError 名字不含特殊符号&#xff08;只能是英文、数字、下划线、中文等&#xff09;名字区分大小写名字先定义后使用 SyntaxError 不符合Python语法书写规范除了语法成分中的保留拼写错误输出中文符号if、for、def等语句末尾忘记冒号 IdentationError 缩进错误&#x…
阅读更多...
迅为iTOP-RK3568开发板Sobel 算子边缘检测

迅为iTOP-RK3568开发板Sobel 算子边缘检测

本小节代码在配套资料“iTOP-3568 开发板\03_【iTOP-RK3568 开发板】指南教程 \04_OpenCV 开发配套资料\32”目录下&#xff0c;如下图所示&#xff1a; Sobel (索贝尔)算子是计算机视觉领域的一种重要处理方法。主要用于获得数字图像的一阶梯度,常见的应用和物理意义是边缘检…
阅读更多...
docker swarm集群

docker swarm集群

集群构建 不包含在任何 Swarm 中的 Docker 节点&#xff0c;称为运行于单引擎&#xff08;Single-Engine&#xff09;模式。一旦被加入 Swarm 集群&#xff0c;则切换为 Swarm 模式。第一步我们要做的就是初始化 Swarm。 初始化swarm集群 将本机作为manager节点 docker swar…
阅读更多...
举例说明用 easylanguage 语言，编写抄底公式

举例说明用 easylanguage 语言，编写抄底公式

EasyLanguage 语言在金融领域被广泛使用&#xff0c;尤其是用于编写交易策略和算法。以下是一个简单的抄底公式示例&#xff1a; swift 复制 // 定义变量和参数 Dim StopLossPrice As Double Dim TakeProfitPrice As Double Dim InitialPosition As Double Dim SafetyZon…
阅读更多...
Promethus(普罗米修斯）安装与配置（亲测可用）

Promethus(普罗米修斯）安装与配置（亲测可用）

1. 普罗米修斯概述 Prometheus(是由go语言(golang)开发)是一套开源的监控&报警&时间序列数 据库的组合。适合监控docker容器。 Prometheus是最初在SoundCloud上构建的开源系统监视和警报工具包 。自2012年成立以来&#xff0c;许多公司和组织都采用了Prometheus&#…
阅读更多...
【Linux进行时】进程状态

【Linux进行时】进程状态

进程状态&#xff1a; ❓假设我们在上课&#xff0c;在B站上上课&#xff0c;请问我们的B站是不是一直运行呢&#xff1f;&#x1f4a1;不是的&#xff01; ❓假设我们同时打开了B站和PDF阅读器时&#xff0c;是怎么运行的呢&#xff1f; &#x1f4a1;每一个进程在CPU跑一会&a…
阅读更多...
工业RFID进口品牌和国内品牌差距有多大?

工业RFID进口品牌和国内品牌差距有多大?

随着国内的RFID技术也逐渐发展成熟&#xff0c;国产工业品牌也不断优化&#xff0c;推出了不少高品质、高性能的工业读写器。对于企业来说&#xff0c;在选择读写器的时候也有了更多的选择&#xff0c;那么&#xff0c;现如今工业RFID进口品牌和国内品牌差距有多大&#xff0c;…
阅读更多...
深度解析NLP文本摘要技术：定义、应用与PyTorch实战

深度解析NLP文本摘要技术：定义、应用与PyTorch实战

目录 1. 概述1.1 什么是文本摘要&#xff1f;1.2 为什么需要文本摘要&#xff1f; 2. 发展历程2.1 早期技术2.2 统计方法的崛起2.3 深度学习的应用2.4 文本摘要的演变趋势 3. 主要任务3.1 单文档摘要3.2 多文档摘要3.3 信息性摘要 vs. 背景摘要3.4 实时摘要 4. 主要类型4.1 抽取…
阅读更多...
迅为i.MX8mm小尺寸商业级/工业级核心板

迅为i.MX8mm小尺寸商业级/工业级核心板

尺寸&#xff1a; 50mm*50mm CPU&#xff1a; NXP i.MX8M Mini 主频&#xff1a; 1.8GHz 架构&#xff1a; 四核Cortex-A53&#xff0c;单核Cortex-M4 PMIC&#xff1a; PCA9450A电源管理PCA9450A电源管理NXP全新研制配&#xff0c;iMX8M的电源管理芯片有六个降压稳压器、五…
阅读更多...
C#-WinForm-发送邮件

C#-WinForm-发送邮件

登录QQ邮箱——设置——开启“POP3/SMTP服务” 登陆QQ邮箱→打开设置→开启“POP3/SMTP服务”&#xff0c;获取“授权码” 简单总结一下&#xff1a; 1、使用SmtpClient发送电子邮件是很简单的&#xff0c;只要正确创建了MailMessage对象和SmtpClient就可以很容易的发送出去电…
阅读更多...
RBTree（红黑树）模拟实现（插入）

RBTree（红黑树）模拟实现（插入）

目录 红黑树的性质 红黑树的模拟插入 叔叔存在且为红色 叔叔不存在 旋转情况​​​​​​​ 叔叔存在且为黑色 总结 插入实现 节点 插入逻辑 左单旋 右单旋 红黑树是一颗平衡搜索二叉树&#xff0c;但是红黑树并不像 AVL 树一样是高度平衡二叉树&#xff0c;任意一…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023