Maxw的小站

Maxw学习记录

发表于 更新于 分类于

530.搜索树的最小绝对差

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了 尝试自己写遍历，虽然有很多莫名其妙的值，但是居然写对了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    TreeNode* maxNode = nullptr;
    int absd  = -1;
    int getMinimumDifference(TreeNode* root) {
        if(!root)return -1;
        int left = -1;
        int right = -1;
        if(root->left)left = getMinimumDifference(root->left);
        if(maxNode != nullptr){
            int maxd = root->val - maxNode->val;
            if(absd == -1){
                absd = maxd;
            }else if(maxd < absd){
                absd = maxd;
            }
        }
        maxNode = root;
        if(root->right)right = getMinimumDifference(root->right);
        return absd;
    }
};

501.二叉搜索树中的众数

如果我自己写，就遍历数组取最大值好了。看题解发现可以中序遍历，按这种方法找： 弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。 而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。 如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

注意计数和判定最大值要分开，并且确定好是判定当前节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    TreeNode* pre = nullptr;
    int cnt = 0;
    int cntMax = 0;
    void traverse(vector<int> &res, TreeNode* root){
        if(!root)return;
        traverse(res, root->left);
        if(!pre){
            cnt++;
        }else if(pre->val == root->val){
            cnt++;
        }else{ //  if(pre->val != root->val)
            cnt = 1;
        }
        if(cnt == cntMax){
            res.push_back(root->val);
        }else if(cnt > cntMax){
            res.clear();
            cntMax = cnt;
            res.push_back(root->val);
        }
        pre = root;
        traverse(res, root->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        traverse(res, root);
        return res;
    }
};

236. 二叉树的最近公共祖先

我的解法就是暴力解，找到p和q的路径并比较路径中不同的节点，前一个就是公共最小祖先了 看了题解发现还可以回溯：

遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。 那么二叉树如何可以自底向上查找呢？ 回溯啊，二叉树回溯的过程就是从底到上。 后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。

搞清楚什么时候返回root也很重要 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q)return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != nullptr && right != nullptr)return root;
        if(left == nullptr)return right;
        return left;
    }
};

发表于 分类于

654.最大二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* maxTree(vector<int>& nums, int l, int r){
        int maxNum = 0;
        int maxI = l;
        for(int i = l;i <= r;i++){
            if(nums[i] > maxNum){
                maxNum = nums[i];
                maxI = i;
            }
        }
        TreeNode* root = new TreeNode(maxNum);
        if(maxI > l)root->left = maxTree(nums, l, maxI-1);
        if(maxI < r)root->right = maxTree(nums, maxI +1, r);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* res = maxTree(nums, 0, nums.size()-1);
        return res;
    }
};

617.合并二叉树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2)return nullptr;
        if(!root1)return root2;
        if(!root2)return root1;
        TreeNode* node = new TreeNode(root1->val + root2->val);
        node->left = mergeTrees(root1->left, root2->left);
        node->right = mergeTrees(root1->right, root2->right);
        return node;
    }
};

700.二叉搜索树中的搜索

不可以在root->val == val之前判定左右子树是否存在，会在搜索到叶子节点时提前结束 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root)return NULL;
        // cout<<"cur val"<<root->val<<endl;
        // if(!root->left && !root->right)return NULL; // --- 不可以在这里判定
        if(root->val == val){
            return root;
        }else if(root->val > val){
            return searchBST(root->left, val);
        }else{
            return searchBST(root->right, val);
        }
    }
};

98.验证二叉搜索树

还是掉坑里了，其实验证二叉树中序遍历是否递增就好。当然也要注意最小值如何取 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* pre = NULL;
    bool isValidBST(TreeNode* root) {
        if(!root)return true;
        bool left = isValidBST(root->left);
        if(pre != NULL && pre->val >= root->val)return false;
        pre = root;
        bool right = isValidBST(root->right);
        return left && right;
    }
};

发表于 更新于 分类于

513. 找树左下角的值

迭代法

此题用迭代法做比较简单，掌握层序遍历即可

⚠️ 注意不可直接写：for (int i = 0; i < layer.size(); i++)

