先找到一个比较舒服的开始模板，然后逐渐适应 java，然后去使用和之前 c++平替的操作，若这个操作过于复杂，则可以记录下来。

若对于 c++这里的代码有一些比较相似的可以使用的可以列出。

对于需要学习的地方

• 图论：对于正常的图论的遍历和基本的操作(如何 DFS/BFS 遍历)，常用的算法(必须复习)：最短路，拓扑排序，LCA，最小生成树等
• 对于 set，map，queue，list 等常用的 api 需要进行测试，以免知道题目怎么做但是不知道 api
• 然后就是 dfs，对于搜索是非常重要的
• 二维偏序问题的解决方法(使用树状数组的解决方法)，对于数据结构而言，需要会：树状数组，并查集，线段树(会基本的即可)
• 需要稍微看看离散化的内容如何实现
• 对于基础的乘法逆元的问题如何解决？快速幂等的实现
• 复习二分答案的写法
• 对于快速 I/O 而言，先不必了，感觉有点恼火。...‘
• 算法讲解046【必备】构建前缀信息的技巧-解决子数组相关问题 我居然不知道前缀和+Hash 的方法。确实是见识少了。/或者也有其他解法？确实是孤陋寡闻了
  • 题目 1：构建前缀和数组。快速解决子数组范围求和的问题
  • 题目 2：构建前缀和最早出现的位置。返回无序数组中累加和为给定值的最长子数组长度
  • 题目 3：构建前缀和出现的次数。返回无序数组中累加和为给定值的子数组数量
  • 题目 4：构建前缀和最早出现的位置。返回无序数组中正数和负数个数相等的最长子数组长度
  • 题目 5：构建前缀和最早出现的位置。表现良好的最长时间段问题
  • 题目 6：构建前缀和余数最早出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被 p 整除
  • 题目 7：构建前缀奇偶状态最早出现的位置。每个元音包含偶数次的最长子串长度

对应关系：

格式 :<cpp的容器/函数>： java 的形式/替代形式

DeepSeek - 探索未至之境

其中比较重要的有：与 cpp 对应的具体方式，遍历方式，输入输出方式，还有一些 api

还有一些比较重要的类的使用方法，例如：Collections,Arrays 等等。需要详细了解。

需要将常用的算法模板都自己写一写：比如快速幂，逆元，等常见的模板

对应

这里给出 cpp->java 可以相互替换的部分：

• #define int long long 在 java 中直接全部 long/Long
• vector 在 java 中使用普通数组/ArrayList
• Set
  • unordered_set->HashSet
  • set->TreeSet
• Map
  • unordered_map->HashMap
  • map->TreeMap

IO

关于读入：(大数据量)

Scanner sc = new Scanner(System.in);//或者也可以： Scanner scanner = new Scanner(new BufferedInputStream(System.in));
int x = sc.nextInt();
System.out.println(x);

// 更快的IO sync_with_stdio(false)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());

关于输出：(大数据量)

PrintWriter pw = new PrintWriter(System.out));

pw.println(x);  // 比System.out快
pw.flush();     // 记得刷新缓冲区

// 读取单个整数
int a = Integer.parseInt(st.nextToken());

// 读取单个长整数
long b = Long.parseLong(st.nextToken());

// 读取单个双精度浮点数
double c = Double.parseDouble(st.nextToken());

// 读取单个字符串
String s = st.nextToken();

// 读取单字符
char ch = st.nextToken().charAt(0);

//当需要读取整行时（比如包含空格的字符串）：
String line = br.readLine();
st = new StringTokenizer(line); // 如果需要分割可以重新创建st

数组

vector ：普通数组/ArrayList

/** cpp **/
// vector<int> v;
// v.push_back(1);
// v.size();
// v[i];

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.size();
list.get(i);

pair <int,int>

迪杰斯特拉算法的两种语言实现：

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
vector<vector<pair<int, int>>> adj;

vector<int> dijkstra(int start) {
    vector<int> dist(adj.size(), INF);
    priority_queue<pair<int, int>> pq;
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist;
}

