剑指 Offer 编程题 gaunthan Posted on Feb 15 2017 ? Programming Exercises ? ? C++ ? ## 用两个栈实现队列 见[《两栈实现队列》](http://gaunthan.leanote.com/post/%E4%B8%A4%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97)。 ## 旋转数组的最小数字 ```cpp #include <iostream> #include <stdexcept> #include <vector> #include <cassert> using namespace std; template<typename Vector> typename Vector::value_type FindMinOfRotateArray__( const Vector& data, int left, int right) { typedef typename Vector::value_type T; if(left == right) return data[right]; // 迭代实现 while(left < right) { if(left == right-1) return min(data[left], data[right]); int mid = left + (right - left)/2; if(data[mid] > data[left]) left = mid + 1; else if(data[mid] < data[left]) right = mid; else if(data[mid] > data[right]) left = mid + 1; else if(data[mid] < data[right]) right = mid; else { // data[left] == data[mid] == data[right] const T leftMin = FindMinOfRotateArray__(data, left, mid-1); const T rightMin = FindMinOfRotateArray__(data, mid+1, right); return min(leftMin, rightMin); } } return data[left]; } template<typename Vector> typename Vector::value_type FindMinOfRotateArray( const Vector& data, int left, int right) { if(data.empty() || left < 0 || right < 0 || left > right) throw invalid_argument("Invalid argument"); return FindMinOfRotateArray__(data, left, right); } int main() { vector<int> vec; try { FindMinOfRotateArray(vec, 0, vec.size() - 1); }catch(const exception& e) { cout << "Success catch: " << e.what() << endl; } vec = {1, 2}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 1); vec = {1}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 1); vec = {2, 1}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 1); vec = {4, 1, 2}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 1); vec = {4, 5, 6, 1}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 1); vec = {4, 4, 4}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 4); vec = {1, 0, 1, 1, 1}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 0); vec = {1, 1, 1, 0, 1}; assert(FindMinOfRotateArray(vec, 0, vec.size() - 1) == 0); cout << "Testing Passed.\n"; return 0; } ``` ## 检查栈的入栈与出栈序列 ```cpp #ifndef PUSH_AND_POP_SEQ_CHECKER_H #define PUSH_AND_POP_SEQ_CHECKER_H #include <vector> #include <stack> #include <algorithm> #include <stdexcept> struct InvalidPopSeqException : public std::exception { const char* what() const throw() { return "invalid pop sequence."; } }; template<typename T> struct PushAndPopSeqChecker { PushAndPopSeqChecker(const std::vector<T>& pushSequence) : pushSeq(pushSequence) { } bool operator()(const std::vector<T>& popSeq) const { std::stack<T>().swap(helper); auto pushSeqIter = pushSeq.cbegin(); for(auto elem : popSeq) { auto elemIter = std::find(pushSeqIter, pushSeq.cend(), elem); if(elemIter != pushSeq.cend()) { // 元素未入栈 // elem之前的元素都需要先入栈 PushBound(helper, pushSeqIter, elemIter); pushSeqIter = ++elemIter; // 直接跳过该元素,作为出栈处理 }else { // 元素应该在辅助栈里 if(helper.empty() || helper.top() != elem) // 出栈序列非法 throw InvalidPopSeqException(); helper.pop(); } } return true; } private: std::vector<T> pushSeq; mutable std::stack<T> helper; template<typename Stack, typename FwdIter> static void PushBound(Stack& stack, FwdIter first, FwdIter last) { while(first != last) { stack.push(*first++); } } }; #endif // PUSH_AND_POP_SEQ_CHECKER_H ``` 赏 Wechat Pay Alipay 图搜索算法:深度优先查找 用单个队列实现栈