/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            int len = q.size();
            vector<int> level;
            for(int i = 0; i < len; i++)
            {
                auto t = q.front();
                q.pop();
                level.push_back(t -> val);
                if(t -> left)
                    q.push(t -> left);
                if(t -> right)
                    q.push(t -> right);
            }
            res.push_back(level);
        }
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root -> left, root -> right);
    }

    bool dfs(TreeNode* p, TreeNode* q){
        if(!q && !p) return true;
        if(!q || !p || p -> val != q -> val) return false;
        if( dfs(p -> left, q -> right) && dfs(p -> right, q -> left) )
            return true;
        else return false;
    }
};

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        s = " " + s;
        vector<int> f(n + 1);
        int x = s[1] - '0';
        if(x) f[1] = 1;
        else f[1] = 0;
        f[0] = 1;
        for(int i = 2; i <= n; i++){
            int t = s[i] - '0';
            int j = 10 * (s[i - 1] - '0') + t;
            if(t) f[i] += f[i - 1];
            if(j >= 10 && j <= 26) f[i] += f[i - 2];
        }
        return f[n];
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int k = m + n -1;
        int i = m - 1, j = n - 1;
        while(i >= 0 && j >= 0){
            if(nums1[i] < nums2[j]) nums1[k--] = nums2[j--];
            else nums1[k--] = nums1[i--];
        }
        while(j >= 0) nums1[k--] = nums2[j--]; 
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& h){
        int n = h.size();
        vector<int> ls(n), rs(n);
        stack<int> stk; 
        for(int i = 0; i < n; i++){
            while(!stk.empty() && h[stk.top()] >= h[i]) stk.pop();
            if(stk.size()) ls[i] = stk.top();
            else ls[i] = -1;
            stk.push(i);
        }
        stk = stack<int>();
        for(int i = n - 1; i >= 0; i--){
            while(!stk.empty() && h[stk.top()] >= h[i]) stk.pop();
            if(stk.size()) rs[i] = stk.top();
            else rs[i] = n;
            stk.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = max(res, h[i] * (rs[i] - ls[i] - 1));
        }
        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if(!matrix.size() || !matrix[0].size()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> f(n, vector<int>(m));

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if(matrix[i][j] == '1')
                {
                    if(!i) f[i][j] = 1;
                    else f[i][j] = 1 + f[i - 1][j];
                }
            } 
        int res = 0;
        for(int i = 0; i < n; i++) res = max(res, largestRectangleArea(f[i]));
        return res;
    }
};

time O(n * n)解法超时了

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1e9);
        f[n - 1] = 0;
        for(int i = n - 2; i >= 0; i--)
            for(int j = i + 1; j <= min(n - 1, i + nums[i]); j++)
            {
                f[i] = min(1 + f[j], f[i]);
            }
        return f[0];
    }
};

巧妙的time O(n)解法

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        for(int i = 1, j = 0; i < n; i++)
        {
            while(j + nums[j] < i)  j++;
            f[i] = f[j] + 1;
        }
        return f[n - 1];
    }
};

//快速幂
for(; k; k >>= 1){
if(k & 1) res = x;
x = x;
}

class Solution {
public:
    typedef long long LL;
    double myPow(double x, int n) {
        bool minus = n < 0;
        double res = 1.0;
        for(LL k = abs(LL(n)); k > 0; k >>= 1){
            if(k & 1) res *= x;
            x *= x;
        }
        if(minus)
            res = 1.0 / res;
        return res;
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size(), m = num2.size();
        vector<int> A, B;
        for(int i = n - 1; i >= 0; i--) A.push_back(num1[i] - '0');
        for(int i = m - 1; i >= 0; i--) B.push_back(num2[i] - '0');
        vector<int> tmp(n + m);

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                tmp[i + j] += A[i] * B[j];
        for(int i = 0, t = 0; i < tmp.size(); i++){
                t += tmp[i];
                tmp[i] = t % 10;
                t = t / 10;
        }
        int idx = tmp.size() - 1;
        while(idx && !tmp[idx])   idx--;
        string res;
        for(int i = idx; i >= 0; i--)   res += tmp[i] + '0';
        return res;
    }
};

O(n) time O(1) space
因为需要O(1)的空间复杂度，所以将符合[1, n]的数分别存入对应的数组下标[0, n - 1],对于n个数，能找到空缺的最小正整数，如果找不到，则返回n+1。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
                swap(nums[i], nums[nums[i] - 1]);
        }
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
};

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool dfs(int x, int y, int u, string& word, vector<vector<char>>& board){
        if(word[u] != board[x][y])  return false;
        if(u == word.size() - 1)  return true;
        char p = board[x][y];
        board[x][y] = '.';
        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < board.size() && b >= 0 && b < board[0].size() && board[a][b] != '.'){
                if(dfs(a, b, u + 1, word, board))  return true;
            }
        }
        board[x][y] = p;
        return false;
    }



    bool exist(vector<vector<char>>& board, string word) {
        int n = word.size();
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(dfs(i, j, 0, word, board))
                    return true;
        return false;
    }
};