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