前言
💫你好，我是辰chen，本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode，当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码
以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：
💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解
旅行终点站
题目链接：旅行终点站
C++版AC代码：
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
// 理解成找出度为0的结点(由题结果必然存在)
unordered_map<string, int> m;
for (int i = 0; i < paths.size(); i ++ ) {
string add = paths[i][0]; // 统计有出度的点
m[add] = 1;
}
string res;
for (int i = 0; i < paths.size(); i ++ ) {
string ed = paths[i][1]; // 找所有出度可能为0的点
if (!m.count(ed)) {
res = ed;
break;
}
}
return res;
}
};
通过翻转子数组使两个数组相等
题目链接：通过翻转子数组使两个数组相等
C++版AC代码：
class Solution {
public:
bool canBeEqual(vector<int>& target, vector<int>& arr) {
unordered_map<int, int> m;
for (int i = 0; i < target.size(); i ++ ) m[target[i]] ++;
bool flag = true;
for (int i = 0; i < arr.size(); i ++ ) {
if (m.count(arr[i]) && m[arr[i]] >= 1) m[arr[i]] --;
else {
flag = false;
break;
}
}
return flag;
}
};
判断路径是否相交
题目链接：判断路径是否相交
C++版AC代码：
原本想用坐标哈希的，但是不能套 pair，根据题目范围：1 <= path.length <= 1e4，故可以把横坐标映射为 1e5，纵坐标映射为 1，映射成 double 类型的 1 和 0.00001 的话会有精度问题
class Solution {
public:
bool isPathCrossing(string path) {
unordered_map<int, int> m;
m[0] = 1;
double nowad = 0;
bool flag = false;
for (int i = 0; i < path.size(); i ++ ) {
char ad = path[i];
if (ad == 'N') nowad += 1e5;
else if (ad == 'S') nowad -= 1e5;
else if (ad == 'E') nowad += 1;
else nowad -= 1;
if (m.count(nowad)) {
flag = true;
break;
}
m[nowad] = 1;
}
return flag;
}
};
两个相同字符之间的最长子字符串
题目链接：两个相同字符之间的最长子字符串
C++版AC代码：
class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
unordered_map<char, int> m;
for (int i = 0; i < s.size(); i ++ ) m[s[i]] = i; // 记录最后一次出现的位置
int res = -1;
for (int i = 0; i < s.size(); i ++ )
res = max(res, m[s[i]] - i - 1);
return res;
}
};
按照频率将数组升序排序
题目链接：按照频率将数组升序排序
C++版AC代码：
注意对 sort 的定义与调用
class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i ++ ) m[nums[i]] ++;
sort(nums.begin(), nums.end(), [&](const int a, const int b) {
if (m[a] == m[b]) return a > b;
return m[a] < m[b];
});
return nums;
}
};
能否连接形成数组 *
题目链接：能否连接形成数组
C++版AC代码：
class Solution {
public:
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
unordered_map<int, int> m;
for (int i = 0; i < pieces.size(); i ++ )
m[pieces[i][0]] = i; // 仅标记第一个
for (int i = 0; i < arr.size();) {
// 注意这里没有 i ++
int k = arr[i];
if (!m.count(k)) return false;
int ad = m.find(k) -> second;
for (int j = 0; j < pieces[ad].size(); j ++, i ++ ) // i 在此更新
if (arr[i] != pieces[ad][j])
return false;
}
return true;
}
};
关于sort
sort(nums.begin(), nums.end(), [&](const int a, const int b) {
if (m[a] == m[b]) return a > b;
return m[a] < m[b];
});
