《剑指offer》专题—算法训练 day05

文章目录

  • 《剑指offer》专题—算法训练 day05
  • 一、删除链表中重复的结点
    • 思路
  • 二、栈的规则性设计
    • 思路
  • 三、栈的压入、弹出序列
    • 思路
  • 四、二叉树的层序遍历
    • 思路
  • 未完待续...


《剑指offer》专题—算法训练 day05



一、删除链表中重复的结点


https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?


在这里插入图片描述

思路

在这里插入图片描述
在这里插入图片描述


相关代码


/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
     
    public ListNode deleteDuplication(ListNode pHead) {
     
        // 建立一个傀儡节点,因为我们不知道头节点是否应该删除
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        ListNode cur = pHead;
        
        while(cur!=null){
     
                            // 如果碰到了重复节点的话
            if( cur.next !=null && cur.val == cur.next.val ){
     
                    // 如果碰到多个连续重复的节点的话
                while( cur.next!= null && cur.val == cur.next.val ){
     
                    cur = cur.next;
                }
                     //走过重复节点之后cur要多走一步
                    cur = cur.next;
              }else{
     
                // 如果没有遇到重复节点
                tmp.next = cur;
                cur = cur.next;
                tmp = tmp.next;
            }
        }
        
        // 如果傀儡节点后面全部是重复节点,那么傀儡节点后面接着空节点
        
        tmp.next = null;
        
        return newHead.next;

    }
}

二、栈的规则性设计


https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?


《剑指offer》专题—算法训练 day05_第1张图片


思路


  很容易想到,在栈内部保存min变量,每次更新的时候,都对min变量进行更新。

  但是,面试官很容易就会问到:如果想拿出第二小,第三小的值怎么拿?

  用上面的办法就不行了

  为了满足通用,我们使用一个辅助栈,内部保存元素的个数和数据栈完全一样,不过,辅助栈内部永远保存本次入栈的数为所有数据的最小值

注意:辅助栈内部元素会出现必要性重复


我们对辅助栈的要求:


1.元素个数永远和数据栈相同

为什么我们要对两个栈同时 pop ,为了保证栈中元素个数的一致.

  为什么要保持一致呢?

  如果面试官问到要查找这个栈中第n个最小的元素

  我们要依次弹出辅助栈栈顶元素,所以辅助栈和数据栈的元素个数得保存一致


2.辅助栈栈顶永远保存当前个数的数据的最小值,其中,辅助栈中数据有可能存在大量重复


相关代码


import java.util.Stack;

public class Solution {
     

    Stack<Integer> data_stack = new Stack<>() ;// 建立一个数据栈
    Stack<Integer> min_stack = new Stack<>();// 建立一个辅助栈
    
    public void push(int node) {
     
        if(min_stack.isEmpty() == true){
     
            // 当辅助栈为空的时候我们把相关的数据插入到 min_stack 辅助栈当中
            min_stack.push(node);
        }else{
     
            
            if(node< min_stack.peek()){
     
                // 当不是第一次入栈,只有 node 小于栈顶元素才能够入栈
                min_stack.push(node);
            }else{
     
                            // 当不是上述的情况时,我们也要插入,但是插入什么呢? 继续插入我们之前保存的辅助栈栈顶元素
            min_stack.push(min_stack.peek());
            }

        }
        // 不管是什么情况,这个数据都要插入到 数据栈中
        data_stack.push(node);
    }
    
    public void pop() {
     
        // 为什么我们要对两个栈同时 pop ,为了保证栈中元素个数的一致.
        // 为什么要保持一致呢? 
        //如果面试官问到要查找这个栈中第n个最小的元素
        //我们要依次弹出辅助栈栈顶元素,所以辅助栈和数据栈的元素个数得保存一致
        min_stack.pop();
        data_stack.pop();
    }
    
    public int top() {
     
        return data_stack.peek();
    }
    
    public int min() {
     
        return min_stack.peek();
    }
}

三、栈的压入、弹出序列


