Datawhale & 阿里云天池LeetCode基础训练营
Task1: 数组
课后习题
1. 在有序数组中删除重复项（Easy）
给一个有序的数组，其中一些是重复的，比如 [1，2，2，2，4] 删除重复项后 [1,2,4]。
请删除重复项并返回新的数组长度。
输入：nums = [0，0，1，1，1，2，3，3] 输出：5, nums = [0，1，2，3，4] 解释：函数应返回新的长度 5 ， 并且原数组 nums 修改前五个元素 0, 1, 2, 3, 4 。数组中超过新长度的元素不需要考虑。 STL 做法
class Solution {
public: int removeDuplicates(vector<int>& nums) {
auto last = unique(nums.begin(),nums.end()); nums.erase(last,nums.end()); return nums.size(); } }; 每次我们统计重复的数字，然后向前移动cnt个位置，就能保证前面的值都是唯一的了
class Solution {
public: int removeDuplicates(vector<int>& nums) {
int len = nums.size(), cnt = 0; for(int i = 1; i < nums.size(); i ){
if(nums[i] == nums[i-1]){
cnt++; len--; }else{
nums[i-cnt] = nums[i]; } } return len; } }; 2. 移除元素（Easy）
**题意：**给你一个数组和值val，从数组中移除所有等于val的元素
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
和上题一样的思路，这里不再赘述
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = nums.size();
int cnt = 0;
for(int i = 0; i < nums.size(); i++){
if(val == nums[i]){
len--;
cnt++;
continue;
}
nums[i-cnt] = nums[i];
}
return len;
}
};
3. 三数之和（Medium)
**题意：**给定一数组，按任意顺序返回三数之和为0 的三元组，其中元素各不重复，且返回的三元组也不重复
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
这道题的难点即在于三元组判重，通过观察可发现，若要三元组不重复，其实就是使三元组的前两个元素不重复出现，
熟悉STL的朋友可以使用set<pair<int,int>> 来判重，然后第三个元素我们通过二分来查找即可
不过Set判重的复杂度也不低，可以优化一下做法:
考虑到我们将数组排序后，元素皆有序，那么问题就变成了有序数组中寻找所有不重复的二元组问题
显然，二元组的第一个元素不枚举重复的，（否则必然导致重复答案）第二个元素也是（同理）。
我实在是想不通为什么我的二分比他们枚举还慢这么多，如果有知道的大佬劳请指点一二
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
if(n < 3) return {
};
sort(nums.begin(),nums.end());
set<pair<int,int>> st;
vector<vector<int>> ans;
for(int i = 0; i < n; i++){
if(nums[i] > 0) break;
for(int j = i+1; j < n; j++){
int l = j + 1, r = n - 1;
while(l < r){
int mid = (l+r)/2;
if(nums[i] + nums[j] + nums[mid] == 0){
l = mid;
break;
}
else if(nums[i] + nums[j] + nums[mid] > 0) r = mid-1;
else l = mid+1;
}
if(l < n && nums[i] + nums[j] + nums[l] == 0){
if(st.find(make_pair(nums[i],nums[j])) == st.end()){
ans.push_back(vector{
nums[i],nums[j],nums[l]});
st.insert(make_pair(nums[i],nums[j]));
}
}
}
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
if(n < 3) return {
};
sort(nums.begin(),nums.end());
vector<vector<int>> ans;
for(int i = 0; i < n; i++){
if(i > 0 && nums[i] == nums[i-1]) continue;//第一个位置判重
for(int j = i+1; j < n; j++){
if(j > i+1 && nums[j] == nums[j-1]) continue;//第二个位置判重
int l = j+1, r = n-1;
while(l < r){
int mid = (l+r)/2;
if(nums[i] + nums[j] + nums[mid] == 0){
l = mid;
break;
}
else if(nums[i] + nums[j] + nums[mid] > 0) r = mid-1;
else l = mid+1;
}
if(l < n && nums[i] + nums[j] + nums[l] == 0){
ans.push_back(vector{
nums[i],nums[j],nums[l]});
}
}
}
return ans;
}
};
Task2：链表
课后习题
1.合并两个有序链表（Easy）
**题意：**给你两个有序的链表，合成一个有序的新链表
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
思路：递归返回或者迭代合并再返回
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1) return list2;
else if(!list2) return list1;
else if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
};
2.相交链表（Easy）
**题意:**给你两个链表，其中有一个节点往后他们都相同，求该节点
[外链图片转存中…(img-sz5pZ068-1645112683925)]
如该处的相交处为2这个节点
思路：直接开哈希表记录结点即可
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *t = headA;
unordered_set< ListNode* > st;
while(t){
st.insert(t);
t = t->next;
}
t = headB;
while(t){
if(st.count(t)) return t;
t = t->next;
}
return nullptr;
}
};
3.删除排序链表中的重复元素 II（Medium）
**题意：**将链表中所有出现1次以上的值的节点删除并返回新链表
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
思路：前后指针（或者叫左右指针）, 首先用一个指针指向前指针，然后比较前后指针的值是否相等，是则一直移动后指针，直到不相等。然后更新左右指针，继续下次循环。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return nullptr;
ListNode *prev = new ListNode(-123);
ListNode *cur = prev;
while (head) {
int cnt = 0;
while (head->next && head->val == head->next->val) {
cnt++;
head = head->next;
} // 循环结束后，head 的值与下个节点的值不一样
if (cnt == 0) {
cur->next = new ListNode(head->val);
cur = cur->next;
}
head = head->next;
}
return prev->next;
}
};
Task3：栈
课后习题
1.最小栈（Easy）
**题意：**设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
利用另外一个栈来保存前缀最小值即可，这里便不模拟栈了，直接使用stl内的栈
class MinStack {
public:
stack<int> stk,min_stk;
MinStack() {
min_stk.push(INT_MAX);
}
void push(int val) {
stk.push(val);
min_stk.push(min( min_stk.top(), val));
}
void pop() {
stk.pop();
min_stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
2.比较含退格的字符串(Easy)
‘ # ’ 字符表示退格操作，给你两个字符串，问退格操作后两字符串是否相等
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
遇到字母就入栈，遇到# 就退栈，最后一次比较每个出栈的字符即可
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<int> s_stk, t_stk;
for(auto &c : s){
if(c != '#'){
s_stk.push(c);
}else{
if(!s_stk.empty()){
s_stk.pop();
}
}
}
for(auto &c : t){
if(c != '#'){
t_stk.push(c);
}else{
if(!t_stk.empty()){
t_stk.pop();
}
}
}
while(!s_stk.empty() && !t_stk.empty()){
if(s_stk.top() != t_stk.top()) return false;
s_stk.pop();
t_stk.pop();
}
return s_stk.empty() && t_stk.empty();
}
};
3.基本计算器 II(Medium)
**题意：**给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
输入：s = "3+2*2"
输出：7
输入：s = " 3/2 "
输出：1
输入：s = " 3+5 / 2 "
输出：5
由于这里的运算比较简单，我们将其转化为一个加法栈，最后求和即可。
我们来看看每组数字前面的运算符
加号 就直接把数字入栈
减号 就把相反数入栈
乘除 就把该组数字与栈顶的数字相运算即可。
最后对加法栈进行求和就是答案。
class Solution {
public:
int calculate(string s) {
stack<int> stk;
int val = 0;
char pre_op = '+';
int len = s.length();
for (int i = 0; i < len; ++i) {
if (isdigit(s[i])) {
val = val * 10 + (s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == len - 1) {
//防止除0和读完数字的情况
switch (pre_op) {
case '+':{
stk.push(val);
break;
}
case '-':{
stk.push(-val);
break;
}
case '*':{
stk.top() *= val;
break;
}
case '/':{
stk.top() /= val;