1、旅行终点站（3分）
题目描述
给你一份旅游线路图，该线路图中的旅行线路用数组 paths表示，其中 paths[i] = [cityAi, cityBi]表示该线路将会从 cityAi直接前往 cityBi。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。
示例 1：
输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo"
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。
本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
示例 2：
输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A".
"B" -> "C" -> "A".
"C" -> "A".
"A".
显然，旅行终点站是 "A" 。
示例 3：
输入：paths = [["A","Z"]]
输出："Z"
提示：
1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
所有字符串均由大小写英文字母和空格字符组成。
解题思路
- 题意中的
paths是一个特殊的一维数组。每个一维数组中的元素是一个含有两个元素的一维数组，元素是string类型。 - 题意本质是找到数组中每个元素的第二个元素不会与元素中第一个元素重复的元素。好比数据结构中的拓扑排序。
- 方法：将数组中每个元素的第一个元素存到
vector<string>中，验证数组中每个元素的第二个元素是否与vector<string>中的元素相匹配，返回匹配不到的元素即可。
代码实现
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
vector<vector<string>>::iterator iter = paths.begin();
vector<string> svec;
for(; iter != paths.end(); iter++)
svec.push_back(*(iter->begin())); // 二级迭代器 用指针表示
for(iter = paths.begin(); iter != paths.end(); iter++)
if(count(svec.begin(), svec.end(), *(iter->begin() + 1)) == 0)
return *(iter->begin() + 1);
return {};
}
};
运行截图
在这里插入图片描述
2、 是否所有 1 都至少相隔 k 个元素（4分）
题目描述
给你一个由若干 0和 1组成的数组nums以及整数k。如果所有 1都至少相隔 k个元素，则返回 True；否则，返回 False。
示例 1：
在这里插入图片描述
输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。
示例 2：
在这里插入图片描述
输入：nums = [1,0,0,1,0,1], k = 2
输出：false
解释：第二个 1 和第三个 1 之间只隔了 1 个元素。
示例 3：
输入：nums = [1,1,1,1,1], k = 0
输出：true
示例 4：
输入：nums = [0,1,0,1], k = 1
输出：true
提示：
1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i] 的值为 0 或 1
解题思路
- A了2次才过的，没有考虑到只有一个 1 和不存在 1 的情况。考虑到了 k = 0 的情况。
- 使用
find()函数。用vector<int>::iterator迭代器找到第一个 1 的位置和下一个 1 的位置，计算两者之间的间隔。符合题意返回true，否则返回false。 - 说明迭代器是可以执行加减运算的。
代码实现
class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
if(nums.size() < 2 || k < 0)
return false;
if(k == 0) // k=0 对任何情况都是成立的
return true;
if(count(nums.begin(), nums.end(), 1) < 2)
return true; // 1的个数不超过2个，自然也是正确的
vector<int>::iterator iter = nums.begin(), itertemp;
iter = find(iter, nums.end(), 1); // 迭代器指向第一个有1的位置
iter++; // 迭代器指向第一个1的位置的下一个位置
while(iter != nums.end())
{ // 逐次判断两个1之间0的个数
itertemp = iter;
iter = find(iter, nums.end(), 1);
if(iter - itertemp < k)
return false;
iter++;
}
return true;
}
};
运行截图
在这里插入图片描述
3、绝对差不超过限制的最长连续子数组（5分）
问题描述
给你一个整数数组 nums，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。如果不存在满足条件的子数组，则返回 0。
示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。
示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。
示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
解题思路
- 设置滑动窗口从左向右遍历整个数组，
i和j分别表示滑动窗口的左右两端。 - 进入滑动窗口中的元素，只要其最大值和最小值之差小于等于
limit，窗口中的所有元素均符合题意。反之，只要最大值和最小值之差大于了limit，那么说明从i号元素开始的符合题意的子序列的最大长度就不会继续更新，这就需要改变（后移）i的值。 - 如何方便的求解滑动窗口中的最大值和最小值的差，最好的办法就是引入
map容器。map容器的特点就是：（1）key值唯一并且是有序排列的。（2）执行map[key]++时，如果key值已经存在，则对key值所对应的value值进行更新。区别于map的insert函数：如果对已经存在的key值的value进行更新，则不会执行。 - 本题目中
map中key对应的value值用于记录整个数组中出现相同元素的次数，当然使用multimap和multiset的方法也可以实现。
代码实现
（1）使用map
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
map<int, int> imap;
int maxnum = 0;
int i = 0; // 用于记录滑动窗口的右边界
for(int j = 0; j < nums.size(); j++) // 用于记录滑动窗口的左边界
{
imap[nums[j]]++; // 用于记录每个相同元素出现的次数
if(imap.rbegin()->first - imap.begin()->first <= limit)
{
maxnum = max(maxnum, j - i + 1);// 新进入滑动窗口的元素符合题意就更新maxnum值
continue;
}
if((--imap[nums[i]]) == 0) // 新进入滑动窗口的元素不合题意
imap.erase(nums[i]); // 不存在任何相同的该元素 就彻底移除map容器
i++; // 不合题意 i 向后移动 即 滑动窗口后移
}
return maxnum;
}
};
（2）使用multiset
-
multiset或者是map不能使用push_back()函数，插入元素使用insert()即可。 -
multiset或者是map的极值自然是其第一个元素和最后一个元素，使用的方法是*iset.begin(),*iset.rbegin()。 - 如果使用
multiset.erase(a)，则会删除所有等于a的元素，正确做法是找到a所在的迭代器：multiset.erase(multiset.find(a))，其中multiset.find(a)返回等于a元素的位置，这样就不至于删除所有的元素了。
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
multiset<int> iset;
int maxlength = 0, i = 0;
for(int j = 0; j < nums.size(); j++)
{
iset.insert(nums[j]);
if(*iset.rbegin() - *iset.begin() <= limit)
{
int size = iset.size();
maxlength = max(maxlength, size);
}
else
iset.erase(iset.find(nums[i++])); // 防止删除多个相同元素
}
return maxlength;
}
};
运行截图
（1）使用map
在这里插入图片描述
（2）使用multiset
在这里插入图片描述
4、有序矩阵中的第 k 个最小数组和（7分）
题目描述
给你一个 m * n的矩阵 mat，以及一个整数 k，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1个元素形成一个数组。返回所有可能数组中的第 k个 最小 数组和。
示例 1：
输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2：
输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17
示例 3：
输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
提示：
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组
解题思路
- （1）暴力解法。即求解出每一行每个元素相加的前K个值，由于这些值需要非递减有序，所以可使用
multimap或者是multiset来存储。需要考虑只有1行的情况。
代码实现
（1）暴力解法
class Solution {
public:
int kthSmallest(vector<vector<int>>& mat, int k) {
if(mat.size() == 1) // 考虑只有1行的情况
return mat[0][k - 1];
vector<int> ivec = mat[0]; // 首先让multiset存储第一行的元素
for(int i = 1; i < mat.size(); i++)
{
multiset<int> imset; //定义临时multiset存储前 i - 1 行到第 i 行的所有元素的加和
for(auto& num1 : ivec)
for(auto& num2 : mat[i])
imset.insert(num1 + num2);
ivec.assign(imset.begin(), imset.end());
ivec.resize(min(k, (int)ivec.size()));
}
return ivec.back();
}
};
运行截图
在这里插入图片描述
LeetCode第 187 场周赛总结
- 前两道题可以使用暴力求解。
- 第三题要明白题目的整个过程，使用滑动窗口的思路来解答问题，很多情况使用
map和set往往要比使用vector更利于解题。 - 第四题由于时间关系暂写暴力求解，二分法后续补充。要学会转变思维，从上向下的求和会更好。
