面试JAVA集合常用方法总结

ArrayList

基于动态数组实现，支持随机索引访问，访问索引的时间复杂度O(1)，非线程安全

ArrayList的排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class LCR074 {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(1);
        list.add(2);
        
		// 默认升序排序
        Collections.sort(list); 
        System.out.println(list); // 输出：[1, 2, 3]

        // 自定义降序排序
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1); // 降序
            }
        });
        System.out.println(list); // 输出：[3, 2, 1]
    }
}

LinkedList

基于双向链表实现，不支持随机索引访问，需要O(n)的时间复杂度遍历查找。但可以向头和尾以O(1)的时间复杂度插值。

HashMap

JDK1.7之前，HashMap是基于数组和链表实现的，JDK1.8之后，如果链表长度超过8，链表就转为红黑树。非线程安全

Hashmap的遍历：

import java.util.HashMap;

public class LCR074 {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("nihao",1);
        //遍历键值对
        for (HashMap.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
        //遍历键
        for (String key : map.keySet()) {
            System.out.println("Key: " + key);
        }
        //遍历值
        for (Integer value : map.values()) {
            System.out.println("Value: " + value);
        }
    }
}

Queue

队列是一种先进先出（FIFO）的数据结构，支持在队尾添加元素，在队头移除元素。在 Java 中，Queue 是一个接口，而 LinkedList 是 Queue 接口的一个实现类。

常用算法：bfs

import java.util.LinkedList;
import java.util.Queue;

public class BFSExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.println("Visited: " + current);

            // 添加邻接节点到队列
            queue.add(current + 1);
            queue.add(current + 2);
        }
    }
}

Stack

Stack 是 Java 中的一个类，继承自 Vector，用于实现后进先出（LIFO，Last In First Out）的栈数据结构。

常用算法：括号匹配、单调栈

括号匹配：使用栈检查括号是否成对匹配。

import java.util.Stack;

public class ParenthesesMatch {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>(); // 使用栈来存储左括号
        for (char c : s.toCharArray()) { // 遍历字符串中的每个字符
            // 如果是左括号，压入栈中
            if (c == '(' || c == '{' || c == '[') stack.push(c);
            // 如果是右括号，检查栈顶是否匹配
            else if (stack.isEmpty() || // 栈为空，说明没有匹配的左括号
                     (c == ')' && stack.pop() != '(') || // 弹出栈顶并检查是否匹配
                     (c == '}' && stack.pop() != '{') ||
                     (c == ']' && stack.pop() != '[')) return false; // 不匹配则返回 false
        }
        return stack.isEmpty(); // 如果栈为空，说明所有括号都匹配
    }

    public static void main(String[] args) {
        System.out.println(isValid("()[]{}")); // true
        System.out.println(isValid("([)]"));   // false
    }
}

单调栈：用于解决“下一个更大元素”类问题，栈中保持单调递减。

import java.util.Stack;

public class MonotonicStack {
    public static int[] nextGreaterElement(int[] nums) {
        int[] result = new int[nums.length]; // 存储结果的数组
        Stack<Integer> stack = new Stack<>(); // 单调栈，栈底到栈顶单调递减
        for (int i = nums.length - 1; i >= 0; i--) { // 从后往前遍历数组
            // 如果栈顶元素小于当前元素，弹出栈顶（维护单调性）
            while (!stack.isEmpty() && stack.peek() <= nums[i]) stack.pop();
            // 如果栈为空，说明没有更大的元素；否则栈顶就是下一个更大元素
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            // 将当前元素压入栈中
            stack.push(nums[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 2, 4, 3};
        int[] result = nextGreaterElement(nums);
        for (int num : result) System.out.print(num + " "); // 输出: 4 2 4 -1 -1
    }
}

PriorityQueue

优先队列，可以理解成有序的队列。

(1) 最小堆优先队列，优先返回队列中最小值

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个最小堆优先队列
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 添加元素
        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(20);
        minHeap.add(15);

        // 输出队列中的元素（按优先级顺序）
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // 输出: 5, 10, 15, 20
        }
    }
}

(2) 最大堆优先队列，优先返回队列中最大值

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个最大堆优先队列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        // 添加元素
        maxHeap.add(10);
        maxHeap.add(5);
        maxHeap.add(20);
        maxHeap.add(15);

        // 输出队列中的元素（按优先级顺序）
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 输出: 20, 15, 10, 5
        }
    }
}

(3) 自定义对象的优先队列，自己定义排序方式

import java.util.PriorityQueue;

public class PriorityQueue2DArray {
    public static void main(String[] args) {
        int[][] array = {
            {3, 5},
            {1, 2},
            {4, 1},
            {2, 8},
            {5, 7}
        };

        // 创建一个优先队列，按第 0 列排序（最小堆）
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        // 将二维数组的每一行加入优先队列
        for (int[] row : array) {
            minHeap.offer(row);
        }

        // 按优先级顺序输出
        while (!minHeap.isEmpty()) {
            int[] row = minHeap.poll();
            System.out.println("[" + row[0] + ", " + row[1] + "]");
        }
    }
}

常用算法：dijkstra

import java.util.*;

public class Dijkstra {

    // 定义图的边
    static class Edge {
        int target; // 目标节点
        int weight; // 边的权重

        public Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    // Dijkstra 算法实现
    public static int[] dijkstra(List<List<Edge>> graph, int start) {
        int n = graph.size(); // 图中节点的数量
        int[] dist = new int[n]; // 存储从起点到每个节点的最短距离
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化为无穷大
        dist[start] = 0; // 起点到自身的距离为 0

        // 优先队列（最小堆），按距离排序
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{start, 0}); // 将起点加入队列

        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // 取出当前距离最小的节点
            int node = current[0];
            int distance = current[1];

            // 如果当前节点的距离已经大于记录的最短距离，跳过
            if (distance > dist[node]) continue;

            // 遍历当前节点的所有邻居
            for (Edge edge : graph.get(node)) {
                int neighbor = edge.target;
                int newDist = dist[node] + edge.weight;

                // 如果找到更短的路径，更新距离并加入队列
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{neighbor, newDist});
                }
            }
        }

        return dist; // 返回起点到所有节点的最短距离
    }

    public static void main(String[] args) {
        // 示例：图的邻接表表示
        int n = 5; // 节点数量
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 添加边
        graph.get(0).add(new Edge(1, 4)); // 0 -> 1，权重 4
        graph.get(0).add(new Edge(2, 1)); // 0 -> 2，权重 1
        graph.get(1).add(new Edge(3, 1)); // 1 -> 3，权重 1
        graph.get(2).add(new Edge(1, 2)); // 2 -> 1，权重 2
        graph.get(2).add(new Edge(3, 5)); // 2 -> 3，权重 5
        graph.get(3).add(new Edge(4, 3)); // 3 -> 4，权重 3

        int start = 0; // 起点
        int[] dist = dijkstra(graph, start);

        // 输出结果
        System.out.println("从节点 " + start + " 到其他节点的最短距离：");
        for (int i = 0; i < n; i++) {
            System.out.println("到节点 " + i + " 的距离: " + dist[i]);
        }
    }
}