leetcode 203. Remove Linked List Elements
/**
* 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* removeElements(ListNode *head, int val) {
// ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
// tem->next = head;
// ListNode *p = tem;
// while(p->next != NULL) {
// if(p->next->val == val) {
// p->next = p->next->next;
// }
// if(p->next && p->next->val != val) p = p->next;
// if(p == NULL) break;
// }
// return tem->next;
if(head == NULL) return head;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};
法1 循环
法2 递归
这个写法很短，看题解所得
好久没看过链表了，写题一脸懵逼（
21. Merge Two Sorted Lists
自己写的腌臜玩意
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *ans = (ListNode*)malloc(sizeof(ListNode)); ans->next = NULL;
ListNode *ANS = ans;
ListNode *p1 = list1, *p2 = list2;
while(p1 && p2) {
ListNode *tem = (ListNode*)malloc(sizeof(ListNode)); // try 定义到外面 公用？
if(p1->val <= p2->val) {
tem->val = p1->val;
tem->next = NULL;
ans->next = tem;
p1 = p1->next; ans = ans->next;
}
else {
tem->val = p2->val;
tem->next = NULL;
ans->next = tem;
p2 = p2->next; ans = ans->next;
}
}
while(p1) {
ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
tem->val = p1->val;
tem->next = NULL;
ans->next = tem;
p1 = p1->next; ans = ans->next;
}
while(p2) {
ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
tem->val = p2->val;
tem->next = NULL;
ans->next = tem;
p2 = p2->next; ans = ans->next;
}
return ANS->next;
}
};
简洁的代码：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *ans = (ListNode*)malloc(sizeof(ListNode));
ans->next = NULL;
ListNode *ANS = ans;
while(list1 && list2) {
if(list1->val <= list2->val) {
ans->next = list1;
ans = ans->next;
list1 = list1->next;
}
else {
ans->next = list2;
ans = ans->next;
list2 = list2->next;
}
}
ans->next = (list1 ? list1 : list2);
return ANS->next;
}
};
改进的地方：
- 不需要保留list1,list2这两个链表的首元素地址了，也就不需要重新定义变量
- 当有一个链表已经空了的时候，这时候直接让ans的next指向另外一个链表，其实就是另一个链表剩下的部分，简化了代码量
141. Linked List Cycle
法1
因为最多有1e4个点，所以当遍历到第 1e4+1 个点时肯定是有环的
class Solution {
public:
bool hasCycle(ListNode *head) {
int cnt = 0;
while(head) {
cnt++;
head = head->next;
if(cnt >= 10001) break;
}
return (cnt >= 10001);
}
};
法2
容易想到第一次访问过一个点就记录一下，注意vis数组里存的是链表元素的数据类型（ListNode）
class Solution {
public:
bool hasCycle(ListNode *head) {
map<ListNode*, int> mp;
int cnt = 0;
while(head) {
if(mp[head]) return 1;
mp[head] = 1;
head = head->next;
}
return 0;
}
};
206. Reverse Linked List
反转链表
注意LeetCode用C++编译器但是写malloc不free会报错
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) return head;
ListNode *tem = new ListNode;
tem->val = head->val; tem->next = NULL;
head = head->next;
while(head) {
ListNode *p = new ListNode;
p->val = head->val; p->next = tem;
tem = p;
head = head->next;
}
return tem;
}
};
20. Valid Parentheses
法1 因为一定有括号是连在一起的，思路是每次找 {} , () , [] 三者中的一个，去掉之后check剩余部分
写得很腌臢，明显可以用 s.replace("{}", "") 来简化
class Solution {
public:
bool isValid(string s) {
if(s.empty()) return 1;
int n = s.size();
if(n % 2 || s[0] == ']' || s[0] == ')' || s[0] == '}') return 0;
int fl = -1;
int i = s.find("()");
if(i != -1) {
fl = i;
}
else {
i = s.find("[]");
if(i != -1) {
fl = i;
}
else {
i = s.find("{}");
if(i != -1) {
fl = i;
}
}
}
if(fl == -1) return 0;
else {
string tem = "";
if(fl > 0) tem += s.substr(0, fl);
if(fl + 2 < n) tem += s.substr(fl + 2);
return isValid(tem);
}
}
};
该好好复习STL了！！！
法2 利用stack，如果遇到左括号直接push，如果是右括号，它一定是跟栈顶的括号配对。如果不配直接return 0，能配对就弹出栈顶
class Solution {
public:
bool isValid(string s) {
// 正解应该是stack + 肯定可以直接配对
stack<char> Sta;
for(auto x : s) {
// if(!Sta.empty()) cout << Sta.top() << endl;
if(x == '(' || x == '[' || x == '{') Sta.push(x);
else {
if(Sta.empty()) return 0;
char tem = Sta.top();
if(x == '}') {
if(tem == '{') Sta.pop();
else return 0;
}
else if(x == ']') {
if(tem == '[') Sta.pop();
else return 0;
}
else if(x == ')') {
if(tem == '(') Sta.pop();
else return 0;
}
}
}
return Sta.empty();
}
};
232. Implement Queue using Stacks
做法就是纯模拟啦，记得栈和队列不要看错了。
原来通过做这道题我才知道，我根本不会cpp......只是会C with STL的菜鸡罢了（呜呜呜
this和构造函数什么的，完全都忘记了啊
typedef struct {
int val;
struct MyQueue *next;
} MyQueue;
MyQueue* myQueueCreate() { /// 头指针
MyQueue *head = (MyQueue*)malloc(sizeof(MyQueue));
head->next = NULL; head->val = 0;
return head;
}
void myQueuePush(MyQueue* obj, int x) {
MyQueue *tem = obj;
MyQueue *p = myQueueCreate();
p->val = x;
while(tem->next) tem = tem->next;
tem->next = p;
}
int myQueuePop(MyQueue* obj) {
if(obj->next == NULL) return NULL;
MyQueue *tem = obj->next;
int x = tem->val;
obj->next = tem->next;
return x;
}
int myQueuePeek(MyQueue* obj) {
if(obj->next == NULL) return NULL;
MyQueue *tem = obj->next;
int x = tem->val;
return x;
}
bool myQueueEmpty(MyQueue* obj) {
return (obj->next == NULL);
}
void myQueueFree(MyQueue* obj) {
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/