蓝桥杯刷题 Day 4 栈与链表

蓝桥杯刷题 Day 4 栈与链表

前言

今天写牛客网模板题中的数据结构模块：栈与列表

一、栈

原题地址: 栈

import java.util.*;

public class Stack1 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // 输入操作次数n以及字符串
        int n = input.nextInt();
        // 创建数组模拟栈操作
        int[] stack = new int[n];
        int size = 0;
        for (int i = 0; i < n; i++) {
            String pattern = input.next();
            switch (pattern){
                case "push":
                    int x = input.nextInt();
                    stack[size++] = x;
                    break;
                case "pop":
                    System.out.println(size == 0 ? "error" : stack[--size]); // --size，先将索引-1，再查找（改变栈，使出栈）
                    break;
                case "top":
                    System.out.println(size == 0? "error" : stack[size - 1]);
            }
        }
    }
}

1. 解题思路

栈是后入先出，将洗完的盘子叠好，再一个个地取出来用。

1. 用数组模拟出入栈

2. 拆解代码（不复杂，不拆了）

二、链表

import java.util.*;

public class Linked {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        MyList myList = new MyList();
        // 输入n个操作数
        int n = input.nextInt();
        // 处理指令
        for (int i = 0; i < n; i++) {
            String command = input.next();
            switch(command){
                case "insert":
                    int x = input.nextInt();
                    int y = input.nextInt();
                    myList.insert(x,y);
                    break;
                case "delete":
                    int num = input.nextInt();
                    myList.delete(num);
                    break;
            }
        }

        System.out.println(myList.print());
    }

    // 自定义列表类
    static class MyList{

        // 定义结构存储
        LinkedList<Integer> list = new LinkedList<>();

        // 插入
        public void insert(int x, int y){
            int position = list.indexOf(x); // indexOf()返回列表第一次出现的位置，lastindexOf()最后一次出现的位置
            if(position != -1){
                list.add(position, y); // 在position处插入，其余往后移
            }else {
                list.addLast(y); // 末尾插入
            }
        }

        // 删除
        public void delete(int x){
            list.remove(Integer.valueOf(x)); // 这样才能按值删除，若为int，则按索引删除
        }

        // 输出
        public String print(){
            if(list.isEmpty()) return "NULL";
            // 将列表转换成字符串输出
            StringBuilder sb = new StringBuilder();
            for(Integer num:list){
                sb.append(num).append(" ");
            }
            // trim()处理末尾空格
            return sb.toString().trim();
        }
    }
}

1. 解题思路

也没啥好说的，看题，写delete()和insert()方法

1.1 主函数

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        MyList myList = new MyList();
        // 输入n个操作数
        int n = input.nextInt();
        // 处理指令
        for (int i = 0; i < n; i++) {
            String command = input.next();
            switch(command){
                case "insert":
                    int x = input.nextInt();
                    int y = input.nextInt();
                    myList.insert(x,y);
                    break;
                case "delete":
                    int num = input.nextInt();
                    myList.delete(num);
                    break;
            }
        }

        System.out.println(myList.print());
    }

1.2 自定义列表类

 static class MyList{

        // 定义结构存储
        LinkedList<Integer> list = new LinkedList<>();
}

1.2.1 插入操作

public void insert(int x, int y){
            int position = list.indexOf(x); // indexOf()返回列表第一次出现的位置，lastindexOf()最后一次出现的位置
            if(position != -1){
                list.add(position, y); // 在position处插入，其余往后移
            }else {
                list.addLast(y); // 末尾插入
            }
        }

1.2.2 删除操作

public void delete(int x){
            list.remove(Integer.valueOf(x)); // 这样才能按值删除，若为int，则按索引删除
        }

1.2.3 按要求输出

 // 输出
        public String print(){
            if(list.isEmpty()) return "NULL";
            // 将列表转换成字符串输出
            StringBuilder sb = new StringBuilder();
            for(Integer num:list){
                sb.append(num).append(" ");
            }
            // trim()处理末尾空格
            return sb.toString().trim();
        }

三、 题后收获

3.1 知识点

1. list.indexOf()：返回列表第一次出现的位置
2. list.add(position, y); // 在position处插入，其余往后移
3. list.addLast(y); // 末尾插入
4. remove(object)与remove(int)：list.remove(Integer.valueOf(x));
5. 将列表转换成字符串输出
   StringBuilder sb = new StringBuilder();
   for(Integer num:list){
   sb.append(num).append(" ");
   }
   // trim()处理末尾空格
   return sb.toString().trim();