难度说明：🟢简单🟡中等🔴困难

学习资料

• 代码随想录

学习目标

• 掌握数据结构核心基础
• 借助数据结构完成常见题型

算法核心技巧

数据结构转化

1.常用转化

⚽集合类型转一维数组Object[]

// 集合类型 转 int[]: 流式转化
// set 转 int[]
res.stream().mapToInt(Integer::intValue).toArray();

// list 转 int[]
List<Integer> res = new ArrayList<>();
res.stream().mapToInt(Integer::valueOf).toArray();

⚽一维数组转集合类型

队列和栈

🔔堆

​ 堆（优先级队列），最常见使用优先级队列就是TOP K问题处理，选择构建大顶堆或者小顶堆。首先需要理解PriorityQueue中存储的内容以及需要比较的权值（决定堆的排序顺序）

​ 例如对于TOP K问题，定义Map<Integer,Integer>存储<元素，对应出现次数>，此处可以定义PriorityQueue<Integer>存储的是key(对应map中的key，但比较的权值是对应的value)

// 构建map存储每个元素的出现频率
Map<Integer, Integer> map = new HashMap<>();
for (int cur : nums) {
    map.put(cur, map.getOrDefault(cur, 0) + 1);
}
// 维护大顶堆(堆存储的元素是map的key值，比较的是value的大小)
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer key1, Integer key2) {
        return map.get(key2) - map.get(key1);
    }
});

​ 如果PriorityQueue要存储完整的key,value值，那么此处也可以定义PriorityQueue<Map.Entry<Integer,Integer>>

​ 当然，也可以定义int[][]二维数组来存储（参考239-滑动窗口最大值），每个行维度存储的是{数组元素,对应索引位置}，即val[i][0]表示数组元素，val[i][1]表示对应索引位置

// 构建大顶堆(int[]:{数组元素,对应索引位置})
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[0] - o1[0];
    }
});

​ 还有一种是基于类对象的设定，例如图论中PriorityQueue<Pair>，此处Pair就是一个类，里面定义了相关的属性，那么优先级队列就可以根据相关值来确定权值以此确定堆的排序顺序

PriorityQueue<Pair>
PriorityQueue<ListNode>    

算法题型总结篇

理论基础

1.核心理论

2.技巧总结

常见题型

01-xxx（123）

1.题目内容

2.题解思路

👻方法1：

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：