devbox
黑客灵魂
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++学习笔记之数据结构

作者：黑客灵魂 | 2024-08-23 03:58:31

赞

踩

C++学习笔记之数据结构

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

一、二叉树

  二叉树是一种常见的数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树具有广泛的应用，如表示树形结构、表达式解析、搜索算法等。

1.1 二叉树的遍历

1.1.1 深度优先搜索（DFS）

  二叉树的遍历是指按照某种顺序访问树中的每一个节点，主要有以下几种方法：

  • 前序遍历（Preorder Traversal）：先访问根节点，然后遍历左子树，最后遍历右子树。顺序为：根 -> 左 -> 右。
/*
执行流程
1.初始化：
	current 指向根节点。
2.访问根节点：
	将 current 节点的值添加到结果中。
3.处理左右子树：
	如果 current 的右子节点不为空，将其压入栈。
	如果 current 的左子节点不为空，将其压入栈。
4.继续遍历：
	从栈中弹出一个节点，并将其设为 current。
	重复步骤 2 和步骤 3，直到栈为空。
*/
class Solution {
public:
    vector<int> PreorderTraversal(TreeNode* root) {
        if (root == nullptr) return;
        
        std::stack<TreeNode*> stack;
        vector<int> res;
        TreeNode* current = root;
    	stack.push(root);
    	
        while (!stack.empty()) {
           	current = stack.top();
            stack.pop();
            res.push_back(current->val);  // 将节点值添加到结果中
            
			// 注意这里的顺序：先右后左，这样在栈中处理时，左子树会先于右子树处理
			if (current->right != nullptr) {
            	stack.push(current->right);  // 将右子节点压入栈
       		 	}
       		if (current->left != nullptr) {
            	stack.push(current->left);   // 将左子节点压入栈
        		}
        }
        return res;
    }
};

  • 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
  • 中序遍历（Inorder Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。顺序为：左 -> 根 -> 右。
/*
执行流程
1.初始化：current 指向根节点，栈为空。
2.遍历左子树：
   内层 while (current != nullptr) 循环将当前节点及其所有左子节点依次压入栈中。
   这一步并没有访问任何节点，只是将节点保存起来。
3.访问节点：
   当 current 变为 nullptr 时，表示已经到达左子树的尽头。
   从栈中弹出一个节点，这个节点是最左的未访问节点。
   访问该节点（打印节点值）。
4.遍历右子树：
   将 current 移动到刚访问节点的右子节点，重复上述过程
*/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        std::stack<TreeNode*> stack;
        vector<int> res;
        TreeNode* current = root;
    
        while (current != nullptr || !stack.empty()) {
            while (current != nullptr) {
                stack.push(current);
                current = current->left;  // 将左子节点压入栈
            }
            current = stack.top();
            stack.pop();
            res.push_back(current->val);  // 将节点值添加到结果中
            current = current->right;  // 转向右子树
        }
        return res;
    }
};

  • 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
  • 后序遍历（Postorder Traversal）：先遍历左子树，然后遍历右子树，最后访问根节点。顺序为：左 -> 右 -> 根。
/*
这种方式是笔者偷师一位大佬的，属于投机取巧，主要是将前序遍历的修改逻辑并通过反转结果来得到后序遍历的结果
*/
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) return;
        
        std::stack<TreeNode*> stack;
        vector<int> res;
        TreeNode* current = root;
    	stack.push(root);
    	
        while (!stack.empty()) {
           	current = stack.top();
            stack.pop();
            res.push_back(current->val);  // 将节点值添加到结果中
            
			// 注意这里的顺序：先右后左，这样在栈中处理时，左子树会先于右子树处理
			if (current->right != nullptr) {
            	stack.push(current->right);  // 将右子节点压入栈
       		 	}
       		if (current->left != nullptr) {
            	stack.push(current->left);   // 将左子节点压入栈
        		}
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

  • 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorderHelper(root, res);
        return res;
    }
    
    void preorderHelper(TreeNode* root, vector<int>& res) {
        if (root == nullptr) return;
        
        // 处理当前节点
        res.push_back(root->val);
        
        // 递归遍历左子树
        preorderHelper(root->left, res);
        
        // 递归遍历右子树
        preorderHelper(root->right, res);
    }
};