layer.size() 在循环过程中是动态变化的，因为在循环中同时 pop() 和 push()，这会让 size() 的结果发生变化。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> layer;
        layer.push(root);
        int val;
        while(!layer.empty()){
            int sz = layer.size();
            for(int i = 0 ; i< sz;i++){
                TreeNode* cur = layer.front();
                layer.pop();
                if(cur->left)layer.push(cur->left);
                if(cur->right)layer.push(cur->right);
                if(i == 0)val = cur->val;
            }
        }
        return val;
    }
};

递归法

全局找值用全局变量即可，先从左子树开始递归，返回的就是左边节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxDepth = 0;
    int leftVal = INT_MIN;
    void findVal(TreeNode* root, int depth){
        if(root)depth++;
        if(depth > maxDepth){
            leftVal = root->val;
            maxDepth = depth;
        }
        if(root->left){
            findVal(root->left, depth);
        }
        if(root->right){
            findVal(root->right, depth);
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        findVal(root, 0);
        return leftVal;
    }
};

112. 路径总和

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root)return false;
        if((!root->left && !root->right) && (root->val == targetSum))return true;
        bool hasLeft = hasPathSum(root->left, targetSum - root->val);
        bool hasRight = hasPathSum(root->right, targetSum - root->val);
        return hasLeft || hasRight;
    }
};

113. 路径总和ii

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> result;
    void pathSum(TreeNode* root, int target, vector<int> path){
        path.push_back(root->val);
        if((!root->left && !root->right) && root->val == target){
            result.push_back(path);
        }
        if(root->left)pathSum(root->left, target - root->val, path);
        if(root->right)pathSum(root->right, target - root->val, path);
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(!root)return result;
        vector<int> path;
        pathSum(root, targetSum, path);
        return result;
    }
};

106.从中序与后序遍历序列构造二叉树

有几种方法可以取出vector的一部分：

✅ 用迭代器构造 vector（构造函数）

1
std::vector<int> v2(v1.begin(), v1.begin() + 3);
  • 创建一个新的 vector
  • 是构造函数，用于初始化
  • 执行的是复制构造过程

✅ assign 方法

1
v2.assign(v1.begin(), v1.begin() + 3);
  • 修改已有的 vector 内容
  • 是成员函数，不是构造
  • 会清除原内容，然后从指定范围赋值

✅ std::span

1
2
3
std::vector<int> original = {10, 20, 30, 40, 50, 60};
// 创建一个 span，引用从 index 2 开始的 3 个元素（即 30, 40, 50）
std::span<int> subspan(original.data() + 2, 3);
  • std::span 仅在 C++20 及以上版本中可用
  • 本身不支持负索引，但可以通过手动计算偏移量

不重复定义vector，每次用下标索引来分割性能会更好 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty())return nullptr;
        if(inorder.size() == 1){
           TreeNode* rt = new TreeNode(inorder[0]);
           return rt; 
        }
        int rootVal = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootVal);
        for(int i=0;i<inorder.size();i++){
            if(inorder[i] == rootVal){
                if(i>0){
                    vector<int> leftIn(inorder.begin(), inorder.begin()+i);
                    vector<int> leftPost(postorder.begin(), postorder.begin()+i);
                    root->left = buildTree(leftIn, leftPost);
                }
                if(i<(inorder.size()-1)){
                    vector<int> rightIn(inorder.begin()+i+1, inorder.end());
                    vector<int> rightPost(postorder.begin()+i, postorder.end()-1);
                    root->right = buildTree(rightIn, rightPost);
                }
                break;
            }
        }
        return root;
    }
};

105.从前序与中序遍历序列构造二叉树

