小米真题

手机流畅运行的秘密

时间限制：1.000S 空间限制：256MB

题目描述

8 月份发布会一结束，米小兔就在公司领到了一台最新发布的 Xiaomi MIX Fold 3 手机，这是一款小米旗舰折叠屏手机，并搭载了全新升级架构的 MIU114 系统。其先进的应用引擎不仅让系统更流畅，应用体验也大幅提升。 在一个优化项中，为了尽可能提升用户白天使用手机的体验和续航，某些已经在系统中注册过的任务会被设置为空闲任务，仅在手机空闲时运行 (比如数据备份或 AI 相册整理)。
 

现在系统中注册了若干组空闲任务，每个任务有各自的耗电量以及允许任务运行的最低初始电量，我们需要计算手机能够串行完成全部任务的最低初始电量。

注意点1: 所有电量以 mAh(毫安时)计，Xiaomi MIX Fold 3 的大电池容量是4800mAh。

注意点2: 本题目假设手机在运行空闲任务期间，不处于充电状态，也没有额外耗电行为。

注意点3: 智能应用引擎会以最合适的顺序串行运行任务。

输入描述

一个描述了所有任务的长字符串。任务与任务之间用逗号隔开，每组任务由耗电量及最低初始电量组成，用冒号隔开。

输出描述

一个数字，代表依次完成全部任务的最低初始电量，如果最低初始电量超过手机电池容量，则返回-1。

输入示例

1:10,2:12,3:10

输出示例

13

提示信息

在样例中，手机至少需要有 13mAh 的初始电量，在运行任务 2 后剩余电量 11mAh、运行任务1后剩余电量 10mAh、运行任务 3 后剩 7 mAh。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;
using ll = long long;int main() {// 读取一行输入，包含任务的描述string input;cin >> input;// 获取输入字符串的长度int n = input.size();// 创建一个二维向量来存储任务的耗电量和最低初始电量vector<vector<ll>> intervals;// 遍历输入字符串，提取每个任务的信息for (int i = 0; i < n; ++i) {int j = i;// 查找下一个逗号的位置while (j < n && input[j] != ',') ++j;// 提取当前任务的描述子串string intervalStr = input.substr(i, j - i);// 查找冒号的位置int colonPos = intervalStr.find(':');// 将描述子串转换为耗电量和最低初始电量，并添加到向量中intervals.push_back({stoll(intervalStr.substr(0, colonPos)),  // 耗电量stoll(intervalStr.substr(colonPos + 1))  // 最低初始电量});i = j;}// 定义一个比较函数，用于排序任务sort(intervals.begin(), intervals.end(), [](vector<ll>& a, vector<ll>& b){// 计算如果先执行任务a，总耗时是多少ll timeWithA = a[1] + max(0LL, b[1] - a[1] + a[0]);// 计算如果先执行任务b，总耗时是多少ll timeWithB = b[1] + max(0LL, a[1] - b[1] + b[0]);// 如果先执行任务a耗时更少，则返回true，表示a应该排在前面return timeWithA < timeWithB;});// 获取任务的数量int numIntervals = intervals.size();// 初始化总的最低初始电量为第一个任务的最低初始电量ll totalTime = intervals[0][1];// 初始化剩余电量为第一个任务完成后剩下的电量ll remainingTime = intervals[0][1] - intervals[0][0];// Xiaomi MIX Fold 3的最大电池容量ll MAX_TIME = 4800;// 遍历剩余的任务for (int i = 1; i < numIntervals; ++i) {// 如果剩余电量足够完成当前任务if (remainingTime >= intervals[i][1]) {// 更新剩余电量remainingTime -= intervals[i][0];} else {// 否则更新总的最低初始电量，并重置剩余电量totalTime += intervals[i][1] - remainingTime;remainingTime = intervals[i][1] - intervals[i][0];}}// 检查总的最低初始电量是否超过了最大电池容量if (totalTime > MAX_TIME) {// 如果超过了，输出-1cout << -1;} else {// 否则输出总的最低初始电量cout << totalTime;}return 0;
}

整体思路

1. 读取输入：从标准输入读取一行描述所有任务的字符串。
2. 解析输入：将这行字符串解析成一系列任务，每个任务由两个数字表示：消耗的电量和开始任务所需的最低电量。
3. 排序任务：根据一个定制的比较函数对任务进行排序，目的是找到一种顺序，使得完成所有任务所需的总起始电量最小。
4. 计算电量需求：遍历排序后的任务列表，计算完成所有任务所需的最低起始电量。
5. 验证结果：检查计算出的最低起始电量是否超过设备的最大电池容量（在这个例子中是4800mAh）。

代码详解

读取输入

string input;
cin >> input;

这里从标准输入读取一行字符串，该字符串包含所有任务的描述。

解析输入

int n = input.size();
vector<vector<ll>> intervals;
for (int i = 0; i < n; ++i) {int j = i;while (j < n && input[j] != ',') ++j;string intervalStr = input.substr(i, j - i);int colonPos = intervalStr.find(':');intervals.push_back({stoll(intervalStr.substr(0, colonPos)),stoll(intervalStr.substr(colonPos + 1))});i = j;
}

这部分代码解析了输入字符串中的每个任务。它首先获取每个任务的子字符串（即两个逗号之间的部分），然后查找冒号的位置来分割任务的消耗电量和所需最低电量，并将这些值存储在一个二维向量 intervals 中。

排序任务

sort(intervals.begin(), intervals.end(), [](vector<ll>& a, vector<ll>& b){ll timeWithA = a[1] + max(0LL, b[1] - a[1] + a[0]);ll timeWithB = b[1] + max(0LL, a[1] - b[1] + b[0]);return timeWithA < timeWithB;
});

这里定义了一个比较函数，用于确定两个任务按何种顺序执行可以使总起始电量最小。比较函数通过计算先执行其中一个任务后所需的总电量，并选择其中总电量较小的情况作为优先级更高的任务。

计算电量需求

int numIntervals = intervals.size();
ll totalTime = intervals[0][1];
ll remainingTime = intervals[0][1] - intervals[0][0];for (int i = 1; i < numIntervals; ++i) {if (remainingTime >= intervals[i][1]) {remainingTime -= intervals[i][0];} else {totalTime += intervals[i][1] - remainingTime;remainingTime = intervals[i][1] - intervals[i][0];}
}

这部分代码遍历经过排序的任务列表，计算完成所有任务所需的最低起始电量。它通过跟踪剩余电量 remainingTime 和总起始电量 totalTime 来实现这一点。

验证结果

if (totalTime > MAX_TIME) {cout << -1;
} else {cout << totalTime;
}

最后，程序检查计算出的总起始电量是否超过了最大电池容量（在这个例子中是4800mAh）。如果超过了，则输出 -1；否则，输出所需的最低起始电量。

小米手机通信校准