// 中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorderHelper(root, res);
        return res;
    }
    
    void inorderHelper(TreeNode* root, vector<int>& res) {
        if (root == nullptr) return;
        
        // 递归遍历左子树
        inorderHelper(root->left, res);
        
        // 处理当前节点
        res.push_back(root->val);
        
        // 递归遍历右子树
        inorderHelper(root->right, res);
    }
};

// 后序遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorderHelper(root, res);
        return res;
    }
    
    void postorderHelper(TreeNode* root, vector<int>& res) {
        if (root == nullptr) return;
        
        // 递归遍历左子树
        postorderHelper(root->left, res);
        
        // 递归遍历右子树
        postorderHelper(root->right, res);
        
        // 处理当前节点
        res.push_back(root->val);
    }
};

  • 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
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

1.1.2 广度优先搜索（BFS）

  与DFS不同，BFS是从一个起始节点开始，首先访问所有相邻的节点，然后逐层向外扩展，依次访问下一层的所有节点。通常使用队列（queue）来实现，常用于最短路径问题、社交网络分析、网络广播、寻找最小生成树等。这里以102.二叉树的层序遍历为例，采用队列的方法，其思路如下：

  1. 申请一个队列q用于暂存节点，定义一个二维数组用来存储遍历结果；
  2. 在循环中定义一个数组currentLevel来存储每一层的节点，并时刻检索当前队列长度；
  3. 遍历当前层的每一个节点，依次取出节点并存储到currentLevel，并将该节点的左右子节点也压入队列中；
  4. 当该层的所有节点均在队列弹出且存入了currentLevel，将currentLevel压入数组；
  5. 按照上面的逻辑重复压入各个层的currentLevel，返回结果。

  117.填充每个节点的下一个右侧节点指针II的思路也是如此，不同之处在于需要定义一个包含 next 指针的 Node 类，以便将同一层的节点连接起来。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);

                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
            }
            result.push_back(currentLevel);
        }

    return 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
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

1.2 对称性（递归法）

  在二叉树中我们简单的介绍了利用递归的遍历方法，这里我们详细学习一下递归。简而言之，递归就是函数的不断自我调用。递归是一种强大的编程技术，特别适用于树和图等结构的操作。递归法的使用思路包括以下几个步骤：

  1. 确定递归的终止条件：这是递归过程的基本条件，决定何时停止递归调用，防止无限递归。
  2. 分解问题：将一个复杂的问题分解成一个或多个相同或相似的子问题。
  3. 递归调用：在函数内部调用函数自身，以解决分解后的子问题。
  4. 合并结果：将子问题的结果合并，以得到原问题的解。

  这里以101.对称二叉树为例，我们可以简单分析出来要满足对称，要求同时满足任意相对称的节点有相同的左、右子树，且他们本身也相等，这也就是我们的规律。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return isMirror(root->left, root->right);
    }

    bool isMirror(TreeNode* left, TreeNode* right) {
    	//确定递归的终止条件
        if (left == nullptr && right == nullptr) return true;
        if (left == nullptr || right == nullptr) return false;
        //分解问题：同时判断左、右子树及其本身的值
        return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);
    } 
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

1.3 构造二叉树

  我们以105.从前序与中序遍历序列构造二叉树为例，根据前面的知识我们知道前序遍历「根-左子树-右子树」，中序遍历「左子树-根-右子树」，根据题目示例：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]，我们的思路大致如下：

  1. 先找到根节点，前序遍历的第一个数组就是根节点[3]；
  2. 中序遍历时根节点[3]的左边部分[9]是左子树，右边部分[15,20,7]是右子树；
  3. 利用递归逐步分析各个子树。
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if(preorder.empty()) return nullptr;
    int left_size = 0;
    for(auto x : inorder){
        if(x == preorder[0]) break;
        left_size++;
    }
    vector<int> pre_l(preorder.begin() + 1, preorder.begin() + 1 + left_size);
    vector<int> pre_r(preorder.begin() + 1 + left_size, preorder.end());
    vector<int> in_l(inorder.begin(), inorder.begin() + left_size);
    vector<int> in_r(inorder.begin() + left_size + 1, inorder.end());
    TreeNode *left = buildTree(pre_l, in_l);
    TreeNode *right = buildTree(pre_r, in_r);
    TreeNode *newroot = new TreeNode(preorder[0], left, right);
    return newroot;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