尝试了一下，发现span的性能也就那样，并不理想。以后可以试试构造map和传区间下标的方式 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<span>
using namespace std;
class Solution {
    public:
        TreeNode* buildT(span<int> preorder, span<int> inorder){
            TreeNode* root = new TreeNode(preorder[0]);
            for(int i = 0; i<inorder.size();i++){
                if(preorder[0] == inorder[i]){
                    if(i > 0){
                        span<int> left_p(preorder.data()+1,preorder.data()+i+1);
                        span<int> left_i(inorder.data(), inorder.data()+i);
                        root->left = buildT(left_p, left_i);
                    }
                    int right_l = inorder.size() - 1 - i;
                    if(right_l>0){
                        span<int> right_p(preorder.data()+i+1, preorder.data()+preorder.size());
                        span<int> right_i(inorder.data()+i+1, inorder.data()+inorder.size());
                        root->right = buildT(right_p, right_i);
                    }
                }
            }
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            span<int> pre(preorder.data(), preorder.data()+preorder.size());
            span<int> in(inorder.data(), inorder.data()+inorder.size());
            TreeNode* root = buildT(pre, in);
            return root;
        }
    };

发表于 分类于

110.平衡二叉树

看到这题我的思路就是求高度算差值，看了题解才发现可以在求深度的同时就判定是否不平衡并剪枝 最后没想到的是居然还能犯打错字符的错，看来以后变量命名还是少偷懒 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int depth(TreeNode* root){
        int d = 0;
        if(!root)return 0;
        d++;
        int l = depth(root->left);
        if(l == -1)return -1;
        int r = depth(root->right);
        if(r == -1)return -1;
        if(abs(l-r)>1){
            return -1;
        }else{
            return d + max(l, r);
        }
    }
    bool isBalanced(TreeNode* root) {
        if(depth(root) == -1)return false;
        return true;
    }
};

257. 二叉树的所有路径

完全不知道该怎么写回溯啊...看了题解提示，有一次带push的递归，就有一次回溯，似乎有点理解了 询问chatgpt,得知如果我一定要用迭代法，应该也是类似递归的逻辑：

  1. 每次将当前节点和路径压入栈。
  2. 如果当前节点是叶子节点，则把路径加入结果。
  3. 否则，将右子树和左子树（如果存在）分别入栈，并将路径扩展。

如果删改执行逻辑，就算多弹出一次节点，到了外层while的下一个循环又会从左节点开始重复遍历

1
s.push_back(path[i]); // ❌

在 string 中直接用 push_back(int)，会被当作 ASCII 字符写进去，而不是数字！
应该改成：

1
s += to_string(path[i]);

这里我path传值不传引用，隐式使用了迭代法函数栈的特性来回溯path： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stack>
using namespace std;
class Solution {
public:
    string vecString(vector<int>& path){
        string s;
        for(int i = 0;i<path.size();i++){
            s += to_string(path[i]);
            if(i != (path.size()-1))s.append("->");
        }
        return s;
    }
    void traverse(TreeNode* root, vector<int>path, vector<string>&result){
        path.push_back(root->val);
        if(!root->left && !root->right){
            result.push_back(vecString(path));
        }
        if(root->left){
            traverse(root->left, path, result);
        }
        if(root->right){
            traverse(root->right, path, result);
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<int> path;
        vector<string> result;
        traverse(root, path, result);
        return result;
    }
};

404.左叶子之和

我直接防御型编程 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if(!root){
            return 0;
        }else if(!root->left){
            sum += 0;
        }else if(!root->left->left && !root->left->right){
            sum += root->left->val;
        }else{
            sum += sumOfLeftLeaves(root->left); // if(root->left)
        }
        if(root->right)sum += sumOfLeftLeaves(root->right);
        return sum;
    }
};

222.完全二叉树的节点个数

\(O(n)\)写法： 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countNodes(TreeNode* root) {
        int cnt = 0;
        if(!root)return cnt;
        cnt++;
        if(root->left)cnt += countNodes(root->left);
        if(root->right)cnt += countNodes(root->right);
        return cnt;
    }
};
使用完全二叉树的性质： 完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。 完全二叉树1 * 对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。 * 对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树 完全二叉树2 可以达到\(O(log n × log n)\)时间复杂度

✅ 推荐修正版本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        TreeNode* left = root;
        TreeNode* right = root;
        int leftDepth = 0, rightDepth = 0;
        while (left) {
            leftDepth++;
            left = left->left;
        }
        while (right) {
            rightDepth++;
            right = right->right;
        }
        if (leftDepth == rightDepth) {
            // 是满二叉树
            return (1 << leftDepth) - 1;
        }
        // 不是满二叉树，递归统计
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

