算法(五)

二叉树遍历

只记录迭代写法。

前序遍历

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    while(root || !stk.empty())
    {
        while(root)
        {
            res.push_back(root->val);
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        root = root->right;
    }
    return res;
}

中序遍历

vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    vector<int> res;
    while (!stk.empty() || root) {
        while (root) {
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        res.push_back(root->val);
        stk.pop();
        root = root->right;
    }
    return res;
}

后序遍历

vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    vector<int> res;
    TreeNode* prev = nullptr;
    while (!stk.empty() || root) {
        while (root) {
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        if (root->right == nullptr || root->right == prev) {
            // 右子树已遍历
            res.push_back(root->val);
            prev = root;
            root = nullptr;
        } else {
            stk.push(root);
            root = root->right;
        }
    }
    return res;
}

字典树

class Trie {
private:
    class Node {
    public:
        Node* next[26];
        bool isVal;

        Node() : isVal(false) {
            for (int i=0; i<26; ++i) {
                next[i] = nullptr;
            }
        }
    };

public:
    Trie() : root(new Node()) {

    }
    
    void insert(string word) {
        Node* tmp = root;
        for (char ch : word) {
            if (tmp->next[ch - 'a'] == nullptr) {
                tmp->next[ch - 'a'] = new Node();
            }
            tmp = tmp->next[ch - 'a'];
        }
        tmp->isVal = true;
    }
    
    bool search(string word) {
        Node* tmp = root;
        for (char ch : word) {
            if (tmp->next[ch - 'a'] == nullptr) {
                return false;
            }
            tmp = tmp->next[ch - 'a'];
        }
        return tmp->isVal;
    }
    
    bool startsWith(string prefix) {
        Node* tmp = root;
        for (char ch : prefix) {
            if (tmp->next[ch - 'a'] == nullptr) {
                return false;
            }
            tmp = tmp->next[ch - 'a'];
        }
        return true;
    }

private:
    Node* root;
};

快速排序/快速选择

快排

void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) {
        return;
    }
    int first = l, last = r, pivot = nums[first];
    while (first < last) {
        while (first < last && nums[last] >= pivot) {
            -- last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] <= pivot) {
            ++ first;
        }
        nums[last] = nums[first];
    }
    nums[first] = pivot;
    quickSort(nums, l, first-1);
    quickSort(nums, first+1, r);
}

快速选择

// 快速选择算法，当 pivot 下标为 k 时结束
void quickSelect(vector<int>& arr, int k, int l, int r) {
    if (l >= r) {
        return;
    }
    int first = l, last = r;
    int pivot = arr[first];
    while (first < last) {
        while (first < last && arr[last] >= pivot) {
            -- last;
        }
        arr[first] = arr[last];
        while (first < last && arr[first] <= pivot) {
            ++ first;
        }
        arr[last] = arr[first];
    }
    arr[first] = pivot;
    if (first == k) {
        return;
    } else if (first < k) {
        quickSelect(arr, k, first+1, r);
    } else {
        quickSelect(arr, k, l, first-1);
    }
}

回溯之排列组合

无重复元素全排列

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    vector<bool> vis(nums.size(), false);
    backtrack(nums, res, vis, cur);
    return res;
}

void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<bool>& vis, vector<int>& cur) {
    if (cur.size() == nums.size()) {
        res.push_back(cur);
        return;
    }
    for (int i=0; i<nums.size(); ++i) {
        if (vis[i]) {
            continue;
        }
        vis[i] = true;
        cur.push_back(nums[i]);
        backtrack(nums, res, vis, cur);
        cur.pop_back();
        vis[i] = false;
    }
}

含重复元素全排列

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());              // 首先排序将重复的元素放在相邻的位置
    vector<vector<int>> res;
    vector<int> cur;
    vector<bool> vis(nums.size(), false);
    backtrack(nums, cur, res, vis);
    return res;
}

void backtrack(vector<int>& nums, vector<int>& cur, vector<vector<int>>& res, vector<bool>& vis) {
    if (cur.size() == nums.size()) {
        res.push_back(cur);
        return;
    }
    for (int i=0; i<nums.size(); ++i) {
        if (vis[i]) {
            continue;
        }
        // 关键点：保证选择第 i 个数时，重复的元素只被选中一次(只选重复元素的第一个数)
        if (i > 0 && nums[i] == nums[i-1] && !vis[i-1]) {
            continue;
        }
        vis[i] = true;
        cur.push_back(nums[i]);
        backtrack(nums, cur, res, vis);
        cur.pop_back();
        vis[i] = false;
    }
}

