序号19~33)"/>
LeetCode Top100 Liked 题单(序号19~33)
19. Remove Nth Node From End of List
题意:给一个链表,删除从尾数起的第n个结点,返回头节点。
我的思路
指针到最后,数出来有多少个,之从前向后数,再删掉节点
代码 10ms Beats 16.06%
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode * p=head;int sz=0;while(p!=NULL){cout<<p->val<<endl;p=p->next; sz++; }p=head; int ta=sz-n;if(ta==0){head=p->next;delete p;p=NULL; return head;}for(int i=1;i<ta;i++)p=p->next;ListNode * q=p->next;p->next=q->next;delete q;p=q=NULL;return head;}
};
标答
双指针,类似追及问题的那种
第一个指针和第二个指针指向head,让第一个指针先跑n个结点,之后第一个指针和第二个指针一起跑,直到第一个指针跑到尾,这时第二个指针就是倒数第n个结点了,删除第二个指针指向的结点就可以了
注意第一个指针为空的情况单独讨论
代码 0ms Beats 100.00% 10.49mb Beats 99.85% 双指针
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode * fr=head;ListNode * se=head;for(int i=1;i<=n;i++) fr=fr->next;if(fr==NULL){head=head->next;delete se; se=NULL;return head;}while(fr->next!=NULL){fr=fr->next;se=se->next;}fr=se->next; se->next=fr->next;delete fr;fr=NULL;return head;}
};
20. Valid Parentheses
题意:括号合法问题
我的思路
用栈看看合不合法
代码 0ms Beats 100.00% 6.40mb Beats 36.00% 栈
好像空间复杂度没办法在当前的时间复杂度下优化了
class Solution {
public:bool isValid(string s) {stack<char> st;for(int i=0;i<s.size();i++){if(s[i]==')'){if(st.empty())return 0;char a=st.top();st.pop();if(a!='(')return 0;}else if (s[i]==']'){if(st.empty())return 0;char a=st.top();st.pop();if(a!='[')return 0;}else if (s[i]=='}'){if(st.empty())return 0;char a=st.top();st.pop();if(a!='{')return 0;}else st.push(s[i]);}if(st.empty())return 1;return 0;}
};
21. Merge Two Sorted Lists
题意:把两个有序链表合成一个有序链表
我的思路
就直接合成
代码 3ms Beats 96.79% 14.72mb Beats 53.74%
class Solution {
public:ListNode* mergeTwoLists(ListNode* l, ListNode* r) {ListNode* ans=NULL;ListNode* m=ans;if(l!=NULL&&r==NULL){return l;}else if(l==NULL&&r!=NULL){return r;}else if(l==NULL&&r==NULL){return ans;}while(l!=NULL&&r!=NULL){if((l->val)<=(r->val)){if (m==NULL){ans=m=l;l=l->next;}else {m->next=l;m=m->next;l=l->next;}}else{if (m==NULL){ans=m=r;r=r->next;}else {m->next=r;m=m->next;r=r->next;}}}if(l!=NULL){m->next=l;}else if(r!=NULL){m->next=r;}return ans;}
};
22. Generate Parentheses
题意:给出括号数,生成所有可能性
我的思路 递归
递归,当右括号数用完的时候跳出递归,同时时刻注意左括号数一定要 大于等于 右括号数
代码 0ms Beats 100.00% 11.26mb Beats 91.80%
class Solution {
public:void solve(int n,int l,int r,vector<string> &ans,string &output){if(r==n){ans.push_back(output);return;}if(l>=r&&l<n){output.push_back('(');solve(n,l+1,r,ans,output);output.pop_back();}if(l>r){output.push_back(')');solve(n,l,r+1,ans,output);output.pop_back();}}vector<string> generateParenthesis(int n) {if(n==0) return {};int l=0,r=0;vector<string> ans;string output;solve(n,l,r,ans,output);return ans;}
};
标答 动态规划
看了看答案 除了递归 还有动态规划的做法,有点像矩阵连乘的动态规划
将问题看成重叠子问题,假设dp[i]包含所有长度为2*i的可能性,例如dp[2]为{ (()) , ()() },那么dp[3]可以被写成:
(
+ dp[0] +)
+ dp[2] =()(()),
()()()
(
+ dp[1] +)
+ dp[1] =(())()
(
+ dp[2] +)
+ dp[0] =((())),
(()())
从上面可以看出,这是个重叠子问题结构(其个数为卡特兰数)
状态转移函数为dp[i] = "(" + dp[j] + ")" + dp[i-j-1]
接下来从数据结构的角度来说,答案在dp[n]中,dp[n]是vector<string>,所以dp的数据结构是vector<vector<string>>,dp[left] 和 dp[right] 也是vector<string>
之后就可以写代码了 注意初始化怎么写!!!
代码 0ms Beats 100.00% 7.36mb Beats 97.26%
class Solution {
public:vector<string> generateParenthesis(int n) {vector< vector<string> > dp(n+1);//开辟空间dp[0]={""};//初始化for(int i=1;i<=n;i++){//动态规划中的nfor(int j=0;j<i;j++){//是状态转移方程中括号里的内容 也就是第几个左for(int l=0;l<dp[j].size();l++){for(int r=0;r<dp[i-j-1].size();r++){string output;output+="(";output+=dp[j][l];output+=")";output+=dp[i-j-1][r];dp[i].push_back(output);}}}}return dp[n];}
};
23. Merge k Sorted Lists
题意:你有一个链表组,排序成一个链表
我的思路
递归,两个两个合并,有种归并排序的意思,但是代码能不能写出来就不知道了呜呜呜;
还有注意链表为空的情况!想了想之前有两个链表排序的例子,不知道能不能用上
但是递归完后,合成的链表放在哪里呢?那就新开一个vector ans,把之前的list clear一下(?)
每个拿到手的list,如果到手的就一个内容return;到手是1个以上,分成【l, r/2】【r/2+1,r】每个函数返回的应该是一个链表,ans把上面两个返回量收集一下,之后合并函数,最后返回一个链表
不会写!!感觉就差一点,但已知runtime error 没办法了;只好写个顺序版的了呜呜呜
代码 115ms Beats 28.75% 12.85 MB 98.25%
class Solution {
public:ListNode* mergeTwoLists(ListNode* l, ListNode* r) {ListNode* ans=NULL;ListNode* m=ans;if(l!=NULL&&r==NULL){return l;}else if(l==NULL&&r!=NULL){return r;}else if(l==NULL&&r==NULL){return ans;}while(l!=NULL&&r!=NULL){if((l->val)<=(r->val)){if (m==NULL){ans=m=l;l=l->next;}else {m->next=l;m=m->next;l=l->next;}}else{if (m==NULL){ans=m=r;r=r->next;}else {m->next=r;m=m->next;r=r->next;}}}if(l!=NULL){m->next=l;}else if(r!=NULL){m->next=r;}return ans;}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size()==0){return NULL;}else if (lists.size()==1){return lists[0];}for(int i = 1; i < lists.size(); i++){lists[0] = mergeTwoLists(lists[0],lists[i]);}return lists[0];}
};
标答 是对半 但不是递归
首先先把[0, n-1],[1, n-2],[2, n-3],[3, n-4]…[n/2-1,n-n/2] 配对合并,把链表放在前者里面,之后合法长度变为(n+1)/2;
以上流程循环,直到n<=1;
代码 12ms Beats 99.55% 12.94mb Beats 92.23% 对半非递归
class Solution {
public:ListNode* mergeTwoLists(ListNode* l, ListNode* r) {ListNode* ans=NULL;ListNode* m=ans;if(l!=NULL&&r==NULL){return l;}else if(l==NULL&&r!=NULL){return r;}else if(l==NULL&&r==NULL){return ans;}while(l!=NULL&&r!=NULL){if((l->val)<=(r->val)){if (m==NULL){ans=m=l;l=l->next;}else {m->next=l;m=m->next;l=l->next;}}else{if (m==NULL){ans=m=r;r=r->next;}else {m->next=r;m=m->next;r=r->next;}}}if(l!=NULL){m->next=l;}else if(r!=NULL){m->next=r;}return ans;}ListNode* mergeKLists(vector<ListNode*>& lists){int n=lists.size();if(lists.size()==0) return NULL;while(n>1){for(int i=0;i<n/2;i++)lists[i] = mergeTwoLists(lists[i], lists[n-i-1]);n = (n+1)/2;}return lists.front();}};
标答 使用递归合并的
mergeTwoLists函数和mergeKLists函数都差不多,重点在于sol是怎么实现的?
哦哦对照了一下,好像是在递归的时候传参传错了
正确的应该是:
int mid=l+(r-l)/2;
ListNode* a=sol(l,mid,lists);
ListNode* b=sol(mid+1,r,lists);我写的错误版本是:
ListNode* a=sol(l,r/2,lists);
ListNode* b=sol(r/2+1,r,lists);为什么我写的是错误的呢?
假设lists的内容是0 1 2 3
0 1 2 3
00 11 21 23
会出现以上错误,也就是说,当l=2,r=3的时候会出现错误!!所以要用mid来解决
代码 12ms Beats 99.55% 12.94mb Beats 92.23%
class Solution {
public:ListNode* mergeTwoLists(ListNode* l, ListNode* r) {ListNode* ans=NULL;ListNode* m=ans;if(l!=NULL&&r==NULL){return l;}else if(l==NULL&&r!=NULL){return r;}else if(l==NULL&&r==NULL){return ans;}while(l!=NULL&&r!=NULL){if((l->val)<=(r->val)){if (m==NULL){ans=m=l;l=l->next;}else {m->next=l;m=m->next;l=l->next;}}else{if (m==NULL){ans=m=r;r=r->next;}else {m->next=r;m=m->next;r=r->next;}}}if(l!=NULL){m->next=l;}else if(r!=NULL){m->next=r;}return ans;}ListNode* sol(int l,int r,vector<ListNode*>& lists){//二分if(l>=r)return lists[l];int mid=l+(r-l)/2;ListNode* a=sol(l,mid,lists);ListNode* b=sol(mid+1,r,lists);return mergeTwoLists(a,b);}ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.size()==0){return NULL;}return sol(0,lists.size()-1,lists);}
};
标答 优先队列
首先创建一个链表指针的优先队列q,接着把list的头指针都放进去,如果q是空的,那么就返回空;创建答案链表的头指针,头指针指向当前堆顶的最小元素,把堆顶元素弹出,如果答案指针之后还有元素,那么就把答案指针的next放回堆中;
创建一个用于答案链表插入的尾指针,尾指针指向堆顶元素,堆顶元素弹出,尾指针指向next元素;如果尾指针next不为空,并放回堆中,直到优先队列q空了,循环停止,这时答案链表也形成了。
代码 14ms Beats 99.29% 13.16mb Beats 82.20%
class Solution {
public:
struct compare {bool operator()(const ListNode* l, const ListNode* r) {return l->val > r->val;}
};
ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queuepriority_queue<ListNode *, vector<ListNode *>, compare> q;for(auto l : lists) {if(l) q.push(l);}if(q.empty()) return NULL;ListNode* result = q.top();q.pop();if(result->next) q.push(result->next);ListNode* tail = result; while(!q.empty()) {tail->next = q.top();q.pop();tail = tail->next;if(tail->next) q.push(tail->next);}return result;
}
};
!标答 直接输入的 但我应该学不会的
代码 5 ms Beats 99.82% 6.2 MB Beats 99.90%
int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);ofstream out("user.out");vector<char> buf;constexpr size_t buf_size = 1e4;buf.resize(buf_size);out.rdbuf()->pubsetbuf(buf.data(), buf_size);vector<int> result;result.reserve(1e4);string in;while (getline(cin, in)){result.clear();for (size_t i = 0, s = size(in); i < s; ++i){const char c = in[i];const bool is_num = (c >= '0') && (c <= '9') || (c == '-');if (!is_num){continue;}else{char* off;result.push_back(strtol(&in[i], &off, 10));i += (off - &in[i]);}}sort(begin(result), end(result));out << '[';for (size_t i = 0, s = size(result); i < s; ++i) {if (0 != i)out << ',';out << result[i];}out << "]\n";}
}
#define main _
class Solution{
public:ListNode *mergeKLists(vector<ListNode *> &lists) { return nullptr; }
};
24. Swap Nodes in Pairs
题意:给定一个链表,交换相邻结点,返回头指针(不修改结点的值)
我的思路
想不出来 先模拟;
如果是头指针的节点交换,那就要单独领出来,如果不是就单独一个函数,函数中输入一个指针,这个指针指向接下来的两个结点,在函数中创建两个指针,指向这两个结点,交换后指针向后跳两次
注意:在循环的时候注意指针指向
代码 Runtime0 ms Beats 100% Memory7.5 MB Beat 68.43%
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==NULL||head->next==NULL)return head;ListNode* p=head;//p是交换结点的前一个位置ListNode* q=head;//p是交换结点的前一个位置//head处理一下,1234的时候,head=q->next;//head指向2p->next=head->next;//p->next指向3,也就是1-3,2-3-4head->next=p;//2-1-3-4,head在2,p在1,q在1q=p->next;//head在2,p在1,q在3,4while(p!=NULL&&p->next!=NULL&&(p->next->next)!=NULL){p->next=q->next;//2-1-4 3-4q->next=p->next->next;//2-1-4 3p->next->next=q;//2-1-4-3 第二个结点指向第一个结点p=p->next->next;q=p->next;}return head;}
};
25. Reverse Nodes in k-Group
题意:给定一个链表,k个k个倒转
我的思路
死做?写一个倒转链表的函数,但我不会写倒转链表的函数,难道要遍历k次吗?
不会做
标答 不递归
首先创造一个新的结点dummy,dummy就是最后要返回的,这个新结点指向head,后面有5个指针,分别是before初始化为dummy,after初始化为head,curr,prev,nxt指针
初始化cursor为after,用来确定k个k个执行
curr是当前节点,prev是当前节点的前一个结点
在k个结点中nxt是当前节点的后一个节点,当前curr指针的下一个指向前一个结点prev,prev指针指向curr,curr指向next
在这个交换中,当前指针curr的next指向前一个结点prev,之后prev变成curr,curr变成nxt,下一个循环中nxt是curr的next,curr再次指向prev,下图是在循环中
在一次循环之后,curr是k个之外的结点向后到原链表的tail,prev之后是指向dummy的,dummy同时指向head
所以在循环之后,after的next指向curr,也就是说当前一段指向dummy的部分指向tail的方向了,同时连接上了两端链表,before的next指向prev,表示当前这一段的起始点和上一段连接;before代表上一段,after代表下一段,所以更新before和after
代码 Runtime12 ms Beats 91.52% Memory11.6 MB Beats 7.22%
ListNode* reverseKGroup(ListNode* head, int k) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* before = dummy;ListNode* after = head;ListNode* curr = nullptr;ListNode* prev = nullptr;ListNode* nxt = nullptr;while(true){ListNode* cursor = after;for(int i = 0; i < k; i++){if(cursor == nullptr) return dummy->next;cursor = cursor->next;}curr = after;prev = before;for(int i = 0; i < k; i++){nxt = curr->next;curr->next = prev;prev = curr;curr = nxt;}after->next = curr;before->next = prev;before = after;after = curr;}}
标答 递归
和上面相同的思路,就是把before和after两个指针用递归代替了,在递归中返回的是prev指针,prev指针代表这一段的开头,head->next代表这一段和上一段接上了,curr作为下一段的开头进入递归
没有dummy,最开始的部分,刚好prev指向NULL,所以head指向NULL刚好
(上面的图再利用,没有before和after)
代码 Runtime 8 ms Beats 98.54% Memory11.6 MB Beats 7.22%
ListNode* reverseKGroup(ListNode* head, int k) {ListNode* cursor = head;for(int i = 0; i < k; i++){if(cursor == nullptr) return head;cursor = cursor->next;}ListNode* curr = head;ListNode* prev = nullptr;ListNode* nxt = nullptr;for(int i = 0; i < k; i++){nxt = curr->next;curr->next = prev;prev = curr;curr = nxt;}head->next = reverseKGroup(curr, k);return prev;}
31. Next Permutation
题意:首先讲了排序是什么,next permutation是字典序下的排列顺序
注意:While the next permutation of arr = [3,2,1]
is [1,2,3]
because [3,2,1]
does not have a lexicographical larger rearrangement,所以是个循环
我的思路
从后向前找,找到第一个应该反过来的两个相邻的数字,把他们反过来,如果都符合的话,就返回sort的值;
出现了反例[1,3,2],应该为[2,1,3],但是输出了[3,1,2];不会做了
标答
已知序列是这样的arr
: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]
.
可以看到从后向前遍历,找到第一个左边小于右边的,记录下这个左边的这个小的数为l,例如[1,3,2],记下1这个位置,再次从右到左找第一个比这个数大的数,记录下这个数为k,交换l和k这两个数,之后l+1之后的位置全部倒着排
代码 Runtime 0 ms Beats 100% Memory12.2 MB Beats 20.53%
class Solution {
public:void nextPermutation(vector<int>& v) {int l=0,r=0,n=(int)v.size();for(l=n-2;l>=0;l--){if(v[l]<v[l+1]) break;}if(l<0)//重拍sort(v.begin(),v.end());else{for(r=n-1;r>l;r--)if(v[r]>v[l])break;swap(v[l],v[r]);reverse(v.begin()+l+1,v.end());}return;}
};
32. Longest Valid Parentheses
题意:最长的合法括号序列
我的思路
我记得是用动态规划做的,但是我不会做ummm,用区间dp?
不会做
标答 用栈
首先输入-1,为的是当栈为空的时候,用减法计算最长长度的时候可以计算正确;栈中输入的字符串序列的序号;如果是左括号(,那么把序号放到栈中;如果是右括号),并且栈中没有左括号了(栈的长度为-1,因为有个初始放进去的-1),那么把栈首设为当前序号;如果不是这样,说明栈中还有左括号,所以先把左括号的序号弹出,之后当前序号减去栈顶序号的差作比较,得到最终答案
代码 Runtime 3 ms Beats 84.77% Memory7.3 MB Beats 62.91%
class Solution {
public:int longestValidParentheses(string s) {stack<int> st;int ans=0;st.push(-1);for(int i=0;i<(int)s.size();i++){if(s[i]=='(')st.push(i); //第一种情况else{if(st.size()==1) st.top()=i; //第二种情况else{ 第三种情况st.pop();ans=max(ans,i-st.top());}}}return ans;}
};
标答 动态规划
和栈首先加入-1相同的原因,字符串的最前面加上右括号;longest[i]用来表示第i个字符之前(包括第i个字符)的合法括号序列的最长长度,初始化为0;
1. 如果当前第i个字符是左括号,合法括号序列不应该由左括号结尾,所以不合法,不用管
2. 如果当前第i个字符是右括号,同时第i-1个字符是左括号,那么longest[i]=longest[i-2]+2
3. 从2中可以推出,如果当前第i个字符是右括号,同时第i-longest[i-1] -1个字符是左括号,那么longest[i]=longest[ i-longest[i-1] -2]+longest[i-1] +2,【为什么是 i-longest[i-1] -2?因为是i-longest[i-1] -1的前一个字符】
例如(())为0 0 2 4
代码 Runtime 3 ms Beats 84.77% Memory7.4 MB Beats 18.16%
class Solution {
public:int longestValidParentheses(string s) {s=')'+s; int n=s.size(),ans=0;vector<int> dp(n,0);for(int i=1;i<n;i++){if(s[i]==')'&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-dp[i-1]-2]+dp[i-1]+2;ans=max(ans,dp[i]);}}return ans;}
};
33. Search in Rotated Sorted Array
题意:有一个升序排列的数组,被哨兵调整过一次,例如[0,1,2,4,5,6,7]
might be rotated at pivot index 3
and become [4,5,6,7,0,1,2];提问:给出一个数,返回这个数在序列中的位置
我的思路
找到哨兵,之后分别做两次二分查找,返回序号
注意:二分的时候while(l<=r),记得有等于号
代码 Runtime 0 ms Beats 100% Memory11.1 MB Beats 45.3%
class Solution {
public:int bins(int l,int r,vector<int>& nums, int tar){// 4 5 6while(l<=r){int mid=l+(r-l)/2; if(nums[mid]>tar)r=mid-1;else if (nums[mid]<tar)l=mid+1;else return mid;}return -1;}int search(vector<int>& nums, int target) {int p=0,n=(int)nums.size();for(p=0;p<n-1;p++) if(nums[p]>nums[p+1]) break;int lf=bins(0,p,nums,target),rf=bins(p+1,n-1,nums,target);return max(lf,rf);}
};
(神奇的是,就算是顺序查找也是0ms)
更多推荐
LeetCode Top100 Liked 题单(序号19~33)
发布评论