发表于 分类于

今天找到了一个将chatGPT内容markdown化的插件（chrome插件商店搜索chatGPT to Markdown），这样整理每天的错题就方便直观多了

堆对象 vs 栈对象 初始化

在 C++ 中，struct 和 class 在语法上几乎没有区别，主要区别只有两点：

  1. 默认访问权限：struct 默认是 public，class 默认是 private

  2. 默认继承权限：struct 默认是 public 继承，class 默认是 private 继承

👉 所以：struct 并不“必须”用 new 来创建对象！

写法 内存位置 生命周期 示例
Class c; 栈 (stack) 自动管理 class 或 struct 都可以
Class* c = new Class(); 堆 (heap) 需要手动 delete class 或 struct 都可以

在需要动态分配的场景使用new（如链表节点）

1
2
3
4
5
6
struct Node {
    int val;
    Node* next;
};

Node* head = new Node(); // ✅ 堆上分配，适合动态数据结构

102. 二叉树的层序遍历

昨天的层序遍历练一练 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> lev;
        vector<vector<int>> res;
        if(!root)return res;
        lev.push(root);
        while(!lev.empty()){
            int len = lev.size();
            vector<int> levVar;
            while(len > 0){
                len--;
                TreeNode* cur = lev.front();
                lev.pop();
                levVar.push_back(cur->val);
                if(cur->left)lev.push(cur->left);
                if(cur->right)lev.push(cur->right);
            }
            res.push_back(levVar);
        }
        return res;
    }
};

226.翻转二叉树

❌ 问题一：错误创建了无用的 TreeNode

1
2
TreeNode* rightT = new TreeNode();
if(root->right) rightT = root->right;

在这里无论 root->right 是否为空，都会创建一个新的 TreeNode 实例。但实际上你只需要记录 root->right 的原始指针。没有 delete 掉那个多余的 new TreeNode()，会造成内存泄漏。在递归中创建新的 TreeNode，可能无限递归，造成 stack overflow。

要删除通过 new TreeNode() 动态创建的对象，只需要调用 delete 并传入该指针即可。例如：

1
2
3
4
TreeNode* node = new TreeNode();
// 使用 node 做一些操作
delete node; // 释放内存
node = nullptr; // 避免悬空指针（可选但推荐）

✅ 注意事项：

  1. 每一个 new 都要对应一个 delete，否则会导致内存泄漏。

  2. 删除后最好将指针设为 nullptr，防止以后误访问已释放的内存。

  3. 如果你创建的是数组，用 new[]，则要用 delete[]。

例如：

1
2
int* arr = new int[10];
delete[] arr;

❌ 问题二：判断逻辑混乱，递归不完整

1
2
3
4
5
6
if(root->left){
    root->right = invertTree(root->left);
}
if(rightT != nullptr){
    root->left = invertTree(rightT);
}

如果 root->left 是 nullptr，就跳过了对 root->right 的赋值

正确的做法是把翻转和赋值分隔开来： 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)return root;
        TreeNode* rightT = invertTree(root->right);
        TreeNode* leftT = invertTree(root->left);
        root->left = rightT;
        root->right = leftT;
        return root;
    }
};

101. 对称二叉树

别忘了判定值是否一致 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isSym(TreeNode* left, TreeNode* right){
        if(!left && !right)return true;
        if((!left && right) || (!right && left))return false;
        if(left->val != right->val)return false;
        bool isIn = isSym(left->right, right->left);
        bool isOut = isSym(left->left, right->right);
        return isIn && isOut;
    }
    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        return isSym(root->left, root->right);
    }
};

104.二叉树的最大深度

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

注意边界条件对代码的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int maxD = 0;
        if(root){
            maxD++;
        }else{
            return maxD;
        }
        int maxL = root->left ? maxDepth(root->left) : 0;
        int maxR = root->right ? maxDepth(root->right) : 0;
        maxD += maxL > maxR ? maxL : maxR;
        return maxD;
    }
};

111.二叉树的最小深度

