温州seo网站推广,wordpress 新建模板文件,视频剪辑怎么自学,来个网站学了一坤时Linux#xff0c;赶紧来俩道题目放松放松。 T1#xff1a;在字符串中找出连续最长的数字串 链接#xff1a;在字符串中找出连续最长的数字串__牛客网
输入一个字符串#xff0c;返回其最长的数字子串#xff0c;以及其长度。若有多个最长的数字子串#xff0c…学了一坤时Linux赶紧来俩道题目放松放松。 T1在字符串中找出连续最长的数字串 链接在字符串中找出连续最长的数字串__牛客网
输入一个字符串返回其最长的数字子串以及其长度。若有多个最长的数字子串则将它们全部输出按原字符串的相对位置
本题含有多组样例输入。
数据范围字符串长度 1≤n≤200 保证每组输入都至少含有一个数字 这题复刻了一道经典dp【力扣53.最大子数组和】,下面是dp的代码 #includeiostream
#includestring
#includevector
using namespace std;
string s;
int main()
{while(cins){int ans0;int ns.size();int cnt0;string temp;string res;vectorintdp(n);if(s[0]0s[0]9) {dp[0]1;temps[0];}for(int i1;in;i){if(s[i]0s[i]9){dp[i]dp[i-1]1;temps[i];}else{dp[i]0;temp;}if(dp[i]ans){restemp;}else if(dp[i]ans){restemp;}ansmax(ans,dp[i]);}coutres,ansendl;}return 0;
}其实dp数组可以用一个变量代替代码会更简洁。 #includeiostream
#includestring
using namespace std;
string s;
int main()
{while(cins){int ans0;int ns.size();int cnt0;string temp;string res;for(int i0;in;i){if(s[i]0s[i]9){cnt;temps[i];}else{cnt0;temp;}if(cntans){restemp;}else if(cntans){restemp;}ansmax(ans,cnt);}coutres,ansendl;}return 0;
} T2数组中出现次数超过一半的数字
链接数组中出现次数超过一半的数字__牛客网
给一个长度为 n 的数组数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次超过数组长度的一半因此输出2。
数据范围n≤50000数组中元素的值 0≤val≤100000
要求空间复杂度O(1)时间复杂度 O(n) emmm,开始看道这题容易想到map一遍但这题的空间复杂度要求是O(1)。 想了用位运算不过那些是跟奇偶性有关。 如何数组中存在众数那众数的数量一定大于数组长度的一半。 我们可以用一种消去的思想比较相邻的俩个数如果不相等就消去。最坏的情况下每次都消去一个众数和一个非众数如果众数存在那最后留下的一定就是众数。 class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param numbers int整型vector * return int整型*/int MoreThanHalfNum_Solution(vectorint numbers) {// write code hereint cnt0;int ans0;int nnumbers.size();for(auto x:numbers){if(!cnt){cnt1;ansx;}else{if(ansx)cnt;else cnt--;}}cnt0;for(auto x:numbers){if(xans)cnt;}if(cntn/2)return ans;return 0;}
};