无重复元素组合

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(n, res, cur, k, 1);
    return res;
}

// 为了防止出现因元素顺序不同导致的重复，需要使用 start 参数来限制每次选择元素的起始位置
void backtrack(int n, vector<vector<int>>& res, vector<int>& cur, int k, int start) {
    if (cur.size() == k) {
        res.push_back(cur);
        return;
    }
    for (int i=start; i<=n; ++i) {
        cur.push_back(i);
        backtrack(n, res, cur, k, i + 1);
        cur.pop_back();
    }
}

组合总和(含重复元素)

// 题目是从 candidates 中挑选若干数使其和为 target
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(candidates, cur, res, 0, target);
    return res;
}

void backtrack(vector<int>& candidates, vector<int> cur, vector<vector<int>>& res, int start, int target) {
    if (target == 0) {
        res.push_back(cur);
        return;
    }
    if (target < 0) {
        return;
    }
    // 关键是去重
    for (int i=start; i<candidates.size(); ++i) {
        if (i > start && candidates[i] == candidates[i-1]) {
            continue;
        }
        cur.push_back(candidates[i]);
        backtrack(candidates, cur, res, i+1, target - candidates[i]);
        cur.pop_back();
    }
}

实现 LRU 缓存

class LRUCache {
public:
    struct Node {
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
        int key;
        int val;
        Node* prev;
        Node* next;
    };
public:
    LRUCache(int capacity) : head(nullptr), tail(nullptr), size(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!mp.count(key)) {
            return -1;
        }
        Node* node = mp[key];   
        makeRecent(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (mp.count(key)) {
            Node* node = mp[key];
            node->val = value;
            makeRecent(node);
        } else {
            if (mp.size() == size) {
                // 删除最后一个节点
                Node* last = tail->prev;
                tail->prev = last->prev;
                last->prev->next = tail;
                mp.erase(last->key);
                delete last;
            }
            Node* newNode = new Node(key, value);
            putInHead(newNode);
            mp[key] = newNode;
        }
    }

private:
    void makeRecent(Node* node) {
        // 移除除 node 节点，并将其放入头部
        node->prev->next = node->next;
        node->next->prev = node->prev;
        putInHead(node);
    }

    void putInHead(Node* node) {
        Node* next = head->next;
        head->next = node;
        node->prev = head;
        node->next = next;
        next->prev = node;
    }

private:
    unordered_map<int, Node*> mp;   // key -> address of Node
    Node* head;                     // head 和 tail 指向两个假节点
    Node* tail;
    int size;
};

实现线程池

#include <iostream>
#include <memory>
#include <mutex>
#include <condition_variable>
#include <deque>
#include <vector>
#include <thread>
#include <functional>

using namespace std;

class ThreadPool {
    public:
        typedef std::function<void()> Task;
        ThreadPool() : running_(false) {}
        ~ThreadPool() {
            if (running_) {
                stop();
            }
        }

        void start(int numThreads) {
            running_ = true;
            threads_.reserve(numThreads);
            for (int i=0; i<numThreads; ++i) {
                threads_.emplace_back(new std::thread(&ThreadPool::runInThread, this));
            }
        }
        void run(const Task& task) {
            if (threads_.empty()) {
                task();
            } else {
                std::lock_guard<std::mutex> lock(mutex_);
                tasks_.push_back(task);
                cv_.notify_one();
            }
        }
        void stop() {
            running_ = false;
            cv_.notify_all();
            for (auto& t : threads_) {
                t->join();
            }
        }
    private:
        void runInThread() {
            while (running_) {
                Task task;
                {
                    std::unique_lock<std::mutex> lock(mutex_);
                    while (tasks_.empty() && running_) {
                        cv_.wait(lock);
                    }
                    if (!running_) {
                        break;
                    }
                    task = tasks_.front();
                    tasks_.pop_front();
                }
                if (task) {
                    task();
                }
            }	
        }
        std::mutex mutex_;
        std::condition_variable cv_;
        std::vector<std::unique_ptr<std::thread>> threads_;
        std::deque<Task> tasks_;
        bool running_;
};