网站开发要用哪些语言开发,网站建设违法行为,网站gif横幅广告怎么做,诸暨市住房和城乡建设局网站一.最长回文子串
1.题目#xff1a;给定一个仅包含小写字母的字符串#xff0c;求它的最长回文子串的长度。
最长回文子串__牛客网
2.算法原理#xff1a;
1动态规划算法:O(n^2),O(n^2) 具有通性#xff0c;凡涉及回文子串的问题都可利用此法解决
知识储备给定一个仅包含小写字母的字符串求它的最长回文子串的长度。
最长回文子串__牛客网
2.算法原理
1动态规划算法:O(n^2),O(n^2) 具有通性凡涉及回文子串的问题都可利用此法解决
知识储备对与只有一个字符的字符串一定是回文串对于有两个字符的字符串当两个字符相等时才是回文串当字符串的长度大于2时若该字符串是回文串则去掉首尾两个字符后仍是回文串。
创建一个n*n的dp表统计[i,j]区间段内的子串是否是回文串。当ij时dp[i][j]0;当ij时dp[i][j]1;当j-i1时判断str[i]和str[j]是否相等当j-i1时若str[i]str[j],则判断dp[i1][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 nA.size();vectorvectorint r(n,vectorint(n));int back;//创建矩阵在r中保存当前r[i][j]是否是回文子串判定的依据为r[i1][j-1]1且A[i]A[j]for(int d0;dn;d)//d两者间的间距{for(int i0;in-d;i){int jid;if(d0)r[i][j]1;else if(d1)r[i][j](A[i]A[j]);elser[i][j](A[i]A[j]r[i1][j-1]1);if(r[i][j]d1ret.size()){backj-i1;}}}return back;
2马拉车算法O(n),O(n) 不具有通性只能用于解决这一种问题
此种算法思想小编暂时还没有掌握后续若是掌握了会在评论区介绍的有兴趣的宝子可以自己尝试理解要是学会了记得教小编一下
3中心扩展算法O(n^2),O(1)
遍历字符串以拿到的字符str[i]为回文子串的中心字符然后利用两个指针left和right以str[i]为中心分别向左右扩展直至不符合str[left]!str[right]更新回文子串的最长长度。
注意因为回文子串的长度可以是奇数也可以是偶数所以对于初始时left的赋值应该考虑lefti,和lefti-1两种情况
#include iostream
#includestring
using namespace std;int main() {string str;cinstr;//中心扩展算法int left0,right0,ret0;for(int i0;istr.size();i){//长度为奇数的回文串lefti-1;righti1;while(left0 rightstr.size() str[left]str[right]){left--;right;}retmax(ret,right-left-1);//长度为偶数的回文串lefti;righti1;while(left0 rightstr.size() str[left]str[right]){left--;right;}retmax(ret,right-left-1);}coutretendl;return 0;
}
二.游游的水果大礼包二元一次方程组的求解问题
1.题目 游游的水果大礼包__牛客网 游游有n个苹果m个桃子。她可以把2个苹果和1个桃子组成价值a元的一号水果大礼包也可以把1个苹果和2个桃子组成价值b元的二号水果大礼包。游游想知道自己最多能组成多少价值总和的大礼包
2.算法原理
利用枚举法从0开始假设可以组成x个1号大礼包x的取值范围为[0,min(n/2,m)],定下来1号礼包的个数那么可以计算出2号礼包的个数ymin(n-2*x,(m-x)/2)则礼包总值为a*xb*y在枚举过程中更新总值的最大值
3.代码实现
#include iostream
using namespace std;int main() {long long n,m,a,b;cinnmab;long long ret0;for(long long x0;xmin(n/2,m);x)//枚举1号礼包个数{long long ymin((n-2*x),(m-x)/2);//计算2号礼包个数retmax(ret,a*xb*y);}coutretendl;return 0;
}注有些题目的数字类型要特别注意否则可能会让测试结果就卡在70%左右非常恶心建议对于可能取大值的数据一律定义long long类型一了百了
三.两个链表的第一个公共节点
1.题目两个链表的第一个公共结点_牛客题霸_牛客网
输入两个无环的单向链表找出它们的第一个公共结点如果没有公共节点则返回空。
2.算法原理
1常规思路统计出两个链表的长度让长的链表先走两链表差值步再和另一链表开始一起向后走当第一次碰到相同的节点时则该节点就是第一个公共节点
注意有可能在长链表走链表差步时就已经达到第一个公共节点处此情况不要忘记考虑
2等量关系让cur1,cur2分别指向两链表的头节点当cur1走到空时让cur1指向另一个链表的头节点同理当cur2走到空时让cur2指向另一个链表的头节点让cur1cur2时所指向的节点就是第一个公共节点。 class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {if(pHead1nullptr || pHead2nullptr) return nullptr;ListNode* cur1pHead1;ListNode* cur2pHead2;while(cur1!cur2){cur1cur1nullptr?pHead2:cur1-next;cur2cur2nullptr?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,则hs;若str[i]y则yh;
3.代码实现
#includeiostream
#includestring
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
