AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

Java刷题模板

作者: 作者的头像   Lic ,  2019-09-17 11:04:37 ,  所有人可见 ,  阅读 6703


61


141

数据输入

一般我常用的数据输入方法有两种,Scanner和BufferedReader。BufferedReader可以读一行,速度比Scanner快,所以数据较多的时候使用。注意BufferedReader用完记得关。

Scanner

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); // String: next(), double: nextDouble()
        int[] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = scan.nextInt();
        // ...
    }
}

BufferedReader

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] nums = new int[n];
        String[] strs = reader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(strs[i]);
        // ...
        reader.close(); // 记得关闭
    }
}

快速排序quickSort

快速排序要注意x取值的边界情况。取x = nums[left], nums分为[left, j]和[j + 1, right],或x = nums[right], nums分为[left, i - 1]和[i, right],否则会StackOverflow。

public void quickSort(int[] nums, int left, int right) {
    if (left >= right)
        return;
    int i = left - 1, j = right + 1, x = nums[left];
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    quickSort(nums, left, j);
    quickSort(nums, j + 1, right);
}

例题:AcWing 785, LeetCode 912


归并排序mergeSort

mergeSort时间复杂度是稳定O(nlogn),空间复杂度O(n),稳定的。quickSort时间复杂度平均O(nlogn),最坏O(n^2),最好O(nlogn),空间复杂度O(nlogn),不稳定的。

public void mergeSort(int[] nums, int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    int k = 0, i = left, j = mid + 1;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right)
        if (nums[i] < nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    while (i <= mid)
        temp[k++] = nums[i++];
    while (j <= right)
        temp[k++] = nums[j++];
    for (i = left, j = 0; i <= right; i++, j++)
        nums[i] = temp[j];
}

例题:AcWing 787, LeetCode 912


二分搜索binarySearch

二分搜索逼近左边界,区间[left, right]被分为左区间[left, mid]和右区间[mid + 1, right]。

public int binarySearchLeft(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(mid))
            right = mid;
        else
            left = mid + 1;
    }
    return nums[left];
}

二分搜索逼近右边界,区间[left, right]被分为左区间[left, mid - 1]和右区间[mid, right]。

public int binarySearchRight(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2 + 1;
        if (check(mid))
            left = mid;
        else
            right = mid - 1;
    }
    return nums[left];
}

暑假在LeetCode打卡的时候发现还有第三种模板,nums[mid] == target 直接return,区间[left, right]被分为[left, mid - 1]和[mid + 1, right]。

public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (check(mid))
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }

例题:AcWing 789, LeetCode 34, LeetCode 35


KMP

public int kmp(String text, String pattern) {
    int m = pattern.length();
    if (m == 0)
        return 0;
    int n = text.length();
    int[] next = new int[m + 1];
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && pattern.charAt(i - 1) != pattern.charAt(j))
            j = next[j];
        if (pattern.charAt(i - 1) == pattern.charAt(j))
            j++;
        next[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && text.charAt(i - 1) != pattern.charAt(j))
            j = next[j];
        if (text.charAt(i - 1) == pattern.charAt(j))
            j++;
        if (j == m)
            return i - m;
    }
    return -1;
}

例题:AcWing 831, LeetCode 28


Trie

public static final int SIZE = 26;

public static class TrieNode {
    TrieNode[] children = new TrieNode[SIZE];
    int times;

    TrieNode() {
        times = 0;
        for (int i = 0; i < SIZE; i++)
            children[i] = null;
    }
}

public static TrieNode root = new TrieNode();

public static void insert(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (node.children[index] == null)
            node.children[index] = new TrieNode();
        node = node.children[index];
    }
    node.times++;
}

public static int query(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (node.children[index] == null)
            return 0;
        node = node.children[index];
    }
    return node.times;
}

例题:AcWing 835


并查集

朴素并查集

public static int[] p;

public static int find(int x) {
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

p[find(a)] = find(b);

例题:AcWing 836


图的存储

n个点,m条边,m约等于$n^2$叫做稠密图,用邻接矩阵存储;n个点,m条边,m远小于$n^2$叫做稀疏图,用邻接表存储。

邻接矩阵

public class Main{
    public static final int INF = 0x3f3f3f3f;
    public static int n;
    public static int[][] g;
    public static int[] dist;
    public static boolean[] visit;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int m = scan.nextInt();
        g = new int[n + 1][n + 1];
        dist = new int[n + 1];
        visit = new boolean[n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i == j)
                    g[i][j] = 0;
                else
                    g[i][j] = INF;
        for (int i = 0; i < m; i++) {
            int x = scan.nextInt(), y = scan.nextInt(), z = scan.nextInt();
            g[a][b] = Math.min(g[a][b], c);
        }
        int res = dijkstra();
        System.out.println(res);
    }
}

邻接表

import java.util.*;

public class Main{
    public static int INF = 0x3f3f3f3f;
    public static int n;
    public static Map<Integer, List<Node>> map = new HashMap<>();
    public static int[] dist;
    public static boolean[] visit;

    public static class Node {
        public int node;
        public int length;

