跳至主要內容

像写项目一样写力扣

大约 13 分钟

像写项目一样写力扣

1. 问题背景

力扣题模式（仅需要编写核心代码）

与传统的竞争性编程网站不同，leetcode 采用的是核心函数模式。这极大丰富了题目的多样性：题目通过函数声明/方法定义，可以考察参赛者指定的数据结构（如 链表 ListNodeopen in new window、二叉树 TreeNodeopen in new window 等），以及各种 设计题open in new window（如 146. LRU 缓存机制open in new window、155. 最小栈open in new window 等）。但在使用本地 IDE 的场景下，leetcode 的输入输出显然比传统 OJ 直接复制 INPUT/OUTPUT 到文件中要麻烦。

尤其是在竞赛（周赛）的场景下，我们的一些提交难免会因 考虑不周 而 WA 到生活不能自理，由于罚时机制的存在，我们在 WA 之后会变得小心翼翼，起码要跑通已知的测试用例（题目示例 + WA 的用例）才会提交，有时候甚至不得不使用本地 IDE 进行调试。这个时候，我们的操作通常是：将用例文本复制到 IDE 中，再转换为 Java 对象，这个环节往往会耗费比较多的时间。

以 “有人相爱，有人夜里开车看海” 的 1. 两数之和open in new window 为例：

题目示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

代码模板：

class Solution {
    public int[] twoSum(int[] nums, int target) {

    }
}

由于是核心函数模式，我们需敲出 main 方法，构造出入参（一个 int[] 和一个 int）和实例来调用目标方法，再通过 System.out.println() 将结果可视化后进行人工比对：

class Solution {
    public int[] twoSum(int[] nums, int target) { ... }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(new Solution().twoSum(nums, target)));
    }
}

如果有多组用例，人工比对会比较吃力；如果单个用例较大，几乎无法用肉眼进行判等；对于一些自定义对象，无法直接通过 System.out.println() 进行可视化，非常的难受。

2. Java 版本选择

上述可以归结为两个问题：输入转换慢，输出比对难。

工欲善其事，必先利其器。在给出解决方案之前，我们先选择合适的 Java 版本。这里我选择的是 Java17。原因如下：

虽然大多 Java 项目还是停留在 Java8，leetcode 环境是 Java13open in new window 但是还是建议大家选择 Java17，它有两个非常重要的 JEP(JDK Enhancement Proposal JDK 增强方案)

JEP 269: Convenience Factory Methods for Collectionsopen in new window

List.of(a, b, c);
Set.of(d, e, f, g);

JEP 378: Text Blocksopen in new window

String html = "<html>\n" +
              "    <body>\n" +
              "        <p>Hello, world</p>\n" +
              "    </body>\n" +
              "</html>\n";

String html = """
              <html>
                  <body>
                      <p>Hello, world</p>
                  </body>
              </html>
              """;

3. 输入转换

关于输入转换，个人总结了一下，以下类型从 题目示例 转换成 Java对象，难受程度由高到低：

1. char[][]（难受程度：4） e.g. 36. 有效的数独open in new window

步骤：先将 [] 替换成 {}；再将 " 替换成 '。

/*
输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
*/
class Solution {
    public boolean isValidSudoku(char[][] board) { ... }

    public static void main(String[] args) {
        // AS-IS
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        // TO-BE
        char[][] board = UtUtils.stringToChars2("""
                [["5","3",".",".","7",".",".",".","."]
                ,["6",".",".","1","9","5",".",".","."]
                ,[".","9","8",".",".",".",".","6","."]
                ,["8",".",".",".","6",".",".",".","3"]
                ,["4",".",".","8",".","3",".",".","1"]
                ,["7",".",".",".","2",".",".",".","6"]
                ,[".","6",".",".",".",".","2","8","."]
                ,[".",".",".","4","1","9",".",".","5"]
                ,[".",".",".",".","8",".",".","7","9"]]
                """);
    }
}

2. List<List<Long>>（难受程度：4） e.g. 1943. 描述绘画结果open in new window

步骤：先将 [] 替换成 List.of() 或 Arrays.asList()；再在每个整数后面加上 L（显式转换为 long）。

/*
输入：segments = [[1,4,5],[4,7,7],[1,7,9]]
输出：[[1,4,14],[4,7,16]]
解释：绘画借故偶可以表示为：
- [1,4) 颜色为 {5,9} （和为 14），分别来自第一和第二个线段。
- [4,7) 颜色为 {7,9} （和为 16），分别来自第二和第三个线段。
*/
class Solution {
    public List<List<Long>> splitPainting(int[][] segments) { ... }

    public static void main(String[] args) {
        // AS-IS
        List<List<Long>> expected = List.of(List.of(1L, 4L, 14L), List.of(4L, 7L, 16L));

        // TO-BE
        List<List<Long>> expected = UtUtils.stringToLongList2("[[1,4,14],[4,7,16]]");
    }
}

