ACM模式学习

由于之前刷题一直是在力扣用的核心模式，而在找工作时很多情况需要用ACM模式来做题，因此需要熟悉一下ACM模式的写法，后续也会用ACM模式重新做一遍hot100，进一步熟悉这种模式。加油！(≧∇≦)ﾉ

hot100的ACM模式解题

1.区分next、nextInt、nextLine

1. next()

功能：读取输入中的下一个单词（以空白符为分隔符）。
行为：
- 跳过输入中的前导空格/换行符。
- 读取字符直到遇到空格、制表符或换行符。
- 不包含末尾的空白符，且不会消耗换行符。
示例：

java

复制
1
2
Scanner sc = new Scanner(System.in);
String word = sc.next();
- 输入 " Hello World\n"，word = "Hello"，剩余输入为 "World\n"。

2. nextInt()

功能：读取输入中的下一个整数。
行为：
- 跳过前导空格/换行符。
- 读取连续数字字符，直到遇到非数字字符（如空格或字母）。
- 不会消耗后续的换行符或空格，可能导致后续nextLine()读到空字符串。
示例：

java

复制
1
2
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
- 输入 " 42\n"，num = 42，剩余输入为 "\n"。
- 输入 "abc" 会抛出 InputMismatchException。

3. nextLine()

功能：读取输入中的一整行内容（到换行符为止）。
行为：
- 读取从当前位置到换行符之间的所有字符（包括空格）。
- 消耗换行符，输入流中不再残留换行符。
示例：

java

复制
1
2
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
- 输入 "Hello World\n"，line = "Hello World"，剩余输入为空。

常见问题及解决方案

问题：混合使用`nextInt()`和`nextLine()`导致跳过输入

场景：

java

复制

1
2
3

Scanner sc = new Scanner(System.in);
int num = sc.nextInt();      // 输入 "42\n"
String line = sc.nextLine(); // line 为空字符串

原因：nextInt()读取了42，但未消耗后面的换行符（\n），nextLine()直接读取了残留的换行符。

解决：在nextInt()后调用一次nextLine()消耗换行符：

java

复制

1
2
3

int num = sc.nextInt();
sc.nextLine(); // 清除残留的换行符
String line = sc.nextLine();

总结

**next()**：适合读取以空格分隔的单词。
**nextInt()**：读取整数，需注意处理残留的换行符。
**nextLine()**：读取整行内容，常用于处理含空格的字符串。

谨慎混用next() 和nextLine()

2.高效处理大量数据

BufferedReader：
- 用于高效读取输入流（比 Scanner 更快）。
- readLine() 方法逐行读取输入。
StringTokenizer：
- 用于将每行输入按空格分割成多个整数。
- hasMoreTokens() 检查是否还有未处理的标记。
- nextToken() 获取下一个标记并转换为整数。

举例说明

//输入：
1 2 3
4 5
0 0 0 0 0
    
//输出
6
9
0

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        
        // 逐行读取输入
        while ((line = br.readLine()) != null) {
            StringTokenizer st = new StringTokenizer(line); // 分割每行的数据
            int sum = 0;
            
            // 遍历每行的所有整数
            while (st.hasMoreTokens()) {
                int num = Integer.parseInt(st.nextToken());
                sum += num;
            }
            
            // 输出当前行的求和结果
            System.out.println(sum);
        }
    }
}

使用技巧

StringTokenizer 高效分割字符串比 split() 更快

3.二叉树相关

1.二叉树的构造

这个是最常用的，可以配合读取一行数据，然后将该行数据转为字符串数组传入该函数得到树根节点

public static TreeNode buildTree(String[] nodes){
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null"))
            return null;

        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        while (!queue.isEmpty() && index < nodes.length){
            TreeNode cur = queue.poll();

            if(index < nodes.length && !nodes[index].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.left);
            }
            index++;

            if(index < nodes.length && !nodes[index].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(cur.right);
            }
            index++;
        }
        return root;
    }

2.二叉树的层序遍历

这个也要熟练掌握，因为有些题目的输出需要，而且有很多层序遍历的变种题目，作为最基础的层序遍历掌握了再写变种题目也会简单的多。

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null)
            return ans;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            int size = deque.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if(node.left != null)
                    deque.offer(node.left);
                if(node.right != null)
                    deque.offer(node.right);
                temp.add(node.val);
            }
            ans.add(temp);
        }
        return ans;
    }

4.数组相关

1.一维数组输出

1	Arrays.toString(nums)

2.二维数组输出

1	Arrays.deepToString(martrix)

3.由输入字符串构建整数数组

Scanner sc = new Scanner(System.in);
   String s = sc.nextLine();
   String[] split = s.split(",");
   int[] nums = new int[split.length];
   for (int i = 0; i < nums.length; i++) {
       nums[i] = Integer.parseInt(split[i]);
   }