迭代法： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minDepth(TreeNode* root) {
        int minD = 0;
        if(!root)return minD;
        minD++;
        if(!root->left && !root->right)return minD;
        if(!root->left && root->right){
            return minD + minDepth(root->right);
        }else if(root->left && !root->right){
            return minD + minDepth(root->left);
        }else{
            int minL = minDepth(root->left);
            int minR = minDepth(root->right);
            minD += minL > minR ? minR : minL;
            return minD;
        }
    }
};

发表于 分类于

HTTP请求报文和响应报文是怎样的，有哪些常见的字段？

HTTP报文分为请求报文和响应报文。

请求报文

请求报文主要由请求行、请求头、空行、请求体构成。 请求行包括如下字段：

  • 方法（Method）：指定要执行的操作，如 GET、POST、PUT、DELETE 等。
  • 资源路径（Resource Path）：请求的资源的URI（统一资源标识符）。
  • HTTP版本（HTTP Version）：使用的HTTP协议版本，如 HTTP/1.1 或 HTTP/2.0。

请求头的字段较多，常使用的包含以下几个：

  • Host：请求的服务器的域名。
  • Accept：客户端能够处理的媒体类型。
  • Accept-Encoding：客户端能够解码的内容编码。
  • Authorization：用于认证的凭证信息，比如token数据。
  • Content-Length：请求体的长度。
  • Content-Type：请求体的媒体类型。（如 application/json、text/html 等）
  • Cookie：存储在客户端的cookie数据。
  • If-None-Match：与 ETag 配合使用，用于缓存控制。
  • Connection：管理连接的选项，如 keep-alive。

方便记忆：

1. 基本身份/环境信息（我是谁、能接受什么）
  • Host：我要访问哪个服务器（主机名）
  • User-Agent：我是哪个浏览器（可选提）
  • Accept / Accept-Encoding：我能接受的内容类型/压缩方式
2. 身份认证/状态维持
  • Authorization：我的身份凭证（如 token）
  • Cookie：我本地保存的 cookie，带回来给你看
3. 请求体相关（仅 POST/PUT 用）
  • Content-Type：我发给你是什么格式（如 JSON）
  • Content-Length：我发给你的内容多大
4. 缓存控制（和上次请求有关）
  • If-None-Match：上次你的资源 ETag 是 XX，看看现在变没
  • If-Modified-Since：上次的修改时间是 XX，资源有变吗？
  • Cache-Control：我是否希望使用缓存？

空行是请求头部和请求主体之间的空行，用于分隔请求头部和请求主体。

请求体通常用于 POST 和 PUT 请求，包含发送给服务器的数据。

响应报文

HTTP响应报文是服务器向客户端返回的数据格式，用于传达服务器对客户端请求的处理结果以及相关的数据。一个标准的HTTP响应报文通常包含状态行、响应头、空行、响应体。

状态行包含HTTP版本、状态码和状态消息。例如：HTTP/1.1 200 OK

响应头部也是以键值对的形式提供的额外信息，类似于请求头部，用于告知客户端有关响应的详细信息。一些常见的响应头部字段包括：

  • Content-Type：指定响应主体的媒体类型。
  • Content-Length：指定响应主体的长度（字节数）。
  • Server：指定服务器的信息。
  • Expires: 响应的过期时间，之后内容被认为是过时的。
  • ETag: 响应体的实体标签，用于缓存和条件请求。
  • Last-Modified： 资源最后被修改的日期和时间。
  • Location：在重定向时指定新的资源位置。
  • Set-Cookie：在响应中设置Cookie。
  • Access-Control-Allow-Origin: 跨源资源共享（CORS）策略，指示哪些域可以访问资源。

方便记忆：

1. 内容信息

  • Content-Type：我返回的是什么格式（如 HTML/JSON）
  • Content-Length：内容有多大

2. 服务器身份

  • Server：我是哪个服务器（如 nginx）

3. 状态维持

  • Set-Cookie：设置 cookie，下次你带回来

4. 缓存相关

  • ETag：这是资源的版本号
  • Last-Modified：资源上次修改时间
  • Cache-Control / Expires：多久前有效/过期时间

5. 跨域和重定向

  • Access-Control-Allow-Origin：谁能访问我（CORS）
  • Location：去这个新地址吧（重定向）