时间限制：1.000S 空间限制：256MB

题目描述

小米手机生产过程中会经过严苛的测试环节，其中包括手机通讯功能中的射频校准。射频校准会打点数据上报到云端。

 

其中包含两组数据:第一组数据中会包含此次校准的频道号(freq)信息；第二组会上传一批数据，包含一组频道号(freg)和其对应的损失值(loss)，其中这一组频道号(freg)不会重复，且是有序的。

 

现在需要根据第一组数据中的频道号(freg)，找到离第二组中频道号(freq)最近的那个freq对应的loss值，如果两边一样近，则取两边loss的平均。 注：输入为int，输出为double类型四舍五入保留1位小数

输入描述

包含两组数据:

第一

组数据中会包含此次校准的频道号(freq)信息。

第二组会上传一批数据，包含一组频道号(freg)和其对应的损失值(loss)，其中这一组频道号(freg)不会重复，且是有序的。

输出描述

离频道号(freq)最近的freq对应的loss值，如果两边一样近，则取两边loss的平均。

输入示例

2800
1950:10 2000:15 3000:9

输出示例

9.0

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <map>using namespace std;// 定义查找最接近损失值的函数
double findClosestLoss(int freq, const string& data) {// 创建一个映射表，键是频道号 (freg)，值是损失值 (loss)map<int, double> fregLossMap;// 将输入的字符串转换为流，便于解析stringstream ss(data);string item;// 循环读取每一组频道号和损失值，并填充到映射表中while (getline(ss, item, ' ')) {stringstream itemStream(item);int freg;double loss;char colon;// 从流中读取频道号、冒号和损失值itemStream >> freg >> colon >> loss;// 将频道号和损失值存入映射表fregLossMap[freg] = loss;}// 使用 lower_bound 查找大于等于 freq 的第一个键的位置auto it = fregLossMap.lower_bound(freq);double closestLoss = 0;// 如果 freq 小于映射表中的所有频道号if (it == fregLossMap.begin()) {// 取第一个频道号的损失值closestLoss = it->second;} // 如果 freq 大于映射表中的所有频道号else if (it == fregLossMap.end()) {// 取最后一个频道号的损失值it--;closestLoss = it->second;} // 如果 freq 在两个频道号之间else {// 获取 freq 前面的一个频道号的信息auto prevIt = prev(it);// 计算 freq 到前后两个频道号的距离int distToPrev = freq - prevIt->first;int distToNext = it->first - freq;// 如果 freq 更靠近前面的频道号if (distToPrev < distToNext) {closestLoss = prevIt->second;} // 如果 freq 更靠近后面的频道号else if (distToPrev > distToNext) {closestLoss = it->second;} // 如果 freq 同时距离前后两个频道号相等else {// 计算两个损失值的平均值closestLoss = (prevIt->second + it->second) / 2.0;}}// 四舍五入保留一位小数return round(closestLoss * 10) / 10;
}int main() {// 读取第一行输入，即频道号 freqint freq;cin >> freq;// 忽略掉输入缓冲区中的换行符cin.ignore();// 读取第二行输入，即频道号和损失值的数据string data;getline(cin, data);// 调用函数计算最接近的损失值double result = findClosestLoss(freq, data);// 设置输出精度为一位小数cout.precision(1);// 输出结果cout << fixed << result << endl;return 0;
}

这段代码的功能是从标准输入读取两行数据：第一行是一个整数 freq 表示频道号，第二行是一系列频道号与对应的损失值，格式为 "频道号:损失值"，频道号和损失值之间用空格分隔。然后，代码会找出与给定频道号 freq 最接近的损失值，并输出这个损失值（四舍五入保留一位小数）。

1. 导入必要的头文件：

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <map>

这些头文件包含了处理字符串、流操作、数学运算和映射容器等功能。

1. 使用命名空间：

using namespace std;

这样可以避免每次调用标准库函数时都需要加上 std:: 前缀。

1. 定义 findClosestLoss 函数：

double findClosestLoss(int freq, const string& data) {// ...
}

这个函数接受一个整数 freq 和一个字符串 data，并返回一个双精度浮点数表示损失值。

1. 创建映射表：

map<int, double> fregLossMap;

映射表用于存储频道号和对应的损失值。

1. 解析输入数据：

stringstream ss(data);
string item;
while (getline(ss, item, ' ')) {// ...
}

使用 stringstream 来解析输入数据，将每一组频道号和损失值添加到映射表中。

1. 查找最接近的损失值：

auto it = fregLossMap.lower_bound(freq);

使用 lower_bound 方法找到第一个键值大于等于 freq 的位置。

1. 计算损失值：
   根据 freq 与映射表中的频道号的关系，决定采用哪个损失值或两个损失值的平均值。
2. 四舍五入保留一位小数：

return round(closestLoss * 10) / 10;

使用 round 函数进行四舍五入，并保留一位小数。

1. 主函数 main：

int main() {// 读取频道号 freqint freq;cin >> freq;// 忽略掉输入缓冲区中的换行符cin.ignore();// 读取频道号和损失值的数据string data;getline(cin, data);// 调用函数计算最接近的损失值double result = findClosestLoss(freq, data);// 设置输出精度为一位小数cout.precision(1);// 输出结果cout << fixed << result << endl;return 0;
}

主函数负责读取输入并调用 findClosestLoss 函数来计算并输出结果。

示例运行

假设输入如下：

100
50:0.2 75:0.5 150:0.8 200:1.2

• freq 是 100。
• 数据是 "50:0.2 75:0.5 150:0.8 200:1.2"。

程序会输出 0.5，因为频道号 100 更接近于 75，所以损失值为 0.5。

leetcode 3102 最小化曼哈顿距离

题目描述如下：

给定一个由整数组成的二维数组 grid，其中 grid[i][j] 表示第 i 行第 j 列的点的值。你需要在网格中找到一个点，使得从这个点到所有其他点的曼哈顿距离之和最小。

曼哈顿距离定义为两点 (x1, y1) 和 (x2, y2) 之间的距离是 |x1 - x2| + |y1 - y2|。

返回最小的曼哈顿距离之和。

示例 1

输入：grid = [[1,0,2],[3,4,5],[6,7,8]]
输出：14
解释：
如果选择点 (1, 1)，即 grid[1][1] = 4，那么到所有其他点的曼哈顿距离之和是最小的，等于 14。

示例 2

输入：grid = [[4,5,6],[7,8,9],[10,11,12]]
输出：12
解释：
选择点 (0, 2) 或 (1, 1) 或 (2, 0) 都会得到最小的曼哈顿距离之和，等于 12。

提示

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• 1 <= m * n <= 100
• -10^6 <= grid[i][j] <= 10^6

解题思路

