Java 知识体系

image.png image.png

# 一、数据结构

数据结构的底层存储方式只有两种：数组（顺序存储）和链表（链式存储）。其他如哈希表、栈、队列、堆、图等各种数据结构都是以数组和链表为结构基础构建。

  • 数组：连续存储，快速检索，节省空间，但是需要处理扩容和缩容（增删）问题。
  • 链表：快速增删，需要更多的内存空间存储节点指针。

# 1. 图

  • 邻接矩阵（二维数组）：判断连通性很迅速，但是如果图比较稀疏则很耗费空间。

  • 邻接表（链表）：节省空间，但很多操作的效率比不上邻接矩阵。

    • 深度遍历（DFS）

    从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点。 然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解: 每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

    核心元素：

    • 顶点数目
    • List数组存储边
    • boolean数组存储顶点是否被访问过

    下面的实现方式是最简单的图构建，可以经过以下进阶：

    1. 封装成Node，Node节点包括存储的值和边
    2. 边的存储可以利用HashMap，key为Node，value为List
    public class Graph {

    // 顶点数目
    private int V;
    
    // 邻接表存储边
    private List<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    // 连接两个点
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    // d
    public void dfs(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");
		
        // 循环遍历顶点v的边
        for (int w : adj[v]) {
            // 该边没有被遍历过
            if (!visited[w]) {
                // 深度遍历
                dfs(w, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);

        boolean[] visited = new boolean[5];
        g.dfs(0, visited);
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    • 广度遍历（BFS）- 利用队列，其他的跟上面的dfs一致
    public void bfs(int s, boolean[] visited) {
    Queue<Integer> queue = new ArrayDeque<>();
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty()) {
        int v = queue.poll();
        System.out.print(v + " ");

        for (int i : adjList[v]) {
            if (!visited[i]) {
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

# 2. 哈希表

通过哈希函数将键映射到一个大数组。对于解决哈希冲突的方法，常见的有拉链法和线性探查法。

  • 拉链法：出现哈希冲突的时候将该值存储到冲突的位置对应的链表上。删除操作简单，直接操作链表。
  • 线性探查法：出现哈希冲突的时候继续沿着冲突的数组位置继续往下找，直到找到空闲的位置。该模式下的数组需要经常扩容。删除操作复杂。

# 3. 树

  • 数组实现则称为“堆”，“堆”是一个完全二叉树，用数组存储不需要节点指针，操作比较简单。
  • 链表实现则是常见的“树”（链表树），在链表树的结构上，又衍生出其他适用不同场景的设计，比如二叉搜索树、AVL树、红黑树、区间树、B树等。

# 3.1 二叉树

先刷二叉树，大部分常考算法的本质上都是树的遍历问题，同时二叉树容易培养框架思维。

101. 对称二叉树 (opens new window)

  • 双指针 + 递归：比较值和左右子树（p的左和q的右，p的右和q的左）

102. 二叉树的层序遍历 (opens new window)

  • 广度优先算法：队列 + 层数控制

104. 二叉树的最大深度 (opens new window)

  • 深度优先算法：ans = max(leftH, rightH) + 1
  • 广度优先算法：ans记录层数

437. 路径总和 III (opens new window)

  • 算法：回溯
  • 叶子节点的判断：
    • 当root.left == null && root.right == null 才为叶子节点，root等于null并不代表叶子节点，因为它是叶子节点的左右节点，而非叶子节点。
  • 回溯位置：
    • 在左右节点递归之后再回溯，如果在中间回溯，则右节点的遍历会缺失该节点。
  • 每遍历某节点，则targetSum - 该节点的值，当targetSum == 0时，则为所求路径。

# 3.2 框架

  1. 计算树的深度：
    1. 深度优先 - 递归
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftH = maxDepth(root.left);
    int rightH = maxDepth(root.right);

    return max(leftH, rightH) + 1;
}
1
2
3
4
5
6
7
8
9
10
  2. 广度优先（层数） - 迭代

public int maxDepth(TreeNode root) {
    if(root == null) {
    	return 0;
    }
    
    Queue<TreeNode> queue = new LinkList<>();
    queue.offer(root);
    
    int deep = 0;
    while(!queue.isEmpty()){
    	int size = queue.size();   
        for(int i = 0;i < size; i ++){
        	TreeNode node = queue.pop();
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        
        deep ++;
    }
    
    return deep;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  1. 对于两棵树之间关系的判断的：
    1. 思考如何利用深度遍历（前序、后序、中序）
    2. 思考边缘条件
      1. 当两棵树都为null时
      2. 当其中一棵树为null时
      3. 当两棵都不为null时

# 二、算法学习

image.png 动态规划、贪心和回溯算法一样，完成一件事情是分步决策的，贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响)，因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的；

# 2.1 动态规划

动态规划问题的一般形式就是求最值。比如最长递增子序列、最小编辑距离等。求解动态规划等核心问题就是穷举，因为要求最值，需要把所有可行的答案穷举出来然后找其最值。

三要素

  1. 动态规划存在重叠子问题，如果暴力破解效率会很低，所以需要“备忘录”或者“DP table”来优化穷举过程。
  2. 动态规划问题具备“最优子结构”，这样才能通过子问题的最值的到原问题的解。
  3. 需要列出“状态转移方程”
    1. 问题的base case是什么？
    2. 问题有什么”状态“？
    3. 对于每个”状态“，可以做什么”选择“使得”状态“发生改变
    4. 如何定义dp数组/函数的含义来变现”状态“和”选择“

特性

  • 重叠子问题：
    • 当一个递归算法不断地调用同一问题时，我们说该最优问题包含重叠子问题。
    • 动态规划通过空间换时间的方式，将子问题解存入数组，保证问题不被重复计算。
  • 最优子结构：通过子问题的最优解可以获得整个问题的最优解

# 2.2 贪心算法

特性

  • 贪心选择特性：
    • 在求解一个最优化的过程中，使用贪心的方式选择了一组内容之后，不会影响下面的子问题的求解。（例如0-1背包，只拿最大价值的放入背包是不对的，会影响到未来问题的选择）
  • 最优子结构：通过子问题的最优解可以获得整个问题的最优解

# 2.3 回溯法

# 1. 框架

result = []

// 模版
public void backtract(路径，选择列表){
	
    if 满足结束条件：
    	result.add(路径)
        return
	
    for 选择 in 选择列表:
    	做选择
        backtract(路径， 选择列表)
        撤销选择
}


// 案例
public void backtract(String s) {
    if (subAns.length() == s.length()) {
        ans.add(subAns.toString());
        return;
    }

    for (int i = 0; i < s.length(); i++) {
        if (!map.containsKey(i)) {
            continue;
        }
        
        subAns.append(s.charAt(i));
        map.put(i, i);
        traverse(s);
        map.remove(i);
        subAns.deleteCharAt(subAns.length() - 1);
    }
}


//案例2：获取所有子集（包含空集）
public static void dfs(int[] nums, List<List<Integer>> ans, List<Integer> subAns, int index) {
    if (index == nums.length) {
        ans.add(new ArrayList<>(subAns));
        return;
    }

    subAns.add(nums[index]);
    dfs(nums, ans, subAns, index + 1);
    subAns.remove(subAns.size() - 1);
    dfs(nums, ans, subAns, index + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

难点：剪枝和去重复（画出树图）

全排列（有重重数的原始数组）去重：
1. 排序
2. 遍历到当前层，如果不是上个节点的子层，并且该节点值与上个节点的值相等，则在重复遍历
(i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
1
2
3
4

image.png

全组合（原始数组中的数可重复使用）去重：
1. 遍历到某一层的节点时，不再考虑该节点之前已经遍历过的节点路径（例如以2为起点的路径，在遍历的时候包含了所有有2的路径的情况，在走3的时候就不再考虑这种情况，否则会有重复）
for (int i = begin; i < candidates.length; i++)
    backtract(candidates, target - candidates[i], i); （i即传为begin）
    
剪枝：
1. 排序
2. if(target - candidates[i] < 0) break;
1
2
3
4
5
6
7
8

image.png

# 2.4 二分搜索法

  • 排序数组的搜索优先考虑二分搜索
  • 可以根据剑指Offer_53熟悉不同情况下的二分搜索框架

# 1. 框架

int binarySearch(int[] nums, int target){
	int left = 0;
    int right = ...;
    
    while(...){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
        	...
        } else if(nums[mid] < target){
        	left = ...;
        } else if(nums[mid] > target){
         	right = ...;   
        }
    }
    return ...;
}

标准版
int binarySearch(int[] nums, int target){
	int left = 0;
    int right = nums.length - 1;
    
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
        	return mid;
        } else if(nums[mid] < target){
        	left = mid + 1;
        } else if(nums[mid] > target){
         	right = mid - 1;   
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 2.5 位运算

# 1. 框架

(n >> i) & 1 : 右边第i + 1位的奇偶性，例如i=0，((n >> i) & 1) == 1表示n的右边第一位为奇数
n & (n - 1)：最右边的1变成0
- if(n & (n - 1) == 0) 则表示改数n为2的整幂次方（即其二进制位上只有一个1）
1
2
3

# 2.6 链表操作

# 1. 框架

1. 获取倒数第k个节点

ListNode slow = head;
ListNode fast = head;

//快指针先走
while (k >= 1) {
    fast = fast.next;
    k --;
}

//快慢同时走，当fast走到null时，slow走到目标节点，若fast走到fast.nexl为null，则slow到达目标节点的前一个节点（例如旋转链表的时候用到）
while (fast != null) {
    fast = fast.next;
    slow = slow.next;
}



2. 链表排序
nums.sort(Comparator.comparing(Integer::intValue));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 2.7 双指针

# 1. 框架

一、滑动窗口

滑动窗口核心概念：
- 窗口为左闭右开
- 判停条件：while(right < s.size())
1
2
3
4
5
6
7
  • 滑动窗口和前缀和在连续子数组和的题目的区别：
    • 都是求连续子数组/子串和，滑动窗口需要求出具体结果，前缀和求符合的数量
    • 滑动窗口子数组是有序的，而前缀和没有

# 2.8 单调栈/队列

# 1. 框架

一、单调栈

1. 从尾到前遍历源数组
2. 循环判断当前元素和栈顶元素的大小关系，如果栈顶元素小于当前元素，则出栈
3. 获取栈顶元素（该元素即为next greater元素）
4. 入栈

tips：栈可以保存元素，也可以保存元素下标

case：leetcode_739，求某天再滴几天后温度才会提升的
public int[] dailyTemperatures(int[] temperatures) {

    Stack<Integer> stack = new Stack<>();

    int[] ans = new int[temperatures.length];
    for (int i = temperatures.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
            stack.pop();
        }

        ans[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
    }

    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 2.9 其他

  • 十进制转二进制
public String toBinary(int x){

    int x = 12;
    String ans = new String();
    while(x != 0){
        int r = x % 2;
        x = x / 2;

        ans = r + ans;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

# 三、技巧总结

  • 当出现连续子数组的题目时，考虑用前缀树、滑动窗口。
  • 当出现求最值时，考虑动态规划。
  • 如果递归时觉得思路正确，但是结果离谱，考虑是多嵌套嵌套错了
Last Updated: 2023-2-16 12:48:09 ├F10: PM┤

←