3. List<List<Integer>>（难受程度：3） e.g. 120. 三角形最小路径和open in new window

步骤：将 [] 替换成 List.of() 或 Arrays.asList()。

/*
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) { ... }

    public static void main(String[] args) {
        // AS-IS
        List<List<Integer>> triangle = List.of(List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3));

        // TO-BE
        List<List<Integer>> triangle = UtUtils.stringToIntegerList2("[[2],[3,4],[6,5,7],[4,1,8,3]]");
    }
}

4. List<List<String>>（难受程度：3） e.g. 332. 重新安排行程open in new window

步骤：将 [] 替换成 List.of() 或 Arrays.asList()。

/*
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]
*/
class Solution {
    public List<String> findItinerary(List<List<String>> tickets) { ... }

    public static void main(String[] args) {
        // AS-IS
        List<List<String>> tickets = List.of(List.of("MUC", "LHR"), List.of("JFK", "MUC"), List.of("SFO", "SJC"), List.of("LHR", "SFO"));

        // TO-BE
        List<List<String>> tickets = UtUtils.stringToStringList2("""
                [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
                """);
    }
}

5. int[][]（难受程度：2） e.g. 48. 旋转图像open in new window

步骤：将 [] 替换成 {}。

/*
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
*/
class Solution {
    public void rotate(int[][] matrix) { ... }

    public static void main(String[] args) {
        // AS-IS
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        // TO-BE
        int[][] matrix = UtUtils.stringToInts2("[[1,2,3],[4,5,6],[7,8,9]]");
    }
}

6. String[][]（难受程度：2） e.g. 剑指 Offer II 086. 分割回文子字符串open in new window

步骤：将 [] 替换成 {}。

/*
输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
*/
class Solution {
    public String[][] partition(String s) { ... }

    public static void main(String[] args) {
        // AS-IS
        String[][] expected = {{"g", "o", "o", "g", "l", "e"}, {"g", "oo", "g", "l", "e"}, {"goog", "l", "e"}};

        // TO-BE
        String[][] expected = UtUtils.stringToStrings2("""
                [["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
                """);
    }
}

解决方案：

我们称上面的 main 方法的输入为 “硬编码”，leetcode 一般一题有上百个测试用例，源文件放不下（如一些 nums.length <= 10^5 的），也不好维护。解决方案是将用例对象序列化后存放到数据库，使用时再反序列化为用例对象（297. 二叉树的序列化与反序列化open in new window 题目中有提示）。我们可以借助一些对象序列化框架将这类输入反序列化为 Java 对象，如 fastjson：

<!-- https://mvnrepository.com/artifact/com.alibaba/fastjson -->
<dependency>
    <groupId>com.alibaba</groupId>
    <artifactId>fastjson</artifactId>
    <version>1.2.80</version>
</dependency>

参考代码：

import com.alibaba.fastjson.JSON;

import java.util.List;
import java.util.stream.Collectors;

public class UtUtils {
    // String => char[][]
    public static char[][] stringToChars2(String input) {
        List<char[]> list = JSON.parseArray(input, char[].class);
        return list.toArray(new char[list.size()][]);
    }

    // String => List<List<Long>>
    public static List<List<Long>> stringToLongList2(String input) {
        return JSON.parseArray(input, String.class).stream()
                .map(s -> JSON.parseArray(s, Long.class))
                .collect(Collectors.toList());
    }

    // String => List<List<Integer>>
    public static List<List<Integer>> stringToIntegerList2(String input) {
        return JSON.parseArray(input, String.class).stream()
                .map(s -> JSON.parseArray(s, Integer.class))
                .collect(Collectors.toList());
    }

    // String => List<List<String>>
    public static List<List<String>> stringToStringList2(String input) {
        return JSON.parseArray(input, String.class).stream()
                .map(s -> JSON.parseArray(s, String.class))
                .collect(Collectors.toList());
    }

    // String => int[][]
    public static int[][] stringToInts2(String input) {
        List<int[]> list = JSON.parseArray(input, int[].class);
        return list.toArray(new int[list.size()][]);
    }

    // String => String[][]
    public static String[][] stringToStrings2(String input) {
        List<String[]> list = JSON.parseArray(input, String[].class);
        return list.toArray(new String[list.size()][]);
    }
}

4. 输出判等

关于输出判等，不难想到，既然人工难以比对，那么我们可以用程序去比对，我们可以把 预期结果 也构造出来，使用类似 Objects.equals()/Arrays.equals() 的方法进行判等，System.out.println() 根据相等与否打印出 YES 或 NO。