1.4 路径总和

  我们以112.路径总和为例，可以利用递归从 targetSum开始，不断地减去路径上的节点值，如果走到叶子节点发现 targetSum=0，就说明我们找到了一条符合题目要求的路径。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        
        if (root == nullptr) return false;

        targetSum -= root->val;

        if (root->left == nullptr && root->right == nullptr) return targetSum == 0;

        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

  我们再以108.将有序数组转换为二叉搜索树为例，这里需要知道平衡二叉搜索树的定义（ 是指该树所有节点的左右子树的深度相差不超过 1。），那么这个时候我们需要找到数组的中值（这里已经升序排列了），然后对其左右两边不断添加新的节点。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector<int>& nums, int left, int right) {
   		// 终止条件
        if (left > right) return nullptr;
        
        // 获得中值
        int mid = (left + right) / 2;
        
        // 创建新节点
        TreeNode* root = new TreeNode(nums[mid]);
        // 进行调用，依次补充节点
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        
        return root;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

1.5 最近公共祖先

  我们以236.二叉树的最近公共祖先为例，利用递归在二叉树中自顶向下地查找节点 p 和 q，然后根据找到的位置来确定它们的公共祖先。根据题目要求，我们可以得出下图所示的几种情况：
在这里插入图片描述
  初看可能会感觉条件判断有点复杂，我们来一条条看：

  1. 如果当前节点 root 为 nullptr（即到达了树的末端）;
  2. 当前节点就是 p/q（p、q在同一子树上），则此时q/p无论是该节点的子节点或是下一级子节点等等，此时则不需要继续递归了，该节点就是要找的公共节点；
  3. 左右都找到的意思 p、q 各在不同的子树，此时按照定义返回其当前节点即可；
  4. 只有左/右子树中找到了 p、q，则只用返回该子树的遍历结果即可；
  5. 若左右子树都没有找到，说明 p 和 q 不在当前分支下，返回 nullptr 表示这条路径上没有 p 或 q。此时，递归返回上一级继续查找其他可能的分支。

  本质上是在自底向上查找，逐步确定最低公共祖先的条件。如果左右子树分别找到了 p 和 q，当前节点就是 LCA；如果都在一个子树中，则继续返回那一侧的结果；如果都没找到，则返回 nullptr。值得注意的是，在递归过程中返回值可能是空节点、节点 p、节点 q ，对于最外层的递归调用者来说，返回值是最近公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || 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;
        else if(left != nullptr) return left;
        else return right;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

1.6 二叉搜索树

  二叉搜索树（Binary Search Tree, BST）是二叉树的一种特殊形式，但它满足特定的顺序性质：

  • 对于树中的每一个节点 N，所有在 N 的左子树中的节点的值都小于 N 的值。
  • 所有在 N 的右子树中的节点的值都大于 N 的值。
  • 这个性质必须对树中的每一个节点都成立。
  • 中序编列结果是有序的。
      对于搜索二叉树我们可以利用中序遍历进行解决，例如230.二叉搜索树中第k小的元素，我们就是申明一个宏定义res用来存储遍历结果，然后在主函数中进行相关操作。
class Solution {
public:
    vector<int> res;
    int kthSmallest(TreeNode* root, int k) {
        inorderHelper(root, res);
        return res[k - 1]; 
    }

    void inorderHelper(TreeNode* root, vector<int>& res){
        if (root == nullptr) return;

        inorderHelper(root -> left,res);
        res.push_back(root -> val);
        inorderHelper(root -> right,res);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

二、哈希表/哈希集合

2.1 元素映射

  所谓元素映射就是将一组元素映射到另一组元素上，建立一一对应关系。这里我们需要先简单了解一下映射的相关定义：

  • 单射：设f是由集合A到集合B的映射，如果所有x，y∈A，且x≠y，都有f(x)≠f(y)，则称f为由A到B的单射。
  • 满射：设A和B是两个集合,如果从A到B的对应f:A→B是映射,并且集合B中的每一个元素在集合A中都有原象，那么映射就叫做从A到B的满射。
  • 双射=单射+满射

  简单来说，单射就是一个集合中两两不同的元素在另一个集合中的对应也两两不同。满射就是另一个对应的集合所有元素都是由一个集合映射过去的我们以290.单词规律为例，我们这里通过维护两个哈希表，分别用于记录 pattern 中的字母与 s 中单词之间的映射关系，另一个用于记录 s 中单词与 pattern 中字母之间的映射关系，这样可以确保双向连接的对应规律。

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> p2s;  // pattern to string map
        unordered_map<string, char> s2p;  // string to pattern map
        
/* 这里需要着重了解一下 stringstream 的用法，它的作用是从字符串中读取数据 */
/* 容许使用标准的输入运算符（>>）来提取数据，按需要的格式读取字符串中的内容。*/
        vector<string> words;
        string word;
        stringstream ss(s);
        // 将字符串 s 按空格拆分成单词存入 words 向量中
        while (ss >> word) {
            words.push_back(word);
        }
        
        // 如果 pattern 长度和 words 长度不一致，直接返回 false
        if (pattern.size() != words.size()) return false;
        
        for (int i = 0; i < pattern.size(); i++) {
            char p = pattern[i];
            string w = words[i];
            
            // 检查 pattern -> string 映射是否一致
            if (p2s.count(p)) {
                if (p2s[p] != w) return false;
            } else {
                p2s[p] = w;
            }
            
            // 检查 string -> pattern 映射是否一致
            if (s2p.count(w)) {
                if (s2p[w] != p) return false;
            } else {
                s2p[w] = p;
            }
        }
        
        return true;
    }
};

  • 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

2.2 字母异位问题

  字母异位词（Anagram）是指由相同字符组成但排列顺序不同的字符串。例如：“listen” 和 “silent” 是字母异位词，因为它们包含的字符完全相同，只是顺序不同。我们这里以49.字母异位词分组为例，它的大体思路为先遍历字符串数组，再利用sort进行升序排列（这是为了将字母异位词统一到一个key下，例如：eat，ate，tea）并分组，之后将哈希表的各个分组输出出来即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashmap;
        
        // 遍历字符串数组
        for (const auto& x : strs) {
            string key = x;
            sort(key.begin(), key.end()); // 将字符串排序
            hashmap[key].push_back(x); // 将原始字符串加入到排序后键对应的向量中
        }
        
        vector<vector<string>> res;
        
        // 遍历哈希表，将每个字母异位词组加入结果中
        for (const auto& t : hashmap) {
            res.push_back(t.second);
        }
        
        return res;
    }
};


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

