牛客刷题——剑指offer(第三期)

** 💟💟前言**

🥇作者简介：友友们大家好，我是你们的小王同学😗😗

🥈个人主页：小王同学🚗****

🥉 系列专栏：牛客刷题专栏📖

📑 推荐一款非常火的面试、刷题神器👉牛客网

觉得小王写的不错的话 麻烦动动小手 点赞👍 收藏⭐ 评论📄

今天给大家带来的刷题系列是：

剑指offer 链接：👉 剑指offer

** 里面有非常多的题库 跟面经知识 真的非常良心了！！**

JZ9 用两个栈实现队列🍔

JZ9 用两个栈实现队列

题目描述🍔

解题思路🍔

借助栈的先进后出规则模拟实现队列的先进先出

1、当插入时，直接插入 stack1

2、当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素

代码详解🍔

import java.util.*;
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
        
        
    }
    
    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    
    }
}

**过辣 这道题 思路出来了 就好写了！~ **

JZ14 剪绳子🍔

JZ14 剪绳子

题目描述🍔

解题思路🍔

• 当n<3时 直接计算即可
• 用dp数组表示长度为i的绳子可以被剪出来的最大乘积，初始化前面4个的规律很好推出
• 遍历每个长度，对于每个长度的最大乘积，可以遍历从1到i的每个固定一段，按照上述公式求的最大值。
• 数组最后一个就是最大值

代码详解🍔

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int cutRope (int n) {
        
        if(n<=3){
            return n-1;
        }
        int dp[]=new int[n+1]; //dp[i]表示长度为i的绳子剪出来的最大乘积
        //初始化 dp 前四段长度的乘积
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=4;
        //遍历后面的长度
        for(int i=5;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            }
                
                
        }
            return dp[n];
            
           // write code here
    }
}     

JZ18 删除链表的节点🍔

JZ18 删除链表的节点

题目描述🍔

解题思路🍔

既然是整个链表元素都不相同，我们要删除给定的一个元素，那我们首先肯定要找到这个元素，然后考虑删除它。

删除一个链表节点，肯定是断掉它的前一个节点指向它的指针，然后指向它的后一个节点，即越过了需要删除的这个节点。

代码详解🍔

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        //加入一个虚拟头结点
        ListNode res= new ListNode(0);
        res.next=head;
        //前序节点
        ListNode pre= res;
        ListNode cur =head;
        
        while(cur!=null){
            //如果找到当前节点
            if(cur.val==val){
                //断开连接
                pre.next=cur.next;
                break;
            }
            
            pre=cur;
            cur=cur.next;
            
            
        }
        //返回删除后链表的头节点
        return res.next;
    
        
        
        
        
        
        
        // write code here
    }
}

牛客是一款不论是面试 还是刷题 都是非常有用的 还等什么注册起来吧！👉👉 全部动态_牛客网 (nowcoder.com)