空行（Empty Line）在响应头和响应体之间，表示响应头的结束。

响应体是服务端实际传输的数据，可以是文本、HTML页面、图片、视频等，也可能为空。

HTTP有哪些请求方式？

  • GET：请求指定的资源。
  • POST：向指定资源提交数据进行处理请求（例如表单提交）。
  • PUT：更新指定资源。
  • DELETE：删除指定资源。
  • HEAD：获取GET请求相同响应的报文首部，不返回报文主体。
  • OPTIONS：查询服务器支持的请求方法。
  • PATCH：对资源进行部分更新

GET请求和POST请求的区别

  • 用途：GET请求通常用于获取数据，POST请求用于提交数据。
  • 数据传输：GET请求将参数附加在URL之后，POST请求将数据放在请求体中。
  • 安全性：GET请求由于参数暴露在URL中，安全性较低；POST请求参数不会暴露在URL中，相对更安全。
  • 数据大小：GET请求受到URL长度限制，数据量有限；POST请求理论上没有大小限制。
  • 幂等性：GET请求是幂等的，即多次执行相同的GET请求，资源的状态不会改变；POST请求不是幂等的，因为每次提交都可能改变资源状态。
  • 缓存：GET请求可以被缓存，POST请求默认不会被缓存。

发表于 更新于 分类于

144.二叉树的前序遍历

递归法

注意边界条件，root为空指针时不再向下迭代叶子节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void preTree(TreeNode* root, vector<int>& vec){
        if(root){
            vec.push_back(root->val);
            preTree(root->left, vec);
            preTree(root->right, vec);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preTree(root, result);
        return result;
    }
};

迭代法

注意栈先入先出的特性对入栈顺序的影响 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(!root)return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* rt = st.top();
            st.pop();
            result.push_back(rt->val);
            if(rt->right)st.push(rt->right);
            if(rt->left)st.push(rt->left);
        }
        return result;
    }
};

145.二叉树的后序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void postTree(TreeNode* root, vector<int>& vec){
        if(!root)return;
        postTree(root->left, vec);
        postTree(root->right, vec);
        vec.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postTree(root, result);
        return result;
    }
};

迭代法

注意栈先入先出的特性对入栈顺序的影响 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root)return result;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* cur = st.top();
            st.pop();
            result.push_back(cur->val);
            if(cur->left)st.push(cur->left);
            if(cur->right)st.push(cur->right);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

94.二叉树的中序遍历

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void inTree(TreeNode* root, vector<int>& vec){
            if(!root)return;
            inTree(root->left, vec);
            vec.push_back(root->val);
            inTree(root->right, vec);
            
        }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inTree(root, result);
        return result;
    }
};

迭代法

写答案的时候一直在想，因为想处理左子树方便，我想stack里面初始没有node，这样该如何定义while的初始条件？看了题解发现可以while (cur != nullptr || !NodeStack.empty())（但是还是写了麻烦的写法）
一直没想明白递归到弹出第一个左叶子之后如何避免在弹出中间节点时再把左叶子压栈，看了题解发现cur = cur->right;此时cur为空指针，直接跳过下一个while即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> NodeStack;
        vector<int> result;
        if(!root)return result;
        NodeStack.push(root);
        TreeNode* cur = root;
        while(!NodeStack.empty()){
            while(cur && cur->left != nullptr){
                cur = cur->left;
                NodeStack.push(cur);
            }
            cur = NodeStack.top();
            result.push_back(cur->val);
            NodeStack.pop();
            if(cur->right){
                NodeStack.push(cur->right);
            }
            cur = cur->right;
        }
        return result;
    }
};

发表于 分类于

150. 逆波兰表达式求值