三、栈

3.1 最小栈

  我们以题155.最小栈为例，这道题看起来复杂，其实只需要构建一个辅助栈（最小栈，来存储当前最小值）即可，唯一要注意的就是再void push(int val)；函数中，我们需要将当前值和最小栈顶元素进行对比，然后将小的一方压入最小栈的栈顶。可能你会疑问如果 st 的栈顶元素不是最小值，为什么 min_st 还要弹出？这是因为当你执行 push(val) 时，min_st 会将当前最小值 min(min_st.top(), val) 压入栈顶，所以min_st 的栈顶元素始终和 st 的栈顶元素是一一对应的。例如st = { 0，1，1，2}，则此时min_st = { 0，0，0，0}，所以在pop中弹出最小栈的元素时不会影响实际的最小值。

class MinStack {
public:
    stack<int> st;
    stack<int> min_st;

    MinStack() {
        min_st.push(INT_MAX);
    }
    
    void push(int val) {
        st.push(val);
        min_st.push(min(min_st.top(), val));
    }
    
    void pop() {
        st.pop();
        min_st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.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

3.2 栈的应用

  栈的相关内容我们还是比较了解了，主要是一个“先入后出”的概念，我们这里以150.逆波兰表达式求值为例。逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，如果遇到操作数，则将操作数入栈；如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i = 0; i < tokens.size(); i++){
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            }
            else st.push(tokens[i]);
        }
    int res = st.top();
    return res;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

