Skip to content

Latest commit

 

History

History
484 lines (368 loc) · 20.2 KB

README.md

File metadata and controls

484 lines (368 loc) · 20.2 KB
Raw

algo-hub-java

基于 jdk21 + maven3.9 + junit5 + jacoco 的 leetcode + codeforces + atcoder + nowcoder 练习仓库。

@since 2021.07.05

（拼搏百天，我要完成 300 道 leetcode 题！（Day87 (2021.09.29) 已完成 303 题）

（拼搏 300 天，我要完成 1000 道 leetcode 题！（Day269 (2022.03.30) 已完成 1001 题）

（Day545 (2022.12.31) 已完成 1665 题）

Day911 (2024.01.01) 已完成：

  • leetcode: 2251 题
  • codeforces: 559 题
  • atcoder: 290 题
  • atcoder-* 存放 atcoder 题目。
  • codeforces-* 存放 codeforces 题目。
  • leetcode-n 存放 100 * (n - 1) + 1 ~ 100 * n 的题目（如 leetcode-19 存放 1801 ~ 1900 的题目）。
  • leetcode-core 存放 leetcode 自定义对象。
  • leetcode-extends 存放 专场竞赛/OJ 题目
  • leetcode-interview 存放 《程序员面试金典》 题目。
  • leetcode-lcp 存放 力扣杯 题目。
  • leetcode-offer 存放 《剑指 Offer》 题目。
  • nowcoder-* 存放 牛客 题目。
  • 数据库 题目存放于 https://gitee.com/gdut_yy/leetcode-hub-mysql

环境信息

$ java -version
openjdk 21 2023-09-19
OpenJDK Runtime Environment (build 21+35-2513)
OpenJDK 64-Bit Server VM (build 21+35-2513, mixed mode, sharing)

$ mvn -v
Apache Maven 3.9.9 (8e8579a9e76f7d015ee5ec7bfcdc97d260186937)
Maven home: D:\programs\apache-maven-3.9.9
Java version: 21, vendor: Oracle Corporation, runtime: D:\programs\jdk-21
Default locale: zh_CN, platform encoding: UTF-8
OS name: "windows 11", version: "10.0", arch: "amd64", family: "windows"

IntelliJ IDEA 2024.2.2 (Community Edition)
Build #IC-242.22855.74, built on September 18, 2024

Command 命令行

# 运行 UT、统计覆盖率（jdk21）：
mvn clean verify -s settings.xml

# 统计做题进度（python3）：
python countSolutions.py

UT、TDD

java 项目中常见的测试框架：

mock 框架：

junit5 常用断言：

  • Assertions.assertEquals
  • Assertions.assertTrue
  • Assertions.assertFalse
  • Assertions.assertArrayEquals

思考：一些较为特殊的判题 UT 写法：

  1. 部分题目使用了自定义对象（链表、二叉树等），Assertions.assertEquals 不能满足这种场景，可使用自定义断言对这类对象进行判等：
    • ListNode 可参考 ListNode#assertListNodeEquals(ListNode expected, ListNode actual)，如第 2、19、21、23、82 题等；
    • TreeNode 可参考 TreeNode#assertTreeNodeEquals(TreeNode expected, TreeNode actual)，如第 105、114、156、226、235 题等；
    • 不失一般性地，其他自定义对象可参考 UtUtils#assertJsonEquals(Object expected, Object actual)，如第 138、430、708 题等；
  2. 部分题目符合题意的答案并不止一个，可以构造一个 List<T> expectedList 去判断是否 contains() 如第 5、162 题等；
  3. 部分题目符合题意的答案是一个集合，但对集合元素的顺序没有要求，可以对 expected 和 actual 集合进行排序后判等：
    • List<List<Integer>> 可参考 UtUtils#INTEGER_LIST_COMPARATOR，如第 18、39、40、46、47 题等；
    • List<List<String>> 可参考 UtUtils#STRING_LIST_COMPARATOR，如第 49、51 题等；
  4. 部分题目是非精确判等（随机问题），如第 384、528 题等；

一些心得：

  1. leetcode 题目，可从 F12 控制台 Request Payload 中 mySubmissionDetail 关键词抓取；
  2. 使用 Java 反射实现 UT 的题目：716、2227、2276、2286；
  3. 类中提供接口，UT 中需实现该接口：341、489、702、1095、1428、1533；

