leetcode中剑指offer的习题 C++语言实现（2）

面试题9 用两个栈实现队列

/*

在写的时候知道只要利用另外一个栈，将其原来栈中的内容反转就可以了，但是忘记了
stack_2中只要还有元素，那么它就可以出栈，因为它已经是元素的逆序了。

但是我在每次删除元素的时候都将stack1中的元素，变到stack2中，
出栈之后再压会stack1中，这样耗费的很多性能，真的是有够笨的
*/
// class CQueue {
// public:
//     CQueue() {

//     }
    
//     void appendTail(int value) {
//         stack_1.push(value);
//     }
    
//     int deleteHead() {
//         if(stack_1.size()==0){
//             return -1;
//         }
//         size_t size= stack_1.size()-1;
//         for(size_t i=0;i<size;++i){
//             stack_2.push(stack_1.top());
//             stack_1.pop(); 
//         }
//         int target = stack_1.top();
//         stack_1.pop();
//         // stack_2.pop();
//         size= stack_2.size();
//         for(size_t i=0;i<size;++i){
//             stack_1.push(stack_2.top());
//             stack_2.pop(); 
//         }
//         clear_stack2();
//         return target;
//     }
//     void clear_stack2(){
//         size_t size= stack_2.size();
//         for(size_t i=0;i<size;++i){
//             stack_2.pop();
//         }
//     }
// // private:
//     std::stack<int> stack_1;
//     std::stack<int> stack_2;
// };
class CQueue {
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        stack_1.push(value);
    }
    
    int deleteHead() {
        if(stack_1.size()==0&&stack_2.size()==0){
            return -1;
        }
        //优化，如果只有一个元素，那就不用移动了，直接pop就可以
        if(stack_1.size()==1&&stack_2.size()==0){
            int target = stack_1.top();
            stack_1.pop();
            return target;
        }
        if(stack_2.size()==0){
            size_t size= stack_1.size();
            for(size_t i=0;i<size;++i){
                stack_2.push(stack_1.top());
                stack_1.pop(); 
            }
        }
        int target = stack_2.top();
        stack_2.pop();
        return target;
    }
// private:
    std::stack<int> stack_1;
    std::stack<int> stack_2;
};

面试题10-1 斐波那契数列

class Solution {
/*
唯一需要记住的一点就是题目内容说的记得取模

因为int类型的表示范围可能不够
*/

public:
    int fib(int n) {
        if(n<=1){
            return n;
        }
        
        int fn_2 =0;
        int fn_1=1;
        int fn=0;
        for(int i=0;i<n-1;++i){
            fn=(fn_1+fn_2)%(1000000007);
            fn_2=fn_1;
            fn_1=fn;
        }
        return fn;
    }
};

面试题10-11 青蛙跳台阶问题

/*
这个题目的思路和斐波那契是一样的，但是需要找到隐藏的关系

首先在测试用例用认为如果n=0，需要return 1;

如果n>=1.可以知道n=1，只有一种方法，n=2只有两种方法，
n=3，则可以在n=1的基础上走两步，在n=2的基础上走一步，所以结果就是f(3)=f(2)+f(1)

目的思路和斐波那契是一样的，但是需要找到隐藏的关系

首先在测试用例用认为如果n=0，需要return 1;

如果n>=1.可以知道n=1，只有一种方法，n=2只有两种方法，
n=3，则可以在n=1的基础上走两步，在n=2的基础上走一步，所以结果就是f(3)=f(2)+f(1)

同样，对于n=4，则可以在n=3的基础上走一步，在n=2的基础上走两步
*/
class Solution {
public:
    int numWays(int n) {
        if(n==0){
            return 1;
        }
        if(n<=2){
            return n;
        }
        int fn_2 = 1;
        int fn_1 = 2;
        int fn = 0;
        for(int i=3;i<=n;++i){
            fn=(fn_1+fn_2)%1000000007;
            fn_2=fn_1;
            fn_1=fn;
        }
        return fn;
    }
};

面试题11 旋转数组中最小的数字

目前只实现了最简单的方法，待更新

class Solution {
public:
    int minArray(vector<int>& numbers) {
        //1.最简单的方法遍历
        // int min_val = numbers[0];
        // for(const auto & item :numbers){
        //     if(min_val>item){
        //         min_val=item;;
        //         break;
        //     }
        // }
        // return min_val;

    }
};