算法宝典——Java版本（持续更新）

注：由于字数的限制，我打算把算法宝典做成一个系列，一篇文章就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. 移除链表元素（力扣；思路：前后指针）

题目跳转链接https://leetcode.cn/problems/remove-linked-list-elements/description/

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

思路：

代码：

/**
 * 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;
    }
   
}

运行结果：

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

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

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

题目跳转链接https://leetcode.cn/problems/reverse-linked-list/description/

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

思路：

代码： 

/**
 * 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.next
            head = cur;
            cur = curNext;
        }

        return head;
    }
}

运行结果：

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

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

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

题目跳转链接https://leetcode.cn/problems/reverse-linked-list/description/

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

思路：

代码： 

/**
 * 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;
    }
}

运行结果：

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

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

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

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

思路：

代码： 

思路一：

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;
    }

运行结果：

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

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

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

题目跳转链接https://leetcode.cn/problems/merge-two-sorted-lists/description/

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

思路：

代码： 

    //合并两个升序链表，有问题
    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;
    }

运行结果：

6. 链表分割（牛客网）

题目跳转链接https://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的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：

代码： 

/*
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或者大于等于x
            if(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;

    }
}

运行结果：

7. 相交链表（力扣）

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

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

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

思路：

代码： 

    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;
    }

运行结果：

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

题目跳转链接https://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){
            //如果不是不相等，返回false
            if(cur.val != slow.val){
                return false;
            }
            //判断偶数的情况：
            if(cur.next == slow){
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }

运行结果：

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

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

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

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

思路：

代码： 

    //判断链表是否有环
    //第一种写法
    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;
    }

运行结果：

【扩展问题】

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

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

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

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

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

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

不允许修改 链表。

思路：

代码： 

    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 + Y
        while (fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

运行结果：

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

1. 有效的括号（力扣）

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

有效字符串需满足：

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

思路：

代码： 

    public static boolean isValid(String s) {
        //创建一个栈来存储括号
        Stack<Character> stack = new Stack<>();
        //用for循环进行拆分String
        for (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. 逆波兰表达式求值（力扣）

题目跳转链接https://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. 栈的压入、弹出序列（牛客网）

题目跳转链接https://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.  最小栈（力扣）

题目跳转链接https://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~127
                minStack.pop();
            }
        }
    }

    //查看栈顶元素
    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

运行结果：

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

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

题目跳转链接https://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) {
        //如果是浪费空间，这里必须多加一个1
        this.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. 用队列实现栈（力扣）

题目跳转链接https://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. 用栈实现队列（力扣）

题目跳转链接https://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. 相同的树（力扣）

题目跳转链接https://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，要么都不为null
        if(p == null && q == null){
            return true;
        }
        //如果两个结点的数值不一样就返回false
        if(p.val != q.val){
            return false;
        }
        return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
    }

运行结果：

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

题目跳转链接https://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，要么都不为null
        if(p == null && q == null){
            return true;
        }
        //如果两个结点的数值不一样就返回false
        if(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. 翻转二叉树（力扣）

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

思路：

（1）先将父亲结点交换

（2）再将子树结点交换

（3）然后递归下去

代码：

    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        //如果为空树，返回null
        if(root == null){
            return null;
        }

        //进行交换
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        invertTree(root.left);//翻转左子树
        invertTree(root.right);//翻转右子树

        return root;

    }

运行结果：

文章来源地址https://www.toymoban.com/news/detail-705525.html

到了这里，关于算法宝典——Java版本（持续更新）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！