        public Node(int node, int length) {
            this.node = node;
            this.length = length;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dist = new int[n + 1];
        visit = new boolean[n + 1];
        int m = scan.nextInt();
        for (int i = 1; i <= n; i++)
            map.put(i, new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int x = scan.nextInt(), y = scan.nextInt(), z = scan.nextInt();
            map.get(x).add(new Node(y, z));
        }
        int res = dijkstra();
        System.out.println(res);
    }
}

Dijkstra

边权不能是负数!
1.dist[1] = 0, dist[i] = +∞
2.for i 1 ~ n
t <- 不在s中的,距离最近的点 – $n^2$ / n
s <- t – n
用t更新其他点的距离 – m / mlogn

public static int dijkstra() {
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!visit[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if (t == n)
            break;
        for (int j = 1; j <= n; j++)
            dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        visit[t] = true;
    }
    if (dist[n] == INF)
        return -1;
    return dist[n];
}

例题:AcWing 849


优化Dijkstra

public static int dijkstra() {
        for (int i = 1; i <= n; i++)
            dist[i] = INF;
        dist[1] = 0;
        PriorityQueue<Node> heap = new PriorityQueue<>((node1, node2) -> node1.length - node2.length);
        heap.add(new Node(1, 0));
        while (!heap.isEmpty()) {
            Node top = heap.poll();
            int length = top.length, cur = top.node;
            if (visit[cur])
                continue;
            visit[cur] = true;
            for (Node next: map.get(cur)) {
                int node = next.node, cost = next.length;
                if (dist[node] > length + cost) {
                    dist[node] = length + cost;
                    heap.add(new Node(node, dist[node]));
                }
            }
        }
        if (dist[n] == INF)
            return -1;
        return dist[n];
    }

例题:AcWing 850


Bellman-ford

O(nm)

public static int bellman_ford() {
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        for (int j = 1; j <= n; j++)
            backup[j] = dist[j]; // deep copy
        for (int k = 0; k < m; k++) {
            int x = edges[k].x;
            int y = edges[k].y;
            int z = edges[k].z;
            dist[y] = Math.min(dist[y], backup[x] + z);
        }
    }
    if (dist[n] > INF / 2)
        return -1;
    else
        return dist[n];
}

例题:AcWing 853


SPFA (队列优化的Bellman-ford算法)

一般O(m),最坏O(nm)。n表示点数,m表示边数。

public static int spfa() {
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(1);
    visit[1] = true;
    while (!queue.isEmpty()) {
        int t = queue.poll();
        visit[t] = false;
        for (Node cur: map.get(t)) {
            int node = cur.node, length = cur.length;
            if (dist[node] > dist[t] + length) {
                dist[node] = dist[t] + length;
                if (!visit[node]) {
                    queue.add(node);
                    visit[node] = true;
                }
            }
        }
    }
    return dist[n];
}

例题:AcWing 851


SPFA 判断图中是否存在负环

O(nm),n表示点数,m表示边数。

public static boolean spfa() {
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 1; i <= n; i++) {
        queue.add(i);
        visit[i] = true;
    }
    while (!queue.isEmpty()) {
        int t = queue.poll();
        visit[t] = false;
        for (Node cur: map.get(t)) {
            int node = cur.node, length = cur.length;
            if (dist[node] > dist[t] + length) {
                dist[node] = dist[t] + length;
                count[node] = count[t] + 1;
                if (count[node] >= n)
                    return true;
                if (!visit[node]) {
                    queue.add(node);
                    visit[node] = true;
                }
            }
        }
    }
    return false;
}

例题:AcWing 852


Floyd

$O(n^3)$

public static void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}

例题:AcWing 854

18 评论


用户头像
Lic   2025-03-21 16:11 · 北京         踩      回复

5年了。。。最近想跳槽又回来刷题,这是我总结的刷题模板嘛。。。完全看不懂了 T_T


用户头像
gugubird229   2024-03-18 19:13         踩      回复

感谢


用户头像
nanahira永远的神   2023-04-05 23:37         踩      回复

感谢大佬分享


用户头像
青木_8   2022-11-10 16:40         踩      回复

感谢分享


用户头像
msskx   2022-03-21 22:53         踩      回复

感谢大佬分享


用户头像
M1m4n9   2022-01-14 17:05         踩      回复

感谢


用户头像
佟子泽   2021-11-14 20:22         踩      回复

love from China.


用户头像
一年达到y总三成功力   2021-06-23 09:57         踩      回复

爱了 爱了


用户头像
hellfancy   2020-10-10 21:26         踩      回复

爱了


用户头像
wyyang   2020-06-20 12:43         踩      回复

BufferedReader 可以用try with resource ,不用考虑释放了~

用户头像
徐扬   2020-07-31 09:14         踩      回复

请问一下,具体代码应该怎么写呢?


用户头像
日暮途远   2020-05-31 17:58         踩      回复

感谢大佬的分享!


用户头像
wyyang   2020-05-22 14:42         踩      回复

赞啊,多谢分享~


用户头像
TY   2020-03-04 17:30         踩      回复

tql


用户头像
emerland666   2019-09-24 23:52         踩      回复

感恩!!


用户头像
TK   2019-09-23 10:46         踩      回复

赞!!!!


用户头像
funny   2019-09-19 03:32         踩      回复

棒!期待后续!!


用户头像
秦淮岸灯火阑珊   2019-09-17 20:59         踩      回复

棒!


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息