堆:Heap
可以迅速找到一堆数中最大或者最小值的数据结构
将根节点最大的堆叫做大顶堆或大根堆，根节点最小的堆叫做小顶堆或小根堆
常见的堆有二叉堆或斐波那契堆
假设是大顶堆，则常见操作(API):
find-max:O(1)
delete-max:O(logN)
insert(create):O(logN)或O(1)
二叉堆实现细节
1.二叉堆一般都通过"数组"来实现
2.假设"第一个元素"在数组中的索引为0的话，则父节点和子节点的关系如下:
I.索引为i的左孩子的索引是2i+1
II.索引为i的有孩子的索引为2i+2
III.索引为i的父节点的索引是floor((i-1)/2)
insert插入操作
1.新元素一律先插入到堆的尾部
2.依次向上调整整个堆的结构(一直到根即可)
Delete Max删除堆顶操作
1.将堆尾元素替换到顶部(即堆顶被替代删除掉)
2.依次从根部向下调整整个堆的结构(一直到堆尾即可)
二叉堆是堆的一种常见且简单的实现；但是并不是最优的实现。
最小的k个数(字节)
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue();
for(int i =0;i<arr.length;i++){
heap.add(arr[i]);
}
int[] list = new int[k];
for (int j=0;j<k;j++){
list[j] = heap.poll();
}
return list;
}
}
滑动窗口最大值(亚马逊)
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
暴力法
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if(n*k == 0) return new int[0];
int[] output = new int[n - k +1];
for(int i = 0;i< n - k + 1;i++){
int maxValue = Integer.MIN_VALUE;
for(int j = i; j < k+i;j++){
maxValue = Math.max(maxValue,nums[j]);
}
output[i] = maxValue;
}
return output;
}
}
大顶堆法
@Test
public int[] maxSlidingWindow(int[] nums, int k) {
//若数组和窗口大小为空，直接返回空数组
if (nums.length == 0 || k == 0)
return new int[0];
int n = nums.length;
int[] result = new int[n-k+1]; //window的大小
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((o1, o2) -> (o2-o1));//大顶堆
for (int i=0;i<n;i++){
int start = i - k;
if (start>=0){//如果有元素漂移到窗口外了，移出这个元素
maxPQ.remove(nums[start]);
}
maxPQ.offer(nums[i]);
if (maxPQ.size() == k) {//窗口为k已经满员了，取一次值
result[i - k + 1] = maxPQ.peek();//取大顶堆最顶部的值放入result中
}
}
return result;
}
}
前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for (int n:nums) {//数组中每个元素出现的次数,n作为key 次数作为value
map.put(n,map.getOrDefault(n,0)+1);
}
//大顶堆
PriorityQueue<Map.Entry<Integer,Integer>> maxPQ = new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
maxPQ.add(entry);//将出现次数从大到小的排列组合map,放入大顶堆中
}
List<Integer> list = new ArrayList<>();
while (list.size()<k){//一次取出大顶堆中的前k个Map,Map中的key也就是元素放入到list中
Map.Entry<Integer,Integer> ent = maxPQ.poll();
list.add(ent.getKey());
}
int[] res = list.stream().mapToInt(Integer::valueOf).toArray();//list转int[]
return res;
}
}
丑数(字节)
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
public int nthUglyNumber(int n) {
int[] uglyNumbers = {2,3,5};//丑数都是2或3或5相乘的结果
Set<Long> set = new HashSet<>();
PriorityQueue<Long> queue = new PriorityQueue<>();//小根堆
queue.add(1L);
int count = 0;
while (!queue.isEmpty()){
Long cue = (Long) queue.poll();//取出小根堆顶部最小值
if (++count>=n){//记录取出的次数，到第n个数时即第n个丑数
return cue.intValue();
}
for (int num : uglyNumbers) {
if (!set.contains(num*cue)){//在集合中过滤重复的丑数
queue.add(num*cue);
set.add(num*cue);
}
}
}
return -1;
}
图
图的属性和分类
图的属性
Graph(V,E)
V-vertex:点
1.度-入度和出度
2.点和点之间:连通与否
E-edge:边
1.有向和无向(单行线)
2.权重(边长)
图的表示和分类
邻接矩阵和邻接表
无向无权图
邻接矩阵
0:表示两点之间没有直接的边相连
1:表示两点之间有直接的边相连
有向无权图
边有方向
无权:所有的边不是0即是1
无向有权图
边没有方向，矩阵对称，边的长度不再是0和1了，有边长
有向有权图
有方向，右边长
DFS和BFS
visited = set()
树可以保证没有环路，图要写visited，有环路避免重复
连通图个数： https://leetcode-cn.com/problems/number-of-islands/
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;//获取数组的行数
int nc = grid[0].length;//获取数组的列数
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';//当前格的值置为0
//遍历上下左右四个
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
//获取数组的行数和列数
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
//遍历数组中每一个元素
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;//若出现元素值为1，则岛屿数量加1
dfs(grid, r, c);//使用深度优先遍历，将此岛屿所有的元素变为0
}
}
}
return num_islands;
}
拓扑排序（Topological Sorting）： https://zhuanlan.zhihu.com/p/34871092
最短路径（Shortest Path）：Dijkstra https://www.bilibili.com/video/av25829980?from=search&seid=13391343514095937158
最小生成树（Minimum Spanning Tree）： https://www.bilibili.com/video/av84820276?from=search&seid=17476598104352152051
网友评论