头像

iltonmi

NEU-China




离线:4小时前



iltonmi
8小时前

经典双堆(题解看注释)

C++ 代码

class MedianFinder {
private:
    priority_queue<int, vector<int>, greater<int>> bigger;
    priority_queue<int> smaller;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        smaller.push(num);
        if(smaller.size() - bigger.size() == 1 && !bigger.empty()) {
            if(smaller.top() > bigger.top()) {
                int a = smaller.top(); smaller.pop();
                int b = bigger.top(); bigger.pop();
                smaller.push(b); bigger.push(a);
            }
        } else if(smaller.size() - bigger.size() == 2) {
            bigger.push(smaller.top()); smaller.pop();
        }
    }

    double findMedian() {
        if(smaller.size() - bigger.size() == 1) return smaller.top();
        else return (smaller.top() + bigger.top()) / 2.0;
    }
};

// if we use a array
// the insert may be slow, the worst o(N)
// the find is o(logN)

// we know that when insert a value in an sorted sequence
// the left part and the right part will change at most 1 value
// the value may be changed because the inserted value
// or the left part may be changed because swim up to the right part

// so lets seperate 2 parts and give a way to find the changed value
// when smaller part's value need to swim up to the bigger part
// we should find the biggest value of the smaller part
// so we need a big top heap
// and in order to know whether the value is bigger than 
// the smallest value of the bigger part
// we need a small top heap for bigger part

// so here the strategy is 2 heaps
// whenever the insertion occurs, we insert the value to the smaller part first.
// if the smaller part's size bigger than bigger part over 1, 
// we need to compare the top of 2 part, and swap if necessary
// the median will be the  top of smaller part
// if the smaller part's size bigger than bigger part over 2,
// move the top of smaller part to bigger part
// the median will be the median of 2 top

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */



iltonmi
9小时前
struct Node {
    bool is_end;
    Node *next[26];
    char val;
    Node() {
        memset(next, 0, sizeof(next));
        this->is_end = false;
    }
    Node(char val) : val(val) {
        memset(next, 0, sizeof(next));
        this->is_end = false;
    }
};

class Trie {
private:
    Node* root;
public:
    /** Initialize your data structure here. */
    Trie() {
        this->root = new Node();
    }

