2024年2月13日力扣题目训练
2024年2月13日力扣题目训练
2024年2月13日第二十天编程训练，今天主要是进行一些题训练，包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成，不过之后我会认真完成的,我会慢慢补回来，争取一天发两篇，把之前的都补上。
594. 最长和谐子序列
链接: 最长和谐子序列
难度： 简单
题目：
运行示例：
思路：
这道题就是简单的排序，之后找比当前值大1的位置。
代码：
class Solution {
public:
int findLHS(vector<int>& nums) {
sort(nums.begin(),nums.end());
int begin = 0;
int ans = 0;
for(int end = 0; end < nums.size(); end++){
while(nums[end] - nums[begin] > 1) begin++;
if(nums[end] - nums[begin] == 1) ans = max(ans,end-begin+1);
}
return ans;
}
};
598. 区间加法 II
链接: 区间加法 II
难度： 简单
题目：
运行示例：
思路：
这道题就是找多次出现的交集，对于每一次操作，给定 (a,b)、，我们会将矩阵中所有满足 0≤i<a0以及 0≤j<b的位置 (i,j)全部加上 1。由于 a,b均为正整数，那么 (0,0)总是满足上述条件，并且最终位置 (0,0)的值就等于操作的次数。因此，我们的任务即为找出矩阵中所有满足要求的次数恰好等于操作次数的位置。
代码：
class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
if(ops.size() == 0) return m*n;
int mina = m;
int minb = n;
for(int i = 0; i < ops.size(); i++){
mina = min(mina,ops[i][0]);
minb = min(minb,ops[i][1]);
}
return mina*minb;
}
};
599. 两个列表的最小索引总和
链接: 最小索引总和
难度： 简单
题目：
运行示例：
思路：
这道题就是利用哈希表计数计算最小的索引和。
代码：
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> res;
for(int i = 0; i < list1.size(); i++){
res[list1[i]]= i+1;
}
int count = INT_MAX;
vector<string> ans;
for(int i = 0; i < list2.size(); i++){
if(res[list2[i]] ){
if(res[list2[i]] + i < count){
ans.clear();
ans.push_back(list2[i]);
count = res[list2[i]] + i;
}else if(res[list2[i]] + i == count){
ans.push_back(list2[i]);
}
}
}
return ans;
}
};
284. 窥视迭代器
链接: 窥视迭代器
难度： 中等
题目：
运行示例：
思路：
这道题可以看出就是利用遍历进行迭代即可。
代码：
class PeekingIterator : public Iterator {
private:
int nextElement;
bool flag;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
// Initialize any member here.
// **DO NOT** save a copy of nums and manipulate it directly.
// You should only use the Iterator interface methods.
flag = Iterator::hasNext();
if(flag){
nextElement = Iterator::next();
}
}
// Returns the next element in the iteration without advancing the iterator.
int peek() {
return nextElement;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
int next() {
int res = nextElement;
flag = Iterator::hasNext();
if(flag){
nextElement = Iterator::next();
}
return res;
}
bool hasNext() const {
return flag;
}
};
287. 寻找重复数
链接: 寻找重复数
难度： 中等
题目：
运行示例：
思路：
这道题存在一个重复的数字，我本来的想法是哈希表，但是这个不符合题意。我看了题解，是采用映射，这样就存在了链表，有重复数字的话就是存在环，则这道题就变成了找环链表入扣的问题。我觉得这个很巧妙，感觉跟之前的题不太一样，这个题可以转化为原来的其他题，而不是直接给出。
代码：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
};
135. 分发糖果
链接: 分发糖果
难度： 困难
题目：
运行示例：
思路：
这道题我们会发现当前孩子获得糖果的状态只跟左右有关，所以我们进行左遍历和右遍历从而找到能满足当前状态的糖果数。不过这个思路也不是我想的，我是看了解析才得到的，只能说我的能力有待提高而且这个思路真的很巧妙，官方题解提到的常数空间遍历，我觉得也是依据这种状态得到的。
代码：
class Solution {
public:
int candy(vector<int>& ratings) {
int count = 0;
vector<int> left(ratings.size(),1);
for(int i = 1; i < ratings.size(); i++){
if(ratings[i] > ratings[i-1]) left[i] = left[i-1]+1;
}
vector<int> right(ratings.size(),1);
count = max(left[ratings.size()- 1],right[ratings.size()- 1]);
for(int i = ratings.size()- 2; i >= 0 ; i--){
if(ratings[i] > ratings[i+1]) right[i] = right[i+1]+1;
count += max(left[i],right[i]);
}
return count;
}
};
