LeetCode算法题中，如何利用容器解决问题？

在LeetCode算法题中，很多题目都涉及到数据结构和算法的知识。而在解决这些问题时，我们可以使用不同的容器来帮助我们更加高效地解决问题。本文将介绍在LeetCode算法题中如何利用容器解决问题，并通过实例演示代码。

1. 数组

数组是一种在LeetCode中非常常见的容器。它是一种线性数据结构，可以存储相同类型的元素。在LeetCode中，我们可以使用数组来解决一些查找、排序和统计等问题。

例如，LeetCode中的“两数之和”问题就可以使用数组来解决。我们可以使用一个数组来存储已经访问过的元素，然后再遍历一遍数组来查找是否存在另一个数与当前数的和等于目标值。

以下是使用数组解决“两数之和”问题的示例代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i) {
            int diff = target - nums[i];
            if(hash.find(diff) != hash.end()) {
                res.push_back(hash[diff]);
                res.push_back(i);
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};

2. 队列

队列是一种先进先出（FIFO）的数据结构。在LeetCode中，我们可以使用队列来解决一些广度优先搜索（BFS）问题。

例如，LeetCode中的“二叉树的层序遍历”问题就可以使用队列来解决。我们可以先将根节点入队列，然后依次取出队列中的节点，并将其左右子节点入队列，直到队列为空。

以下是使用队列解决“二叉树的层序遍历”问题的示例代码：

class Solution {
public:
    vector<vector<int>> levelOrder(Treenode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q{{root}};
        while(!q.empty()) {
            vector<int> level;
            for(int i = q.size(); i > 0; --i) {
                TreeNode* 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;
    }
};

3. 堆

堆是一种可以快速找到最大值或最小值的数据结构。在LeetCode中，我们可以使用堆来解决一些贪心算法和最短路径问题。

例如，LeetCode中的“最小的k个数”问题就可以使用堆来解决。我们可以使用一个最大堆来存储最小的k个数，每次遍历数组时，如果当前数比堆顶元素小，则弹出堆顶元素并将当前数入堆。

以下是使用堆解决“最小的k个数”问题的示例代码：

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> res;
        if(k == 0) return res;
        priority_queue<int> q;
        for(int i = 0; i < arr.size(); ++i) {
            if(q.size() < k) {
                q.push(arr[i]);
            } else if(arr[i] < q.top()) {
                q.pop();
                q.push(arr[i]);
            }
        }
        while(!q.empty()) {
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

4. 栈

栈是一种后进先出（LIFO）的数据结构。在LeetCode中，我们可以使用栈来解决一些逆波兰表达式和括号匹配等问题。

例如，LeetCode中的“有效的括号”问题就可以使用栈来解决。我们可以遍历字符串，如果当前字符是左括号，则入栈，如果当前字符是右括号，则判断栈顶元素是否与之匹配，如果匹配则弹出栈顶元素，否则返回false。

以下是使用栈解决“有效的括号”问题的示例代码：

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(char c : s) {
            if(c == "(" || c == "[" || c == "{") {
                stk.push(c);
            } else {
                if(stk.empty()) return false;
                char t = stk.top();
                stk.pop();
                if(c == ")" && t != "(") return false;
                if(c == "]" && t != "[") return false;
                if(c == "}" && t != "{") return false;
            }
        }
        return stk.empty();
    }
};

5. 哈希表

哈希表是一种可以快速查找和插入元素的数据结构。在LeetCode中，我们可以使用哈希表来解决一些查找和统计等问题。

例如，LeetCode中的“两数之和”问题（之前已经演示过了）就可以使用哈希表来解决。

以下是使用哈希表解决“两数之和”问题的示例代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i) {
            int diff = target - nums[i];
            if(hash.find(diff) != hash.end()) {
                res.push_back(hash[diff]);
                res.push_back(i);
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};

总结

在LeetCode算法题中，我们可以使用不同的容器来帮助我们更加高效地解决问题。本文介绍了数组、队列、堆、栈和哈希表等容器在LeetCode算法题中的应用，并通过实例演示了这些容器的使用方法。当我们遇到LeetCode算法题时，可以根据题目要求选择合适的容器来解决问题，从而更加高效地完成任务。