MyBlog3：4月5日
LeetCode239滑动窗口最大值
import java.util.LinkedList;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(k < 1 || nums == null || nums.length<k)return null;
LinkedList<Integer> list = new LinkedList<>();
int[] res = new int[nums.length - k + 1]; //所有元素-窗口范围的元素为实际窗口移动次数，再加上窗口包住的也会生成一个相对最大值
int index = 0;
for (int i = 0; i < nums.length; i++) { //数组中的每个元素都会进入队列一次
//新进来的元素会和队列中从后往前依次比较，如果是比新进来的小的，把它弹出
while (!list.isEmpty() && nums[list.peekLast()] <= nums[i])
list.pollLast();
//把新来的加进去,也是从尾部加
list.addLast(i);
//判断元素过期？元素过期，恰好在边界处
if (list.peekFirst() == i - k) list.pollFirst();
if (i >= k - 1) res[index++] = nums[list.peekFirst()];//list保存的是索引
}
return res;
}
}
LeetCode20有效的括号
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] s_charArray = s.toCharArray();
for(int i = 0 ; i < s_charArray.length ; i++){
var c = s_charArray[i];
if(c == '{' || c == '[' || c == '(')stack.push(c);
else if(c == '}'){
if(stack.isEmpty() || stack.peek() != '{')return false;
stack.pop();
}
else if(c == ']'){
if(stack.isEmpty() || stack.peek() != '[')return false;
stack.pop();
}
else if(c == ')'){
if(stack.isEmpty() || stack.peek() != '(')return false;
stack.pop();
}
}
if(!stack.isEmpty())return false;
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
顺序栈
/**
* @Author: 幸幸
* @Date: 2023/04/05/16:46
* @Description: 4月5日顺序栈
*/
public class MySqStack4_5 <E> { //泛型类
private static final int initCapacity = 10;
private int capacity;
private E[] data; //存放元素的数组
private int top = -1; //栈顶指针 : 指向栈顶元素
public MySqStack4_5(){
data = (E[]) new Object[initCapacity];//初始化1个长度为10的数组
capacity = initCapacity; //capacity 时刻记录 大小
top = -1;
}
//改变顺序栈的容量
public void updateCapacity(int newCapacity){
//定义一个新容量的数组
E[] newData = (E[])new Object[newCapacity];
//将data中的数组拷贝到新数组中
for(int i = 0 ; i < data.length;i++){
newData[i] = data[i];
}
//将newData的地址 赋 给 data数组
data = newData;
capacity = newCapacity;
}
//判断栈是否为空的方法
public boolean isEmpty(){
return top == -1; //栈顶指针没有指向任何数据
}
//栈的push 方法
//每次push新元素，都判断top指针是否到了栈的最大下标了
public void push(E e){
if(top == capacity-1) updateCapacity(capacity*2);//如果top指针到了最大下标,两倍扩容
top ++;
data[top] = e;
}
//pop出栈方法
public E pop(){
if(isEmpty())throw new RuntimeException("栈空无法pop");
//先取走 该元素,再将top--, 虽然该元素依旧在数组中,但0-top 才是有效元素范围，不用就行
E e = data[top];
top--;
if(capacity > initCapacity && top+1 == capacity/4)updateCapacity(capacity/2);
return e;
}
//peek 观察栈顶元素
public E peek(){
if(isEmpty())throw new RuntimeException("栈空无法peek");
E e = data[top];
return e;
}
}
判断出栈序列是否合法
import java.util.Stack;
/**
* @Author: 幸幸
* @Date: 2023/04/05/20:37
* @Description:
*/
public class IsLegalStackSequence {
public static void main(String[] args) {
int[] sequenceA = {1,3,2,4};
int[] sequenceB = {1,2,3,4};
System.out.println(isLegalStackSequenceWay1(sequenceA,sequenceB));
System.out.println(isLegalStackSequenceWay2(sequenceA,sequenceB));
}
public static boolean isLegalStackSequenceWay1(int[] sequenceA, int[] sequenceB) {
//sequenceA为进栈序列，sequenceB为出栈序列，判断是否sequenceB为合法出栈序列
if(sequenceA.length != sequenceB.length)return false;
int topA = 0, topB = 0;
int len = sequenceA.length;
Stack<Integer> stack = new Stack<>();
while(topA<len && topB<len){
if(stack.isEmpty() || stack.peek() != sequenceB[topB]){//如果栈为空或者栈顶元素和B序列对应的topB位置不同，A序列的值继续进栈
stack.push(sequenceA[topA]);
topA++;
}else{ //stack栈 不为空且栈顶元素==B序列对应的topB的值
stack.pop();
topB++;
}
}
while(!stack.isEmpty() && stack.peek() == sequenceB[topB]){
//上一个循环topA肯定先==len跳出while，此while为了确保元素全比较完。如果不是合法的出栈序列，最后栈内肯定剩下元素且topB的值小于len
stack.pop();
topB++;
}
if(topB == len) return true;
return false;
}
public static boolean isLegalStackSequenceWay2(int[] sequenceA, int[] sequenceB){
if(sequenceA.length != sequenceB.length)return false;
int topA = 0, topB = 0;
int len = sequenceA.length;
Stack<Integer> stack = new Stack<>();
while(topA<len){ //跳出while，说明sequenceA的所有元素一定全放入了栈
stack.push(sequenceA[topA]);
topA++;
while (!stack.isEmpty() && stack.peek()==sequenceB[topB]){
stack.pop();
topB++;
}
}
return stack.isEmpty();
}
}
链栈（带头节点）
/**
* @Author: 幸幸
* @Date: 2023/04/05/21:17
* @Description: 带有头节点的链栈
*/
public class MyLinkedStack<E> {
//成员变量
Node<E> headNode;
public MyLinkedStack(){
headNode = new Node<>();
}
public boolean isEmpty(){
return headNode.next==null; // 如果头节点的next域下没有结点，则为空
}
public void push(E e){
//链栈由一个个节点构成
Node<E> newNode = new Node<>(e);
newNode.next = headNode.next; //将头节点后边的内容先 连在新节点后面,先进来的节点会慢慢往后面跑
headNode.next = newNode;
}
public E pop(){
if(isEmpty()){
throw new RuntimeException("栈空不能pop");
}
E res = headNode.next.data;
headNode.next = headNode.next.next;
return res;
}
public E peek(){
if(isEmpty()){
throw new RuntimeException("栈空不能peek");
}
E res = headNode.next.data;
return res;
}
}
今天是4月5日，清明放假。最近情绪有点低落。可能是感觉自己什么都学不会吧。学了也很快忘记了。都不知道以后能干些什么。
后悔转专业，后悔参加考试，后悔当时没直接工作的念头一直徘徊在脑海中，也真是够累的.
标签：return,int,top,stack,new,public,MyBlog3 From： https://www.cnblogs.com/DoubleLucky/p/17291032.html