当前位置：网站首页>牛客刷题——剑指offer(第三期)

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

2022-08-02 09:48:00 【学好c语言的小王同学】

前言
作者简介：友友们大家好，我是你们的小王同学
个人主页：小王同学
系列专栏：牛客刷题专栏
推荐一款非常火的面试、刷题神器牛客网
觉得小王写的不错的话麻烦动动小手点赞收藏评论
今天给大家带来的刷题系列是：
剑指offer 链接：剑指offer

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

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 剪绳子

题目描述

解题思路

当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 删除链表的节点

题目描述

解题思路

既然是整个链表元素都不相同，我们要删除给定的一个元素，那我们首先肯定要找到这个元素，然后考虑删除它。
删除一个链表节点，肯定是断掉它的前一个节点指向它的指针，然后指向它的后一个节点，即越过了需要删除的这个节点。

代码详解

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