对于一维的情况，要使所有点到某一点的距离之和最小，应该选择中位数作为该点。因此，可以分别对每一行和每一列计算出中位数，然后选择这两个中位数对应的位置作为最终的点。

复杂度分析

时间复杂度：O(m*n*log(m*n))，主要消耗在查找行和列的中位数上。
空间复杂度：O(m + n)，用于存储行和列的值。

分析

在解决“Minimize Manhattan Distances”（最小化曼哈顿距离）这个问题时，核心思想是利用中位数的特性来找到一个点，使得该点到网格中所有其他点的曼哈顿距离之和最小。具体步骤如下：

1. 一维问题的解决：首先，我们需要理解在一维情况下，要使所有点到某一点的距离之和最小，应选择中位数作为目标点。这是因为，中位数将数据分为两半，一半的数据点离它更近，另一半则更远，所以选择中位数可以最小化总距离。

   

2. 行和列中位数的计算：将二维问题分解为一系列一维问题，分别处理行和列。对于每一行和每一列，我们将它们视为一维数据集，并找出各自的中位数。这样，我们就可以找到一个点，它的行坐标和列坐标分别是行中位数和列中位数。
3. 确定最优解：行中位数和列中位数对应的位置即是我们要找的最优解，因为这个点到网格中所有其他点的曼哈顿距离之和是所有可能点中最小的。

实现细节

• 计算行中位数：遍历每一行，对行中的所有元素进行排序，然后找到中位数。
• 计算列中位数：遍历每一列，对列中的所有元素进行排序，然后找到中位数。
• 曼哈顿距离计算：一旦找到行中位数和列中位数，就可以用这个点计算与所有其他点的曼哈顿距离之和，这个和即是最小的曼哈顿距离和。

时间和空间复杂度

• 时间复杂度：O(m*n*log(m*n))，其中 m 是行数，n 是列数。主要开销在于对行和列的元素进行排序以找到中位数。
• 空间复杂度：O(m + n)，用于存储行和列的值以便计算中位数。

这种方法利用了中位数的数学特性，有效地解决了二维网格上的最小化曼哈顿距离问题。

代码

方法一：有序集合
枚举要移除的点，用两个有序集合维护其他 n−1 个点的 x
′
和 y
′
，用 max{max(x
′
)−min(x
′
),max(y
′
)−min(y
′
)} 更新答案的最大值。