https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?


《剑指offer》专题—算法训练 day05_第2张图片


思路


1.遍历入栈序列,只要 popA的第一个数据 和当前 pushA 的数据不相等时,就一直入栈

2.只要stack 栈顶值 和 popA 的出栈序列数据是相等的,则一直执行出栈逻辑

3.如果最后 stack 为空的话,那么说明 弹出序列 符合 压入数据的顺序,如果不为空,说明 弹出顺序 不符合压入顺序.


相关代码


import java.util.*;

public class Solution {
     
    public boolean IsPopOrder(int [] pushA,int [] popA) {
     
        // 先对参数进行合法性判断
       if(pushA ==null || popA ==null|| pushA.length != popA.length){
     
           return false;
       }       
        Stack<Integer> stack = new Stack<>();
        
        // 遍历入栈pushA的数组序列
        int i = 0;
        int j = 0;
        for(;i<pushA.length;i++){
     
            stack.push(pushA[i]);
           // 当入栈的元素等于出栈数组中对应的元素时,开始循环出栈,如果每次出栈的元素等于 出栈数组的元素,那么持续循环出栈
            while( !stack.empty() && stack.peek() == popA[j]){
     
                stack.pop();
                j++;
            }
           // 如果出栈的元素 不等于 出栈数组中对应的元素,那么在入栈
        }
        
        // 经过上面的循环之后,如果最后 stack 中的元素为空那么说明 弹出序列是正确的
        // 如果最后 stack 中的元素不为空,那么说明弹出序列是不正确的
        return stack.empty();
    }
}

四、二叉树的层序遍历


https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?


《剑指offer》专题—算法训练 day05_第3张图片


思路


《剑指offer》专题—算法训练 day05_第4张图片


如图所示,我们要把二叉树的每一层从左至右依次遍历节点

在这里呢,我们要借助队列的结构


0.root入 queue

1.队列queue 出一个节点

2.访问该节点

3.将当前节点的left 入队列(如果左子树不为空),再将当前节点的右子树 right 入队列(如果右子树不为空).


  我们就对上面的二叉树进行一次思路的层序遍历吧


首先1作为根节点入队
《剑指offer》专题—算法训练 day05_第5张图片

  1出队,保存出队的节点,放在ArrayList 返回的集合当中。将1的左子树入队,然后将1 的右子树入队(注意判空操作)
《剑指offer》专题—算法训练 day05_第6张图片

  2出队,保存出队的节点,放在ArrayList 返回的集合当中。将2的左子树入队,然后将2 的右子树入队(注意判空操作)
《剑指offer》专题—算法训练 day05_第7张图片

  3出队,保存出队的节点,放在ArrayList 返回的集合当中。将3的左子树入队,然后将3 的右子树入队(注意判空操作)
《剑指offer》专题—算法训练 day05_第8张图片

  4出队,保存出队的节点,放在ArrayList 返回的集合当中。将4的左子树入队,然后将4 的右子树入队(注意判空操作)
《剑指offer》专题—算法训练 day05_第9张图片

  就是依次循环这样的操作,直到queue 队列为空停止循环,返回 ArrayList 存放遍历结果的集合,就是题解.


相关代码


import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
     
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
     
   
        ArrayList<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
         if(root == null){
     
            return result;
        }
        
        // 先把根节点入队
        queue.offer(root);
        while(!queue.isEmpty()){
     
            // 根节点出队,访问出队的这个节点
            TreeNode p = queue.poll();
            result.add(p.val);
            // 当根节点有左子树,根节点的左子树入队
            if(p.left!=null){
     
                queue.offer(p.left);
            }
            // 当根节点有右子树,根节点的右子树入队
            if(p.right !=null){
     
                queue.offer(p.right);
            }
        }
        
        return result;
        
    }
}


  好了,今天的内容就结束了,希望大家多多练习~~



谢谢欣赏!!!


《剑指offer》 算法训练day6 敬请期待…



未完待续…

你可能感兴趣的