洛谷数据结构1-1线性表 java（持续更新）

技术笔记：算法与数据结构经典问题解析

本文将通过五道经典编程问题，讲解栈、哈希表、队列等数据结构的核心应用，以及在不同场景下的解题思路和代码实现技巧，帮助你掌握这些基础算法的实际应用。

一、 寄包柜操作（稀疏数据的哈希表存储）

题目核心要求

处理对n个寄包柜的q次操作，包括存入/清空物品和查询物品。寄包柜的格子数量未知且可能非常大，但实际操作的格子总数不超过10^7。

解题思路

这道题的核心挑战在于处理稀疏且大规模的潜在数据：

1. 数据结构选择：使用List<Map<Integer, Integer>>，为每个寄包柜分配一个哈希表。
   这样可以只存储有物品的格子，避免为稀疏数据分配巨大的数组空间。
2. 输入输出优化：使用BufferedReader和PrintWriter来加速输入和输出，
   应对q最大为10^5的情况。
3. 操作逻辑：对于存入操作，若k为0则从哈希表中移除该格子，否则更新值；
   对于查询操作，直接从对应哈希表中取值。

完整Java代码

importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterpw=newPrintWriter(System.out);StringTokenizerst=newStringTokenizer(br.readLine());intn=Integer.parseInt(st.nextToken());intq=Integer.parseInt(st.nextToken());List<Map<Integer,Integer>>lockers=newArrayList<>(n+1);for(inti=0;i<=n;i++){lockers.add(newHashMap<>());}for(inti=0;i<q;i++){st=newStringTokenizer(br.readLine());intop=Integer.parseInt(st.nextToken());intcabinet=Integer.parseInt(st.nextToken());intslot=Integer.parseInt(st.nextToken());if(op==1){intk=Integer.parseInt(st.nextToken());if(k==0){lockers.get(cabinet).remove(slot);}else{lockers.get(cabinet).put(slot,k);}}elseif(op==2){Map<Integer,Integer>map=lockers.get(cabinet);pw.println(map.get(slot));}}pw.flush();pw.close();br.close();}}

关键注意点

1. 空间效率：哈希表的方式避免了为每个寄包柜预分配巨大数组，只在有数据时才占用空间。
2. 时间效率：哈希表的增删改查操作时间复杂度都是O(1)，保证了操作的高效性。
3. 输入输出：StringTokenizer配合BufferedReader是处理大规模输入的高效组合，
   PrintWriter的批量输出也能显著提升性能。

二、 后缀表达式求值（栈的经典应用）

题目核心要求

计算一个包含+ - * /的后缀表达式的值，其中除法结果向0取整。

解题思路

这是栈的一个经典应用场景：

1. 核心原理：后缀表达式的计算天然适合用栈来处理。遇到数字就压栈，遇到运算符就弹出两个操作数进行计算，再将结果压栈。
2. 数字解析：遍历字符串，累积字符形成完整的数字，遇到.时将数字压入栈并重置。
3. 运算符处理：弹出栈顶两个元素（注意顺序，后弹出的是左操作数），根据运算符计算结果并压栈。

完整Java代码

importjava.util.Scanner;importjava.util.Stack;publicclassMain2{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Strings=sc.nextLine();Stack<Integer>stack=newStack<>();intn=0;for(inti=0;i<s.length();i++){charc=s.charAt(i);if(c>='0'&&c<='9'){n=n*10+(c-'0');}elseif(c=='.'){stack.push(n);n=0;}elseif(c=='@'){break;}else{intb=stack.pop();inta=stack.pop();intres=0;switch(c){case'+':res=a+b;break;case'-':res=a-b;break;case'*':res=a*b;break;case'/':res=a/b;break;}stack.push(res);}}System.out.println(stack.pop());sc.close();}}

关键注意点

1. 操作数顺序：后缀表达式中，运算符后面的是右操作数，前面的是左操作数，
   因此计算时要注意a和b的顺序。
2. 数字拼接：处理多位数时，需要通过n = n * 10 + (c - '0')来累积数字。
3. 终止条件：题目中以@作为表达式结束符，遇到时应立即停止计算。

三、 约瑟夫环问题（模拟与链表）

题目核心要求

n个人围成一圈，每次数到第m个人出列，输出所有人的出列顺序。

解题思路

这是一个经典的约瑟夫环问题，这里我们使用动态数组模拟：

1. 数据结构选择：使用ArrayList来模拟人群，因为它支持高效的随机访问和删除操作。
2. 核心算法：维护一个当前索引currentIndex，每次计算下一个要移除的人的索引为
   (currentIndex + m - 1) % people.size()，移除该元素并加入结果列表。