class Solution {
public:int minimumDistance(vector<vector<int>>& points) {multiset<int> xs, ys;for (auto& p : points) {xs.insert(p[0] + p[1]);ys.insert(p[1] - p[0]);}int ans = INT_MAX;for (auto& p : points) {int x = p[0] + p[1], y = p[1] - p[0];xs.erase(xs.find(x)); // 移除一个 xys.erase(ys.find(y)); // 移除一个 yint dx = *xs.rbegin() - *xs.begin();int dy = *ys.rbegin() - *ys.begin();ans = min(ans, max(dx, dy));xs.insert(x);ys.insert(y);}return ans;}
};作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimize-manhattan-distances/solutions/2716755/tu-jie-man-ha-dun-ju-chi-heng-deng-shi-b-op84/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {public int minimumDistance(int[][] points) {TreeMap<Integer, Integer> xs = new TreeMap<>();TreeMap<Integer, Integer> ys = new TreeMap<>();for (int[] p : points) {xs.merge(p[0] + p[1], 1, Integer::sum);ys.merge(p[1] - p[0], 1, Integer::sum);}int ans = Integer.MAX_VALUE;for (int[] p : points) {int x = p[0] + p[1];int y = p[1] - p[0];if (xs.get(x) == 1) xs.remove(x);else xs.merge(x, -1, Integer::sum); // 移除一个 xif (ys.get(y) == 1) ys.remove(y);else ys.merge(y, -1, Integer::sum); // 移除一个 yint dx = xs.lastKey() - xs.firstKey();int dy = ys.lastKey() - ys.firstKey();ans = Math.min(ans, Math.max(dx, dy));xs.merge(x, 1, Integer::sum);ys.merge(y, 1, Integer::sum);}return ans;}
}作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimize-manhattan-distances/solutions/2716755/tu-jie-man-ha-dun-ju-chi-heng-deng-shi-b-op84/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二

在解决诸如“最小化曼哈顿距离”等算法问题时，维护最大次大和最小次小的策略是一种高效的方法。这种方法的核心思想在于动态地更新一组关键数值，以避免在每次数据变化时都需要对所有数据进行排序或遍历，从而显著降低计算复杂度。下面，我们将详细解析这一策略的实施步骤及其背后的逻辑。

理解最大次大和最小次小

• 最大次大：在一组数中，去除最大值后剩下的最大值。
• 最小次小：在一组数中，去除最小值后剩下的最小值。

实施步骤

1. 初始化：从数据集中选择两个最大值和两个最小值，将其中较小的最大值标记为最大次大，较大的最小值标记为最小次小。
2. 动态更新：当数据集发生变化（例如，添加或删除元素）时，检查新元素是否会影响最大次大或最小次小的值：

• • 如果新元素大于当前最大值，则更新最大值，并将原最大值设为最大次大。
  • 如果新元素大于最大次大但小于最大值，则更新最大次大。
  • 类似地，对最小值和最小次小进行更新。

1. 处理相同值：特别注意，最大次大和最小次小可能与最大值和最小值相同，这是因为可能存在重复值。因此，在更新时需要额外的逻辑来处理这种情况，确保正确性。

进一步地，要移除的点只能是 x
′
或 y
′
最大最小的点（不然移除前后都一样），所以额外维护最大最小值的下标，一共 4 个，最后只需遍历这 4 个坐标，而不是遍历整个 points 数组。

class Solution {public int minimumDistance(int[][] points) {final int INF = Integer.MAX_VALUE;int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF;int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF;int maxXi = 0, minXi = 0, maxYi = 0, minYi = 0;for (int i = 0; i < points.length; i++) {int[] p = points[i];int x = p[0] + p[1];int y = p[1] - p[0];// x 最大次大if (x > maxX1) {maxX2 = maxX1;maxX1 = x;maxXi = i;} else if (x > maxX2) {maxX2 = x;}// x 最小次小if (x < minX1) {minX2 = minX1;minX1 = x;minXi = i;} else if (x < minX2) {minX2 = x;}// y 最大次大if (y > maxY1) {maxY2 = maxY1;maxY1 = y;maxYi = i;} else if (y > maxY2) {maxY2 = y;}// y 最小次小if (y < minY1) {minY2 = minY1;minY1 = y;minYi = i;} else if (y < minY2) {minY2 = y;}}int ans = INF;for (int i : new int[]{maxXi, minXi, maxYi, minYi}) {int dx = (i == maxXi ? maxX2 : maxX1) - (i == minXi ? minX2 : minX1);int dy = (i == maxYi ? maxY2 : maxY1) - (i == minYi ? minY2 : minY1);ans = Math.min(ans, Math.max(dx, dy));}return ans;}
}

class Solution {// 更新最大次大void update_max(int i, int v, int& max_i, int& max1, int& max2) {if (v > max1) {max_i = i;max2 = max1;max1 = v;} else if (v > max2) {max2 = v;}}// 更新最小次小void update_min(int i, int v, int& min_i, int& min1, int& min2) {if (v < min1) {min_i = i;min2 = min1;min1 = v;} else if (v < min2) {min2 = v;}}public:int minimumDistance(vector<vector<int>>& points) {int max_xi, min_xi, max_yi, min_yi;int max_x1 = INT_MIN, max_x2 = INT_MIN, max_y1 = INT_MIN, max_y2 = INT_MIN;int min_x1 = INT_MAX, min_x2 = INT_MAX, min_y1 = INT_MAX, min_y2 = INT_MAX;for (int i = 0; i < points.size(); i++) {auto& p = points[i];int x = p[0] + p[1];int y = p[1] - p[0];update_max(i, x, max_xi, max_x1, max_x2);update_min(i, x, min_xi, min_x1, min_x2);update_max(i, y, max_yi, max_y1, max_y2);update_min(i, y, min_yi, min_y1, min_y2);}int ans = INT_MAX;for (int i : {max_xi, min_xi, max_yi, min_yi}) {int dx = (i == max_xi ? max_x2 : max_x1) - (i == min_xi ? min_x2 : min_x1);int dy = (i == max_yi ? max_y2 : max_y1) - (i == min_yi ? min_y2 : min_y1);ans = min(ans, max(dx, dy));}return ans;}
};作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimize-manhattan-distances/solutions/2716755/tu-jie-man-ha-dun-ju-chi-heng-deng-shi-b-op84/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思考题
如果题目求的是欧氏距离，要怎么做？

关键词：凸包、旋转卡壳。

class Solution {
public:
int minimumDistance(vector<vector>& points) { multiset st1; multiset st2; for (auto& p : points) { int x = p[0], y = p[1]; st1.insert(x + y); st2.insert(x - y); } int ans = INT_MAX; for (auto& p : points) { int x = p[0], y = p[1]; st1.erase(st1.find(x + y)); st2.erase(st2.find(x - y)); ans = min(ans, max(*st1.rbegin() - *st1.begin(), *st2.rbegin() - *st2.begin())); st1.insert(x + y); st2.insert(x - y); } return ans; } };

23年B站真题

#include <iostream>
#include <vector>
using namespace std;
int main() {string s1, s2;cin >> s1 >> s2;vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));// s1 如果变成空串的最小删除ASCLL值综合for (int i = 1; i <= s1.size(); i++) dp[i][0] = dp[i - 1][0] + s1[i - 1];// s2 如果变成空串的最小删除ASCLL值综合for (int j = 1; j <= s2.size(); j++) dp[0][j] = dp[0][j - 1] + s2[j - 1];for (int i = 1; i <= s1.size(); i++) {for (int j = 1; j <= s2.size(); j++) {if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);}}cout << dp[s1.size()][s2.size()] << endl;
}

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s1 = scanner.nextLine();String s2 = scanner.nextLine();int[][] dp = new int[s1.length() + 1][s2.length() + 1];// s1 如果变成空串的最小删除ASCII值综合for (int i = 1; i <= s1.length(); i++) {dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);}// s2 如果变成空串的最小删除ASCII值综合for (int j = 1; j <= s2.length(); j++) {dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);}for (int i = 1; i <= s1.length(); i++) {for (int j = 1; j <= s2.length(); j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));}}}System.out.println(dp[s1.length()][s2.length()]);scanner.close();}
}

def min_delete_sum(s1: str, s2: str) -> int:dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]# s1 如果变成空串的最小删除ASCII值综合for i in range(1, len(s1) + 1):dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])# s2 如果变成空串的最小删除ASCII值综合for j in range(1, len(s2) + 1):dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])for i in range(1, len(s1) + 1):for j in range(1, len(s2) + 1):if s1[i - 1] == s2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), dp[i][j - 1] + ord(s2[j - 1]))return dp[len(s1)][len(s2)]if __name__ == "__main__":s1 = input().strip()s2 = input().strip()print(min_delete_sum(s1, s2))

这段代码实现了一个动态规划算法，用于解决计算两个字符串 s1 和 s2 的最小ASCII删除代价问题。这里的“最小ASCII删除代价”指的是，将两个字符串通过删除一些字符使其变成相同的字符串所需的最小ASCII值总和。具体而言，每次可以选择删除 s1 或 s2 中的一个字符，目标是使两个字符串完全相同，而删除一个字符的代价是该字符的ASCII值。

以下是代码的详细解释：

1. 输入两个字符串:

string s1, s2;
cin >> s1 >> s2;

从标准输入读取两个字符串 s1 和 s2。

1. 初始化动态规划表:

vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));

创建一个二维动态规划表 dp，其大小为 (s1.size() + 1) x (s2.size() + 1)，并在所有位置初始化为0。dp[i][j] 将存储 s1 的前 i 个字符和 s2 的前 j 个字符变为相同字符串所需的最小ASCII删除代价。

1. 初始化边界条件:

for (int i = 1; i <= s1.size(); i++) dp[i][0] = dp[i - 1][0] + s1[i - 1];
for (int j = 1; j <= s2.size(); j++) dp[0][j] = dp[0][j - 1] + s2[j - 1];

这里设置的边界条件是：

• • 如果 s2 是空串，则最小删除代价是删除 s1 所有字符的ASCII值总和。
  • 如果 s1 是空串，则最小删除代价是删除 s2 所有字符的ASCII值总和。

1. 填充动态规划表:

for (int i = 1; i <= s1.size(); i++) {for (int j = 1; j <= s2.size(); j++) {if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];else dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);}
}

对于 dp 表的每个非边界位置，有两种情况：

• • 如果 s1 和 s2 在当前位置的字符相同，则不需要删除任何字符，dp[i][j] 直接等于 dp[i-1][j-1]。
  • 如果字符不同，则需要在删除 s1 的当前字符和删除 s2 的当前字符中选择代价较小的一个。选择代价较小的删除操作，即 min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1])。

1. 输出结果:

cout << dp[s1.size()][s2.size()] << endl;

输出 dp 表的右下角元素，即 dp[s1.size()][s2.size()]，它代表了使两个字符串完全相同的最小ASCII删除代价。

这个算法的时间复杂度为 O(mn)，其中 m 和 n 分别是 s1 和 s2 的长度。空间复杂度同样为 O(mn)，因为需要存储整个动态规划表。

两个字符串的最小 ASCII 删除总和

时间限制：1.000S 空间限制：256MB
题目描述
给定两个字符串 s1 和 s2（0 <= s1.length, s2.length <= 1000），返回使两个字符用相等所需删除字符的 ASCLL 值的最小和。

