leetcode20-3-19


面试题09. 用两个栈实现队列

  • Used for test inserting images and codes.

  • 题解:
class CQueue {
public:
    stack Astack, Bstack;
    int size = 0;
    CQueue() {

    }

    void appendTail(int value) {
        Astack.push(value);
        size += 1;
    }

    int deleteHead() {
        if(size == 0) 
            return -1;
        while(!Astack.empty()) {
            Bstack.push(Astack.top());
            Astack.pop();
        }
        int ans = Bstack.top();
        Bstack.pop();
        while(!Bstack.empty()){
            Astack.push(Bstack.top());
            Bstack.pop();
        }
        size -= 1;
        return ans;
    }
}

2020.3.19 每日一题

  • 题解:
class Solution {
public:
    map counter;
    int res = 0;
    int longestPalindrome(string s) {
        for(int i = 0; i < s.size(); ++i) {
            if(counter.find(s.at(i)) == counter.end()) {
                counter.insert(map::value_type(s.at(i), 1));
            }else {
                counter[s.at(i)] += 1;
            }
        }
        for(auto iter = counter.begin(); iter != counter.end(); ++iter){
            if(iter->second % 2 == 1)
                res += 1;
        }
        return res == 0 ? s.size(): s.size() - res + 1 ;
    }
};

面试题10-I. 斐波那契数列

  • 题解
class Solution {
public:
    int res[110];
    int mod = 1e9+7;
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        res[1] = 1; 
        for(int i = 2; i <= n; ++i) {
            res[i] = (res[i-1] + res[i-2]) % mod; 
        }
        return res[n];
    }
};

面试题16. 数值的整数次方(快速幂)

  • 题解:
class Solution {
public: 
    double ans = 1, exponent = 1; 
    double myPow(double x, int n) {
        exponent = x;
        int sgnn = n;
        // note: 快速幂可以直接考虑指数为负数的情况,但是为负数时不能用移位运算。
        for(; sgnn; sgnn /= 2) { 
            if(sgnn & 1){
                ans = ans * exponent;
            } 
            exponent *= exponent;
        }
        return n > 0? ans: 1/ ans;
    }
};

面试题12. 矩阵中的路径

  • 复习 回溯法 深度优先搜索

class Solution {
private:
    int dir_x[4] = {0, 1, 0, -1};
    int dir_y[4] = {1, 0, -1, 0};
public:
    bool search(pair start, set> &record,vector> board, string word, int row, int col, int depth) {
        if(depth == word.size()) return true; 
        for(int i = 0; i < 4; ++i) {
            int new_x = start.first + dir_x[i];
            int new_y = start.second + dir_y[i];
            if(record.find(make_pair(new_x, new_y)) == record.end() && new_x >= 0 && new_y >= 0 && new_x < row && new_y < col && board.at(new_x).at(new_y) == word.at(depth)) {
                record.insert(make_pair(new_x, new_y));
                if(search(make_pair(new_x, new_y), record, board, word, row, col, depth+1))
                    return true;
                record.erase(make_pair(new_x, new_y));
            }
        }
        return false;
    }
    bool exist(vector>& board, string word) {
        if(board.size() == 0) return false;
        int row = board.size(), col = board.at(0).size();
        for(int i = 0; i < row; ++i) {
            for(int j = 0; j < col; ++j) {
                if(board.at(i).at(j) == word.at(0)) {
                    set> record;
                    record.insert(make_pair(i, j));
                    if(search(make_pair(i, j), record, board, word, row, col, 1))
                        return true;   
                }
            }
        }
        return false;
    }
};

文章作者: Jason Yuan
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Jason Yuan !
  目录