每日打卡

剑指offer【07-11】

07.重建二叉树

class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,
        int root,int start,int end){
        if(start>end)return nullptr;
        TreeNode *tree = new TreeNode(preorder[root]);
        int i= start;
        while(i<end&&preorder[root]!=inorder[i])i++;
        tree->left = build(preorder,inorder,root+1,start,i-1);
        tree->right = build(preorder,inorder,root+i-start+1,i+1,end);
        return tree;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder,inorder,0,0,preorder.size()-1);
    }

};

09.用两个栈实现队列

#include<stack>

using namespace std;

class CQueue {
    stack<int> st_1;
    stack<int> st_2;
public:
    CQueue() {

    }

    void appendTail(int value) {
        st_1.push(value);
    }

    int deleteHead() {
        if(!st_2.empty()){
            int tmp = st_2.top();
            st_2.pop();
            return tmp;
        }
        if(st_1.empty())return -1;
        while(!st_1.empty()){
            st_2.push(st_1.top());
            st_1.pop();
        }
        int val = st_2.top();
        st_2.pop();
        return val;
    }
};

010-1:斐波那契数列

class Solution {
public:
const int modi = 1000000007;
    int fib(int n) {
        int val_0 = 0;
        int val_1 = 1;
        if(n==0)return val_0;
        if(n==1)return val_1;
        int res ;
        for(int i = 2;i<=n;i++){
            res = (val_0+val_1)%modi;
            val_0 = val_1;
            val_1 = res;
        }
        return res%modi;
    }
};

11旋转数组的最小数字

需要注意的是一定是和右侧元素做比较，因为是升序旋转求最小值的，非对称

#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
       int minArray(vector<int> numbers) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            if (numbers[r] > numbers[mid]) {
                r = mid;
            } else if (numbers[r] < numbers[mid]) {
                l = mid + 1;
             //去重
            } else r--;
        }
        return numbers[l];
    }

};