s1 和 s2 由小写英文字母组成。

输入描述
输入共两行，每行一个字符串。
输出描述
输出一个正整数，表示使两个字符用相等所需删除字符的 ASCLL 值的最小和。
输入示例
sea
eat
输出示例
231
提示信息
解释:在“sea”中删除“s”并将"s”的值(115)加入总和。

在"eat”中删除“t“并将116 加入总和。

结束时，两个字符串相等，115+116 =231 就是符合条件的很小和。

// 包含必要的头文件
#include <iostream>
#include <string>
#include <vector>// 使用标准命名空间
using namespace std;// 定义函数minimumDeleteSum，该函数接受两个字符串s1和s2作为参数，并返回一个整数
int minimumDeleteSum(string s1, string s2) {// 获取字符串s1和s2的长度int m = s1.size(), n = s2.size();// 创建一个动态规划表dp，其维度为(m+1)x(n+1)，所有元素初始值为0vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 初始化dp表的第一列，表示将s1的前i个字符变成空字符串需要的ASCII值之和for (int i = 1; i <= m; ++i)// dp[i][0]等于dp[i-1][0]加上s1的第i-1个字符的ASCII值dp[i][0] = dp[i - 1][0] + static_cast<int>(s1[i - 1]);// 初始化dp表的第一行，表示将s2的前j个字符变成空字符串需要的ASCII值之和for (int j = 1; j <= n; ++j)// dp[0][j]等于dp[0][j-1]加上s2的第j-1个字符的ASCII值dp[0][j] = dp[0][j - 1] + static_cast<int>(s2[j - 1]);// 遍历s1和s2的所有字符for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {// 如果s1的第i-1个字符等于s2的第j-1个字符if (s1[i - 1] == s2[j - 1])// dp[i][j]等于dp[i-1][j-1]，即不需要改变这两个字符dp[i][j] = dp[i - 1][j - 1];else// 否则，dp[i][j]等于dp[i-1][j]加上s1的第i-1个字符的ASCII值和dp[i][j-1]加上s2的第j-1个字符的ASCII值中的较小者dp[i][j] = min(dp[i - 1][j] + static_cast<int>(s1[i - 1]), dp[i][j - 1] + static_cast<int>(s2[j - 1]));}}// 返回dp表的最后一项，即使s1和s2相等所需的ASCII值之和的最小值return dp[m][n];
}// 主函数
int main() {// 定义两个字符串s1和s2string s1, s2;// 从标准输入读取两个字符串cin >> s1 >> s2;// 输出使s1和s2相等所需的ASCII值之和的最小值cout << minimumDeleteSum(s1, s2) << endl;// 返回0，表示程序正常结束return 0;
}

最长同值路径

时间限制：1.000S 空间限制：256MB
题目描述
给定一个二叉树的 root ，返回最长的路径的长度，这个路径中的每节点具有相同值。这条路径可以经过也可以不经过根节点。两个节点之间的路径长度 由它们之间的边数表示。

树的节点数的范围是 [0,10^4] -1000 <= Node.val <= 1000

树的深度将不超过 1000

输入描述
输入共两行，第一行是一个整数 n，表示第二行的字符串数。

第二行包含 n 个字符串，空格隔开，数字的字符串代表该节点存在，并且值为数字，null 代表是一个空结点。

输出描述
输出一个正整数，代表最长路径长度。
输入示例
7
5 4 5 1 1 null 5
输出示例
2
提示信息
通过层序遍历构建二叉树如下：

官方题解

#include <iostream>
#include <queue>
#include <vector>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;          // 节点值TreeNode* left;   // 左子节点指针TreeNode* right;  // 右子节点指针TreeNode(int x) : val(x), left(NULL), right(NULL) {}  // 构造函数
};// 根据层序遍历数组构建二叉树
TreeNode* constructBinaryTree(const vector<string>& levelOrder) {if (levelOrder.empty()) return NULL;TreeNode* root = new TreeNode(stoi(levelOrder[0]));  // 创建根节点queue<TreeNode*> q;  // 队列，用于层序遍历q.push(root);  // 先将根节点入队int i = 1;     // 用于追踪levelOrder数组中的下一个元素// 循环直到队列为空或处理完所有节点while (!q.empty() && i < levelOrder.size()) {TreeNode* current = q.front();  // 获取队列头部的节点q.pop();  // 出队// 处理左子节点if (i < levelOrder.size() && levelOrder[i] != "null") {current->left = new TreeNode(stoi(levelOrder[i]));  // 创建左子节点q.push(current->left);  // 将新创建的左子节点入队}i++;  // 移到下一个数组元素// 处理右子节点if (i < levelOrder.size() && levelOrder[i] != "null") {current->right = new TreeNode(stoi(levelOrder[i]));  // 创建右子节点q.push(current->right);  // 将新创建的右子节点入队}i++;  // 再次移动到下一个数组元素}return root;  // 返回构建好的树的根节点
}int result = 0;  // 记录最长路径的长度// 树形深度优先搜索（DFS）
int dfs(TreeNode* node) {if (node == NULL) return 0;  // 如果节点为空，返回0// 递归获取左右子树的路径长度int leftPath = dfs(node->left);int rightPath = dfs(node->right);int leftNum = 0, rightNum = 0;// 检查左子树是否与当前节点值相等，并更新路径长度if (node->left != NULL && node->left->val == node->val) {leftNum = leftPath + 1;}// 检查右子树是否与当前节点值相等，并更新路径长度if (node->right != NULL && node->right->val == node->val) {rightNum = rightPath + 1;}// 更新全局最长路径result = max(result, leftNum + rightNum);// 返回当前节点能贡献给父节点的最大路径长度return max(leftNum, rightNum);
}int main() {int n;cin >> n;  // 读取节点数vector<string> levelOrder(n);  // 创建存放层序遍历结果的向量for (int i = 0; i < n; i++) cin >> levelOrder[i];  // 读取层序遍历结果TreeNode* root = constructBinaryTree(levelOrder);  // 构建二叉树dfs(root);  // 执行深度优先搜索并计算最长路径cout << result << endl;  // 输出最长路径的长度return 0;
}

Java

