演算法訓練營
- 字串中找到連續最長的數字串
- 陣列中出現次數超過一半的數字
字串中找到連續最長的數字串
解題思路：
遍歷字串，用cur去記錄連續的數字串，如果遇到的不是數字字符，則表示一個連續的數字串結束了，則將數字串跟之前的數字串比較，如果更長，則更新更長的數字串更新到res，
int main()
{
string str, res, cur;
cin >> str;
for (int i = 0; i <= str.length(); i++)
{
if (str[i] >= '0' && str[i] <= 9)
{
cur += str[i];
}
else
{
if (res.size() < cur.size())
{
res = cur;
}
else
cur.clear();
}
}
cout << res;
return 0;
}
陣列中出現次數超過一半的數字
解題思路1：
陣列排序過后，如果符合條件的數存在，則一定是陣列中間的那個數，但時間復雜度是o（NlogN）.
class solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
if (numbers.empty()) return 0;
sort(numbers.begin(), numbers.end());
int middle = numbers[numbers.size() / 2];
int count = 0;
for (int i = 0; i < numbers.size(); ++i)
{
if (numbers[i] == middle) ++count;
}
return (count > numbers.size() / 2) ? middle : 0;
}
};
解題思路2：
利用眾數的思想，如果兩個數不相等，就消去這兩個數，最壞情況下，每次消去一個眾數和一個非眾數，如果存在眾數，那么最后留下的數肯定是眾數，
class solution {
public:
int MoreThanHalfNum_solution(vector<int> numbers)
{
if (numbers.empty()) return 0;
int result = numbers[0];
int times = 1;
for (int i = 1; i < numbers.size(); ++i)
{
if (times != 0)
{
if (numbers[i] == result)
{
++times;
}
else
{
--times;
}
}
else
{
result = numbers[i]
;
}
}
times = 0;
for (int i = 0; i < numbers.size(); ++i)
{
if (numbers[i] == result) ++times;
}
return (times > numbers.size() / 2) ? result : 0;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/321323.html
標籤：其他
下一篇：常量變數的反復橫跳