老男孩linux网站gps建站教程

张

张建站

2026/4/7 19:48:48

10分钟阅读

老男孩linux网站,gps建站教程,vc 做网站源码,企业平台的作用在LeetCode刷题或实际后端开发中#xff0c;选择合适的数据结构往往比算法逻辑本身更能决定代码的简洁度与运行效率。Java提供了庞大的集合框架#xff08;Java Collections Framework#xff09;#xff0c;但在算法竞赛或笔试中#xff0c;我们需要关注的仅仅是其中最核…在LeetCode刷题或实际后端开发中选择合适的数据结构往往比算法逻辑本身更能决定代码的简洁度与运行效率。Java提供了庞大的集合框架Java Collections Framework但在算法竞赛或笔试中我们需要关注的仅仅是其中最核心、最高效的那一部分。主要讲解常用的数据结构接口涉及的LeetCode题不做详解。一、线性容器的核心Deque, Queue 与 Stack在早期的Java版本JDK 1.0中java.util.Stack是实现栈的标准类。然而在现代Java开发JDK 1.6中官方已强烈不推荐使用Stack类。1.1 为什么要抛弃 Stackjava.util.Stack继承自java.util.Vector。性能问题Vector的所有方法都是synchronized同步的。这意味着在单线程的算法题环境中每次方法调用都会有不必要的锁开销Lock Overhead严重影响执行效率。设计缺陷作为一个“栈”它竟然允许通过索引随机访问元素因为它继承了Vector这破坏了栈“后进先出”LIFO的封装原则。最佳实践在Java中无论是需要栈Stack还是队列Queue统一使用java.util.Deque接口并优先选择ArrayDeque作为实现类。1.2 Deque 接口详解Deque全称Double Ended Queue双端队列它既可以从头部插入/删除也可以从尾部插入/删除。因此它即可以完全模拟栈也可以完全模拟队列。Deque定义了两套操作方法的API一套在操作失败时抛出异常另一套返回特殊值null或false。在算法题中为了避免未捕获的异常导致程序崩溃或者为了通过返回值判断边界条件通常推荐使用返回特殊值的方法除了模拟栈时的pop。操作类型抛出异常 (Throws Exception)返回特殊值 (Special Value)说明插入 (Tail)add(e)/addLast(e)offer(e)/offerLast(e)队尾插入 (Queue的入队)插入 (Head)addFirst(e)/push(e)offerFirst(e)队头插入 (Stack的入栈)删除 (Head)remove()/removeFirst()/pop()poll()/pollFirst()队头移除 (Queue出队 / Stack出栈)删除 (Tail)removeLast()pollLast()队尾移除查看 (Head)element()/getFirst()peek()/peekFirst()查看队头 (Stack/Queue peek)查看 (Tail)getLast()peekLast()查看队尾(注push()和pop()是 Deque 为了模拟 Stack 专门命名的方法它们本质上等同于addFirst()和removeFirst()。)图示1.3 实现类对比ArrayDeque vs LinkedListDeque接口有两个主要的实现类ArrayDeque和LinkedList。在95%的算法题场景下ArrayDeque优于LinkedList。ArrayDeque (数组双端队列)底层实现基于循环数组Circular Array实现维护head和tail指针。扩容机制当数组满时容量翻倍Double Capacity并通过位运算优化下标计算。优点内存紧凑直接在数组中存储对象引用没有额外的节点对象Node开销。缓存友好数组在内存中是连续的CPU缓存命中率高。速度快大多数操作是平摊O ( 1 ) O(1)O(1)且常数因子极小。缺点不支持存储null值。LinkedList (链表双端队列)底层实现双向链表Doubly Linked List每个元素是一个Node对象包含prev,next和item。优点支持存储null值虽然在算法题中很少用到。扩容时不需要复制整个数组但每次插入都需要new Node。缺点内存碎片化大量节点散落在堆内存中。GC压力频繁的入队出队会创建和销毁大量Node对象增加垃圾回收压力。缓存差非连续内存CPU访问慢。结论除非题目明确要求操作链表节点否则一律使用ArrayDeque。1.4 常用代码模板场景一模拟栈 (Stack) - LIFO// 声明与初始化DequeIntegerstacknewArrayDeque();// 入栈 (注意使用 push语义清晰)stack.push(1);stack.push(2);// 查看栈顶inttopstack.peek();// 返回 2// 出栈 (注意如果栈为空pop会抛异常poll会返回null)// 推荐在确定非空时用 pop或者检查 isEmpty()while(!stack.isEmpty()){System.out.println(stack.pop());}场景二模拟队列 (Queue) - FIFO// 声明与初始化接口可以用 Queue也可以用 DequeQueueIntegerqueuenewArrayDeque();// 或者 DequeInteger queue new ArrayDeque();// 入队 (使用 offer比 add 安全)queue.offer(1);queue.offer(2);// 查看队头intheadqueue.peek();// 返回 1// 出队while(!queue.isEmpty()){System.out.println(queue.poll());}场景三双端操作 (如滑动窗口)DequeIntegerdequenewArrayDeque();// 队尾加队头出标准队列deque.offerLast(1);deque.pollFirst();// 队头加队尾出特殊逻辑deque.offerFirst(2);deque.pollLast();1.5 对应的 LeetCode 例题栈的应用LeetCode 20. Valid Parentheses (有效的括号)简述利用栈的匹配特性左括号入栈右括号匹配出栈。classSolution{privatestaticfinalMapCharacter,CharacterMAPnewHashMap();static{MAP.put((,));MAP.put({,});MAP.put([,]);}publicbooleanisValid(Strings){if(s.length()%2!0)returnfalse;DequeCharacterstacknewArrayDeque();for(Characterc:s.toCharArray()){if(MAP.containsKey(c)){stack.push(MAP.get(c));}else{if(stack.isEmpty()||stack.pop()!c)returnfalse;}}returnstack.isEmpty();}}二、优先队列PriorityQueuePriorityQueue是算法题中处理“Top K”、“中位数”、“贪心策略”等问题的神器。它在Java中基于二叉堆Binary Heap实现默认是一个小顶堆Min-Heap。2.1 核心特性时间复杂度入队 (offer):O ( log ⁡ n ) O(\log n)O(logn)出队 (poll):O ( log ⁡ n ) O(\log n)O(logn)查看堆顶 (peek):O ( 1 ) O(1)O(1)注意remove(Object o)操作需要先查找元素复杂度为O ( n ) O(n)O(n)应尽量避免。底层动态数组。排序它并不保证内部数组是有序的它只保证**堆顶head**是按照规则排列的最值。因此切勿使用for循环直接遍历 PriorityQueue遍历出来的顺序是无序的。必须通过while(!pq.isEmpty()) { pq.poll(); }来获取有序序列。2.2 定义比较规则 (Comparator)这是使用PriorityQueue的难点。你需要告诉它如何定义“优先级”。默认小顶堆 (Min-Heap)保存整数时队头是最小值。PriorityQueueIntegerminHeapnewPriorityQueue();minHeap.offer(10);minHeap.offer(5);System.out.println(minHeap.peek());// 输出 5自定义大顶堆 (Max-Heap)需要传入Comparator。在Java 8 中推荐使用 Lambda 表达式。// 写法 1Lambda 表达式 (推荐)// (a, b) - b - a 表示降序。注意处理溢出风险严谨写法是 (a, b) - Integer.compare(b, a)PriorityQueueIntegermaxHeapnewPriorityQueue((a,b)-b-a);// 写法 2Collections.reverseOrder()PriorityQueueIntegermaxHeap2newPriorityQueue(Collections.reverseOrder());复杂对象排序假设有一个int[]数组表示[value, index]我们要根据value降序排列PriorityQueueint[]pqnewPriorityQueue((a,b)-{// 比较两个数组的第一个元素returnb[0]-a[0];});2.3 常用 API 细节方法描述注意事项offer(E e)插入元素如果违反容量限制可能抛错但在PQ中通常会自动扩容。peek()获取堆顶元素堆为空返回null。poll()获取并移除堆顶堆为空返回null。这是获取有序数据的唯一方式。size()获取元素个数O ( 1 ) O(1)O(1)。remove(Object o)移除特定对象O ( n ) O(n)O(n)。如果需要频繁移除任意节点说明你不应该只用 PriorityQueue可能需要配合 Hash辅助或使用TreeSet。2.4 对应的 LeetCode 例题Top K 问题LeetCode 215. Kth Largest Element in an Array (数组中的第K个最大元素)简述维护一个大小为 K 的小顶堆。遍历数组元素入堆当堆大小超过 K 时poll()。最后堆顶即为第 K 大。三、哈希表HashMapHashMap是解决算法题中最通用的数据结构用于处理映射关系、计数、去重HashSet等。Java 的 HashMap 在 JDK 1.8 进行了重大优化引入了红黑树Red-Black Tree来处理哈希冲突严重的桶。3.1 核心机制简述Key-Value键值对存储。Key 必须覆写hashCode()和equals()方法Integer, String 等内置类已实现。时间复杂度理想情况下put和get均为O ( 1 ) O(1)O(1)。最坏情况全部碰撞JDK 8 为O ( log ⁡ n ) O(\log n)O(logn)红黑树JDK 7 为O ( n ) O(n)O(n)链表。无序性HashMap不保证遍历顺序。如果需要插入顺序使用LinkedHashMap如果需要按 Key 排序使用TreeMap。3.2 必须掌握的高效 API在算法题中代码的精简程度直接影响编写速度。掌握 JDK 8 新增的 Map 方法至关重要。getOrDefault(Object key, V defaultValue)场景统计词频。如果 key 存在则取值不存在则返回默认 0。旧写法if(map.containsKey(num)){map.put(num,map.get(num)1);}else{map.put(num,1);}新写法 (优雅)map.put(num,map.getOrDefault(num,0)1);putIfAbsent(K key, V value)场景只有当 key 不存在时才插入。// 构建图的邻接表时常用map.putIfAbsent(u,newArrayList());map.get(u).add(v);computeIfAbsent(K key, Function mappingFunction)场景同上但更高效。如果 key 存在直接返回 value如果不存在执行函数创建 value放入 map 并返回。// 邻接表构建的一行代码流// 如果 u 对应的 list 不存在new 一个然后 add(v)map.computeIfAbsent(u,k-newArrayList()).add(v);3.3 遍历 HashMap在算法题中我们经常需要遍历 Map。方式一遍历 Key (KeySet)for(Integerkey:map.keySet()){Integervaluemap.get(key);// 再进行一次哈希查找// ...}效率一般因为get(key)需要再次计算哈希。方式二遍历 Entry (EntrySet) -推荐for(Map.EntryInteger,Integerentry:map.entrySet()){Integerkeyentry.getKey();Integervalueentry.getValue();// ...}效率最高直接拿到键和值无需二次查找。方式三遍历 Valuesfor(Integerval:map.values()){// 只能获取值无法获取键}3.4 对应的 LeetCode 例题基础哈希LeetCode 1. Two Sum (两数之和)简述利用 Map 存储target - current_value的索引实现O ( n ) O(n)O(n)查找。classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.length;i){intjtarget-nums[i];if(map.containsKey(j)){returnnewint[]{i,map.get(j)};}map.put(nums[i],i);}returnnewint[0];}}四、常用的辅助类与数组技巧实际写算法时离不开java.util.Arrays和java.util.Collections以及String的处理。4.1 数组与集合工具类排序Arrays.sort(int[] a): 对基本类型数组排序双轴快速排序不稳定。Collections.sort(ListT list): 对列表排序TimSort归并排序的优化版稳定。数组转列表Arrays.asList(T... a): 返回一个固定长度的列表。不要对其进行add或remove操作会抛出UnsupportedOperationException。正确做法new ArrayList(Arrays.asList(1, 2, 3))。4.2 字符串处理StringBuilder在Java中String是不可变的。如果在循环中进行字符串拼接s a会产生大量临时对象O ( n 2 ) O(n^2)O(n2)的复杂度。必须使用StringBuilderStringBuildersbnewStringBuilder();for(inti0;i100;i){sb.append(i);// O(1)}Stringressb.toString();// sb.reverse() // 翻转字符串神器// sb.deleteCharAt(sb.length() - 1) // 回溯算法中常用的撤销操作五、总结与建议栈 (LIFO)→ \rightarrow→DequeT stack new ArrayDeque();(用push/pop/peek)队列 (FIFO)→ \rightarrow→QueueT queue new ArrayDeque();(用offer/poll/peek)优先队列→ \rightarrow→PriorityQueueT pq new PriorityQueue();(注意 Comparator 的写法)哈希映射→ \rightarrow→HashMapK, V map new HashMap();(熟练getOrDefault和computeIfAbsent)哈希集合→ \rightarrow→HashSetT set new HashSet();(去重专用)避免使用Stack类避免使用Vector在非特定场景下尽量避免使用LinkedList。理解ArrayDeque的环形数组实现和HashMap的哈希桶机制。