细节很重要，注意数字可能有多位，有负数；数学表达式操作前后数字顺序影响结果 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(string ss: tokens){
            char ssEnd = ss[ss.size()-1];
            if(ssEnd <= '9' && ssEnd >= '0'){
                int val = 0;
                int times = 1;
                while(!ss.empty()){
                    if(ss[ss.size()-1] == '-'){
                        val = 0 - val;
                    }else{
                        int n = (ss[ss.size()-1] - '0');
                        val += n * times;
                        times = times * 10;
                    }
                    ss.pop_back();
                }
                st.push(val);
            }else{
                int n1 = st.top();
                st.pop();
                int n2 = st.top();
                st.pop();
                int opVal = 0;
                if(ssEnd == '+'){
                    opVal = n2 + n1;
                }else if(ssEnd == '-'){
                    opVal = n2 - n1;
                }else if(ssEnd == '*'){
                    opVal = n2 * n1;
                }else{
                    opVal = n2 / n1;
                }
                st.push(opVal);
            }
        }
        return st.top();
    }
};

239. 滑动窗口最大值

注意单调栈判断条件；top查询应在代码逻辑最后 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyQueue{
private:
    deque<int> dq;
public:
    MyQueue(){}
    void push(int val){
        while(!dq.empty() && val > dq.back()){
            dq.pop_back();
        }
        dq.push_back(val);
    }
    void pop(int val){
        if(!dq.empty() && dq.front() == val){
            dq.pop_front();
        }
    }
    int top(){
        return dq.front();
    }
};
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue mq;
        vector<int> maxWin;
        for(int i = 0; i<nums.size();i++){
            mq.push(nums[i]);
            if(i>(k-1)){
                mq.pop(nums[i-k]);
            }
            if(i>=(k-1)){
                maxWin.push_back(mq.top());
            }
        }
        return maxWin;
    }
};

347.前 K 个高频元素

注意operator()一定要是public的，因为小顶堆每次弹出堆顶最小元素所以最后要逆序填入vector
为什么priority_queue第三个参数要传入一个类？priority_queue 只需要知道这个类的类型（模板参数），它会自己构造一个比较器对象myComp comp 来比较元素 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    class myComp{
        public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>&rhs){
            return lhs.second > rhs.second;// 插入元素判断为true时走入叶子节点，所以是小顶堆
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        for(int n:nums){
            mp[n]++;
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, myComp> priQue;
        for(unordered_map<int, int>::iterator p = mp.begin();p!=mp.end();p++){
            priQue.push(*p);
            if(priQue.size()>k)priQue.pop();
        }
        vector<int> res(k);
        for(int i = k-1;i>=0;i--){
            res[i] = priQue.top().first;
            priQue.pop();
        }
        return res;
    }
};

发表于 分类于

232.用栈实现队列

我的想法是一旦pop或者peek就把数据导到输出栈，输出后再一个一个push回去。看了题解有更简捷的方式：

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。 最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stack>
using namespace std;
class MyQueue {
private:
    stack<int> inStack;
    stack<int> outStack;
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if(outStack.empty()){
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int r = outStack.top();
        outStack.pop();
        return r;
    }
    
    int peek() {
        int r = this->pop();
        outStack.push(r);
        return r;
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

225. 用队列实现栈

用一个队列实现的方法比较简洁。注意队列和栈两种数据结构的函数用法不一样 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<queue>
using namespace std;
class MyStack {
private:
    queue<int> q;
public:
    MyStack() {
        
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int s = q.size() - 1;
        while(s>0){
            s--;
            int a = q.front();
            q.pop();
            q.push(a);
        }
        int r = q.front();
        q.pop();
        return r;
    }
    
    int top() {
        int r = this->pop();
        q.push(r);
        return r;
    }
    
    bool empty() {
        return q.empty();
    }
};

20. 有效的括号

注意一下几种可能遇到的错误情况即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stack>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        stack<char> pairP;
        for(char c: s){
            if(c == '(' || c == '[' || c=='{'){
                pairP.push(c);
            }else if(c == ')' || c == ']' || c == '}'){
                if(pairP.empty())return false;
                char lPair = pairP.top();
                if( (c == ')' && lPair == '(') || (c == ']' && lPair == '[')||(c == '}' && lPair == '{')){
                    pairP.pop();
                }else{
                    return false;
                }
            }
        }
        if(!pairP.empty())return false;
        return true;
    }
};

1047. 删除字符串中的所有相邻重复项

