当前位置: 首页 > news >正文

宝鸡网站建设抖音推广怎么收费

宝鸡网站建设,抖音推广怎么收费,门户网站 建设 如何写,镇江网友之家手机版19. Remove Nth Node From End of List 题意:给一个链表,删除从尾数起的第n个结点,返回头节点。 我的思路 指针到最后,数出来有多少个,之从前向后数,再删掉节点 代码 10ms Beats 16.06% class Solution…

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; }
};

http://www.dinnco.com/news/37287.html

相关文章:

  • 网站开发是做什么舆情监测分析系统
  • web网站开发字体百度搜索引擎关键词
  • 中国建设官方网站首页百度推广平台登陆
  • 政务公开网站建设整改方案成品视频直播软件推荐哪个好一点
  • 建个网站 做ib代理搜索引擎营销的原理是什么
  • 广西网络公司有几家北京seo全网营销
  • 营销型网站方案杭州网站搜索排名
  • 常宁网站定制企业网站的推广形式有
  • 宝安中心地铁站时间表河南郑州最新事件
  • 广州美容网站建设互联网去哪里学
  • 网站目录扫描建网站多少钱
  • 深圳聘请做网站人员如何在百度推广自己
  • 移动互联网营销的目标是( )南宁seo费用服务
  • 做ppt的模板的网站有哪些bt磁力狗
  • 莆田网站建设收费标准百度搜索引擎的网址是多少
  • p2p网上贷款网站建设方案.docxseog
  • 东莞php网站建设企业推广公司
  • 如何做网站经营性备案seo网络排名优化哪家好
  • 深圳高端网站制作价格如何搭建自己的网站
  • win10怎么做网站百度人气榜
  • 开发网站需要多少资金seo权重优化软件
  • 东莞做外贸网站公司龙岗seo网络推广
  • 天津武清做网站tjniu百度手机助手下载安卓
  • 长沙建站官网东莞外贸优化公司
  • 郑州网站推广¥做下拉去118cr优化分析
  • 广州网站开发技术百度手机助手
  • .网站开发工具dw口碑营销经典案例
  • 商务网站建设与维护论文上海seo网站优化软件
  • 注册安全工程师管理系统seo页面代码优化
  • 高要区住房和城乡建设局网站企业文化的重要性