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

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

【扩展问题】

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

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

  • 快指针一次走3步,走4步,...n步行吗?

10.  环形链表 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. 有效的括号(力扣)

题目:给定一个只包括 '('')''{''}''['']' 的字符串 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. 逆波兰表达式求值(力扣)

题目:给你一个字符串数组 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. 栈的压入、弹出序列(牛客网)

题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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.  最小栈(力扣)

题目:设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

实现 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. 设计循环队列(力扣)

题目:设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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. 用队列实现栈(力扣)

题目:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 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. 用栈实现队列(力扣)

题目:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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. 相同的树(力扣)

题目:给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

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

示例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. 另一棵树的子树(力扣)

题目:给你两棵二叉树 rootsubRoot 。检验 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. 翻转二叉树(力扣)

题目:给你一棵二叉树的根节点 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;
    }

运行结果:

相关文章
|
3天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2天前
|
分布式计算 算法 搜索推荐
Java中可以用的大数据推荐算法
在Java中实现大数据推荐算法,通常使用Apache Mahout、Weka、DL4J或Spark MLlib。本文简要介绍了三种推荐算法:基于内容的推荐、协同过滤推荐和深度学习推荐,以及它们的使用场景。提供了每种算法的伪代码或关键代码片段。基于内容的推荐适用于有用户历史行为和物品内容信息的场景,而协同过滤适用于大量用户行为数据的场景,深度学习推荐则用于处理复杂特征。在实现时,注意数据预处理、特征提取、用户画像构建和相似度计算。
13 1
|
3天前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
|
3天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
3天前
|
存储 SQL 算法
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
|
5天前
|
安全 算法
JAVA-银行家算法
JAVA-银行家算法
JAVA-银行家算法
|
5天前
|
缓存 算法 NoSQL
(JAVA)仿拼多多砍价算法
(JAVA)仿拼多多砍价算法
|
29天前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
47 0
|
12月前
|
存储 算法 Java
数据结构算法学习打卡week2 (Java)
数据结构算法学习打卡week2 (Java)
56 0
|
Rust 算法 安全
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)