import java.util.*;

public class Main {
    static final int INF = (int)1e9;
    static List<List<Pair>> adj;
    
    static class Pair {
        int first, second;
        Pair(int f, int s) { first = f; second = s; }
    }
    
    static int[] dijkstra(int start) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, INF);
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.first - b.first);
        dist[start] = 0;
        pq.add(new Pair(0, start));
        
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int d = p.first, u = p.second;
            if (d > dist[u]) continue;
            
            for (Pair edge : adj.get(u)) {
                int v = edge.first, w = edge.second;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.add(new Pair(dist[v], v));
                }
            }
        }
        return dist;
    }
}

栈，队列，堆

这里还需要对应的 api 函数的使用方式

stack<int> s;
queue<int> q;
priority_queue<int> pq; // 最大堆

Stack<Integer> stack = new Stack<>();
Queue<Integer> queue = new LinkedList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 最小堆
// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
//PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

set&map

set<int> s;
unordered_set<int> us;
map<int, int> m;
unordered_map<int, int> um;

TreeSet<Integer> set = new TreeSet<>(); // 有序
HashSet<Integer> hashSet = new HashSet<>(); // 无序
TreeMap<Integer, Integer> map = new TreeMap<>(); // 有序
HashMap<Integer, Integer> hashMap = new HashMap<>(); // 无序

排序

sort(v.begin(), v.end());

Collections.sort(list); // 对List排序
Arrays.sort(arr); // 对数组排序

lambda 表达式： 更加推荐 Integer.compare(a, b)的写法

List<Integer> list = Arrays.asList(5, 2, 8, 1);
list.sort((a, b) -> b - a); // 降序排序 [8, 5, 2, 1]

这里对于非数值类型的排序：

// 字符串长度排序
List<String> strings = Arrays.asList("apple", "banana", "pear");
strings.sort((s1, s2) -> s1.length() - s2.length());

若规则更加复杂：

// 先按年龄降序，年龄相同按姓名升序
people.sort((p1, p2) -> {
    int ageCompare = p2.age - p1.age;
    if (ageCompare != 0) return ageCompare;
    return p1.name.compareTo(p2.name);
});

对于 lambda 的其他优化(感觉不算特别有用)：

// 等价于 (a, b) -> a - b
Comparator<Integer> natural = Comparator.comparingInt(a -> a);

// 等价于 (a, b) -> b - a
Comparator<Integer> reversed = Comparator.comparingInt(a -> -a);

// 按字符串长度排序
List<String> strings = Arrays.asList("apple", "banana", "pear");
strings.sortlength);
strings.sortlength).reversed();

自定义排序

class Person {
    String name;
    int age;
    // 构造方法等
}

List<Person> people = ...;
people.sort((p1, p2) -> p1.age - p2.age); // 按年龄升序
people.sort((p1, p2) -> p2.age - p1.age); // 按年龄降序

遍历

普通数组：

int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

for (int num : arr) {
    System.out.println(num);
}

Arrays.streamprintln;//性能较差

List 的遍历：

List<Integer> list = Arrays.asList(1, 2, 3);
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

//java中的增强for为只读视图，无法修改元素
for (Integer num : list) {
    System.out.println(num);
}

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Set 遍历：

Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3));
for (Integer num : set) {
    System.out.println(num);
}

Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

Map 的遍历

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
//类似C++17的for(auto& [key, value] : map)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

//不是特别建议
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}

map.forEach((k, v) -> System.out.println(k + ": " + v));

Queue 的遍历

Queue<Integer> q = new LinkedList<>(Arrays.asList(1, 2, 3));
while (!q.isEmpty()) {
    System.out.println(q.poll());
}

// PriorityQueue同样适用
PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(3, 1, 2));
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // 按优先级顺序
}

二分

lower_bound(v.begin(), v.end(), x);
upper_bound(v.begin(), v.end(), x);
binary_search(v.begin(), v.end(), x);

Collections.binarySearch(list, x); // 基本二分查找
// 需要自己实现lower_bound和upper_bound
int lowerBound(List<Integer> list, int x) {
    int l = 0, r = list.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        if (list.get(m) < x) l = m + 1;
        else r = m;
    }
    return l;
}

