文章目录
- 引言
- 新作
- 括号生成
- 个人实现
- 实现时遇到的问题
- 实现代码
- 参考思路
- 实现代码
- 合并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;
}
总结
- 今天两道题基本上都写出来，但是效率都不高，学到了新的知识点，不错，明天继续。