import java.util.*;class TreeNode {int val;TreeNode left, right;TreeNode(int x) {val = x;left = null;right = null;}
}public class Main {public static int result = 0;public static TreeNode constructBinaryTree(List<String> levelOrder) {if (levelOrder.isEmpty()) return null;TreeNode root = new TreeNode(Integer.parseInt(levelOrder.get(0)));Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int i = 1;while (!queue.isEmpty() && i < levelOrder.size()) {TreeNode current = queue.poll();if (i < levelOrder.size() && !levelOrder.get(i).equals("null")) {current.left = new TreeNode(Integer.parseInt(levelOrder.get(i)));queue.add(current.left);}i++;if (i < levelOrder.size() && !levelOrder.get(i).equals("null")) {current.right = new TreeNode(Integer.parseInt(levelOrder.get(i)));queue.add(current.right);}i++;}return root;}public static int dfs(TreeNode node) {if (node == null) return 0;int leftPath = dfs(node.left);int rightPath = dfs(node.right);int leftNum = 0, rightNum = 0;if (node.left != null && node.left.val == node.val) {leftNum = leftPath + 1;}if (node.right != null && node.right.val == node.val) {rightNum = rightPath + 1;}result = Math.max(result, leftNum + rightNum);return Math.max(leftNum, rightNum);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();  // consume the newline characterList<String> levelOrder = new ArrayList<>();for (int i = 0; i < n; i++) {levelOrder.add(sc.next());}TreeNode root = constructBinaryTree(levelOrder);dfs(root);System.out.println(result);sc.close();}
}

python
from typing import List, Optional
from collections import deque
import sysclass TreeNode:def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):self.val = valself.left = leftself.right = rightdef construct_binary_tree(level_order: List[str]) -> Optional[TreeNode]:if not level_order:return Noneroot = TreeNode(int(level_order[0]))queue = deque([root])i = 1while queue and i < len(level_order):current = queue.popleft()if i < len(level_order) and level_order[i] != "null":current.left = TreeNode(int(level_order[i]))queue.append(current.left)i += 1if i < len(level_order) and level_order[i] != "null":current.right = TreeNode(int(level_order[i]))queue.append(current.right)i += 1return rootresult = 0def dfs(node: Optional[TreeNode]) -> int:global resultif node is None:return 0left_path = dfs(node.left)right_path = dfs(node.right)left_num = right_num = 0if node.left is not None and node.left.val == node.val:left_num = left_path + 1if node.right is not None and node.right.val == node.val:right_num = right_path + 1result = max(result, left_num + right_num)return max(left_num, right_num)if __name__ == "__main__":input = sys.stdin.readdata = input().strip().split()n = int(data[0])level_order = data[1:]root = construct_binary_tree(level_order)dfs(root)print(result)

小红的区间翻转

时间限制：1.000S 空间限制：256MB
题目描述
小红拿到了两个长度为 n 的数组 a 和 b，她可以进行恰好一次以下操作：选择a数组中的一个区间[l,Tr]，将它们翻转。例如，对于 a = [2,3,4,1,5,6]，小红可以选择区间[3,5]，数组 a 则变成[2,3,5,1,4,6]。

小红希望操作后 a 数组和 b 数组完全相同。请你告诉小红有多少种操作的方案数。

输入描述
第一行输入一个正整数 n，代表数组的长度；

第二行输入 n 个正整数 ai；

第三行输入 n 个正整数 bi。

输出描述
选择区间的方案数。
输入示例
4
1 2 3 1
1 3 2 1
输出示例
2
提示信息
数据范围

1 ≤ n, ai ,bi ≤ 103

#include <iostream>
#include <vector>
using namespace std;// 定义一个函数检查是否通过翻转[a[left], a[right]]可以使a和b相等
bool canTransform(const vector<int>& a, const vector<int>& b, int left, int right) {// 首先检查翻转区间内的元素是否匹配（翻转后）for (int i = left, j = right; i <= right; i++, j--) {// 如果翻转区间内的元素不匹配，则无法通过翻转使a和b相等if (a[i] != b[j]) {return false;}}// 检查翻转区间左侧的元素是否匹配for (int i = 0; i < left; i++) {if (a[i] != b[i]) {return false;}}// 检查翻转区间右侧的元素是否匹配for (int i = right + 1; i < a.size(); i++) {if (a[i] != b[i]) {return false;}}// 如果所有检查都通过，说明可以通过翻转[a[left], a[right]]使a和b相等return true;
}int main() {int n;// 读取数组的长度cin >> n;// 定义两个数组a和b，分别读取它们的元素vector<int> a(n);vector<int> b(n);// 读取数组a的元素for (int i = 0; i < n; i++) {cin >> a[i];}// 读取数组b的元素for (int i = 0; i < n; i++) {cin >> b[i];}int count = 0;// 遍历所有可能的子数组的左边界for (int left = 0; left < n; left++) {// 遍历所有可能的子数组的右边界，右边界始终大于等于左边界for (int right = left; right < n; right++) {// 检查翻转[a[left], a[right]]是否能使a和b相等if (canTransform(a, b, left, right)) {// 如果可以，增加计数器count++;}}}// 输出可以使得a和b相等的子数组的数量cout << count << endl;return 0;
}

#include <iostream>
#include <vector>using namespace std;int main() {// 读取数组的大小int n;cin >> n;// 初始化两个数组a和bvector<int> a(n), b(n);// 读取数组a的元素for (int i = 0; i < n; i++) {cin >> a[i];}// 读取数组b的元素for (int i = 0; i < n; i++) {cin >> b[i];}// 初始化前缀和后缀匹配标识数组vector<int> prefix(n, 0), suffix(n, 0);// 计算前缀相等的位置，即a和b从开始有多少个连续相等的元素int p = 0;while (p < n && a[p] == b[p]) {prefix[p] = 1; // 标记为匹配p++;}// 计算后缀相等的位置，即a和b从结束有多少个连续相等的元素int s = n - 1;while (s >= 0 && a[s] == b[s]) {suffix[s] = 1; // 标记为匹配s--;}// 初始化计数器int count = 0;// 遍历所有可能的子数组范围for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {// 检查子数组的前缀和后缀是否与b相等if ((i == 0 || prefix[i - 1] == 1) && (j == n - 1 || suffix[j + 1] == 1)) {// 检查子数组a[i...j]翻转后是否与b[i...j]相等bool is_palindrome = true;for (int k = 0; k <= (j - i) / 2; k++) {if (a[i + k] != b[j - k]) {is_palindrome = false;break;}}// 如果翻转后相等，增加计数if (is_palindrome) {count++;}}}}// 输出可以翻转的子数组的数量cout << count << endl;return 0;
}

leetcode 3098.求出所有子序列的能量和

