笔试强训每日一题(三)
字符串中找出连续最长的数字串
题目描述
输入一个字符串str，输出str中连续最长的数字串
输入描述：
个测试输入包含1个测试用例，一个字符串str，长度不超过255。
输出描述：
在一行内输出str中里连续最长的数字串
解题思路一
使用三个string对象，str对象用来读取输入的字符串，cur对象用来保存当前遍历位置的连续数字串，ret用来保存当前遍历位置最长的连续数字串，遍历str时，当遇到数字字符时，就将数字字符放入cur中，直到数字字符结束，此时需要判断cur的大小和ret的大小，如果cur的大，就更新ret，如果cur的小，就将cur清空，继续遍历。这里需要注意边界，当连续数字串在结尾时，i在等于size时也需要进去判断一次。
解题代码一
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str;
getline(cin,str);
string cur;
string ret;
for(int i = 0;i <= str.size();i++)
{
if(str[i]>='0' && str[i]<='9')
{
cur += str[i];
}
else
{
if(ret.size()<cur.size())
{
ret = cur;
}
else
{
cur.clear();
}
}
}
cout<<ret<<endl;
return 0;
}
解题思路二
通过遍历，找数字字符(>=‘0’<=‘9’)，找到起始下标i，用j来保存，然后判断连续的个数：while(str[i + 1] >= ‘0’&& str[i + 1] <= ‘9’)，_count++。循环结束，如果比当前最大连续的个数大更新count，更新起始下标，_count置0
解题代码二
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str;
getline(cin, str);
int count = 0;
int _count = 0;
int beginPos = 0;
for (size_t i = 0; i < str.size(); i++)
{
if (str[i] >= '0' && str[i] <= '9')
{
_count = 1;
int j = i;
while (str[i + 1] >= '0' && str[i + 1] <= '9')
{
_count++;
i++;
}
if (_count > count)
{
count = _count;
beginPos = j;
}
_count = 0;
}
}
for (int i = beginPos; i < beginPos + count; i++)
{
cout << str[i];
}
cout << endl;
return 0;
}
数组中出现次数超过一半的数字
题目描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
示例1
输入：
[1,2,3,2,2,2,5,4,2]
返回值：
2
示例2
输入：
[3,3,3,3,2,2,2]
返回值：
3
解题思路一：排序
- 首先对数组进行排序
- 找到中间的数字
- 再次遍历这个数组，计算这个数字出现了多少次
解题代码一
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
if(numbers.empty())
{
return 0;
}
sort(numbers.begin(),numbers.end());
int midNum = numbers[numbers.size()/2];
int count = 0;
for(int i =0;i<numbers.size();i++)
{
if(midNum == numbers[i])
{
count++;
}
}
if(count > numbers.size()/2)
{
return midNum;
}
return 0;
}
};
解题思路二：抵消
如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数
解题代码二
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
if(numbers.empty())
{
return 0;
}
int result = numbers[0];
int count = 1;
for(int i = 1;i<numbers.size();i++)
{
if(count != 0)
{
if(numbers[i] != result)
{
count--;
}
else
{
count++;
}
}
else
{
result = numbers[i];
count = 1;
}
}
count = 0;
for(int i = 0;i<numbers.size();i++)
{
if(result == numbers[i])
{
count++;
}
}
return count > numbers.size()/2? result:0;
}
};
|