盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

LeetCode 代码模板Java版_leetcode java 解题模板

作者：盐析白兔 | 2024-02-20 01:49:39

踩

leetcode java 解题模板

二分查找

排序的写法

在这里插入图片描述
算法复杂度：

快速排序

private static int[] quickSort(int arr[], int left, int right) {
        if (right <= left) {
            return;
        }
        int base = partition(arr, left, right);
        quickSort(arr, left, base - 1);
        quickSort(arr, base + 1, right);
        return arr;
}

private static int partition(int[] arr, int low, int high) {
    int base = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= base){
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= base){
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = base;
    return low;
}
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

归并排序

 //将有二个有序数列a[first...mid]和a[mid...last]合并。
 private static void mergearray(int[] arr, int left, int mid, int right) {
     int i = left, j = mid + 1, k = 0;
     int temp[] = new int[right - left + 1];
     while (i <= mid && j <= right) {
         temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
     }

     while (i <= mid)
         temp[k++] = arr[i++];

     while (j <= right)
         temp[k++] = arr[j++];

     for (int p = 0; p < k; p++) {
         arr[left + p] = temp[p];
     }
 }
public static void mergesort(int a[], int left, int right) {
    if (right <= left) {
        return;
    }
    int mid = (left + right) >> 1; // (left + right) / 2
    mergesort(a, left, mid);    //左边有序
    mergesort(a, mid + 1, right); //右边有序
    mergearray(a, left, mid, right); //再将二个有序数列合并
}
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

BFS的写法

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> allResults = new ArrayList<>();
        if (root == null) {
            return allResults;
        }
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            List<Integer> results = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = nodes.poll();
                results.add(node.val);
                if (node.left != null) {
                    nodes.add(node.left);
                }
                if (node.right != null) {
                    nodes.add(node.right);
                }
            }
            allResults.add(results);
        }
        return allResults;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

DFS的写法

dfs 栈实现

    public static void dfs(TreeNode root){
        Stack<TreeNode> stack = new Stack<TreeNode>(); //借助stack
        if(root == null)
            return;
        stack.push(root);
        while(!stack.isEmpty()){ //若栈非空
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if(node.right != null) //先将右孩子结点压入堆栈
                stack.push(node.right);
            if(node.left != null) //然后将左孩子结点压入堆栈
                stack.push(node.left);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归实现

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> allResults = new ArrayList<>();
        if (root == null) {
            return allResults;
        }
        travel(root, 0, allResults);
        return allResults;
}

private void travel(TreeNode root, int level, List<List<Integer>> results) {
    if (results.size() == level) {
        results.add(new ArrayList<>());
    }
    results.get(level).add(root.val);
    if (root.left != null) {
        travel(root.left, level + 1, results);
    }
    if (root.right != null) {
        travel(root.right, level + 1, results);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

回溯法

树

递归

迭代

前序遍历

 private void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        pre.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
}
1
2
3
4
5
6
7
8

中序遍历

private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        in.add(root.val);
        inOrder(root.right);
}
1
2
3
4
5
6
7
8

后序遍历

private void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        post.add(root.val);
}
1
2
3
4
5
6
7
8

构建完全二叉树

并查集

 /**
     * 并查集
     */
    class UnionFind {
        private int count = 0;
        private int[] parent;

        public UnionFind(int n) {
            count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];
                p = parent[p];
            }
            return p;
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return;
            }
            parent[rootP] = rootQ;
            count--;
        }
    }
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

前缀树

图遍历

Dijkstra算法

Floyd-Warshall算法

Bellman-Ford算法

最小生成树

Kruskal算法

Prim算法

拓扑排序

双指针

动态规划

function DP(){
	dp = [][]
	for (int i = 0,i < N;i++){
		for (int j = 0,j < M;j++){
			dp[i][j] = _Function(dp[i`][j`])
		}	
	}
	return dp[M][N]
}
1
2
3
4
5
6
7
8
9

斐波那契数列
爬楼梯
换零钱
打家劫舍
股票买卖

状态搜索

贪心

AVL

平衡因子：某个结点的左子树的高度减去右子树的高度得到的差值。[-1,0,1]由高度来决定查找速度

左旋：右右子树。抛弃左孩子，将之和旋转后的节点A 相连，成为节点 A的右孩子。
右旋：左左子树。抛弃右孩子，将之和旋转后的节点 C 相连，成为节点 C 的左孩子。

左右旋：先左旋，变成左左子树
右左旋：先右旋，变成右右子树

在这里插入图片描述

红黑树

红黑树是一种近似平衡的二叉搜索树 (Binary Search Tree)，它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：
•每个结点要么是红色，要么是黑色
•根结点是黑色
•每个叶结点 (NI结点，空结点）是黑色的。
•不能有相邻接的两个红色结点
•从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。