3.3 单调栈

  单调栈（Monotonic Stack）是一种特殊类型的栈，它在操作过程中保持一定的单调性，这与普通的栈相比，增加了一个维护顺序的约束。我们先以739.每日温度为例，简单学习一下单调栈的性质。以下是本题的简单思路：

  1. 申请一个单调栈用于存储下标，申请一个数组result并全部初始化为0；
  2. 遍历temperatures中的元素：若当前元素大于栈顶元素，将下标差(i - st.top)存入result[i]，并弹出栈顶元素；
  3. 重复这个过程直到当前元素不大于栈顶元素；
  4. 若当前元素不大于栈顶元素，则将当前元素也压入栈中。
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> st; // 递增栈
        vector<int> result(n, 0);
        for (int i = 0; i < n; i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) { // 注意栈不能为空
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);

        }
        return result;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

四、链表

4.1 链表反转

  我们以96.反转链表II为例，我们需要先知道反转的过程是怎样的，其思路大致如下：

  1. 创建一个next节点，用来存储current节点的下一节点(右节点)；
  2. 创建一个pre节点，表示current节点的前一个(左节点)，将current->next指向该节点，表示链表方向反转；
  3. 将pre节点更新为current节点，将current节点更新成next节点；
  4. 将所有指定节点反转完，即可完成整体反转。
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr || left == right) return head;

        // 创建一个哨兵节点，便于处理头部边界
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        // 移动 prev 到 left 的前一个节点
        for (int i = 1; i < left; ++i) {
            prev = prev->next;
        }

        // current 是要反转的子链表的第一个节点
        ListNode* current = prev->next;
        ListNode* next = nullptr;
        ListNode* pre = nullptr;

        // 反转子链表
        for (int i = 0; i <= right - left; ++i) {
            next = current->next;   // 1. 存储 current 的下一节点
            current->next = pre;    // 2. 将 current->next 指向 pre 节点
            pre = current;          // 3. 将 pre 更新为 current
            current = next;         // 4. 将 current 更新为 next
        }

        // 连接反转后的链表部分
        prev->next->next = current; // 将反转后的子链表尾部与 right 后的部分连接
        prev->next = pre;           // 将 prev 连接到反转后的链表头部

        return dummy->next; // 返回新的头节点
    }
};

  • 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

4.2 旋转链表

  选择链表的主要思路就是先形成环再断开的过程，我们以61.旋转链表为例，其思路大致如下：

  1. 遍历链表，确定节点个数并到达尾节点；
  2. 将尾节点指向头节点形成环；
  3. 确定位移位置并到达新节点；
  4. 断开环。
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) return head;

        // 计算链表长度
        int n = 1; // 起始为1，因为我们从head节点开始
        ListNode* current = head;
        while (current->next != nullptr) {
            current = current->next;
            n++;
        }

        // 形成一个环
        current->next = head;

        // 计算新的尾节点的位置
        int offset = n - k % n;
        for (int i = 0; i < offset; i++) {
            current = current->next;
        }

        // 新的头节点是新尾节点的下一个节点
        ListNode* newHead = current->next;

        // 断开环
        current->next = nullptr;

        return newHead;
    }
};

  • 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

4.3 删除节点

  删除节点的过程就很简单了，以19.删除链表的倒数第N个节点为例，我们只需要先确定节点的总数，然后到达指定节点并修改其指向的下一节点，跳过要删除的节点即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == nullptr) return head;

        // 计算链表长度
        ListNode* p = head;
        int index = 0;
        while (p != nullptr) {
            p = p->next;
            index++;
        }


        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* current = dummy;

        for(int i = 0; i < index - n; i++){
            current = current -> next;
        }
        current -> next = current -> next -> next;
        return dummy->next;
    }
};

  • 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

