力扣题目解析--有效的括号

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

代码展示 

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> Charmap = {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        };

        if (s.empty()) {
            return true; // 空字符串也被认为是有效的括号序列
        }

        // 使用栈来辅助判断括号是否匹配
        stack<char> st;
        for (char c : s) {
            if (Charmap.count(c)) { // 如果是左括号，则入栈
                st.push(c);
            } else if (!st.empty() && Charmap[st.top()] == c) { // 如果是右括号，检查是否与栈顶元素匹配
                st.pop();
            } else { // 不匹配的情况
                return false;
            }
        }

        return st.empty(); // 如果栈为空，说明所有括号都匹配
    }
};

写者心得 

学者在最初接触的这道题的时候，刚开始的想法就是利用地图查找法来进行匹配，但是那样写的代码太过于臃肿，而且出了问题。然后经过学习，认为地图查找法可以使用，但是需要辅助。于是利用栈来辅助判断括号。代码有以下几个优点：

1.栈（下面来详细介绍一下占数组之间有何特点和优点，这样可以帮助我们更加正确的认识这样的使用，在以后解决问题的过程中，我们可以正确的使用栈的特点和优点。）

栈的特点和特性

1. 后进先出（LIFO）：

   • 栈的主要特点是后进先出。这意味着最后插入的元素将最先被移除。例如，如果你依次将元素 A、B、C 压入栈中，那么最先被弹出的将是 C，其次是 B，最后是 A。

2. 操作限制：

   • 栈通常只允许在栈顶进行操作，如压入（push）和弹出（pop）。不允许在中间或底部进行插入或删除操作。

3. 动态大小：

   • 栈的大小通常是动态的，可以根据需要增加或减少。大多数编程语言提供的栈实现都支持动态调整大小。

4. 高效的插入和删除操作：

   • 栈的插入和删除操作（push 和 pop）通常都是 O(1) 时间复杂度，因为它们只需要操作栈顶元素。

5. 内存管理：

   • 栈通常使用连续的内存空间，这使得访问速度快，但也可能导致内存碎片问题。

栈的应用场景

1. 表达式求值和转换：

   • 栈常用于表达式的求值和转换，如中缀表达式转后缀表达式（逆波兰表示法）。

2. 递归调用：

   • 计算机系统中的函数调用栈就是栈的一个典型应用。每次函数调用时，新的栈帧会被压入调用栈，函数返回时栈帧被弹出。

3. 括号匹配：

   • 如你之前的括号匹配问题，栈可以帮助检查括号是否正确匹配。

4. 回溯算法：

   • 回溯算法中，栈可以用来记录路径选择的历史，方便撤销选择。

5. 浏览器历史记录：

   • 浏览器的前进和后退功能可以用栈来实现，后退操作相当于从栈中弹出一个页面，前进操作相当于重新压入一个页面。

如何利用栈的特点和特性

1. 高效的数据操作：

   • 利用栈的 O(1) 插入和删除操作，可以在需要频繁进行插入和删除操作的场景中提高效率。

2. 简化代码逻辑：

   • 栈的 LIFO 特性使得某些问题的解决变得更加直观和简单。例如，括号匹配问题中，使用栈可以很容易地跟踪未匹配的左括号。

3. 避免内存碎片：

   • 如果你需要频繁地分配和释放小块内存，使用栈可以避免内存碎片问题，因为栈通常使用连续的内存空间。

4. 递归替代：

   • 在某些情况下，递归可能会导致栈溢出。你可以使用显式的栈来模拟递归过程，从而避免栈溢出问题。

2.charMap.count(c)

Charmap.count(c) 是 unordered_map 提供的一个成员函数，用于检查键 c 是否存在于 unordered_map 中。具体来说，count 函数会返回一个整数值：

• 如果键 c 存在于 unordered_map 中，count(c) 返回 1。
• 如果键 c 不存在于 unordered_map 中，count(c) 返回 0。

在代码中，Charmap.count(c) 用于检查当前字符 c 是否是一个左括号。如果是左括号，它会在 unordered_map 中找到对应的右括号。

• Charmap.count('(') 返回 1，因为 ( 是一个键。
• Charmap.count(')') 返回 0，因为 ) 不是一个键。
• Charmap.count('[') 返回 1，因为 [ 是一个键。
• Charmap.count(']') 返回 0，因为 ] 不是一个键.

代码解析 

1. 创建映射表：

   unordered_map<char, char> Charmap = {
       {'(', ')'},
       {'[', ']'},
       {'{', '}'}
   };

   • unordered_map<char, char> Charmap 创建了一个无序映射表 Charmap，用于存储左括号和对应的右括号。
   • 初始化列表 { {'(', ')'}, {'[', ']'}, {'{', '}'} } 将每个左括号与其对应的右括号关联起来。

2. 检查空字符串：

   if (s.empty()) {
       return true; // 空字符串也被认为是有效的括号序列
   }

   • if (s.empty()) 检查字符串 s 是否为空。
   • 如果字符串为空，返回 true，因为空字符串被认为是有效的括号序列。

3. 初始化栈：

   stack<char> st;

   • stack<char> st 创建了一个栈 st，用于存储未匹配的左括号。

4. 遍历字符串：

   for (char c : s) {

   • for (char c : s) 使用范围基的 for 循环遍历字符串 s 中的每一个字符 c。

5. 检查左括号：

   if (Charmap.count(c)) { // 如果是左括号，则入栈
       st.push(c);
   }

   • if (Charmap.count(c)) 检查当前字符 c 是否是左括号（即 c 是否存在于 Charmap 中）。
   • 如果是左括号，将其压入栈 st 中。

6. 检查右括号：

   else if (!st.empty() && Charmap[st.top()] == c) { // 如果是右括号，检查是否与栈顶元素匹配
       st.pop();
   }

   • else if (!st.empty() && Charmap[st.top()] == c) 检查当前字符 c 是否是右括号，并且栈不为空且栈顶的左括号与当前右括号匹配。
   • 如果匹配，弹出栈顶的左括号。

7. 处理不匹配的情况：

   else { // 不匹配的情况
       return false;
   }

   • else 处理不匹配的情况，即当前字符 c 既不是左括号，也不是与栈顶左括号匹配的右括号。
   • 返回 false，表示字符串 s 不是有效的括号序列。

8. 检查栈是否为空：

   return st.empty(); // 如果栈为空，说明所有括号都匹配

   • return st.empty() 检查栈是否为空。
   • 如果栈为空，说明所有左括号都有匹配的右括号，返回 true。
   • 如果栈不为空，说明有未匹配的左括号，返回 false。