剑指 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
```