五、图

  图是一种非线性数据结构，由节点（或称顶点，Vertices，图中的基本元素，用来表示对象或位置。） 和 边（Edges，连接两个节点的线，表示节点之间的关系或路径。）组成。它可以用于表示各种复杂的关系，比如社交网络中的朋友关系、交通网络中的路径、互联网中的连接等等。图的种类有以下4种：

  • 有向图（Directed Graph）：边具有方向性，从一个节点指向另一个节点。
  • 无向图（Undirected Graph）：边没有方向，两个节点之间的关系是对称的。
  • 加权图（Weighted Graph）：边带有权重，表示两个节点之间的距离或关系的强度。
  • 非加权图（Unweighted Graph）：边没有权重，表示两个节点之间的简单连接。

5.1 岛屿问题、围绕区域问题

  这些问题可以被映射到图论中的连通性问题，通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。以题200.岛屿数量为例，这里是是构建了一个“传染辅助函数”，如果周围有陆地则进行“传染”并打上标记，最后再进行双循环遍历每一个地址的情况进行统计。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int r = grid.size();    // 行数
        if (r == 0) return 0;
        int c = grid[0].size(); // 列数

        int count = 0;
        for (int i = 0; i < r; i++) {  // 使用 i 来遍历行
            for (int j = 0; j < c; j++) {  // 使用 j 来遍历列
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);  // 发现一个岛屿，开始深度优先搜索
                }
            }
        }
        return count;
    }

private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int m = grid.size();    // 行数
        int n = grid[0].size(); // 列数

        // 标记当前土地为 '0'，表示已经访问过
        grid[r][c] = '0';

        // 向上、下、左、右四个方向继续搜索
        if (r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);    // 向上检索
        if (r + 1 < m && grid[r + 1][c] == '1') dfs(grid, r + 1, c);    // 向下检索
        if (c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);    // 向左检索
        if (c + 1 < n && grid[r][c + 1] == '1') dfs(grid, r, c + 1);    // 向右检索
    }
};

  • 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

六、字典树

  字典树是一种树形数据结构，用于存储动态集合或数组中的字符串，每个节点代表字符串中的一个字符。每个节点可以有多个子节点，子节点的数量取决于字母表的大小（例如，英文的字典树有 26 个子节点）。通常被用于实现快速前缀查找、字符串搜索、单词自动补全、拼写检查等功能。字典树的主要特点如下：

  • 根节点通常不包含字符，代表空字符串。
  • 每个节点的所有子节点拥有共同的前缀。
//Trie 的结构
struct TreeNode {
    VALUETYPE value;    //结点值
    TreeNode* children[NUM];    //指向孩子结点
};

  • 1
  • 2
  • 3
  • 4
  • 5


  以208.实现Trie(前缀树)为例，其核心在于将字符串拆分，在每一级子节点中进行查找是否含有当前字母，当我们存储的时候会给单词结尾的节点打上标记，表示已经存储了该单词。其具体思路如下：

  • TrieNode 类：
      children 使用了 unordered_map<char, TrieNode*> 来代替固定大小的数组。这使得每个节点可以根据需要动态分配子节点，而不需要为每个可能的字符预先分配空间。
  • insert 方法：
      通过 find 方法检查哈希表中是否已经存在当前字符对应的子节点。
    如果不存在，则创建一个新节点并添加到哈希表中。
  • search 和 startsWith 方法：
      同样使用 find 方法来检查哈希表中是否存在当前字符对应的子节点，区别在于查询单词需要对标记进行判断。例如，存储apple时，只在e处进行标记，所以检查时发现apple存在而app不存在；而检查前缀则只需要保证每个字母都出现即可，是否是存储的单词则不重要。
class Trie {
private:
    // 定义TrieNode节点
    struct TrieNode {
        bool isEnd; // 标记是否是一个单词的结尾
        unordered_map<char, TrieNode*> children; // 使用哈希表来存储子节点
    };
    
    TrieNode* root; // 根节点

public:
    // 初始化前缀树对象
    Trie() {
        root = new TrieNode();
    }
    
    // 向前缀树中插入字符串 word
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true; // 标记单词结束
    }
    
    // 检查字符串 word 是否在前缀树中
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEnd;
    }
    
    // 检查是否存在以 prefix 为前缀的单词
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

  • 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
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/1019376
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号