class Solution:# 定义一个类Solution，包含求解特定问题的方法def sumOfPowers(self, nums: List[int], k: int) -> int:# 方法sumOfPowers接收一个整数列表nums和一个整数k，返回一个整数结果mod = 1_000_000_007# 定义一个模数mod用于最终结果的取模操作，保证结果在一定范围内nums.sort()# 对输入列表nums进行排序，便于后续操作@cache# 使用lru_cache装饰器来缓存函数dp的返回结果，避免重复计算def dp(root: int, length: int):# 定义一个辅助函数dp，它接收两个参数：root表示当前考虑的子序列的最后一个元素的索引，# length表示子序列的长度。函数的目的是计算所有可能子序列中最小差值的计数。cnt = defaultdict(int)# 初始化一个默认字典cnt，用于存储不同差值的出现次数if length == 2:# 当子序列长度为2时，是最简单的基线情况for i in range(root):# 遍历到root之前的每个元素diff = nums[root] - nums[i]# 计算当前元素与前一个元素的差值cnt[diff] += 1# 更新差值的计数else:# 当子序列长度大于2时，需要递归地考虑更短的子序列for i in range(length - 2, root):# 遍历从length-2到root之间的每个元素diff = nums[root] - nums[i]# 计算当前元素与前一个元素的差值for lastDiff, lastCnt in dp(i, length - 1).items():# 对于i作为根节点，长度为length-1的所有子序列的差值分布if lastDiff < diff:# 如果前一个子序列中的最小差值小于当前差值，那么这个差值不会成为新的最小差值# 因此，将前一个子序列中所有差值的计数添加到当前差值的计数中cnt[lastDiff] += lastCntelse:# 否则，当前差值成为新的最小差值，将其计数加上前一个子序列中所有差值的总计数cnt[diff] += lastCntreturn cnt# 返回最终的差值计数字典ans = 0# 初始化答案变量ans为0，用于累积所有子序列的“能量”和for i in range(k - 1, len(nums)):# 遍历所有可能成为子序列末尾的元素，从第k-1个元素开始直到列表结尾for diff, cnt in dp(i, k).items():# 获取以i为根节点，长度为k的所有子序列的差值分布ans = (ans + diff * cnt) % mod# 将差值乘以其计数，累加到答案中，并取模以保持数值大小适中return ans# 返回最终的答案

这段代码实现了一个算法，用于解决一个关于数组中子序列的特定问题。具体来说，它计算了所有长度为 ( k ) 的子序列中，最小元素差值的加权和。这里的“加权和”是指，对于每个子序列，找到其中最小的元素差值（即两个相邻元素之间的最小差），然后将这个差值乘以它在所有满足条件的子序列中出现的次数，最后将这些乘积求和并取模。

下面是每部分实现思想的详细解释：

1. 初始化与排序:

mod = 1_000_000_007
nums.sort()

• • mod: 这是一个常量，用来对最终结果取模，确保输出结果不会过大。
  • nums.sort(): 对输入的列表 nums 进行排序，这一步是为了简化后续的子序列选择过程，因为排序后可以利用数组的有序性来优化搜索。

1. 动态规划函数 dp:

@cache
def dp(root: int, length: int):...

内部逻辑:

• • @cache: 这是一个装饰器，用于缓存函数的结果，避免重复计算相同子问题，这是动态规划的一个关键特性。
  • 函数 dp 的目标是计算以 nums[root] 结尾，长度为 length 的所有子序列中最小差值的分布。它返回一个字典 cnt，其中键是差值，值是该差值出现的次数。
  • 当 length 为 2 时，处理最简单的情况，即直接计算所有可能的两元素子序列的差值。
  • 当 length 大于 2 时，递归地构建更长的子序列。它遍历所有可能的子序列末尾元素 nums[i]，并递归调用 dp(i, length - 1) 来获取更短子序列的信息。

1. 计算最终答案:

ans = 0
for i in range(k - 1, len(nums)):for diff, cnt in dp(i, k).items():ans = (ans + diff * cnt) % mod
return ans

• • ans 初始化为 0，它是最终的加权和结果。
  • 对于长度为 k 的子序列，其末尾元素 nums[i] 可能从 nums[k-1] 到 nums[-1]。
  • 对于每个可能的末尾元素，调用 dp(i, k) 获得所有以 nums[i] 结尾的子序列中最小差值的分布。
  • 每次迭代中，将差值 diff 和它的计数 cnt 相乘，然后累加到 ans 中，并且每次累加都进行模运算以保持结果在限定范围内。

整个算法的核心在于使用动态规划来高效地计算子序列中最小差值的分布，从而避免了暴力枚举所有子序列的时间复杂度过高的问题。这种方法的时间复杂度和空间复杂度都显著优于简单枚举方案，尤其是在数组较大时。

LEETCODE 1. 两数之和

题解地址
. - 力扣（LeetCode）
有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

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

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

分析

方法一：暴力枚举

思路及算法

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return {i, j};}}}return {};}
};来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

上述代码是一个简单的解决LeetCode上"两数之和"问题的实现。下面对该代码的复杂度进行分析。

设输入的数组长度为n。

1. 外层循环：i从0到n-1，共进行n次迭代。
2. 内层循环：j从i+1到n-1，平均情况下进行(n-1-i)/2次迭代（假设n足够大）。

因此，总的迭代次数为：
n + (n-1) + (n-2) + ... + 1 ≈ n^2 / 2

由于内层循环中只有常数次的操作，可以忽略不计，所以算法的时间复杂度为O(n^2)。

在空间复杂度方面，除了存储结果的返回数组外，算法并没有使用额外的空间，因此空间复杂度为O(1)（常数级别）。

需要注意的是，由于解决两数之和问题的最优解是哈希表，其时间复杂度为O(n)，因此上述代码存在较高的时间复杂度，不是最优解。但在一些规模较小的问题上，该算法的实际性能可能仍然可接受。

作者：LeetCode-Solution
链接：. - 力扣（LeetCode）
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：哈希表

哈希表（Hash Table），也被称为散列表，是一种常用的数据结构。它通过利用哈希函数（Hash Function）来实现快速的数据插入、删除和查找操作。

哈希表由一个数组和哈希函数组成。哈希函数将每个元素映射到数组中的一个位置，该位置称为哈希值或哈希码。数组的索引即为哈希值，可以直接访问到对应位置的元素。

具体的工作原理如下：

1. 对于要插入或查找的元素，首先经过哈希函数得到它的哈希值。
2. 将元素存储在计算得到的哈希值对应的数组位置上。
3. 若存在相同的哈希值，则可能发生冲突（Hash Collision）。冲突可以通过使用开放寻址法和链地址法来解决。

• • 开放寻址法：当发生冲突时，不断地探测下一个空闲位置，直到找到合适的位置插入元素。
  • 链地址法：在哈希表的每个位置上维护一个链表，每个链表存储哈希值相同的元素，冲突时将元素插入链表中。

1. 插入和查找元素时，再次通过哈希函数计算哈希值，然后在对应位置上进行操作。

哈希表通过利用哈希函数的快速计算和数组的随机访问特性，实现了高效的元素插入、删除和查找。在理想情况下，哈希表的插入、删除和查找操作的平均时间复杂度为O(1)。

哈希表在很多应用中都得到广泛的使用，例如数据库索引、缓存系统、编译器中的符号表等。

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for (int i = 0; i < nums.size(); ++i) {auto it = hashtable.find(target - nums[i]);if (it != hashtable.end()) {return {it->second, i};}hashtable[nums[i]] = i;}return {};}
};