在实际工程项目中，我们称之为 UT (Unit Test 单元测试)，我们可以借鉴用于此。在 Java 中，Junit 是事实上的单元测试标准（Spring Boot Starter Test 也选择了它），Junit 的常用断言有（当前最新版本为 Junit5，使用时需注意与 Junit4 的差异）：

  • Assertions.assertEquals(expected, actual)
  • Assertions.assertTrue(boolean condition)
  • Assertions.assertFalse(boolean condition)
  • Assertions.assertArrayEquals(expected, actual)

关于 Java 自有对象的精确判等，用 Assertions 就很舒服~~

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class Solution1Tests {
    private final Solution1 solution1 = new Solution1();

    @Test
    public void example1() {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] expected = {0, 1};
        Assertions.assertArrayEquals(expected, solution1.twoSum(nums, target));
    }

    @Test
    public void example2() {
        int[] nums = {3, 2, 4};
        int target = 6;
        int[] expected = {1, 2};
        Assertions.assertArrayEquals(expected, solution1.twoSum(nums, target));
    }
}

5. 扩展：自定义对象

5.1 自定义对象输入

如何输入自定义对象？这个问题不难，我们可以直接编码构造

e.g. 94. 二叉树的中序遍历open in new window

/*
输入：root = [1,null,2,3]
输出：[1,3,2]
*/
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) { ... }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
    }
}

如何可视化自定义对象？这个问题也不难，将自定义对象序列化为字符串就可以 System.out.println() 了。leetcode 的 playground 中为我们提供了 ListNode、TreeNode 对象的序列化/反序列化处理，这里列出 API 定义，有兴趣的可自行前往阅读：

class Wrapper {
    // ListNode 序列化
    public static ListNode stringToListNode(String input) { ... }
    // ListNode 反序列化
    public static void prettyPrintLinkedList(ListNode node) { ... }

    // TreeNode 序列化
    public static String treeNodeToString(TreeNode root) { ... }
    // TreeNode 反序列化
    public static TreeNode stringToTreeNode(String input) { ... }
}

5.2 自定义对象判等

对于 TreeNode 的判等，我们可以直接复用 100. 相同的树open in new window 的代码：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

对于 ListNode 的判等，同理（只是比二叉树少了一个节点），直接秒杀：

class Solution {
    public boolean isSameList(ListNode p, ListNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameList(p.next, q.next);
        }
    }
}

对于 “非标” 的自定义对象，如：

总不能每个自定义对象都写一套判等方法吧？

class Solution {
    public boolean isSameObjectByJson(Object p, Object q) {
        return JSON.toJSONString(p).equals(JSON.toJSONString(q));
    }
}

相当于开挂，前面的 isSameTree() 和 isSameList() 也不再需要了。

6. 扩展：非精确判等

显然，并不是所有的题目都要求 “答案唯一”：

如果存在多种答案，只需返回 任意一个 即可。

思路：对于可以枚举出全部答案的，我们可以将答案全部枚举出来，放到集合类（如 Set<T>）中去判断是否 contains() 即可。

思路：对于难以枚举出全部答案的，考虑将目标输出放回题干中判断是否满足题意。

你可以按 任意顺序 返回答案。

思路：按一定的顺序进行排列后再判等即可。

7. 度量测试用例质量

Pairwise

jacoco

8. 进阶：设计类题目

刚结束的 第 287 场周赛open in new window T4 2227. 加密解密字符串open in new window 为例。

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.serializer.SerializerFeature;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.lang.reflect.Constructor;
import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;

public class Solution2227Tests {
    @Test
    public void example1() {
        char[] keys = {'a', 'b', 'c', 'd'};
        String[] values = {"ei", "zf", "ei", "am"};
        String[] dictionary = {"abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"};

        Solution2227.Encrypter encrypter = new Solution2227.Encrypter(keys, values, dictionary);

        // 返回 "eizfeiam"。
        // 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
        Assertions.assertEquals("eizfeiam", encrypter.encrypt("abcd"));

        // return 2.
        // "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。
        // 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。
        // 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。
        Assertions.assertEquals(2, encrypter.decrypt("eizfeiam"));
    }

    @Test
    public void example1_2() throws Exception {
        reflection("solution2227-example1-input.txt", "solution2227-example1-output.txt");
    }

    @Test
    public void example2() throws Exception {
        // 201 / 203 个通过测试用例
        reflection("solution2227-example2-input.txt", "solution2227-example2-output.txt");
    }