// 必须先排序！
Arrays.sort(arr);
int pos = Arrays.binarySearch(arr, 5); 

// 返回值：
// 找到则返回索引
// 未找到则返回 -(插入点) - 1

字符串处理

string s = "hello";
s += " world";
s.substr(1, 3);
s.find("ll");

String s = "hello";
s += " world";
s.substring(1, 4); // 注意Java是[1,4)而不是长度
s.indexOf("ll");

大数处理

java 内置高精度模板

BigInteger bigInt = new BigInteger("12345678901234567890");
BigDecimal bigDec = new BigDecimal("123.456");

java 标准库函数

Math.abs(x);
Math.max(a, b);
Math.min(a, b);
// swap需要手动实现
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
//java特有的：>>>无符号右移
boolean isOdd = (x & 1) != 0;  // 比x%2==1更快更安全
a ^= b; b ^= a; a ^= b;// 交换两个变量（不需要临时变量）

存放一些问题

• 对于 pq 而言，遍历的时候为什么输出的不是按照大小排序的？
  • 需要使用的是 while 和 poll 进行遍历
• 那么请你给出 java 的常用容器的遍历方式，如果有多种方式给出说明并说明不同。
  • 详情见遍历部分
• (a, b) -> b - a 的方式一般可以怎样使用呢，可以在哪些场景中使用呢？正着和反着相减分别有怎样的效果呢？
  • (a, b) -> b - a 是降序排列，反之为升序
  • 这里当 b 很大，a 很小的情况下，可能会出现溢出的情况，所以更加推荐使用(a, b) -> Integer.compare(a, b);
  • 更多详情参见排序的 lambda 表达式部分
• TreeSet/HashSet 是做什么的？java 对于 set ，map，list 等有很多种类型，那么哪些是更加对应的，哪些更加是更加适合在算法竞赛中使用的呢？
• Arrays 和 Array 类有什么样的不同，在算法竞赛中有哪些比较常用的函数呢？
• 对于 cpp 中的 tostring,tochar,isdigit 函数 java 中有吗？

//...

IO 总结

写了太多了，太乱了，这里总结：(前提为输入输出数据量大的情况，否则 stdio 即可)

关于标准输入输出：

Scanner scanner = new Scanner(new BufferedInputStream(System.in));

//Scanner scanner = new Scanner(System.in);

scanner.nextInt();
scanner.next();
scanner.nextDouble();
scanner.nextLine();

输出需要了解保留小数等特殊的情况

输入推荐：

• 如果需要更复杂的输入处理，使用 BufferedReader/StreamTokenizer (大量数据的推荐)。

若使用 BufferedReader/StreamTokenizer 的注意事项：

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);

in.nextToken();//每个都要加
//整数
in.nextToken();
int n = (int) in.nval;
//
in.nextToken();
double num = in.nval
//
in.nextToken();
String str = in.sval

//读取数组，ArrayList类似
in.nextToken();
int size = (int)in.nval; // 读取数组大小
int[] array = new int[size];
for (int i = 0; i < size; i++) {
    in.nextToken();
    array[i] = (int)in.nval;
}


//br.close()

读取自定义对象：

class Person {
    String name;
    int age;

    static Person readPerson(StreamTokenizer in) throws Exception {
        in.nextToken();
        String name = in.sval; // 假设第一个是名字
        in.nextToken();
        int age = (int)in.nval; // 然后是年龄
        return new Person(name, age);
    }

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

// 使用
in.nextToken();
int size = (int)in.nval; // 读取Person数组大小
ArrayList<Person> people = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
    people.add(Person.readPerson(in));
}

输出推荐

• (若需要输出例如 ${10}^5$ 个)推荐使用 PrintWriter，API 更多，更易于使用

若使用 PrintWriter 的注意事项：

PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

out.println(compute());
//还有更多API需要补充

//结束处理：（算法题也可以不处理）
out.flush();//这个不太清楚是每次输出都带还是最后带？
out.close();

