企业手机建站系统,深圳建设网站企业,网站建设开发ppt模板,网站模板后台技术笔记#xff1a;算法与数据结构经典问题解析 本文将通过五道经典编程问题#xff0c;讲解栈、哈希表、队列等数据结构的核心应用#xff0c;以及在不同场景下的解题思路和代码实现技巧#xff0c;帮助你掌握这些基础算法的实际应用。 一、 寄包柜操作#xff08;稀疏…技术笔记算法与数据结构经典问题解析本文将通过五道经典编程问题讲解栈、哈希表、队列等数据结构的核心应用以及在不同场景下的解题思路和代码实现技巧帮助你掌握这些基础算法的实际应用。一、 寄包柜操作稀疏数据的哈希表存储题目核心要求处理对n个寄包柜的q次操作包括存入/清空物品和查询物品。寄包柜的格子数量未知且可能非常大但实际操作的格子总数不超过10^7。解题思路这道题的核心挑战在于处理稀疏且大规模的潜在数据数据结构选择使用ListMapInteger, Integer为每个寄包柜分配一个哈希表。这样可以只存储有物品的格子避免为稀疏数据分配巨大的数组空间。输入输出优化使用BufferedReader和PrintWriter来加速输入和输出应对q最大为10^5的情况。操作逻辑对于存入操作若k为0则从哈希表中移除该格子否则更新值对于查询操作直接从对应哈希表中取值。完整Java代码importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));PrintWriterpwnewPrintWriter(System.out);StringTokenizerstnewStringTokenizer(br.readLine());intnInteger.parseInt(st.nextToken());intqInteger.parseInt(st.nextToken());ListMapInteger,IntegerlockersnewArrayList(n1);for(inti0;in;i){lockers.add(newHashMap());}for(inti0;iq;i){stnewStringTokenizer(br.readLine());intopInteger.parseInt(st.nextToken());intcabinetInteger.parseInt(st.nextToken());intslotInteger.parseInt(st.nextToken());if(op1){intkInteger.parseInt(st.nextToken());if(k0){lockers.get(cabinet).remove(slot);}else{lockers.get(cabinet).put(slot,k);}}elseif(op2){MapInteger,Integermaplockers.get(cabinet);pw.println(map.get(slot));}}pw.flush();pw.close();br.close();}}关键注意点空间效率哈希表的方式避免了为每个寄包柜预分配巨大数组只在有数据时才占用空间。时间效率哈希表的增删改查操作时间复杂度都是O(1)保证了操作的高效性。输入输出StringTokenizer配合BufferedReader是处理大规模输入的高效组合PrintWriter的批量输出也能显著提升性能。二、 后缀表达式求值栈的经典应用题目核心要求计算一个包含 - * /的后缀表达式的值其中除法结果向0取整。解题思路这是栈的一个经典应用场景核心原理后缀表达式的计算天然适合用栈来处理。遇到数字就压栈遇到运算符就弹出两个操作数进行计算再将结果压栈。数字解析遍历字符串累积字符形成完整的数字遇到.时将数字压入栈并重置。运算符处理弹出栈顶两个元素注意顺序后弹出的是左操作数根据运算符计算结果并压栈。完整Java代码importjava.util.Scanner;importjava.util.Stack;publicclassMain2{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringssc.nextLine();StackIntegerstacknewStack();intn0;for(inti0;is.length();i){charcs.charAt(i);if(c0c9){nn*10(c-0);}elseif(c.){stack.push(n);n0;}elseif(c){break;}else{intbstack.pop();intastack.pop();intres0;switch(c){case:resab;break;case-:resa-b;break;case*:resa*b;break;case/:resa/b;break;}stack.push(res);}}System.out.println(stack.pop());sc.close();}}关键注意点操作数顺序后缀表达式中运算符后面的是右操作数前面的是左操作数因此计算时要注意a和b的顺序。数字拼接处理多位数时需要通过n n * 10 (c - 0)来累积数字。终止条件题目中以作为表达式结束符遇到时应立即停止计算。三、 约瑟夫环问题模拟与链表题目核心要求n个人围成一圈每次数到第m个人出列输出所有人的出列顺序。解题思路这是一个经典的约瑟夫环问题这里我们使用动态数组模拟数据结构选择使用ArrayList来模拟人群因为它支持高效的随机访问和删除操作。核心算法维护一个当前索引currentIndex每次计算下一个要移除的人的索引为(currentIndex m - 1) % people.size()移除该元素并加入结果列表。循环终止条件当模拟人群的列表为空时所有元素都已出列。完整Java代码importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;publicclassMain3{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();ListIntegerpeoplenewArrayList();for(inti1;in;i){// 修正学号从1开始people.add(i);}ListIntegerresultnewArrayList();intcurrentIndex0;while(!people.isEmpty()){currentIndex(currentIndexm-1)%people.size();result.add(people.remove(currentIndex));}// 输出结果for(intnum:result){System.out.print(num );}sc.close();}}关键注意点索引计算(currentIndex m - 1) % people.size()是核心公式确保索引在列表范围内循环。元素移除ArrayList的remove(index)操作会自动将后续元素前移非常适合模拟出列的过程。初始编号题目中的人是从1开始编号的初始化列表时要注意这一点。四、 机器翻译LRU缓存模拟题目核心要求模拟一个机器翻译软件的内存缓存机制计算需要从外存词典中查询的次数。内存容量为M当满时最早进入的单词会被移除。解题思路这是一个典型的LRU最近最少使用缓存问题的简化版本这里是FIFO先进先出数据结构选择使用LinkedHashSet它既可以像HashSet一样快速判断元素是否存在又可以像链表一样维护插入顺序方便移除最旧的元素。核心逻辑对于每个单词如果不在内存中就需要查询词典计数1。如果内存已满就移除最旧的元素再将新单词加入。效率保证LinkedHashSet的contains、add和remove操作都是O(1)时间复杂度。完整Java代码importjava.util.*;publicclassMain4{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intMsc.nextInt();intNsc.nextInt();intcount0;// 使用LinkedHashSet来维护内存中的单词它可以保持插入顺序SetIntegermemorynewLinkedHashSet();for(inti0;iN;i){intwordsc.nextInt();if(!memory.contains(word)){count;if(memory.size()M){intfirstmemory.iterator().next();memory.remove(first);}memory.add(word);}}System.out.println(count);sc.close();}}关键注意点缓存淘汰策略题目中是“清空最早进入内存的那个单词”即FIFO策略LinkedHashSet完美契合这种需求。计数逻辑只有当单词不在内存中时才需要增加查询次数。边界处理当内存未满时直接添加新单词只有当内存已满时才需要淘汰最旧的。五、 平衡括号生成栈与括号匹配题目核心要求给定一个由( ) [ ]组成的字符串使其成为一个平衡括号序列。对于无法匹配的括号在其旁边添加一个匹配的括号。解题思路这道题是经典括号匹配问题的扩展核心数据结构使用一个栈来记录所有左括号在结果字符串中的位置。遍历处理遇到左括号(或[直接加入结果并将其位置压入栈。遇到右括号)或]检查栈顶的左括号是否能匹配。若能匹配则弹出栈顶并加入右括号若不能匹配则直接加入一对完整的括号。收尾处理遍历结束后栈中可能还有未匹配的左括号需要在它们的右边补充对应的右括号。完整Java代码importjava.util.*;publicclassMain5{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringssc.next();StringBuilderresnewStringBuilder();DequeIntegerstacknewLinkedList();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()){intidxstack.pop();charleftres.charAt(idx);res.insert(idx1,left(?):]);}System.out.println(res.toString());}}关键注意点栈的作用栈不仅用于判断括号是否匹配还记录了左括号的位置这使得我们可以在最后为未匹配的左括号补充右括号。结果构建使用StringBuilder来动态构建结果字符串效率比直接拼接字符串高。插入操作StringBuilder的insert方法可以在指定位置插入字符非常适合为栈中剩余的左括号补充右括号。