Stack / heap / queue question brushing (Part 2)

One 、 Median in data stream

Solution 1 : Violence law

class Solution {
    
public: 
    vector<int>data;
    void Insert(int num) {
    
        data.push_back(num);
    }

    double GetMedian() {
    
        sort(data.begin(),data.end());
        int n=data.size();
        if(n&1)// It's odd 
            return (double)data[n>>1];// Return intermediate value 
        else// Even number returns the sum and division of the middle two numbers 2
            return (double)(data[n>>1]+data[(n-1)>>1])/2;
    }
};

Time complexity :O(n${\log }_2$n), Quick sort
Spatial complexity :O(n)

Solution 2 : Insertion sort

Use insert sort when saving values , Drain after saving
lower_bound( begin,end,num)： From array begin Position to end-1 Position bisection finds the first greater than or equal to num The number of , Find the address that returns the number , Returns if it does not exist end. Subtract the starting address from the returned address begin, Find the subscript of the number in the array .

class Solution {
    
public:
    #define transfer static_cast<double>
    vector<int>data;
    void Insert(int num) {
    
        if(data.empty())
            data.push_back(num);
        else{
    
            auto it=lower_bound(data.begin(),data.end(),num);
            data.insert(it,num);
        }
    }

    double GetMedian() {
     
        int n=data.size();
        if(n&1)
            return transfer(data[n>>1]);
        else
            return transfer(data[n>>1]+data[(n-1)>>1])/2;
    }

};

Time complexity ：Insert() by O(n), That is, binary search O(${\log }_2$n) And moving data O(n), GetMedian() by O(1)
Spatial complexity ：O(n)

Solution 3 : Pile up

• Use two stack values , Big top stacking small value , Top Max , Small top stacking big value , The top is the smallest , The median is at the top of two piles
• * The odd number is specified to take the top value of the large top stack , Take the average value of the top of two piles even , Even two stacks should be the same size , Odd numbers are different , One more pile on the top
• The data of the large top heap cannot be less than that of the small top heap , Need to detect , And balance the size of the two piles

class Solution {
    
public:
    #define transfer static_cast<double>
    // Big pile top , The element value is small 
    priority_queue<int> min; 
    // Small cap pile , The element values are larger than the big top pile 
    priority_queue<int, vector<int>, greater<int>> max;
    // Maintain two heaps , Just take the top of two piles 
    void Insert(int num) {
           
        // First add a smaller part  
        min.push(num);
        // Take out the maximum value of the smaller part , Into a larger part of 
        max.push(min.top());  
        min.pop();
        // Balance the number of two heaps 
        if(min.size() < max.size()){
      
            min.push(max.top());
            max.pop();
        }        
    }
    double GetMedian() {
    
        return min.size()>max.size()?transfer(min.top()):transfer(min.top()+max.top())/2;
        // An odd number 
        if(min.size() > max.size())  
            return (double)min.top();
        else
            // Even number 
            return (double)(min.top() + max.top()) / 2; 
    }
};

Time complexity ：Insert function )O(${\log }_2$n), Maintain the complexity of the heap ,GetMedian function O(1）, Direct access
Spatial complexity ：O(n), Space for two heaps , Although there are two , But a heap is the most n/2

Two 、 Expression evaluation

Solution 1 : Stack + recursive

• Realize priority processing with stack , encounter + Normal stack ,- Take the opposite number and put it on the stack ,* Multiply the ejected element in the stack by the last element and then put it on the stack , Finally, add all the elements in the stack
• The processing of parentheses treats the operations in parentheses as subproblems with the help of recursion

class Solution {
    
public:
    vector<int>fun(string str,int index)
    {
    
        stack<int>s;
        int num=0,i;
        char op='+';
        for(i=index;i<str.length();i++)
        {
    
            // Number of characters 
            if(isdigit(str[i]))
            {
    
                num=num*10+str[i]-'0';
                if(i!=str.length()-1)
                    continue;
            }
            // encounter '(' when , Treat the whole bracket as a number 
            if(str[i]=='(')
            {
    
                vector<int>tmp=fun(str,i+1);
                num=tmp[0];
                i=tmp[1];
                if(i!=str.length()-1)
                    continue;
            }
            switch(op)
            {
    
                case '+':
                    s.push(num);
                    break;
                case '-':
                    s.push(-num);
                    break;
                case '*':// Calculate the multiplication sign first 
                    int ret=s.top();
                    s.pop();
                    s.push(ret*num);
                    break;
            }
            num=0;
            if(str[i]==')')
                break;
            else
                op=str[i];
        }
        int sum=0;
        while(!s.empty())
        {
    
            sum+=s.top();
            s.pop();
        }
        return vector<int>{
    sum,i};// The first element of the array is the operation value , The second is string length 
    }
    int solve(string s) {
    
        // write code here
        return fun(s,0)[0];
    }
};

Time complexity ：O(n),n Is the length of a string , It is equivalent to traversing all elements of the string
Spatial complexity ：O(n), Space of auxiliary stack and recursive stack

Solution 2 : Double stack method

• Use two stacks , op Save operator ,val Save values
  Traverse the string , If the character is a number , Then put consecutive numbers into val Stack , Operators are stored in op Stack
• If ops The stack is empty or the current character is ’(; perhaps op The element at the top of the stack is ’(', The stack ;
• If the current character is ’’, because ’‘ Priority ratio +,- high , So move back one bit and directly connect the subsequent consecutive numbers with val Multiply the elements at the top of the stack and put them in val
• If the current character is ’)',+,-, At the end of , Will val Two numbers in op Stack top operation , Put the results on the stack ;
  here , The top element of the stack may be +,-,*
• If the current character is ’);, It will be ’(' Also pop up the stack , If it's the end , Then exit the loop directly .
  val The top element of the stack is the final result .

class Solution {
    
public:
    int solve(string s) {
    
        stack<int> val;
        stack<char> op;
        for(int i=0; i<=s.length();){
    
            if(isdigit(s[i]))
                val.push(to_int(s, i));
            else if(op.empty()||op.top()=='('||s[i]=='(')
                op.push(s[i++]);
            else if(s[i]=='*'){
    
                int v1=val.top(),v2=to_int(s, ++i);
                val.pop();
                val.push(v1*v2);
            }
            else{
    
                int v2=val.top();
                val.pop();
                int v1=val.top();
                val.pop();
                if(op.top()=='+')
                    val.push(v1+v2);
                else if(op.top()=='-')
                    val.push(v1-v2);
                else if(op.top()=='*')
                    val.push(v1*v2);
                op.pop();
                if(s[i]==')'){
    
                    op.pop();
                    i++;
                }
                else if(i==s.length())
                    break;
            }
        }
        return val.top();
    }
    int to_int(string s,int &i){
    
        int tmp=0;
        while(isdigit(s[i]))
            tmp=tmp*10+s[i++]-'0';
        return tmp;
    }
};

Time complexity :O(n), Traversal string
Spatial complexity :O(n), The space of the two stacks adds up to the string length n