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

支付招聘网站套餐费用怎么做帐新网站如何做推广软文

支付招聘网站套餐费用怎么做帐,新网站如何做推广软文,国外优秀创意的个人网页设计欣赏,深圳外贸公司集中在哪些地方一.最长回文子串 1.题目&#xff1a;给定一个仅包含小写字母的字符串&#xff0c;求它的最长回文子串的长度。 最长回文子串__牛客网 2.算法原理&#xff1a; <1>动态规划算法:O(n^2),O(n^2) 具有通性&#xff0c;凡涉及回文子串的问题都可利用此法解决 知识储备&am…

一.最长回文子串

1.题目:给定一个仅包含小写字母的字符串,求它的最长回文子串的长度。

最长回文子串__牛客网

2.算法原理:

<1>动态规划算法:O(n^2),O(n^2) 具有通性,凡涉及回文子串的问题都可利用此法解决

知识储备:对与只有一个字符的字符串一定是回文串;对于有两个字符的字符串当两个字符相等时,才是回文串;当字符串的长度大于2时,若该字符串是回文串则去掉首尾两个字符后仍是回文串。

创建一个n*n的dp表,统计[i,j]区间段内的子串是否是回文串。当i<j时,dp[i][j]=0;当i==j时,dp[i][j]==1;当j-i==1时,判断str[i]和str[j]是否相等;当j-i>1时,若str[i]==str[j],则判断dp[i+1][j-1]是否为1,若str[i]!=str[j],则dp[i][j]=0

注意:要是按照常规思维,利用字符串的长度两次循环的话,会出现判断dp[3][6]需要去看dp[4][5]的情形,而dp[4][5]还没有进行计算的情况,所以我们可以利用首尾字符间的距离作为第一层循环的自变量,从而避免访问还未判断位置的信息的情况


int getLongestPalindrome(string A) {int n=A.size();vector<vector<int>> r(n,vector<int>(n));int back;//创建矩阵在r中保存当前r[i][j]是否是回文子串,判定的依据为r[i+1][j-1]==1且A[i]==A[j]for(int d=0;d<n;d++)//d:两者间的间距{for(int i=0;i<n-d;i++){int j=i+d;if(d==0)r[i][j]=1;else if(d==1)r[i][j]=(A[i]==A[j]);elser[i][j]=(A[i]==A[j]&&r[i+1][j-1]==1);if(r[i][j]&&d+1>ret.size()){back=j-i+1;}}}return back;

<2>马拉车算法:O(n),O(n)  不具有通性,只能用于解决这一种问题

此种算法思想小编暂时还没有掌握,后续若是掌握了会在评论区介绍的,有兴趣的宝子可以自己尝试理解,要是学会了记得教小编一下

<3>中心扩展算法:O(n^2),O(1)

遍历字符串,以拿到的字符str[i]为回文子串的中心字符,然后利用两个指针left和right以str[i]为中心,分别向左右扩展,直至不符合str[left]!=str[right],更新回文子串的最长长度。

注意:因为回文子串的长度可以是奇数也可以是偶数,所以对于初始时left的赋值应该考虑left=i,和left=i-1两种情况

#include <iostream>
#include<string>
using namespace std;int main() {string str;cin>>str;//中心扩展算法int left=0,right=0,ret=0;for(int i=0;i<str.size();i++){//长度为奇数的回文串left=i-1;right=i+1;while(left>=0 && right<str.size() && str[left]==str[right]){left--;right++;}ret=max(ret,right-left-1);//长度为偶数的回文串left=i;right=i+1;while(left>=0 && right<str.size() && str[left]==str[right]){left--;right++;}ret=max(ret,right-left-1);}cout<<ret<<endl;return 0;
}

二.游游的水果大礼包(二元一次方程组的求解问题)

1.题目: 游游的水果大礼包__牛客网

游游有n个苹果,m个桃子。她可以把2个苹果和1个桃子组成价值a元的一号水果大礼包,也可以把1个苹果和2个桃子组成价值b元的二号水果大礼包。游游想知道,自己最多能组成多少价值总和的大礼包?

2.算法原理:

利用枚举法从0开始假设可以组成x个1号大礼包,x的取值范围为[0,min(n/2,m)],定下来1号礼包的个数,那么可以计算出2号礼包的个数,y=min(n-2*x,(m-x)/2),则礼包总值为a*x+b*y,在枚举过程中更新总值的最大值

3.代码实现:

#include <iostream>
using namespace std;int main() {long long n,m,a,b;cin>>n>>m>>a>>b;long long ret=0;for(long long x=0;x<=min(n/2,m);x++)//枚举1号礼包个数{long long y=min((n-2*x),(m-x)/2);//计算2号礼包个数ret=max(ret,a*x+b*y);}cout<<ret<<endl;return 0;
}

注:有些题目的数字类型要特别注意,否则可能会让测试结果就卡在70%左右非常恶心,建议对于可能取大值的数据一律定义long long类型,一了百了

三.两个链表的第一个公共节点

1.题目:两个链表的第一个公共结点_牛客题霸_牛客网

输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。

2.算法原理:

<1>常规思路:统计出两个链表的长度,让长的链表先走两链表差值步,再和另一链表开始一起向后走,当第一次碰到相同的节点时,则该节点就是第一个公共节点

注意:有可能在长链表走链表差步时,就已经达到第一个公共节点处,此情况不要忘记考虑

<2>等量关系:让cur1,cur2分别指向两链表的头节点,当cur1走到空时,让cur1指向另一个链表的头节点;同理,当cur2走到空时,让cur2指向另一个链表的头节点,让cur1==cur2时,所指向的节点就是第一个公共节点。

class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if(pHead1==nullptr || pHead2==nullptr) return nullptr;ListNode* cur1=pHead1;ListNode* cur2=pHead2;while(cur1!=cur2){cur1=cur1==nullptr?pHead2:cur1->next;cur2=cur2==nullptr?pHead1:cur2->next;}return cur1;}
};