一些 Trick

  // 数组 使用 Map<Integer, Integer> 统计每个数值出现的频次
  int[] nums = {4, 1, 2, 1, 2};
  Map<Integer, Integer> cntMap = new HashMap<>();
  for (int num : nums) {
      // Verbose
      if (!cntMap.containsKey(num)) {
          cntMap.put(num, 0);
      }
      cntMap.put(num, cntMap.get(num) + 1);
      // Obvious
      cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
  }
  // 有向图 使用 Map<Integer, List<Integer>> 建图
  int[][] edges = {{0, 1}, {0, 2}, {0, 3}, {1, 4}};
  Map<Integer, List<Integer>> adj = new HashMap<>();
  for (int[] edge : edges) {
      int u = edge[0];
      int v = edge[1];
      // Verbose
      if (!adj.containsKey(u)) {
          adj.put(u, new ArrayList<>());
      }
      adj.get(u).add(v);
      // Obvious
      adj.computeIfAbsent(u, key -> new ArrayList<>()).add(v);
  }

常用算法模板

打表

预计算结果

预计算结果是指：用户预先计算了部分或全部测试用例结果，并将其直接添加到至提交代码中。

规则及判分方式：如果参赛者的提交代码存在预计算结果的行为，我们建议参赛者附上生成预计算结果的代码。如参赛者含预计算结果的代码 “AC” 了题目，力扣将判定参赛者的提交为有效提交。

线段树

快速幂

模板代码

双指针

快慢指针

买卖股票系列

打家劫舍系列

存在重复元素系列

最大连续 1 的个数

Manacher 马拉车算法

数制转换

螺旋矩阵

二叉树

二叉树前序遍历 (preorder)、中序遍历 (inorder)、后序遍历 (postorder)

扩展到 N 叉树（N 叉树没有 中序遍历）

二叉树层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> resList = new ArrayList<>();
    if (root == null) {
        return resList;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        List<Integer> curLevel = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            // 上下文已保证 cur 不为 null
            TreeNode cur = queue.remove();
            curLevel.add(cur.val);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        resList.add(curLevel);
    }
    return resList;
}

二叉树序列化

其他

单调栈

注意：Java 中 "栈" 应使用 Deque 代替 Stack（Java 官方建议）。即：

// Bad
Stack<T> stack = new Stack<>();

// Good
Deque<T> stack = new ArrayDeque<>();

注意二者转 stream 时的顺序：

Stack<Integer> stack1 = new Stack<>();
Deque<Integer> stack2 = new ArrayDeque<>();
stack1.push(1); stack1.push(2); stack1.push(3);
stack2.push(1); stack2.push(2); stack2.push(3);
System.out.println(Arrays.toString(stack1.stream().mapToInt(i -> i).toArray())); // [1, 2, 3]
System.out.println(Arrays.toString(stack2.stream().mapToInt(i -> i).toArray())); // [3, 2, 1]

状态压缩 DP

只出现一次的数字系列

  1. 136. 只出现一次的数字
  2. 137. 只出现一次的数字 II
  3. 260. 只出现一次的数字 III
// 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
    int single = 0;
    for (int num : nums) {
        single ^= num;
    }
    return single;
}

// 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
public int singleNumber2(int[] nums) {
    int a = 0;
    int b = 0;
    for (int num : nums) {
        b = ~a & (b ^ num);
        a = ~b & (a ^ num);
    }
    return b;
}

// 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
public int[] singleNumber2(int[] nums) {
    int xorsum = 0;
    for (int num : nums) {
        xorsum ^= num;
    }
    // 防止溢出
    int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
    int type1 = 0;
    int type2 = 0;
    for (int num : nums) {
        if ((num & lsb) != 0) {
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    return new int[]{type1, type2};
}

石子游戏系列

图论

  • 顶点 Vertex (复数 vertices)
  • 边 Edge
  • 有向图 directed graph
  • 无向图 undirected graph
  • 有向无环图 DAG (Directed Acyclic Graph)
  • 入度 indegree
  • 出度 outdegree

拓扑排序 (Topological Sort)

每次将入度为 0 的顶点加入队列。

并查集 (UnionFind)

模板代码

最短路 (Shortest Path)

  • Floyd 求任意两个结点之间的最短路。 时间复杂度 O(n^3)
  • Dijkstra 求解 非负权图 上单源最短路径的算法。时间复杂度 O(n^2) / O(mlogn)
  • Bellman ford 可以求出有负权的图的最短路 时间复杂度 O(mn)

欧拉回路 (Eulerian Circuit)

Hierholzer 算法

二分图最大权匹配

二部图 Bipartite Graph

匈牙利算法（KM 算法）

最小生成树 (Minimum Spanning Trees)

  • Prim（普里姆）算法
  • Kruskal（克鲁斯卡尔）算法 边优先 O(mlogm) m 条边

网络流问题 (Network Flow Problems)

  • Ford-Fulkerson 算法（最坏情况时间复杂度 O(f*m) f 为最大流大小 m 为边的数量）
  • Edmonds-Karp 算法 最短路 时间复杂度 O(n*m^2) n 为顶点数量 m 为边数量
  • Dinic 算法 时间复杂度 O(m*n^2) level graph

学习资源

（全文完）