프로그래머 면접 100 문제 2

제목: 스 택 의 데이터 구 조 를 정의 합 니 다. min 함 수 를 추가 하여 스 택 의 최소 요 소 를 얻 을 수 있 도록 해 야 합 니 다.요구 함수 min, push 및 pop 의 시간 복잡 도 는 모두 O (1) 입 니 다.
해법: 두 개의 vector 로 이 기능 을 실현 합 니 다. 하 나 는 스 택 에 있 는 실제 데 이 터 를 저장 하 는 데 사 용 됩 니 다. 하 나 는 스 택 에 들 어 갈 때마다 가장 작은 요 소 를 저장 하 는 데 사 용 됩 니 다.
우선 vector 의 함수 들 을 복습 합 니 다.
/ / vector 정의
std::vector c;
/ / 사용 가능 한 기능
c.clear()         용기 의 모든 데 이 터 를 제거 합 니 다.
c.empty()         용기 가 비어 있 는 지 아 닌 지 를 판단 하 다.
c.erase(pos)        pos 위치 데이터 삭제
c. erase (beg, end) 에서 [beg, end) 구간 의 데 이 터 를 삭제 합 니 다.
c.front()         첫 번 째 데 이 터 를 되 돌려 줍 니 다.
c.back()       마지막 데 이 터 를 되 돌려 줍 니 다.
c.insert(pos,elem) pos 위치 에 elem 복사 삽입
c.pop_back()     마지막 데 이 터 를 삭제 합 니 다.
c. push back (elem) 은 끝 에 데 이 터 를 추가 합 니 다.
c.resize(num)     이 용기 의 크기 를 다시 설정 합 니 다.
c.size()         용기 에 있 는 실제 데이터 의 개 수 를 되 돌려 줍 니 다.
c.begin()           용기 의 첫 번 째 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
c.end()             용기 의 마지막 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
코드 는 다음 과 같 습 니 다:


  
  
  
  
   
   
   
   // minstack.cpp : Defines the entry point for the console application.  
   
   
   
   //  
   
   
   
    
   
   
   
   #include "stdafx.h"  
   
   
   
   #include<iostream>  
   
   
   
   // vector          
   
   
   
   #include<vector>  
   
   
   
   //assert()          
   
   
   
   #include<assert.h>  
   
   
   
   using namespace std;  
   
   
   
    
   
   
   
   //       
   
   
   
   template<class T> class MinStack  
   
   
   
   {  
   
   
   
       public:  
   
   
   
           MinStack(){};//            
   
   
   
           ~MinStack(){};  
   
   
   
           T& top();  
   
   
   
           void push(const T value);  
   
   
   
           void pop();  
   
   
   
           T& min();  
   
   
   
       private:  
   
   
   
           vector<T> stackdata;  
   
   
   
           vector<T> minstackdata;  
   
   
   
    
   
   
   
   };  
   
   
   
   template<class T> T& MinStack<T>::top()  
   
   
   
   {  
   
   
   
       return stackdata.back();  
   
   
   
    
   
   
   
   }  
   
   
   
   template<class T> void MinStack<T>::push(const T value)  
   
   
   
   {  
   
   
   
       stackdata.push_back(value);  
   
   
   
       if(minstackdata.size()==0)  
   
   
   
           minstackdata.push_back(0);  
   
   
   
       else 
   
   
   
       {  
   
   
   
           if(value<stackdata[minstackdata.back()])  
   
   
   
               minstackdata.push_back(stackdata.size()-1);  
   
   
   
           else 
   
   
   
               minstackdata.push_back(minstackdata.back());  
   
   
   
       }  
   
   
   
    
   
   
   
   }  
   
   
   
   template<class T> void MinStack<T>::pop()  
   
   
   
   {  
   
   
   
       //  assert  
   
   
   
       assert(stackdata.size()>0);  
   
   
   
           assert(minstackdata.size()>0);  
   
   
   
           stackdata.pop_back();  
   
   
   
       minstackdata.pop_back();  
   
   
   
    
   
   
   
   }  
   
   
   
   template<class T> T& MinStack<T>::min()  
   
   
   
   {       assert(stackdata.size()>0);  
   
   
   
           assert(minstackdata.size()>0);  
   
   
   
    
   
   
   
       return stackdata[minstackdata.back()];  
   
   
   
   }  
   
   
   
   int main(int argc, char* argv[])  
   
   
   
   {  
   
   
   
       MinStack<int> a;//             
   
   
   
       a.push(3);  
   
   
   
       cout<<a.min()<<endl;  
   
   
   
       a.push(4);  
   
   
   
           cout<<a.min()<<endl;  
   
   
   
       a.push(2);  
   
   
   
           cout<<a.min()<<endl;  
   
   
   
       a.push(1);  
   
   
   
           cout<<a.min()<<endl;  
   
   
   
       cout<<a.top()<<endl;  
   
   
   
       a.pop();  
   
   
   
    
   
   
   
       return 0;  
   
   
   
   }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

양식 제출 후 제출 버튼 비활성화

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

프로그래머 면접 100 문제 2

좋은 웹페이지 즐겨찾기