3. 循环终止条件：当模拟人群的列表为空时，所有元素都已出列。

完整Java代码

importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassMain3{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();List<Integer>people=newArrayList<>();for(inti=1;i<=n;i++){// 修正：学号从1开始people.add(i);}List<Integer>result=newArrayList<>();intcurrentIndex=0;while(!people.isEmpty()){currentIndex=(currentIndex+m-1)%people.size();result.add(people.remove(currentIndex));}// 输出结果for(intnum:result){System.out.print(num+" ");}sc.close();}}

关键注意点

1. 索引计算：(currentIndex + m - 1) % people.size()是核心公式，
   确保索引在列表范围内循环。
2. 元素移除：ArrayList的remove(index)操作会自动将后续元素前移，
   非常适合模拟出列的过程。
3. 初始编号：题目中的人是从1开始编号的，初始化列表时要注意这一点。

四、 机器翻译（LRU缓存模拟）

题目核心要求

模拟一个机器翻译软件的内存缓存机制，计算需要从外存（词典）中查询的次数。
内存容量为M，当满时，最早进入的单词会被移除。

解题思路

这是一个典型的LRU（最近最少使用）缓存问题的简化版本（这里是FIFO，先进先出）：

1. 数据结构选择：使用LinkedHashSet，它既可以像HashSet一样快速判断元素是否存在，
   又可以像链表一样维护插入顺序，方便移除最旧的元素。
2. 核心逻辑：对于每个单词，如果不在内存中，就需要查询词典（计数+1）。
   如果内存已满，就移除最旧的元素，再将新单词加入。
3. 效率保证：LinkedHashSet的contains、add和remove操作都是O(1)时间复杂度。

完整Java代码

importjava.util.*;publicclassMain4{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intM=sc.nextInt();intN=sc.nextInt();intcount=0;// 使用LinkedHashSet来维护内存中的单词，它可以保持插入顺序Set<Integer>memory=newLinkedHashSet<>();for(inti=0;i<N;i++){intword=sc.nextInt();if(!memory.contains(word)){count++;if(memory.size()>=M){intfirst=memory.iterator().next();memory.remove(first);}memory.add(word);}}System.out.println(count);sc.close();}}

关键注意点

1. 缓存淘汰策略：题目中是“清空最早进入内存的那个单词”，即FIFO策略，
   LinkedHashSet完美契合这种需求。
2. 计数逻辑：只有当单词不在内存中时，才需要增加查询次数。
3. 边界处理：当内存未满时，直接添加新单词；只有当内存已满时，才需要淘汰最旧的。

五、 平衡括号生成（栈与括号匹配）

题目核心要求

给定一个由( ) [ ]组成的字符串，使其成为一个平衡括号序列。
对于无法匹配的括号，在其旁边添加一个匹配的括号。

解题思路

这道题是经典括号匹配问题的扩展：

1. 核心数据结构：使用一个栈来记录所有左括号在结果字符串中的位置。
2. 遍历处理：
   • 遇到左括号(或[，直接加入结果，并将其位置压入栈。
   • 遇到右括号)或]，检查栈顶的左括号是否能匹配。
     若能匹配，则弹出栈顶并加入右括号；若不能匹配，则直接加入一对完整的括号。
3. 收尾处理：遍历结束后，栈中可能还有未匹配的左括号，
   需要在它们的右边补充对应的右括号。

完整Java代码

importjava.util.*;publicclassMain5{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Strings=sc.next();StringBuilderres=newStringBuilder();Deque<Integer>stack=newLinkedList<>();for(charc:s.toCharArray()){if(c=='('||c=='['){res.append(c);// 记录该左括号在res中的下标（res长度-1就是最后一个字符的索引），压入栈顶stack.push(res.length()-1);}else{if(c==')'){if(!stack.isEmpty()&&res.charAt(stack.peek())=='('){stack.pop();res.append(')');}else{res.append("()");}}elseif(c==']'){if(!stack.isEmpty()&&res.charAt(stack.peek())=='['){stack.pop();res.append(']');}else{res.append("[]");}}}}while(!stack.isEmpty()){intidx=stack.pop();charleft=res.charAt(idx);res.insert(idx+1,left=='('?')':']');}System.out.println(res.toString());}}

关键注意点

1. 栈的作用：栈不仅用于判断括号是否匹配，还记录了左括号的位置，
   这使得我们可以在最后为未匹配的左括号补充右括号。
2. 结果构建：使用StringBuilder来动态构建结果字符串，效率比直接拼接字符串高。
3. 插入操作：StringBuilder的insert方法可以在指定位置插入字符，
   非常适合为栈中剩余的左括号补充右括号。