[programming compulsory training 3] find the longest consecutive number string in the string + the number that appears more than half of the times in the array

1. Find the longest consecutive number string in the string -> link

【 Their thinking 】：
Traversal string , Use cur To record a continuous string of numbers , If you encounter non numeric characters , It means that a continuous number string ends , Then compare the number string with the previous number string , If it's longer , Then update the longer number string to res.

Code implementation ：

#include<iostream>
#include<string>
using namespace std;

int main()
{
    
    string s, ret, cur;
    cin >> s;
    for (int i = 0; i <= s.length(); i++)
    {
    
        if (s[i] >= '0' && s[i] <= '9')
        {
    
            cur += s[i];
        }
        else {
    
            //  Find a longer string , Then update the string 
            if (ret.size() < cur.size())
            {
    
                ret = cur;
            }
            else
            {
    
                cur.clear();
            }

        }
    }
    cout << ret;
    return 0;
}

2. A number that appears more than half the times in an array -> link

【 Their thinking 1】：

Train of thought ： After array sorting , If the qualified number exists , Then it must be the number in the middle of the array . Although this method is easy to understand , But because it involves fast platoon sort, Its time complexity is O(NlogN) Not optimal .

Code implementation ：

class Solution {
    
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    
    if(numbers.empty()) // Sentenced to empty 
        return 0;
    sort(numbers.begin(),numbers.end());// Sort 
    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;
        
        
    }
};

【 Their thinking 2】：

The number of ： The number that occurs more than half the length of the array

If two numbers are not equal , Just eliminate these two numbers , In the worst case , Eliminate one mode and one non mode at a time , So if there are modes , The last number left must be the mode .

Code implementation ：

class Solution {
    
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
    
        if (numbers.empty()) return 0;
        //  Traverse each element , And record the number of times ; If it's the same as the previous element , Then the number of times plus 1, Otherwise, the times will be reduced 1
        int result = numbers[0];
        int times = 1; //  frequency 
        for (int i = 1; i < numbers.size(); ++i)
        {
    
            if (times != 0)
            {
    
                if (numbers[i] == result)
                {
    
                    ++times;
                } 
                else
                {
    
                --times;
                }
            }
                else
                {
    
                result = numbers[i];
                times = 1;
                }
        } 
            //  Judge result Whether the conditions are met , That is, the number of occurrences is greater than half of the length of the array 
                    times = 0;
                for (int i = 0; i < numbers.size(); ++i)
                {
    
                    if (numbers[i] == result) ++times;
                } 
                    return(times > numbers.size() / 2) ? result : 0;
    }
};