上述代码是使用哈希表来解决LeetCode上"两数之和"问题的实现。该算法的时间复杂度为O(n)，空间复杂度为O(n)。

具体分析如下：

1. 创建一个哈希表 hashtable，用于存储数组中的元素及其对应的索引。
2. 遍历数组 nums，对于每个元素 nums[i]，进行以下操作：

• • 在哈希表 hashtable 中寻找是否存在 target - nums[i] 的键值对，即找到了另外一个数与当前数之和为目标值 target。
  • 如果找到了，返回对应的索引和当前元素的索引。
  • 如果没有找到，将当前元素 nums[i] 插入哈希表 hashtable 中，键为元素值，值为元素索引。

1. 如果遍历结束仍未找到满足条件的元素对，返回空数组。

在这个算法中，通过哈希表的快速查找特性，将寻找 target - x 的时间复杂度降低为O(1)。因此，总的时间复杂度为O(n)。同时，哈希表用来存储元素及其索引，所需的额外空间为O(n)。

相比于方法一，方法二使用哈希表使得算法的时间复杂度大幅降低，是更优的解法。

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

当然可以！通过使用两个指针，可以将时间复杂度降低到O(n)。下面是一个优化的算法：

假设有一个排序好的数组，并且我们要找到两个数之和等于目标值target。使用双指针方法可以高效地解决这个问题。

1. 初始化两个指针left和right，分别指向数组的开头和结尾。
2. 计算两个指针指向的元素的和sum。

• • 如果sum等于target，那么找到了两个数的和等于目标值，返回它们的索引。
  • 如果sum小于target，说明需要增加两个数的和，因此将left指针右移一位。
  • 如果sum大于target，说明需要减小两个数的和，因此将right指针左移一位。

1. 重复步骤2直到找到满足条件的两个数，或者left大于等于right时停止搜索。

这个算法的时间复杂度为O(n)，因为在最坏情况下，我们需要遍历数组一次。而空间复杂度仍为O(1)，因为只需要额外存储两个指针的索引。

需要注意的是，这个方法适用于已经排序好的数组。如果输入的数组无序，我们可以先对其进行排序，然后再使用双指针方法。

def two_sum(nums, target):left = 0right = len(nums) - 1while left < right:sum = nums[left] + nums[right]if sum == target:return [left, right]elif sum < target:left += 1else:right -= 1# 若找不到满足条件的两个数，则返回空列表return []# 示例输入
nums = [-2, 0, 3, 6, 7, 9, 11]
target = 9result = two_sum(nums, target)
if result:print("找到满足条件的两个数的索引：", result)
else:print("找不到满足条件的两个数")

代码随想录：

梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！_哔哩哔哩_bilibili

思路

很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。

本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。

C++中map，有三种类型： !如图

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。 更多哈希表的理论知识请看关于哈希表，你该了解这些！。

这道题目中并不需要key有序，选择std::unordered_map 效率更高！使用其他语言的录友注意了解一下自己所用语言的map结构的内容实现原理。

接下来需要明确两点：

map用来做什么
map中key和value分别表示什么
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下表，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下表}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

过程如下：

!过程一

!过程二

C++代码：

class Solution {
public:
vector twoSum(vector& nums, int target) { std::unordered_map <int,int> map; for(int i = 0; i < nums.size(); i++) { // 遍历当前元素，并在map中寻找是否有匹配的key auto iter = map.find(target - nums[i]); if(iter != map.end()) { return {iter->second, i}; } // 如果没找到匹配对，就把访问过的元素和下标加入到map中 map.insert(pair<int, int>(nums[i], i)); } return {}; } };

总结

这道题目关键是在于明确map是用来做什么的，map中的key和value用来存什么的。

这个想清楚了，题目代码就比较清晰了。

很多录友把这道题目 通过了，但都没想清楚map是用来做什么的，以至于对代码的理解其实是 一知半解的。

其他语言版本

Java：

public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i];
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
}
map.put(nums[i], i);
}
return res;
}
Python：

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
records = dict()

    # 用枚举更方便，就不需要通过索引再去取当前位置的值for idx, val in enumerate(nums):if target - val not in records:records[val] = idxelse:return [records[target - val], idx] # 如果存在就返回字典记录索引和当前索引

Go：

func twoSum(nums []int, target int) []int {
for k1, _ := range nums {
for k2 := k1 + 1; k2 < len(nums); k2++ {
if target == nums[k1] + nums[k2] {
return []int{k1, k2}
}
}
}
return []int{}
}
// 使用map方式解题，降低时间复杂度
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for index, val := range nums {
if preIndex, ok := m[target-val]; ok {
return []int{preIndex, index}
} else {
m[val] = index
}
}
return []int{}
}
Rust

use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec, target: i32) -> Vec { let mut map = HashMap::with_capacity(nums.len());

    for i in 0..nums.len() {if let Some(k) = map.get(&(target - nums[i])) {if *k != i {return vec![*k as i32,  i as i32];}}map.insert(nums[i], i);}panic!("not found")
}

}
Javascript

var twoSum = function (nums, target) {
let hash = {};
for (let i = 0; i < nums.length; i++) {
if (hash[target - nums[i]] !== undefined) {
return [i, hash[target - nums[i]]];
}
hash[nums[i]] = i;
}
return [];
};
php

function twoSum(array

target): array
{
for (

i < count(

i++) {
// 计算剩下的数

target -

i];
// 匹配的index，有则返回index， 无则返回false

residue,

match_index !== false &&

i) {
return array(

match_index);
}
}
return [];
}
Swift：

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var res = Int
var dict = Int : Int
for i in 0 ..< nums.count {
let other = target - nums[i]
if dict.keys.contains(other) {
res.append(i)
res.append(dict[other]!)
return res
}
dict[nums[i]] = i
}
return res
}
Scala:

object Solution {
// 导入包
import scala.collection.mutable
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
// key存储值，value存储下标
val map = new mutable.HashMapInt, Int
for (i <- nums.indices) {
val tmp = target - nums(i) // 计算差值
// 如果这个差值存在于map，则说明找到了结果
if (map.contains(tmp)) {
return Array(map.get(tmp).get, i)
}
// 如果不包含把当前值与其下标放到map
map.put(nums(i), i)
}
// 如果没有找到直接返回一个空的数组，return关键字可以省略
new ArrayInt
}
}
C#:

public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int ,int> dic= new Dictionary<int,int>();
for(int i=0;i<nums.Length;i++){
int imp= target-nums[i];
if(dic.ContainsKey(imp)&&dic[imp]!=i){
return new int[]{i, dic[imp]};
}
if(!dic.ContainsKey(nums[i])){
dic.Add(nums[i],i);
}
}
return new int[]{0, 0};
}
}

画图解