8/2复习剑指offer

1.用两个栈实现队列
思路：利用两个栈，一个栈用来进数据，当出数据时，看另一个栈是否为空，如果为空，就压入栈1的所有元素，然后出栈顶，不为空直接出栈顶。

class CQueue {
public:
    stack<int> s1,s2;
public:
    CQueue() {
        while (!s1.empty()) {
            s1.pop();
        }
        while (!s2.empty()) {
            s2.pop();
        }
    }//清空里面的元素

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

    int deleteHead() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }//如果s2是空的，就压入s1的元素
        if(s2.empty())
        {
            return -1;
        }
        //否则，正常pop()栈顶即可
        int a=s2.top();
        s2.pop();
        return a;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

2.旋转数组的最小数字
思路：注意不会溢出的二分写法，和右比，返回左。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;//这种不会溢出
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            }//45123
            else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            }//23451
            else {
                high -= 1;
            }
        }
        return numbers[low];
    }
};

3.矩阵中的路径

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size()==0||board[0].size()==0||word.length()==0) return false;
        int rows=board.size(),cols=board[0].size();
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(judge(i,j,rows,cols,board,word,0))
                {
                    return true;
                }
            }
        }
        return false;
    }
    bool judge(int row,int col,int rows,int cols,vector<vector<char>>& board, string word,int k)
    {
        if (row >= rows || row < 0 || col >= cols || col < 0 || board[row][col] != word[k]) 
            return false;//非法直接返回false
        if (k == word.length() - 1)
            return true;//遍历到字符串末尾返回true
        char temp = board[row][col];
        board[row][col] = '/';//用一个不可能存在的字符来代替visited数组
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int q = 0; q < 4; q ++ ) {
            int m = row + dx[q], n = col + dy[q];
            if (judge(m,n,rows,cols,board,word,k+1)) return true;
        }
        board[row][col] = temp;//如果没有出现true，就返回原值
        return false;
    }
};