4.10
动态规划
不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
n为1的时候有一棵树，n为2有两棵树，这个是很直观的。
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
如图所示：
确定dp数组（dp table）以及下标的含义
dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。
确定递推公式
在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素，从1遍历到i为止。
所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
j-1 为j为头结点左子树节点数量：二叉搜索树，头节点的左子树一定有j-1 个节点，右子树有 i-j个节点
dp数组如何初始化
初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
那么dp[0]应该是多少呢？
从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1
确定遍历顺序
首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
那么遍历i里面每一个数作为头结点的状态，用j来遍历。
代码如下：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
举例推导dp数组
n为5时候的dp数组状态如图：
class Solution {
public int numTrees(int n) {
// 初始化动态规划数组dp，长度为n+1，因为我们要从0计算到n
int[] dp = new int[n+1];
// 基础情况：当树为空时（0个节点），只有一种结构，即空树
// 当树只有一个节点时，也只有一种结构
dp[0] = 1;
dp[1] = 1;
// 开始填充dp数组，从2到n，i代表节点的总数
for(int i = 2; i <= n; i++){
// 对于每一个i（节点总数），我们尝试每一个j作为根节点
for(int j = 1; j <= i; j++){
// dp[i]累加上以j为根节点时左、右子树的组合数量。
// 左子树的节点数量是j-1，对应的二叉搜索树数量为dp[j-1]
// 右子树的节点数量是i-j，对应的二叉搜索树数量为dp[i-j]
// 以j为根节点时的总树数量为左、右子树数量的乘积
dp[i] += dp[j-1] * dp[i-j];
}
}
// 返回总节点数为n时的二叉搜索树数量
return dp[n];
}
}
注意细节
//初始化0个节点和1个节点的情况 dp[0] = 1; dp[1] = 1;
在这段代码中，
dp[1] = 1;这行代码强调的是当只有一个节点时，存在的二叉搜索树的数量。这是因为基于二叉搜索树的定义，当只有一个节点时，只可能构成一棵树（即只有根节点本身），无论这个节点的值是什么。这是一个初始条件，与dp[0] = 1;一起构成了动态规划的基础情况。动态规划基础情况解释
dp[0] = 1;表示当树为空时，也就是没有节点时，按定义可以认为存在一种形状的二叉树，那就是空树。这个基础情况对于解题是必需的，因为在计算以某个节点为根节点时，左子树或右子树可能为空，这时候就需要用到dp[0]。dp[1] = 1;表示当树只有一个节点时，存在一种形状的二叉搜索树，即仅包含根节点的树。这个情况是构造所有其他情况的基础。无论这个单一节点的值是多少，在二叉搜索树的上下文中，它只能形成一种结构。
为何这两个基础情况重要
这两个基础情况为整个动态规划过程提供了起点。在计算
dp[i]（即i个节点能构成的二叉搜索树的数量）时，我们需要考虑每个节点作为根节点时左右子树的节点分布。根据二叉搜索树的性质，左子树的所有节点必须小于根节点，右子树的所有节点必须大于根节点。因此，对于每个j（从1到i），我们都假设它是根节点，那么左子树的节点数就是j-1（因为是从1到j-1），右子树的节点数就是i-j（因为是从j+1到i）。于是，当
j为根节点时，该树的结构数为dp[j-1] * dp[i-j]。累加每个j作为根节点时的情况，就得到了i个节点能构成的二叉搜索树的总数。这个过程基于一个关键观察：二叉搜索树的数量只取决于树中节点的数量，而与节点的具体值无关。这允许我们通过动态规划的方式，从小到大计算出任意
n个节点所能形成的二叉搜索树数量。//对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加 //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j dp[i] += dp[j-1] * dp[i-j];
0-1背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
例如：背包最大重量为4。
物品为：
重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 问背包能背的物品最大价值是多少？
如果暴力：就回溯算法遍历，有2的n次方种情况
二维dp数组01背包
确定dp数组以及下标的含义
对于背包问题，有一种写法， 是使用二维数组，即dpi 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的
dp[i][j] 是从 0到i 之间的物品， 任取放到容量为 j 的背包里
确定递推公式
再回顾一下dpi的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dpi，
不放物品i：由
dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)放物品i：由
dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i]（物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max( dp[i - 1][j] , dp[i - 1][j - weight[i]] + value[i]);
递推公式由 左上方 和 正上方 推导而来
dp数组如何初始化
关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dpi的定义出发，如果背包容量j为0的话，即dpi，无论是选取哪些物品，背包价值总和一定为0。如图：
背包容量为 0 时，初始化dq数组为0
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i是由 i-1 推导出来，那么i为0的时候就一定要初始化。dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，
dp[0][j]应该是 0，因为背包容量比编号0的物品重量还小。当
j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号0物品。
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
确定遍历顺序
在如下图中，可以看出，有两个遍历的维度：物品与背包重量
那么问题来了，先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：
再来看看先遍历背包，再遍历物品呢?大家可以看出，虽然两个for循环遍历的次序不同，但是dpi所需要的数据就是左上角，根本不影响dpi公式的推导！**其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了**。
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
// 循环读取每组测试数据
while(in.hasNextInt()){
int M = in.nextInt(); // 物品数量
int N = in.nextInt(); // 背包容量
int[] weights = new int[M]; // 物品重量数组
// 读取每个物品的重量
for(int i = 0; i < M; i++){
weights[i] = in.nextInt();
}
int[] values = new int[M]; // 物品价值数组
// 读取每个物品的价值
for(int i = 0; i < M; i++){
values[i] = in.nextInt();
}
// 调用动态规划方法求解最大价值，并打印结果
int res = find(weights, values, M, N);
System.out.println(res);
}
}
private static int find(int[] weights, int[] values, int m, int n){
// 动态规划数组，dp[i][j]表示考虑前i个物品，当背包容量为j时能够获得的最大价值
int[][] dp = new int[m][n+1];
// 初始化动态规划数组的第一列，当背包容量为0时，能获得的最大价值自然为0
for(int i = 0; i < m; i++){
dp[i][0] = 0;
}
// 初始化动态规划数组的第一行，考虑只有第一个物品时的情况
for(int j = 0; j <= n; j++){
// 如果背包容量大于等于第一个物品的重量，则背包的价值为第一个物品的价值
if(j >= weights[0]){
dp[0][j] = values[0];
}else{
// 否则背包无法装下任何物品，价值为0
dp[0][j] = 0;
}
}
// 填充动态规划数组的剩余部分
for(int i = 1; i < m; i++){
for(int j = 1; j <= n; j++){
// 如果当前背包容量小于第i个物品的重量，则无法装下该物品
if(j < weights[i]){
/**
* 当前背包的容量都没有当前物品i大的时候，是不放物品i的
* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i-1][j];
}else{
// 否则，考虑装下该物品与不装下该物品的情况，取最大价值
/**
* 当前背包的容量可以放下物品i
* 那么此时分两种情况：
* 1、不放物品i
* 2、放物品i
* 比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weights[i]] + values[i]);
}
}
}
// 返回考虑所有物品且背包容量为n时能获得的最大价值
return dp[m-1][n];
}
}
注意细节
// 动态规划数组，dp[i][j]表示考虑前i个物品，当背包容量为j时能够获得的最大价值int[][] dp = new int[m][n+1];要考虑当前
j能否装下dp[i][j] = dp[i-1][j];以及能装下时，是否要装下
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weights[i]] + values[i]);
4.12
数组
质数合数
小红有一个数组，她想知道这个数组不同的质数和不同的合数共有多少个。
package 笔试;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class 不同的质数和不同的合数共有多少个 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()){
// 读取第一个整数n
int n = scanner.nextInt();
Set<Integer> primes = new HashSet<>(); // 存储不同的质数
Set<Integer> composites = new HashSet<>(); // 存储不同的合数
// 读取整数并分类
for (int i = 0; i < n; i++) {
int number = scanner.nextInt();
if (isPrime(number)) { // 检查是否为质数
primes.add(number);
} else if (number > 1) { // 排除1，因为1既不是质数也不是合数
composites.add(number);
}
}
int count = primes.size() + composites.size();
System.out.println(count);
System.out.println("不同质数的数量: " + primes.size());
System.out.println("不同合数的数量: " + composites.size());
}
}
// 判断一个数是否为质数
public static boolean isPrime(int number) {
// 小于2的数不是质数
if (number < 2) {
return false;
}
// 只需要检查到sqrt(number)即可
for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
return false; // 如果找到其他因子，则不是质数
}
}
return true; // 如果没有找到因子，则是质数
}
}
贪心
单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
class Solution {
// 方法接收一个整数n，并返回一个单调递增的整数
public int monotoneIncreasingDigits(int n) {
// 将整数n转换成字符串
String s = String.valueOf(n);
// 将字符串转换成字符数组，以便逐位操作
char[] chars = s.toCharArray();
// 'start'将标记从哪一位开始需要将后续的所有数位变成9
int start = s.length();
// 从倒数第二位开始向前遍历字符数组
for (int i = s.length() - 2; i >= 0; i--) {
// 如果当前位的数字大于其右侧相邻位的数字
if (chars[i] > chars[i + 1]) {
// 将当前位的数字减1
chars[i]--;
// 标记从当前位的下一位开始，后面的所有数位都将变成9
start = i + 1;
}
}
// 从'start'位开始，将后续所有数位变成9
for (int i = start; i < s.length(); i++) {
chars[i] = '9';
}
// 将修改后的字符数组转换回整数并返回
return Integer.parseInt(String.valueOf(chars));
}
}
本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。
想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。
4.13
双指针
区间删除
小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。
小美想知道，一共有多少种不同的删除方案?
输入描述 第一行输入两个正整数n，k。
第二行输入n个正整数ai，代表小美拿到的数组。第一行输入两个正整数n，k。
第二行输入n个正整数ai，代表小美拿到的数组
import java.util.Scanner;
public class Main {
// 定义最大数组大小
static final int N = 1000010;
// 定义两个数组，用于存储每个数字分解后2的个数和5的个数
static int[] a2 = new int[N];
static int[] a5 = new int[N];
// 定义全局变量，cnt2 和 cnt5 用于累计整个数组中2的个数和5的个数
static int cnt2 = 0, cnt5 = 0;
// 定义数组大小，目标0的个数，以及临时变量x
static int n, k, x;
// 计算数组中每个数分解后2的个数和5的个数
public static void cnt2Cnt5Count() {
Scanner input = new Scanner(System.in);
// 遍历数组
for (int i = 0; i < n; i++) {
x = input.nextInt(); // 读入每个数
// 计算当前数分解出的2的个数
while (x % 2 == 0) {
a2[i]++;
x /= 2;
cnt2++;
}
// 计算当前数分解出的5的个数
while (x % 5 == 0) {
a5[i]++;
x /= 5;
cnt5++;
}
}
// 不再读入数据，所以关闭Scanner
input.close();
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
n = input.nextInt(); // 读入数组大小
k = input.nextInt(); // 读入目标0的个数
cnt2Cnt5Count(); // 调用函数计算2的和5的个数
int l = 0; // 左指针
long res = 0; // 结果变量，用于存储方案总数
// 右指针开始遍历数组
for (int r = 0; r < n; r++) {
// 更新包含当前右指针所指元素的2的和5的个数
cnt2 -= a2[r];
cnt5 -= a5[r];
// 使用左指针和右指针维护区间
while (Math.min(cnt2, cnt5) < k && l <= r) {
// 左指针右移，更新2和5的个数
cnt2 += a2[l];
cnt5 += a5[l];
l++;
}
// 将所有可能的左指针位置对应的方案数加到结果中
res += (long) (r - l + 1);
}
// 输出所有可能的方案总数
System.out.println(res);
}
}
注意细节
双指针，维护删除该区间后，剩余的cnt2和cnt5的最小数量，也就是能尾缀0的最小数量要满足要求（2和5都存在1个时，才构成1个0）
遍历向右
r不满足要求，就要l向右移动，缩小区间，来达到当前r最极限的满足要求的位置为什么是
r - l + 1呢？因为在索引l和r之间（包括l和r），你可以选择删除以下区间：从
l到r从
l+1到r...
从
r到r（实际上没有删除任何元素）
注意用
(long)
1. 完美矩阵
2*2的矩阵，如果所有数都相同，就是完美矩阵
package 笔试.;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
/**
* 输入 n m ；然后是矩阵，要求矩阵中多少个2*2的好矩阵
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int m = in.nextInt();
int[][] nums = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
nums[i][j] = in.nextInt();
}
}
int count = 0;
for(int i = 0; i < n - 1; i++){ // 好矩阵至少2维度
for(int j = 0; j < m - 1; j++){
if(nums[i][j] == nums[i+1][j+1] && nums[i][j] == nums[i+1][j] && nums[i][j] == nums[i][j+1]){
count++;
}
}
}
System.out.println(count);
}
}
}
2. 操作最大次数
package 笔试.;
import java.util.Arrays;
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
long k = in.nextLong();
long[] nums = new long[n];
for(int i = 0; i < n; i++){
nums[i] = Math.abs(in.nextLong());
}
Arrays.sort(nums);
long used_k = 0;
int res = 0;
for(int i = 0; i < n; i++){
if(used_k + nums[i] <= k){
used_k += nums[i];
res++;
}else {
break;
}
}
System.out.println(res);
}
}
}
3. 红黑节点
小美有一棵有n个节点的树，根节点为1号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。 输入描述： 第一行输入一个整数 n(1 <n < 10^5)表示节点数量, 第二行输入一个长度为n的字符串s表示节点的颜色，第i个节点的颜色为si，若 si为'B' 表示节点的颜色为黑色，若si为'R' 则表示节点的颜色为红色。 接下来n -1行，每行输入两个整数 u,v(1≤u,v≤n)表示树上的边 输出描述： 输出一个整数表示答案。
示例 1： 输入： 3 BRB 1 2 2 3 输出：2 说明： 1号和2号节点的子树都满足条件。
package 笔试.;
import java.util.*;
public class Main3 {
static List<Integer>[] tree;
static char[] colors;
static boolean[] visi;
static int resCountNode;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt(); // 节点数量
in.nextLine();
String s = in.nextLine();
colors = s.toCharArray();
tree = new ArrayList[n+1];
for(int i = 0; i <=n; i++){
tree[i] = new ArrayList<>();
}
for(int i = 0; i < n-1; i++){
int u = in.nextInt();
int v = in.nextInt();
tree[u].add(v);
tree[v].add(u);
}
visi = new boolean[n+1];
dfs(1);
System.out.println(resCountNode);
}
}
static class Res{
int redCount;
int blackCount;
Res(int redCount, int blackCount){
this.redCount = redCount;
this.blackCount = blackCount;
}
}
private static Res dfs(int node){
visi[node] = true;
int red = 0;
int black = 0;
if(colors[node - 1] == 'R'){
red++;
} else if (colors[node - 1] == 'B') {
black++;
}
for(int child: tree[node]){
if(!visi[child]){
Res res = dfs(child);
red += res.redCount;
black += res.blackCount;
}
}
if(red > 0 && black > 0){
resCountNode++;
}
return new Res(red, black);
}
}
示例1: 线性树（链状树）
首先，我们以你最初提到的输入为例，其中节点编号和连接如下：
节点数: 4 颜色串: BRBB 连接: 1 - 2 2 - 3 3 - 4这可以用下面的形式可视化：
1 (R) -- 2 (B) -- 3 (B) -- 4 (B)这里的树实际上是一个单线链状结构，每个节点都只与前一个和后一个节点相连（除了第一个和最后一个节点）。
示例2: 分支树
为了展示更通用的树结构，我们可以考虑另一个例子，比如：
节点数: 5 颜色串: BRBBB 连接: 1 - 2 1 - 3 3 - 4 3 - 5这个树结构可以画成如下形状：
1 (R) / \ 2 (B) 3 (B) / \ 4 (B) 5 (B)在这个示例中，节点1是根节点，它有两个子节点2和3。节点3又有两个子节点，分别是4和5。这展示了一个典型的树状分支结构，每个节点可以有多个子节点。
4. 因子数×
小美拿到了一个数组，她有q次查询，每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗? 注:由于数组元素过多，所以是按连续段的方式给定。例如，[1,1,2,3,3,3]有2个1，1个2，3个3，因此表示为<2,1>,<1,2>,<3,3>。 输入描述： 第一行输入两个正整数n,m，代表数组的大小，以及连续段的数量。 接下来的m行，每行输入两个正整数ui,vi，代表一段区间内有vi个ui。 接下来的一行输入一个正整数q，代表询问次数。 接下来的q行，每行输入两个正整数l,r，代表询问的是第l个数到第r个数的乘积的因子数量。 1≤n≤10^14, 1≤m, q≤10^5, 1≤ui≤10, 1≤vi≤10^9, 1≤l≤r≤n, 保证所有的vi之和恰好等于n。 输出描述: 输出q行，每行输出一个整数，代表最终的乘积因子数量。由于答案可能过大,请对10^9+ 7取模。 示例1: 输入: 6 3 1 2 2 1 3 3 2 1 3 2 6 输出 2 8 说明: 该输入表示的数组是[1,1,2,3,3,3]，第一次询问的答案是2的因子，有1和2这2个因子:第二次询问的是233*3=54的因子数量，共有1,2,3,6,9,18,27,54这8个因子。
如果数很少（这并不符合题意）
package 笔试.;
import java.util.*;
public class Main4 {
/**
* 所有元素的乘积有多少因子
*/
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int m = in.nextInt();
int[] nums = new int[n];
int numsIndex = 0;
for(int i = 0; i < m ; i++){
int u = in.nextInt();
long v = in.nextLong();
for(int j = 0; j < v; j++){
nums[numsIndex] = u;
numsIndex++;
}
}
int q = in.nextInt();
// q次询问
for(int i = 0; i < q ; i++){
int l = in.nextInt();
int r = in.nextInt();
findCountNum(nums, l, r);
}
}
}
private static void findCountNum(int[] nums, int l, int r){
int res = 0;
int value = 1;
for(int i = l-1; i < r; i++){
value *= nums[i];
}
for(int i = 1; i <= Math.sqrt(value); i++){
if(value % i == 0){
if(i == value / i){
res = (res + 1) % MOD;
}else{
res = (res + 2) % MOD;
}
}
}
res = res % MOD;
System.out.println(res);
}
}
5. 子串×
小美有一个数字串 x ，她将 x 的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合 S 中。 她想知道集合 S 的大小最终有多大，请你帮她计算一下吧。 (注意:根据数学知识我们知道，集合中的元素具有互异性，即两两不同) (在本题中，子序列可以存在前导0，也就是说如“011"和“00011”是不同的) 输入描述： 输入包含一行一个数字串x (0 ≤x≤ 10^1000000)，表示小美的数字x。 ( x可能含有前导 0) 输出描述： 输出包含一行一个整数，表示集合的大小。 (由于结果可能很大，因此你只要输出答案对 1000000007 取模的结果。 补充说明： 子序列:指从一个字符串中任选一些位置删除(也可以不删)后得到的结果字符串。 示例1： 输入： 12121 输出： 9 说明： 1 12 121 1212 12121 2 21 212 2121 集合中共这9个子序列.
4.15
字符串
HJ1 字符串最后一个单词的长度
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextLine()) { // 注意 while 处理多个 case
String[] strs = in.nextLine().split(" ");
int n = strs.length;
String s = strs[n-1];
int count = 0;
for(Character c: s.toCharArray()){
count++;
}
System.out.println(count);
}
}
}
HJ2 计算某字符出现次数
写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String str = in.nextLine().toLowerCase();
String tar = in.nextLine().toLowerCase();
int res = str.length() - str.replaceAll(tar,"").length();
System.out.println(res);
}
}
贪心
无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
移除区间的思路：
贪心算法的核心思想是，在每一步选择中都采取当前情况下最优的选择（即局部最优解），希望通过一系列的局部最优选择，达到全局的最优解。在这个问题中，局部最优的策略是：
按起始位置排序：首先按照区间的起始位置进行排序。这样做的目的是按顺序处理区间，使得一旦发生重叠，就可以立即处理。
处理重叠：遍历排序后的区间列表，使用变量
pre来记录当前保留区间的结束位置。对于每个区间：如果当前区间的起始位置小于
pre：说明当前区间与上一个保留的区间有重叠。因此，为了使总体重叠最小，需要进行如下操作：
增加移除计数：记录一次重叠，即这意味着需要“移除”一个区间。
选择结束较早的区间保留：更新
pre为当前区间和前一个区间中结束时间较早的那个。这是因为结束较早的区间留给后面的区间更大的空间，减少未来的重叠机会。
如果当前区间的起始位置大于或等于
pre：说明当前区间与前一个区间不重叠，更新pre为当前区间的结束位置。
这种方法通过每次遇到重叠时都优先保留结束时间较早的区间，确保了每步决策都尽可能减少未来的重叠可能，从而实现了整体的最优解策略。
实例解释：
假设有区间 [1,2], [2,3], [1,3]：
首先按起始排序：[1,2], [1,3], [2,3]
比较 [1,2] 和 [1,3]，它们重叠，保留结束较早的 [1,2]，移除计数为 1。
接下来比较保留的 [1,2] 和 [2,3]，它们不重叠，更新
pre为 [2,3] 的结束位置。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
int pre = intervals[0][1]; // 第一个的右边界
int count = 0;
for(int i = 1; i < intervals.length; i++){
if(pre > intervals[i][0]){
count++; // 有重叠
pre = Math.min(pre, intervals[i][1]); // 移动缩小区间，使之不重叠
}else{
pre = intervals[i][1];
}
}
return count;
}
}
注意细节
思路是：左侧排序，然后，重叠的部分，就加一需要移除，同时，实际去移除，缩小右边界为 pre 或 当前右边界 最小的一个
Lambda 表达式解释
(a, b) -> a[0] - b[0]
这个Lambda表达式用于比较两个区间
a和b，它们都是数组，其中a[0]和b[0]分别是区间a和b的起始位置。这个表达式的结果是一个整数，其值是a[0] - b[0]：如果
a[0] < b[0]，则结果为负数，表示a应该在b前面。如果
a[0] > b[0]，则结果为正数，表示a应该在b后面。如果
a[0] == b[0]，则结果为0，表示a和b在排序时可视为等价（排序算法可以自行决定它们的相对位置）。
为什么是升序
这个比较逻辑决定了数组会按照每个区间的起始位置的升序进行排序。这是因为
Arrays.sort()根据比较器的结果进行排序，当比较器返回负数时，它会将较小（这里是指起始位置较小）的元素放在前面。
划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
如图：
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new ArrayList<>(); // 用于存放每个片段的长度
int[] lastIndex = new int[26]; // 存放每个字符最后一次出现的索引
// 第一次遍历：记录每个字符最后出现的位置
for(int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
lastIndex[c - 'a'] = i; // 通过字符减去 'a' 得到索引，记录该字符最后一次出现的位置
}
int last = -1; // 上一个片段的结束索引
int maxTempIndex = 0; // 当前片段的最远索引
// 第二次遍历：根据字符最后一次出现的位置来确定片段的边界
for(int i = 0; i < S.length(); i++) {
maxTempIndex = Math.max(maxTempIndex, lastIndex[S.charAt(i) - 'a']); // 更新当前片段的最远索引
if (maxTempIndex == i) { // 如果当前索引等于片段的最远索引，说明可以结束当前片段
list.add(i - last); // 计算当前片段的长度并添加到结果列表
last = i; // 更新上一个片段的结束索引
}
}
return list; // 返回结果列表
}
}
1. 使用 char[] 数组
javaCopy code char[] chars = S.toCharArray();
在这个版本中，将字符串 S 转换为字符数组 chars。这样做的好处是在随后的循环中访问每个字符可能比直接从字符串中访问更快，因为它减少了每次迭代时的方法调用开销（String.charAt()）。Java 字符串内部是字符数组，但每次调用 charAt() 都可能涉及范围检查和其他检查，而直接操作数组则可以避免这些。
2. 使用 LinkedList
javaCopy code List<Integer> list = new LinkedList<>();
使用 LinkedList 而不是 ArrayList 在这种情况下的优势主要体现在添加元素的操作上。因为我们在循环中频繁地在列表的末尾添加元素，LinkedList 的 add() 操作时间复杂度为 O(1)。虽然 ArrayList 的 add() 操作通常也是 O(1)，但当需要扩容时，它的时间复杂度会变为 O(n)。不过，考虑到 ArrayList 的扩容并不频繁，并且在大多数情况下，内存连续性和较小的内存开销使得 ArrayList 在许多场景下仍然有更好的性能。
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new LinkedList<>();
int[] edge = new int[26];
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
edge[chars[i] - 'a'] = i;
}
int idx = 0;
int last = -1;
for (int i = 0; i < chars.length; i++) {
idx = Math.max(idx,edge[chars[i] - 'a']);
if (i == idx) {
list.add(i - last);
last = i;
}
}
return list;
}
}
赛码网试用
排序
FindK
描述
给你三个有序数组，求这三个数组中的第k大元素是多少。
输入描述
第一行两个整数n,k，表示三个数组的长度，以及题目要求第k大的数是多少。
第二行n个整数ai，表示第一个数组的元素
第三行n个整数bi，表示第二个数组的元素
第四行n个整数ci，表示第三个数组的元素
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
int k = in.nextInt();
int[] nums = new int[n *3];
for(int i = 0; i < n*3; i++){
nums[i] = in.nextInt();
}
Arrays.sort(nums);
System.out.println(nums[k-1]);
}
}
}
题目列表
描述
小明同学收集了n道编程问题，他想做一个网站把这些题目放在上面。对于每一道问题给出问题的名称name，该问题的提交次数X，该问题的通过次数Y。一个问题的通过率定义为Y/X。小明根据通过率把问题难度分了3个等级：
1、通过率0%<= Y/X <= 30%，难度为5。
2、通过率30%< Y/X <=60%，难度为4。
3、通过率60%< Y/X <=100%，难度为3。
为了方便大家查阅题目，小明希望所有题目按照题目名称的字典序从小到大排列在网站上，并且能显示每个题目的难度。你能帮他实现吗？
输入描述
输入一个数n，接下来有n(n <=100)行，每行输入一个字符串name，整数X，整数Y，依次表示每个题目的名称，提交次数和通过次数。name的长度不超过100，name中只有小写字母，1<=X<=1000，0<=Y<=X。 输入保证所有题目的名称不同。
4 math 100 90 algorithm 10 8 string 50 1 dp 100 50
输出描述
输出n行，按字典序从小到大排序后的题目，每行先输出一个字符串，题目的名称，再输出一个数，题目的难度等级，用一个空格隔开。
algorithm 3 dp 4 math 3 string 5
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
if (!scanner.hasNextInt()) {
System.out.println("No input provided");
return; // Early return if no input to prevent NoSuchElementException
}
int n = scanner.nextInt(); // 读取题目总数
scanner.nextLine(); // 读取剩余的行结束符
List<Problem> problems = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!scanner.hasNextLine()) {
System.out.println("Insufficient input lines");
return; // Early return if not enough lines are provided
}
String line = scanner.nextLine();
String[] parts = line.split(" ");
if (parts.length < 3) {
System.out.println("Incorrect input format");
return; // Early return if the input format is not correct
}
String name = parts[0];
int X = Integer.parseInt(parts[1]);
int Y = Integer.parseInt(parts[2]);
Problem problem = new Problem(name, X, Y);
problems.add(problem);
}
// 对问题列表按名称排序
Collections.sort(problems, Comparator.comparing(problem -> problem.name));
// 输出结果
for (Problem problem : problems) {
System.out.println(problem.name + " " + problem.getDifficulty());
}
}
static class Problem {
String name;
int X, Y;
public Problem(String name, int X, int Y) {
this.name = name;
this.X = X;
this.Y = Y;
}
public int getDifficulty() {
double rate = Y * 100.0 / X; // 计算通过率，转换为百分比
if (rate <= 30.0) {
return 5;
} else if (rate <= 60.0) {
return 4;
} else {
return 3;
}
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取题目总数
scanner.nextLine(); // 跳过行尾的换行符
List<String[]> problems = new ArrayList<>();
for (int i = 0; i < n; i++) {
String line = scanner.nextLine();
String[] details = line.split(" ");
problems.add(details);
}
// 对问题按名称排序
Collections.sort(problems, (a, b) -> a[0].compareTo(b[0]));
// 输出排序和计算后的结果
for (String[] problem : problems) {
int X = Integer.parseInt(problem[1]);
int Y = Integer.parseInt(problem[2]);
int difficulty = calculateDifficulty(X, Y);
System.out.println(problem[0] + " " + difficulty);
}
}
private static int calculateDifficulty(int X, int Y) {
double rate = Y * 100.0 / X;
if (rate <= 30.0) {
return 5;
} else if (rate <= 60.0) {
return 4;
} else {
return 3;
}
}
}
4.16
回溯算法
子集问题分析：
时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。
空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。
排列问题分析：
时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ..... 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：
result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。空间复杂度：$O(n)$，和子集问题同理。
组合问题分析：
时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：$O(n)$，和子集问题同理。
一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！
而使用used数组在时间复杂度上几乎没有额外负担！
使用set去重，不仅时间复杂度高了，空间复杂度也高了
全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路：
排序
用used数组去重
size = length，添加path
回溯
还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
class Solution {
//存放结果
List<List<Integer>> result = new ArrayList<>();
//暂存结果
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTrack(nums, used);
return result;
}
private void backTrack(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
//如果同⼀树⽀nums[i]没使⽤过开始处理
if (used[i] == false) {
used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
path.add(nums[i]);
backTrack(nums, used);
path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
used[i] = false;//回溯
}
}
}
}
每层一个hashSet去重：
class Solution {
private List<List<Integer>> res = new ArrayList<>(); // 用于存储所有的排列结果
private List<Integer> path = new ArrayList<>(); // 用于存储当前的排列路径
private boolean[] used = null; // 用于标记数组中的元素是否被使用过
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length]; // 初始化used数组，长度与nums相同
Arrays.sort(nums); // 对数组进行排序，有助于后续的去重操作
backtracking(nums); // 开始回溯
return res; // 返回最终的排列结果
}
public void backtracking(int[] nums) {
if (path.size() == nums.length) { // 如果当前路径长度等于nums的长度，说明找到了一个完整的排列
res.add(new ArrayList<>(path)); // 将当前路径复制到结果中
return;
}
HashSet<Integer> hashSet = new HashSet<>(); // 用于当前层的去重，保证在同一层递归中不使用重复元素
for (int i = 0; i < nums.length; i++) {
if (hashSet.contains(nums[i])) // 如果当前元素在本层已被处理过，跳过
continue;
if (used[i] == true) // 如果当前元素已在其他位置被使用，跳过
continue;
hashSet.add(nums[i]); // 将当前元素添加到HashSet中，记录本层已处理过该元素
used[i] = true; // 标记当前元素已被使用
path.add(nums[i]); // 将当前元素添加到路径中
backtracking(nums); // 递归继续处理下一个元素
path.remove(path.size() - 1); // 回溯，移除路径中的最后一个元素
used[i] = false; // 回溯，取消当前元素的使用标记
}
}
}
注意细节
排列问题，不直接从
startIndex开始，而是遍历从used[i] == false开始去重要用
continue：if(i > 0 && nums[i] == nums[i-1] && used[i-1] == true){continue;}
重新安排行程
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
提示：
如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
所有的机票必须都用一次 且 只能用一次。
示例 1：
输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2：
输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
这道题目有几个难点：
一个行程中，如果航班处理不好容易变成一个圈，成为死循环
有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
搜索的过程中，如何遍历一个机场所对应的所有机场。
如何理解死循环
对于死循环，我来举一个有重复机场的例子：
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。
回溯【会超时】
class Solution {
private LinkedList<String> res;
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backTracking((ArrayList) tickets, used);
return res;
}
public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
for (int i = 0; i < tickets.size(); i++) {
if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
path.add(tickets.get(i).get(1));
used[i] = true;
if (backTracking(tickets, used)) {
return true;
}
used[i] = false;
path.removeLast();
}
}
return false;
}
}
官方【没看懂】
class Solution {
// 使用一个哈希图来存储从每个机场出发可以到达的目的地列表。键是出发机场，值是优先级队列（最小堆）。
Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
// 用来存储最终的行程。
List<String> itinerary = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
// 遍历所有机票，构建图。
for (List<String> ticket : tickets) {
String src = ticket.get(0), dst = ticket.get(1);
// 如果map中还没有src这个出发点，就新建一个优先级队列，并放入map中。
if (!map.containsKey(src)) {
map.put(src, new PriorityQueue<String>());
}
// 将目的地添加到对应出发点的优先级队列中。
map.get(src).offer(dst);
}
// 从JFK机场开始进行深度优先搜索。
dfs("JFK");
// 因为我们是在离开每个机场时才将机场添加到行程中，所以最终的行程是反向的。这里我们需要反转它。
Collections.reverse(itinerary);
return itinerary;
}
public void dfs(String curr) {
// 当前机场还有可到达的目的地时，继续搜索。
while (map.containsKey(curr) && map.get(curr).size() > 0) {
// 获取并移除当前机场的字典序最小的目的地。
String tmp = map.get(curr).poll();
// 深度优先搜索这个目的地。
dfs(tmp);
}
// 当一个机场没有其他可到达的目的地时，将其添加到行程中。
// 注意：这是在递归回溯的过程中完成的，所以是从行程的最后一个目的地向前添加的。
itinerary.add(curr);
}
}
构图深搜
数据结构初始化
图（Graph）：使用一个
HashMap，键是字符串（代表机场的代码），值是一个PriorityQueue（优先队列），用于存储可以从该机场直接到达的其他机场。优先队列自然地按照字母顺序排序，确保我们总是先访问字典序最小的目的地。行程（Itinerary）：使用
LinkedList，便于在列表的前端插入元素。这对于我们在递归过程中构建最终路径非常有用，因为我们是在返回（回溯）过程中逐步构建行程的。
图的构建
遍历给定的tickets列表，对于列表中的每一对
[from, to]：
检查
graph是否已经有from这个机场作为键。如果没有，则为
from创建一个新的优先队列。将
to添加到from键的优先队列中。
深度优先搜索（DFS）
从"JFK"机场开始调用
dfs方法。在dfs中：
首先检查当前机场
airport的所有可达机场（从它的优先队列中取得）。对于每一个可以到达的机场，递归地调用
dfs方法探索更深的路径。当从
dfs递归调用返回时（也就是当从某个机场不能再继续深入时），将当前机场加入到行程的最前端。
路径构建
通过在每次递归返回时将机场插入到
itinerary的前端，我们实际上是在构建一个逆序的行程。因为深度优先搜索保证了我们在无法继续探索更深的路径时才回溯，所以这种方法自然地解决了行程的重建问题，确保了使用所有机票。
返回结果
最终，
findItinerary函数返回构建好的行程列表。
public class Solution {
// graph用于存储从每个机场出发可以到达的目的地机场的映射，其中每个出发机场对应一个优先队列（小顶堆），
// 以保证我们可以按照字典序获取到目的地。
private Map<String, PriorityQueue<String>> graph = new HashMap<>();
// itinerary用于存储最终的行程，使用LinkedList因为我们需要频繁地在列表的前端插入元素，LinkedList在这方面更高效。
private LinkedList<String> itinerary = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
// 构建图的过程：遍历每一张机票，机票中包含了出发地和目的地
for (List<String> ticket : tickets) {
String src = ticket.get(0); // 获取出发地
String dst = ticket.get(1); // 获取目的地
// 如果graph中没有src这个机场，则添加src，并且新建一个优先队列，用于存储可以去的目的地机场
if (!graph.containsKey(src)) {
graph.put(src, new PriorityQueue<>());
}
// 将目的地添加到出发地的优先队列中
graph.get(src).offer(dst);
}
// 从JFK机场开始，进行深度优先搜索
dfs("JFK");
// 返回最终的行程
return itinerary;
}
private void dfs(String airport) {
// 获取当前机场可以直接到达的所有机场的优先队列
PriorityQueue<String> nextAirports = graph.getOrDefault(airport, new PriorityQueue<>());
// 只要当前机场的优先队列不为空，即还有未访问的邻接机场
while (!nextAirports.isEmpty()) {
// 弹出字典序最小的机场，并对其进行深度优先搜索
String nextAirport = nextAirports.poll();
dfs(nextAirport);
}
// 将当前机场添加到行程的最前面，这是因为我们是在返回过程中添加机场的，
// 逆序添加正好可以得到从起点到终点的路径
itinerary.addFirst(airport);
}
}
private Map<String, PriorityQueue<String>> graph = new HashMap<>();在这个Java程序中，
graph是用于表示机场之间航线的数据结构，它采用的是邻接表的形式。这里，graph是一个HashMap，其中键（Key）是一个字符串，表示出发机场的代码，值（Value）是一个PriorityQueue<String>，存储从该出发机场可以直接到达的所有目的地机场的代码。为什么使用 HashMap？
键值对存储：
HashMap提供了一种通过键快速访问数据的方式。在这个场景中，机场代码作为键，可以非常快速地查找到从该机场出发的所有可能目的地。高效的查找性能：
HashMap在理想情况下提供常数时间的查找性能，这使得在多次递归调用中快速检索信息成为可能，极大地提高了算法的效率。
为什么使用 PriorityQueue？
自动排序：
PriorityQueue是一个基于优先级的队列，它可以保持元素的排序状态。在这个场景中，它用于自动按字典序排列机场代码，因此每次从PriorityQueue中取出的都是字典序最小的目的地。高效的插入和删除：
PriorityQueue允许在对数时间内插入新元素，并在常数时间内检索最小元素，这对于本问题中字典序的要求非常有用。
在图构建中的作用：
构建邻接表：通过为每个出发机场创建一个优先队列，
graph存储了从每个机场可以飞往的所有目的地列表。这种方式的存储是非常适合表示航线图的，因为它可以高效地添加和查询航线。保证访问顺序：因为使用了
PriorityQueue，当有多条航线从同一个机场出发时，始终优先考虑字典序最小的机场作为下一个访问点。这保证了在存在多个有效行程的情况下，总是返回字典序最小的行程。
if (!graph.containsKey(src)) { graph.put(src, new PriorityQueue<>()); }在这段代码中，我们处理的是在建立航线图时的一个重要步骤，具体来说是检查图的表示中是否已经包含了某个特定的起点机场（
src），如果没有，那么就为这个起点机场创建一个新的条目，并关联一个新的优先队列（PriorityQueue）。这个优先队列用于存储所有从这个起点机场可以直接到达的目的地机场（dst）。这样的处理保证了图中的每个节点都被正确初始化，并且可以存储对应的邻接信息。检查机场存在性：
if (!graph.containsKey(src))：这行代码检查graph这个HashMap中是否已经有了以src（起点机场代码）作为键的条目。如果没有（即containsKey返回false），说明我们还没有记录从这个机场出发的任何航线。
添加新机场及其优先队列：
graph.put(src, new PriorityQueue<>());：这行代码在graph中为src机场添加一个新的条目，并且与之关联一个空的PriorityQueue对象。这个优先队列用来存储所有可以从src直接到达的目的地机场。之所以选择PriorityQueue，是因为它可以自动按字典顺序排序存储的元素，从而帮助我们在之后构建行程时，总是能优先考虑字典序最小的航线。
itinerary.addFirst(airport);在深度优先搜索（DFS）算法中，
itinerary.addFirst(airport);这行代码是在遍历结束后，向行程列表中添加机场的关键步骤。这种添加机场的方法特别适用于所谓的“后序遍历”（postorder traversal），其中一个节点（在本例中是机场）在其所有邻接点都被探访之后才被处理。在解决行程规划问题时，这种方法特别有效，具体解释如下：步骤和原理：
深度优先搜索（DFS）：DFS是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索树的分支。在此题中，DFS用于遍历机场图，从起始机场开始，深入到每一个可能的目的地，直到没有其他可飞往的机场。
逆序添加：在DFS的过程中，每当到达一个没有后续可以前往的机场（或者所有后续机场都已访问），就会结束当前路径的探索，并开始回溯。
itinerary.addFirst(airport);这行代码是在DFS返回阶段被调用的，即在探索完一个机场的所有可能行程后。由于这是在递归函数返回过程中执行的，实际上是按照从终点到起点的顺序添加机场的。构建最终路径：由于DFS是从终点机场回溯到起点机场，直接添加机场将导致行程是反向的（从终点到起点）。通过在行程列表的前端（头部）插入机场，确保了当函数完全返回到最初的调用（即从JFK开始的调用）时，构建的行程列表是正确的顺序，从JFK到最后一个机场。
好处：
简化逻辑：使用
addFirst方法可以避免在DFS完成后还需要反转列表的额外步骤，从而简化了代码逻辑，提高了效率。保持正确顺序：这种方法自然而然地保持了行程的正确顺序，无需额外的数据结构或操作来逆转路径。
整个代码如何完成保持假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次的：
代码中实现的确保所有机票都使用一次且只使用一次，以及保证行程的合理性的逻辑，主要体现在图的构建、深度优先搜索（DFS）遍历和回溯的管理中。下面详细解释这些关键步骤是如何共同工作来满足这些条件的：
图的构建
构建邻接表：首先，代码使用一个哈希表
graph，其中键是出发机场，值是一个优先队列（小顶堆）。优先队列用于存储所有可达的目的地机场，并且自动按字典顺序排序。这样做不仅可以直接控制访问顺序，还保证了如果有多条路径可选，总是优先选择字典序最小的路径。填充图：通过遍历机票列表
tickets，将每个机票的出发点和目的地添加到图中。如果图中还没有该出发点，就会创建一个新的条目并关联一个新的优先队列。然后，目的地会被添加到对应的优先队列中。这保证了所有机票都被考虑进图的结构中。
深度优先搜索（DFS）
遍历图：从 "JFK" 开始，DFS 递归地遍历图。对于每一个当前机场
airport，会从其关联的优先队列中取出目的地（即队列中的最小元素），并递归地进行DFS。每次从优先队列中取出一个元素，都相当于使用了一张机票。保证机票只用一次：从优先队列中移除一个目的地（即
nextAirport = nextAirports.poll()）的操作，确保了每张机票只被使用一次。因为一旦一个目的地被取出来用于DFS，它就不再位于队列中，因此不可能被重复使用。
结束条件和回溯
结束和回溯：当DFS到达一个机场，该机场没有更多的可飞往的目的地时（即对应的优先队列为空），这意味着从该机场出发的所有机票都已使用完毕。此时，DFS将当前机场添加到行程列表的前端并返回。这种添加方式正是回溯的体现，它确保了在构建最终行程时，路径是按照从终点到起点逆序构建的。
综合保证
所有机票使用一次：每张机票在构建图时被加入，且每次通过
poll()方法确保每张机票在生成行程时只被使用一次。保证至少存在一种合理的行程：题目假设总存在至少一种合理的行程，所以DFS设计上是基于这一假设，通过深度优先探索所有可能的路径来构建行程。优先队列的使用进一步确保了按字典序处理多个可选的目的地。
注意细节
private LinkedList<String> res; private LinkedList<String> path = new LinkedList<>();
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));在比较函数中，这确实实现了升序排序。这是因为
compareTo方法遵循这样的规则：如果
a.get(1)小于b.get(1)，则compareTo返回一个负数。如果
a.get(1)等于b.get(1)，则返回0。如果
a.get(1)大于b.get(1)，则返回一个正数。
在排序算法中，当
compareTo返回负数时，它意味着第一个参数（在这个例子中是a.get(1)）应该在第二个参数（b.get(1)）之前，这样就实现了升序排列。
![[2024最新教程]地表最强AGI：Claude 3注册账号/登录账号/访问方法，小白教程包教包会（附已注册账号密码成品）](https://img-blog.csdnimg.cn/direct/3a32ddbbca6c44a1919142b1939870c1.png)