有了前面的经验，这一题就相对简单了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> adjStack;
        string r;
        for(char c: s){
            if(!adjStack.empty() && adjStack.top() == c){
                adjStack.pop();
            }else{
                adjStack.push(c);
            }
        }
        while(!adjStack.empty()){
            char c = adjStack.top();
            adjStack.pop();
            r.push_back(c);
        }
        if(r.empty())return r;
        int left = 0;
        int right = r.size() - 1;
        while(left<right){
            char e = r[left];
            r[left] = r[right];
            r[right] = e;
            left++;
            right--;
        }
        return r;
    }
};

发表于 更新于 分类于

151.翻转字符串里的单词

需要注意反转的过程，不能想当然 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void rev(char* left, char* right){
        while(left < right){
            char c = *left;
            *left = *right;
            *right = c;
            left++;
            right--;
        }
    }
    string reverseWords(string s) {
        string ss;
        string res;
        for(int i = s.size() - 1; i>=0;i--){
            if(s[i] != ' '){
                // cout<<"s[i]:"<<s[i]<<endl;
                ss.push_back(s[i]);
            }else{
                if(!ss.empty()){
                    rev(&ss[0], &ss[ss.size() - 1]);
                    res.append(ss);
                    res.push_back(' ');
                    ss = "";
                }
            }
        }
        if(!ss.empty() && ss[ss.size()-1] != ' '){
            rev(&ss[0], &ss[ss.size() - 1]);
            res.append(ss);
        }
        if(res[res.size() - 1] == ' ')res.pop_back();
        return res;
    }
};

卡码网：55.右旋转字符串

一步一步输出看结果，总算是做对了 贴一下题目：

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<string>
using namespace std;
int main(){
    int k;
    cin>>k;
    string s;
    cin.ignore();
    getline(cin, s);
    // cout<<"k:"<<k<<" s:"<<s<<endl;
    string ss;
    int len = s.size();
    for(int i = (len - 1); i>=(len-k);i--){
        ss.push_back(s[i]);
        s.pop_back();
    }
    // cout<<"ss:"<<ss<<" s:"<<s<<endl;
    char* left = &ss[0];
    char* right = &ss[ss.size() - 1];
    while(left < right){
        char c = *left;
        *left = *right;
        *right = c;
        left++;
        right--;
    }
    ss.append(s);
    cout<<ss;
}

28. 实现 strStr()

使用KMP算法求最长相等前后缀的过程，实际上是在：

  • 后缀指针是外层循环
  • 若前后缀判断不相等，前缀指针可以一直往前跳跃至上一个判断不相等的位置，直到长度计数归零或者找到相等位置。如果找到相等位置，则参考下一条将计数加一
  • 重复利用之前已经判断相等的前后缀，如果一直相等，则长度每次都加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void getNext(vector<int> &nextTable, string s){
        nextTable.push_back(0);
        int j = 0;
        for(int i = 1;i<s.size();i++){
            while(j > 0 && s[i] != s[j]){
                j = nextTable[j - 1];
            }
            if(s[i] == s[j]){
                j++;
            }
            nextTable.push_back(j);
        }
    }
    int strStr(string haystack, string needle) {
        vector<int> n;
        getNext(n, needle);
        for(int i:n){
            cout<<i;
        }
        cout<<endl;
        int j = 0;
        for(int i = 0;i<haystack.size();i++){
            while(j>0 && haystack[i] != needle[j]){
                j = n[j-1];
            }
            if(haystack[i] == needle[j]){
                if(j == needle.size() - 1)return i-j;
                j++;
            }
        }
        return -1;
    }
};

459.重复的子字符串

关键是数学证明：最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，那么不包含的子串 就是s的最小重复子串 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        vector<int> nextT;
        nextT.push_back(0);
        int j= 0;
        for(int i = 1;i<s.size();i++){
            while(j>0 && s[i] != s[j]){
                j = nextT[j-1];
            }
            if(s[i] == s[j]){
                j++;
            }
            nextT.push_back(j);
        }
        int cnt = 0;
        for(int k = 0;k<nextT.size();k++){
            if(nextT[k] == 0){
                cnt++;
            }else{
                break;
            }
        }
        int len = s.size();
        if(nextT.back()!=0 && (len % (len - j) == 0))return true;
        return false;
    }
};

0%