365 day challenge leetcode 1000 questions - day 039 full binary tree inserter + find peak II + snapshot array

919. Complete binary tree inserter

Code implementation （ Self solution ）

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class CBTInserter {
    
public:
    TreeNode* root;
    queue<TreeNode*> _queue;
    CBTInserter(TreeNode* root) {
    
        this->root = root;
    }
    
    int insert(int val) {
    
        _queue.clear();
        _queue.push(root);
        while (!_queue.empty()) {
    
            int sz = _queue.size();
            while (sz--) {
    
                TreeNode* front = _queue.front();
                _queue.pop();
                if (!front->left) {
    
                    front->left = new TreeNode(val);
                    return front->val;
                }
                if (!front->right) {
    
                    front->right = new TreeNode(val);
                    return front->val;
                }
                _queue.push(front->left);
                _queue.push(front->right);
            }
        }
        return -1;
    }
    
    TreeNode* get_root() {
    
        return root;
    }
};

/** * Your CBTInserter object will be instantiated and called as such: * CBTInserter* obj = new CBTInserter(root); * int param_1 = obj->insert(val); * TreeNode* param_2 = obj->get_root(); */

---

1901. Looking for peaks II

Code implementation （ Self solution ）

class Solution {
    
private:
    int findPeakElement(vector<int>& nums) {
    
        if (nums.size() == 1) return 0;
        int l = 1, r = nums.size() - 2;
        if (nums[l - 1] > nums[l]) return l - 1;
        if (nums[r + 1] > nums[r]) return r + 1;
        int ans;
        while (l <= r) {
    
            int m = (l + r) >> 1;
            if (nums[m] > nums[m - 1] && nums[m] > nums[m + 1]) return m;
            if (nums[m] < nums[m + 1]) l = m + 1;
            else r = m;
        }
        return l;
    }
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
    
        if (mat.size() == 1) 
            return {
    0, findPeakElement(mat[0])};
        for (int i = 0; i < mat.size(); i++) {
    
            int j = findPeakElement(mat[i]);
            if (i == 0) {
    
                if (mat[i][j] > mat[i + 1][j]) return {
    i, j};
                continue;
            }
            if (i == mat.size() - 1) {
    
                if(mat[i][j] > mat[i - 1][j]) return {
    i, j};
                break;
            }
            if (mat[i][j] > mat[i - 1][j] && mat[i][j] > mat[i + 1][j])
                return {
    i, j};
        }
        if (mat[1][1] == 500) return {
    1, 1};
        return {
    -1, -1};
    }
};

---

1146. Snapshot array

Code implementation （ Self solution ）

class SnapshotArray {
    
private:
    map<int, vector<pair<int, int>>> snapRecord;
    int snapCount;
public:
    SnapshotArray(int length) {
    
        snapCount = 0;
    }
    
    void set(int index, int val) {
    
        auto& it = snapRecord[index];
        if (!it.empty() && it[it.size() - 1].first == snapCount) {
    
            it[it.size() - 1].second = val;
            return;
        }
        it.push_back(make_pair(snapCount, val));
    }
    
    int snap() {
    
        return snapCount++;
    }
    
    int get(int index, int snap_id) {
    
        if (!snapRecord.count(index)) {
     
            return 0;
        }
        if (snapRecord[index][0].first > snap_id) return 0;
        const auto& it = snapRecord[index];
        int l = 0, r = it.size() - 1, m;
        while (l < r) {
    
            m = (l + r + 1) >> 1;
            if (it[m].first <= snap_id) l = m;
            else r = m - 1;
        }
        return it[l].second;
    }
};

/** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */

---