IO

输入为 ${10}^5$ 级别时，建议使用 BufferedReader / StreamTokenizer？BufferedReader / String.split 呢？
输出为 ${10}^5$ 级别时，建议使用 BufferedWriter？PrintWriter 稍慢

输入推荐：

• 如果数据格式简单，推荐使用 BufferedReader/String.split。
• 如果需要更复杂的输入处理，使用 BufferedReader/StreamTokenizer。

若使用 BufferedReader/String.split 的注意事项：(感觉挺麻烦的，而且相对较慢！)略

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

//读入int
String s=in.readLine();
int n=Integer.parseInt(s);

//若是一行读入多个，空格间隔，读入到ArrayList
ArrayList<String> list = new ArrayList<>();
String line = in.readLine();
String[] items = line.split("\\s+");
for (String item : items) {
	list.add(item);
}

//in.close()

输出(若需要输出很多东西)推荐使用 PrintWriter，API 更多，更易于使用

若使用 PrintWriter

实际上，对于 IO 的哪种方式好，还没有想好！平时使用一个较为简单的，能处理大量数据的即可（能做到不被时间卡住即可！）。

//对于大数据比较好，那就用这个
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
OR
//Scanner scanner = new Scanner(System.in);

接收数据(有新的东西补充即可)

scanner.nextInt();
scanner.next();
scanner.nextDouble();
scanner.nextLine();

需要寻找一个尽量 FAST_IO 的方式！(适用于数据量很大的情况)
需要抛出 throws IOException

// 创建一个 BufferedReader，用于从标准输入流（System.in）读取数据  
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
// 创建一个 StreamTokenizer，用于将输入流解析为标记（tokens）  
StreamTokenizer in = new StreamTokenizer(br);  
// 创建一个 PrintWriter，用于向标准输出（System.out）写入数据（结果）  
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));  

//结束位置->
// 刷新输出流，确保所有数据都被写出
out.flush();
// 关闭流，进行资源释放
out.close();
br.close();

若要读入(这里的读入还是相对麻烦的！)

//读入一个int
in.nextToken();
int n = (int) in.nval;

所以在数据量不大的情况下，尽量用 Scanner 即可。

普通数组

和 c++很像

int[] array = new int[5]; // 创建一个长度为5的int数组，初始值为0

//复制整个数组：
int[] copy = array.clone();

Arrays.fill(array, value);

int[][] twoDimArray = new int[3][2]; // 创建一个3x2的二维数组

//0 1 0 0 0 ->
//[0, 1, 0, 0, 0]
String arrayString = Arrays.toString(array);

vector

对于 c++的 vector，在 java 中用 ArrayList 替代即可。

//vector<int> a(10,0);
ArrayList<Integer> a=new ArrayList<>(Collections.nCopies(10, 0));

//a[0]=1;
a.set(0, 1);

//快速遍历方式
a.forEachprintln;

//vector<vector<int>> a(26);
ArrayList<ArrayList<Integer>> a = new ArrayList<>(26);  
for(int i=0;i<26;i++)a.add(new ArrayList<>());


//这种方式不推荐，所有数组都引用的同一个对象！会出问题！
//ArrayList<ArrayList<Integer>> a = new ArrayList<>(Collections.nCopies(26, new ArrayList<>()));  


// 向指定位置插入元素  
a.get(0).add(1);  //a[0].push_back(1);
a.get(0).add(2); 

// 获取指定位置的元素  
int element = a.get(0).get(1);//a[0][1];

对于排序

• 推荐 Collections.sort 和 lambda 方式进行排序(总之，我认为越简单越好！)
• a.sort((x,y)->x-y); 深得我心

//sort(a.begin(),a.end());
a.sort(new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o1 - o2;//反过来则为降序排序
	}
});
//lambda<->等价
a.sort((x,y)->x-y);

Collections.sort(a,new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2-o1;
	}
});

二分：

//int x=lower_bound(ans.all(),k)-ans.begin();
int x=Collections.binarySearch(ans, k);

String

//s[i]
s.charAt(i);