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

系统管理员 2022-08-28 07:50 84阅读 0赞

### 文章目录 ###

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

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

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

[https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?][https_www.nowcoder.com_practice_fc533c45b73a41b0b44ccba763f866ef]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70]

## 思路 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 2]

相关代码

/*
     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?][https_www.nowcoder.com_practice_4c776177d2c04c2494f2555c9fcc1e49]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]

## 思路 ##

>   很容易想到，在栈内部保存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?][https_www.nowcoder.com_practice_d77d11405cc7470d82554cb392585106]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 思路 ##

> 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?][https_www.nowcoder.com_practice_7fe2212963db4790b57431d9ed259701]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]

## 思路 ##

![在这里插入图片描述][3e756dcb9b6242a3a3ee528200143553.png]

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

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

> 0.root入 queue

> 1.队列queue 出一个节点

> 2.访问该节点

> 3.将当前节点的left 入队列（如果左子树不为空），再将当前节点的右子树 right 入队列（如果右子树不为空）.

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

> 首先1作为根节点入队  
> ![在这里插入图片描述][b08ac6daf4984962a0ad97ba52dba4a6.png]

>   1出队，保存出队的节点，放在ArrayList 返回的集合当中。将1的左子树入队，然后将1 的右子树入队（注意判空操作）  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]

>   2出队，保存出队的节点，放在ArrayList 返回的集合当中。将2的左子树入队，然后将2 的右子树入队（注意判空操作）  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]

>   3出队，保存出队的节点，放在ArrayList 返回的集合当中。将3的左子树入队，然后将3 的右子树入队（注意判空操作）  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 5]

>   4出队，保存出队的节点，放在ArrayList 返回的集合当中。将4的左子树入队，然后将4 的右子树入队（注意判空操作）  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 6]

>   就是依次循环这样的操作，直到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 敬请期待…**

# 未完待续… #

[https_www.nowcoder.com_practice_fc533c45b73a41b0b44ccba763f866ef]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70]: /images/20220828/14f2ed1c2839419c8ce9be721e7324e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 1]: /images/20220828/2435c1c1a23d429f9598f39e9965f115.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JhaW42Nw_size_16_color_FFFFFF_t_70 2]: /images/20220828/c2029becf3d14d08aa0fb96210a95e06.png
[https_www.nowcoder.com_practice_4c776177d2c04c2494f2555c9fcc1e49]: https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/04f464020169400aab80027fb8e51aa6.png
[https_www.nowcoder.com_practice_d77d11405cc7470d82554cb392585106]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/2f6df38b7dd140a1bce94d65f6fd10a6.png
[https_www.nowcoder.com_practice_7fe2212963db4790b57431d9ed259701]: https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/2c41a9d336554c0b8efe1cd39ff4e05d.png
[3e756dcb9b6242a3a3ee528200143553.png]: /images/20220828/1a0843bbbed54c91892370ca61cd5d27.png
[b08ac6daf4984962a0ad97ba52dba4a6.png]: /images/20220828/620603cc701c4b11933beedadf1e57f5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/4c2ba75d9eae4f779158ebecb888a2a0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/9c8835151cee47b9982783e7eff5a440.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/de78c5374b4943a9bb3481f0a7e51638.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/17c0f0c29c97487eab3ca0e59f8b281a.png