小小感慨一下,果然普通人是比不上天才的,这种思路绝对不是我这种普通人能想出来的🥲

四.Mari和shiny(多状态的动态规划问题)

1.题目:在一个字符串中找出"shy"的子序列

注:子串和子序列是不一样的,子串要求在原字符串中连续出现,但是子序列不要求连续出现,吐槽一句真恶心

2.算法原理:

利用数组统计在该字符前有多少个满足条件的选项。

创建shy数组统计该字符前有多少个“sh",若是str[i]=='y',则shy[i]=shy[i-1]+sh[i];若不等,则shy[i]=shy[i-1]

创建sh数组统计该字符前有多少个“s",若是str[i]=='h',则sh[i]=sh[i-1]+s[i];若不等,则sh[i]=sh[i-1]

创建s数组统计该字符前有多少个“s",若是str[i]=='s‘,则s[i]=s[i-1]+1;若不等,则s[i]=s[i-1]

注:可对本题做空间优化,即不创建数组直接利用三个变量统计

若str[i]=='s',则s++;若str[i]=='h',则h+=s;若str[i]=='y',则y+=h;

3.代码实现:

#include<iostream>
#include<string>
using namespace std;int main()
{string str;cin >> str;int s = 0, h = 0, y = 0;for (int i = 0; i < str.size(); i++){if (str[i] == 's') s++;else if (str[i] == 'h') h += s;else if (str[i] == 'y') y += h;}cout << y << endl;return 0;
}

zhu 

http://www.yayakq.cn/news/341709/

相关文章:

  • 东莞网站关键排名网站建设深圳哪家好
  • 类似猪八戒的网站建设ping一下新浪网站怎么做
  • 静安郑州阳网站建设自己做的网站怎么连接域名
  • 网店运营推广网站建设通网站的信息是哪里来的
  • 网站要懂代码网站媒体给房开做内容推广
  • 搭建网站是seo的入门南通网络科技有限公司
  • wordpress怎么屏蔽蜘蛛宝塔优化wordpress
  • 网站推广软文是什么江苏电力建设网站
  • 手机网站怎么优化关键词newsletter wordpress
  • 自己可以做英文网站么淘宝指数网站
  • 网站软件开发招聘wordpress 可以商业
  • 商城网站栏目昆明信息港官网
  • 网站开发前端技术宁波网站建设公司
  • 怎么创建网站 优帮云开福区城乡建设局门户网站
  • 学网站建设与管理好吗企业网站制作一般多少钱
  • 用.net编写网站电商主图设计网站
  • 外贸网站推广方法网页版梦幻西游礼品码
  • 公司网站建设需推广怎么做资源网站
  • 花都网站设计柚子皮 wordpress
  • 商城网站建设专业公司wordpress在线阅读pdf
  • 龙岗企业网站建设我们一起做网站
  • 怎么样让客户做网站和小程序wordpress进入仪表盘
  • 昭通建设局网站浙江网站搭建
  • 回收手表的网站wordpress主题 产品展示
  • 网站建设最新资讯seo关键词挖掘
  • 电子商务网站建设与管理a卷答案河北seo网络推广
  • 网站改版解决方案网站数据展示
  • 咨询聊城网站建设受欢迎的邢台做网站
  • 巢湖市网站建设优化wordpress 企业小程序
  • 广州网站设计素材如何使用阿里云建站