文章目录
- 引言
- 新作
- 括号生成
- 个人实现
- 实现时遇到的问题
- 实现代码
- 参考思路
- 实现代码
- 合并K个有序链表
- 个人实现
- 实现代码
- 参考实现
- 实现代码
- 总结
引言
- 今天把第二篇论文投了，后续有审稿意见再说，然后在进行修改的。
- 后续的生活要步入正轨了，每天刷题，然后再背八股。
新作
括号生成
- 题目链接
个人实现
- 之前做过一个题目，是验证括号是否合法，这道题是让生成括号。可以在暴力的基础上，进行括号合法性的验证。最终的思路如下
- 有两种情况，验证括号的栈是否为空
- 如果栈为空，
- 还可以入栈，那就入栈
- 所有括号已经匹配完毕，为空，将结果加入到res中
- 如果栈不为空
- 入栈
- 出栈
- 如果栈为空，
- 想的挺好的，但是实现起来比较困难，没有啥头绪，所以采用了最直接的方法进行暴力遍历所有的组合，然后判定是否符合要求，符合要求再添加对应的元素。时间复杂度是真的高 ，好在数据量并不多。
实现时遇到的问题
- 排列组合应该怎么用代码实现，想了半天，写的有点不熟，自己一点点理出来的，应该好好记住才对。
- 这里是使用dfs实现组合的。
实现代码
实现代码
#include <iostream>
#include <stack>
#include <vector>using namespace std;bool judge(string s){stack<char> st;for (auto c:s) {if (c == '(') st.push(c);else{if (st.empty()) return false;else st.pop();}}return st.empty();
}vector<string> vt;
void dfs(string s,int t,int k){if (t == k){vt.push_back(s);}else{dfs(s + "(",t + 1,k);dfs(s + ")",t + 1,k);}
}vector<string> generateParenthesis(int n){vector<string> res;dfs("",0,2*n);for (auto t:vt) {if (judge(t)) res.push_back(t);}return res;
}
int main(){}
参考思路
下面这个是个好东西，经常用，需要呗
-
一个合法的括号序列的充分必要条件
- 任意前缀中，左括号的数量，大于等于右括号数量
- 左右括号数量相等
-
所以，第二个条件已经满足了，所以需要需要针对第一个条件进行计算
-
使用递归来实现将所有合法方案输出的情况
- 任何情况，都可以填左括号
- 什么时候填右括号
- 满足数量要求
- 前缀的左括号数量的大于等于右括号
-
定理：卡特兰数
实现代码
太牛逼了，这个代码写的真丝滑！！
vector<string> res;
void dfs(int n,int lc,int rc,string s){/** n表示括号数量，lc表示左括号数量，rc表示右括号数量，s表示字符串*/// 判定什么时候加左括号if (lc == n && rc == n) res.push_back(s); else{// 什么时候加右括号if (lc < n) dfs(n,lc + 1,rc,s + "(");if (lc > rc && rc < n) dfs(n,lc,rc + 1,s + ")");}
}vector<string> generateParenthesis(int n){dfs(n,0,0,"");return res;
}
实现过程中，有如下问题
- 注意，实现判断的是否相等，不相等再加括号，相等了就不加括号
- 如果加括号，再继续往下处理。
合并K个有序链表
- 题目链接
个人实现
- 将所有的链表合成一个新的有序链表，有以下两个特征
- 有序链表
- 多个合成一个
- 之前做过两个有序链表合成一个有序链表，用的两个指针同时比较，选择一个最小的然后进行链接。
- 如果采用同样的方法，计算复杂度有点高，有什么别的办法吗？如果不行，就只能暴力了。
- 最多是500个子队列，然后要维护500个指针。这个方法是不得行的。
- 跳过，这个不会做。
还有什么思路
维系一个最值的队列
- 计算每一个链表的最大值和最小值，然后比较对应的最值，根据最值进行链接。
如果最值就是数次链接，这道题只能这样遍历
实现代码
暴力匹配
- 编程的具体实现就是，两两匹配，然后将第三者元素加入其中。将问题拆解。
- 具体实现如下，头一次跑通了一个hard的题目，心情很不错，向这种拆解问题的思想，真的很好用呀！
/*** 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* mergeKLists(vector<ListNode*>& lists) {auto dummy = new ListNode(-1);auto temp = dummy;for (auto t:lists) {temp->next = mergeTwoLists(temp->next,t);return dummy->next;}return dummy->next;
}ListNode* mergeTwoLists(ListNode* aNode,ListNode* bNode){auto dummy = new ListNode(-1);auto temp = dummy;while(aNode && bNode){if (aNode->val < bNode->val){temp->next = aNode;aNode = aNode->next;}else{temp->next = bNode;bNode = bNode->next;}temp = temp->next;}temp->next = aNode == nullptr ? bNode:aNode;return dummy->next;
}};
参考实现
-
使用堆来找最小值，改变时间复杂度有k变成logk
-
stl中的优先队列是使用堆进行排序的，所以这里使用优先队列进行实现。
- 这里自定义优先队里的比较函数比较生僻，需要死记硬背
定义一个保存ListNode 的优先队列
- 这个必须要记住，而且必须加上对应的容器
struct Cmp{bool operator()(ListNode* a,ListNode* b){return a->val > b->val;}
};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode* ,vector<ListNode*>,Cmp> heap;
}
实现代码
- 下面这个题写的真简洁，学到了。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
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) {}
};struct Cmp{bool operator()(ListNode* a,ListNode* b){return a->val > b->val;}
};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode* ,vector<ListNode*>,Cmp> heap;auto dummy = new ListNode(-1),tail = dummy;for (auto t:lists) if(t) heap.push(t);while(heap.size()){auto t = heap.top();heap.pop();tail->next = t;tail = tail->next;if (t->next) heap.push(t->next);}return dummy->next;
}
总结
- 今天两道题基本上都写出来，但是效率都不高，学到了新的知识点，不错，明天继续。