    ~Trie() {
        queue<Node*> q;
        q.push(this->root);
        while(q.size()) {
            auto p = q.front(); q.pop();
            for(int i = 0; i < 26; i++)
                if(p->next[i]) q.push(p->next[i]);
            delete p;
        }
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node *node = this->root;
        for(auto& ch : word) {
            if(!node->next[ch - 'a']) {
                node->next[ch - 'a'] = new Node(ch);
            }
            node = node->next[ch - 'a'];
        }
        node->is_end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node *node = this->root;
        for(auto& ch : word) {
            if(!node->next[ch - 'a']) return false;
            node = node->next[ch - 'a'];
        }
        return node->is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node *node = this->root;
        for(auto& ch : prefix) {
            if(!node->next[ch - 'a']) return false;
            node = node->next[ch - 'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */




iltonmi
23小时前

层次遍历

C++ 代码 O(N)

/**
 * 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:
    // level traversal, if level k has x non-null nodes
    // level k+1 must have 2 * x nodes, no matter non-null nodes' children are null or not
    // if an encoded node is null, it's child wont be endoded
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans = "[";
        queue<TreeNode*> q;
        auto dummy = new TreeNode(1001);
        if(root) q.push(root);
        while(q.size()) {
            int size = q.size();
            bool has_child = false;
            for(int i = 0; i < size; i++) {
                auto p = q.front(); q.pop();
                if(p->val == 1001)  ans += "null,";
                else {
                    ans += to_string(p->val);
                    ans += ',';
                    if(p->left) q.push(p->left), has_child = true;
                    else q.push(dummy);
                    if(p->right) q.push(p->right), has_child = true;
                    else q.push(dummy);
                }
            }
            if(!has_child) break;
        }
        if(ans.back() == ',') ans.pop_back();
        ans += ']';
        delete dummy;
        return ans;
    }

    int read_int(string& data, int& idx) {
        int val = 0;
        bool neg = false;
        if(data[idx] == '-') neg = true, idx++;
        for(char ch = data[idx]; isdigit(ch); ch = data[++idx]) 
            val = val * 10 + (ch - '0');
        if(neg) val *= -1;
        return val;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 2) return NULL;
        int idx = 1;
        TreeNode* ans = new TreeNode(read_int(data, idx));
        queue<TreeNode*> q;
        q.push(ans);
        while(q.size()) {
            int n = q.size();
            for(int i = 0; i < n; i++) {
                auto p = q.front(); q.pop();
                if(data[idx] == ',') idx++;
                if(data[idx] == 'n') idx += 4;
                else if(isdigit(data[idx]) || data[idx] == '-') 
                    p->left = new TreeNode(read_int(data, idx)), q.push(p->left);

                if(data[idx] == ',') idx++;
                if(data[idx] == 'n') idx += 4;
                else if(isdigit(data[idx]) || data[idx] == '-') 
                    p->right = new TreeNode(read_int(data, idx)), q.push(p->right);
            }
        }
        return ans;
    }
};


活动打卡代码 AcWing 71. 二叉树的深度

iltonmi
1天前
/**
 * 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:
    int ans;
    int treeDepth(TreeNode* root) {
        this->ans = 0;
        dfs(root, 0);
        return ans;
    }

    void dfs(TreeNode* root, int depth) {
        if(!root) return;
        depth++;
        ans = max(ans, depth);
        dfs(root->left, depth);
        dfs(root->right, depth);
    }
};



iltonmi
1天前

1. Morris遍历

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        TreeNode* prev = nullptr;
        while(root) {
            if(root->left) {
                auto t = root->left;
                while(t->right && t->right != root) t = t->right;
                if(t->right == nullptr) t->right = root, root = root->left;
                else {
                    ans = min(ans, root->val - t->val);
                    t->right = nullptr, prev = root, root = root->right;
                }
            } else {
                if(prev) ans = min(ans, root->val - prev->val);
                prev = root, root = root->right;
            }
        }
        return ans;
    }
};

2. 非递归中序遍历

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr;
        while(root || stk.size()) {
            if(root) {
                stk.push(root);
                root = root->left;
            } else {
                root = stk.top(); stk.pop();
                if(prev) ans = min(ans, root->val - prev->val);
                prev = root;
                root = root->right;
            }
        }
        return ans;
    }
};

3. 递归中序遍历

class Solution {
public:
    int ans;
    int minDiffInBST(TreeNode* root) {
        this->ans = INT_MAX;
        int pre = -1;
        dfs(root, pre);
        return ans;
    }

    void dfs(TreeNode* root, int& pre) {
        if(!root) return;
        dfs(root->left, pre);
        if(pre != -1) ans = min(ans, root->val - pre);
        pre = root->val;
        dfs(root->right, pre); 
    }
};



iltonmi
1天前
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        TreeNode* prev = nullptr;
        while(root) {
            if(root->left) {
                auto t = root->left;
                while(t->right && t->right != root) t = t->right;
                if(t->right == nullptr) t->right = root, root = root->left;
                else {
                    ans = min(ans, root->val - t->val);
                    t->right = nullptr, prev = root, root = root->right;
                }
            } else {
                if(prev) ans = min(ans, root->val - prev->val);
                prev = root, root = root->right;
            }
        }
        return ans;
    }
};


活动打卡代码 AcWing 35. 反转链表

iltonmi
1天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* res = NULL;
        while(head != NULL)
        {
            ListNode* tmp = head -> next;
            head -> next = res;
            res = head, head = tmp;
        }
        return res;
    }
};



iltonmi
2天前

DP O(N)

C++ 代码

class Solution {
public:
    int minSideJumps(vector<int>& obs) {
        int n = obs.size();
        int a[2][3] = {{1, 0, 1}, {-1, -1, -1}};
        // 遍历全部列
        for(int i = 1; i < n - 1; i++) {
            int mj = n;
            // 遍历全部行
            for(int j = 0; j < 3; j++) {
                // 有石头
                if(j == obs[i] - 1) a[i % 2][j] = n + 1;
                // 前面有石头,先标记一下
                else if(obs[i - 1] - 1 == j) a[i % 2][j] = -1;
                // 前面没石头,不用跳,记录最小值
                else a[i % 2][j] = a[(i-1)%2][j], mj = min(mj, a[i % 2][j]);
                // 如果这列,有2行可以通过直走到达,直走到A行再侧跳到B行,会不会相比直走到B行更优呢?
                // 不可能,因为同一列最多相差1,A的前一列比B的前一列侧跳数量小1。
                // 那么,直走到A后侧跳+1,和直走到B是一样的
            }
            // 侧跳到无法直达的地方
            for(int j = 0; j < 3; j++)
                if(a[i % 2][j] == -1) a[i % 2][j] = mj + 1;
        }
        int idx = (n-2)%2;
        return min(a[idx][0], min(a[idx][1], a[idx][2]));
    }
};


BFS最短路 O(N)

C++ 代码

class Solution {
public:
    // c = n + 1
    // id = i * c + j
    // id -> id + 1, for i in (0, 1, 2): i * c + id % c, if no stone...
    // 细节多,容易错
    int n;
    static const int maxn = (int)1.5e6 + 10;
    int dist[maxn];
    bool vis[maxn];
    int id(int i, int j) {
        return i * n + j;
    }

    int minSideJumps(vector<int>& obs) {
        this->n = obs.size();
        memset(dist, 0x3f, sizeof(dist));
        memset(vis, false, sizeof(vis));
        deque<int> q;
        q.push_back(id(1, 0));
        dist[id(1, 0)] = 0;
        while(q.size()) {
            auto t = q.front(); q.pop_front();
            if(vis[t]) continue;
            vis[t] = true;
            int x = t / n, y = t % n;
            if(y == n - 1) continue;
            if(obs[y + 1] - 1 != x) {
                int tid = t + 1;
                if(dist[t] < dist[tid])
                    dist[tid] = dist[t], q.push_front(tid);
            }
            for(int i = 0; i < 3; i++) {
                if(i == x || obs[y] - 1 == i) continue;
                int tid = id(i, y);
                if(dist[t] + 1 < dist[tid])
                    dist[tid] = dist[t] + 1, q.push_back(tid);
            }
        }
        int res = n + 1;
        for(int i = 0; i < 3; i++) res = min(res, dist[i * n + n - 1]);
        return res;
    }
};




iltonmi
2天前
class Solution {
public:
    int minSideJumps(vector<int>& obs) {
        int n = obs.size();
        int a[2][3] = {{1, 0, 1}, {-1, -1, -1}};
        for(int i = 1; i < n - 1; i++) {
            int mj = n;
            for(int j = 0; j < 3; j++) {
                if(j == obs[i] - 1) a[i % 2][j] = 0x3f3f3f3f;
                else if(obs[i - 1] - 1 == j || a[(i-1)%2][j] == -1) a[i % 2][j] = -1;
                else a[i % 2][j] = a[(i-1)%2][j], mj = min(mj, a[i % 2][j]);
            }
            for(int j = 0; j < 3; j++)
                if(a[i % 2][j] == -1) a[i % 2][j] = mj + 1;
        }
        int idx = (n-2)%2;
        return min(a[idx][0], min(a[idx][1], a[idx][2]));
    }
};


新鲜事 原文

iltonmi
2个月前
提前预祝大家新春快乐!hhhhh