161. 说说哈希表的实现原理。你会如何设计一个哈希函数？

哈希表（Hash Table）是个高效的键值存储结构，核心想法是把键（key）通过一个哈希函数映射到一个数组的下标，然后把对应的值（value）存到那儿。查找时再用同样的哈希函数算一遍下标，直接去数组里取值。简单说，它把“查字典”变成了“查数组”。

怎么设计一个哈希函数？

162. 给定两个大文件，存储URL，如何找到相同的URL？

问题分析

解题思路

163. 解释vector中resize和reserve的作用，它们如何影响capacity和size？

size 和 capacity

resize的作用

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    std::cout << "初始 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 3, capacity: 3 (或更大，视实现)

    v.resize(5); // 变大，默认填充 0
    std::cout << "resize(5) 后 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 5, capacity: >=5 (可能 6、8)
    for (int x : v) std::cout << x << " "; // 1 2 3 0 0
    std::cout << "\n";

    v.resize(2); // 变小，砍掉后面
    std::cout << "resize(2) 后 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 2, capacity: 未变 (还是 >=5)
    for (int x : v) std::cout << x << " "; // 1 2
    std::cout << "\n";

    return 0;
}

reserve 的作用

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    std::cout << "初始 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 3, capacity: 3 (或更大)

    v.reserve(10); // 预留空间
    std::cout << "reserve(10) 后 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 3, capacity: >=10 (可能 10、16)
    for (int x : v) std::cout << x << " "; // 1 2 3
    std::cout << "\n";

    v.push_back(4); // 不重新分配
    std::cout << "push_back 后 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 4, capacity: 未变
    for (int x : v) std::cout << x << " "; // 1 2 3 4
    std::cout << "\n";

    v.reserve(6);
    std::cout << "reserve(6) 后 size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    // 输出: size: 4, capacity: 未变
    for (int x : v) std::cout << x << " "; // 1 2 3 4
    std::cout << "\n";
    return 0;
}

164. 算法题：判断一个完全二叉树是不是满二叉树

#include <iostream>
#include <queue>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 判断是否满二叉树
class Solution {
private:
    // 判断是否为满二叉树
    bool isFullBinaryTree(TreeNode* root) {
        if (!root) return true; // 空树认为是满的
        // 检查每个非叶子节点是否都有两个子节点
        if ((root->left && !root->right) || (!root->left && root->right)) {
            return false;
        }
        return isFullBinaryTree(root->left) && isFullBinaryTree(root->right);
    }

    // 判断是否为完全二叉树
    bool isCompleteBinaryTree(TreeNode* root) {
        if (!root) return true;  // 空树认为是完全二叉树
        std::queue<TreeNode*> q;
        q.push(root);
        bool isNullChild = false;  // 标记是否遇到过缺少子节点的情况
        
        // 1 2 3 4 nullptr nullptr nullptr nullptr nullptr

        // 1 2 3 nullptr nullptr 4 nullptr
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (!node) {
                isNullChild = true;  // 遇到空节点
            } else {
                // 如果已经遇到空节点，再出现非空节点，说明不是完全二叉树
                if (isNullChild) {
                    return false;
                }
                // 把左右子节点加入队列
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }

public:
    void checkBinaryTreeType(TreeNode* root) {
        if (isFullBinaryTree(root)) {
            std::cout << "This is a Full Binary Tree.\n";
        } else if (isCompleteBinaryTree(root)) {
            std::cout << "This is a Complete Binary Tree.\n";
        } else {
            std::cout << "This is neither a Full nor a Complete Binary Tree.\n";
        }
    }
};

// 构造树并测试
TreeNode* buildFullTree() {
    // 树：  1
    //      / \
    //     2   3
    //    / \  /\
    //   4   5 6 7
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    return root;
}

TreeNode* buildCompleteTree() {
    // 树：  1
    //      / \
    //     2   3
    //    /
    //   4
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    return root;
}

TreeNode* buildNeitherTree() {
    // 树：  1
    //      / \
    //     2   3
    //        / 
    //       4
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    return root;
}

void deleteTree(TreeNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;

    // 测试用例 1：满二叉树
    TreeNode* fullTree = buildFullTree();
    solution.checkBinaryTreeType(fullTree);  // 预期：满二叉树
    deleteTree(fullTree);

    // 测试用例 2：完全二叉树
    TreeNode* completeTree = buildCompleteTree();
    solution.checkBinaryTreeType(completeTree);  // 预期：完全二叉树
    deleteTree(completeTree);

    // 测试用例 3：既不是满二叉树也不是完全二叉树
    TreeNode* neitherTree = buildNeitherTree();
    solution.checkBinaryTreeType(neitherTree);  // 预期：既不是满二叉树也不是完全二叉树
    deleteTree(neitherTree);

    return 0;
}

165. 如何理解C++线程中的sleep和wait ？

sleep（线程休眠）

wait（线程等待）

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！