    private void reflection(String inputFile, String outputFile) throws Exception {
        // 类、构造器、类方法
        Class<?> clazz = Solution2227.Encrypter.class;
        Constructor<?> constructor = clazz.getConstructor(char[].class, String[].class, String[].class);
        Method encrypt = clazz.getMethod("encrypt", String.class);
        Method decrypt = clazz.getMethod("decrypt", String.class);

        // 入参
        String[] methods = JSON.parseObject(UtUtils.loadingString(inputFile, 0), String[].class);
        String[] parameters = JSON.parseObject(UtUtils.loadingString(inputFile, 1), String[].class);
        String[] returns = JSON.parseObject(UtUtils.loadingString(outputFile, 0), String[].class);
        String[] args = JSON.parseObject(parameters[0], String[].class);
        char[] keys = JSON.parseObject(args[0], char[].class);
        String[] values = JSON.parseObject(args[1], String[].class);
        String[] dictionary = JSON.parseObject(args[2], String[].class);

        // 实例化
        List<Object> invokes = new ArrayList<>();
        invokes.add(null);
        Object obj = constructor.newInstance(keys, values, dictionary);
        for (int i = 1; i < methods.length; i++) {
            String method = methods[i];
            String parameter = parameters[i];
            Object expected = returns[i];

            Object invoke = null;
            if (method.equals("encrypt")) {
                String word1 = JSON.parseObject(parameter, String[].class)[0];
                invoke = encrypt.invoke(obj, word1);
            } else if (method.equals("decrypt")) {
                String word2 = JSON.parseObject(parameter, String[].class)[0];
                invoke = decrypt.invoke(obj, word2);
            }
            Assertions.assertEquals(expected, String.valueOf(invoke));
            invokes.add(invoke);
        }
        System.out.println(JSON.toJSONString(invokes, SerializerFeature.WRITE_MAP_NULL_FEATURES));
    }
}

9. 进阶：数据库类题目

mysql-test-run 官方文档: https://dev.mysql.com/doc/dev/mysql-server/latest/PAGE_MYSQL_TEST_RUN.htmlopen in new window

普通的二进制包是没有 mysql-test 的，需要额外下载 Test Suite，下载链接: https://dev.mysql.com/downloads/mysql/open in new window

Compressed TAR ArchiveMD5
mysql-8.0.28-linux-glibc2.12-x86_64.tar.xz5be32f68d6859aace1eb61cea1d00bff
mysql-test-8.0.28-linux-glibc2.12-x86_64.tar.xz1aa16282acb18eb7cc74ea024989058b
# 解压压缩包
$ tar xvf mysql-8.0.28-linux-glibc2.12-x86_64.tar.xz
$ tar xvf mysql-test-8.0.28-linux-glibc2.12-x86_64.tar.xz

# clone 本项目到 /mysql-test/suite 目录
$ cd mysql-8.0.28-linux-glibc2.12-x86_64/mysql-test/suite/
$ git clone https://gitee.com/gdut_yy/leetcode-hub-mysql.git
$ cd ..

# 运行 mysql-test-run
$ ./mtr --suite leetcode-hub-mysql

10. 延申：标准输入/输出

对于实际招聘的笔试/机试题目，可能还是 标准输入/输出 更多一点。我们可以通过重定向输入输出流来进行判等（如 System.setIn(InputStream in)、System.setOut(PrintStream out)），如：

package base;

import org.apache.commons.io.FileUtils;
import org.junit.jupiter.api.Assertions;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.net.URL;
import java.nio.charset.StandardCharsets;

public class AbstractOjTests {
    private static final String DEFAULT_INPUT = "input.txt";
    private static final String DEFAULT_OUTPUT = "output.txt";
    protected static final String INPUT2 = "input2.txt";
    protected static final String OUTPUT2 = "output2.txt";

    private final String path;
    private final File actualFile;

    public AbstractOjTests(String path) {
        URL url = getClass().getResource(path);
        URL actualUrl = getClass().getResource("/actual.txt");
        Assertions.assertNotNull(url);
        Assertions.assertNotNull(actualUrl);
        this.path = url.getPath();
        this.actualFile = new File(actualUrl.getPath());
    }

    protected void doSetSystemInOut() throws IOException {
        this.doSetSystemInOut(DEFAULT_INPUT);
    }

    protected void doSetSystemInOut(String inputName) throws IOException {
        File inputFile = new File(path + inputName);
        FileInputStream inputStream = new FileInputStream(inputFile);
        PrintStream printStream = new PrintStream(actualFile);
        System.setIn(inputStream);
        System.setOut(printStream);
    }

    protected void doAssertion() throws IOException {
        this.doAssertion(DEFAULT_OUTPUT);
    }

    protected void doAssertion(String outputName) throws IOException {
        File outputFile = new File(path + outputName);
        String expected = FileUtils.readFileToString(outputFile, StandardCharsets.UTF_8.name());
        String actual = FileUtils.readFileToString(actualFile, StandardCharsets.UTF_8.name());
        Assertions.assertEquals(expected.trim(), actual.trim());
    }
}

11. 链接

以上示例完整代码详见 Github/Gitee 仓库。

（全文完）

Copyright © 2018-2023 gdut-yy