每日一题——力扣20. 有效的括号（举一反三+思想解读+逐步优化）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

我的写法

专业点评

时间复杂度分析

空间复杂度分析

代码优化建议

我要更强

优化方案1：使用动态数组

优化方案2：使用有限状态机

优化方案3：简化逻辑（不使用动态内存分配）

总结

哲学和编程思想

优化方案1：使用动态数组

1. 动态内存管理

2. 抽象

3. 扩展性

4. 资源管理

优化方案2：使用有限状态机

1. 状态化思维

2. 确定性

3. 简化逻辑

优化方案3：简化逻辑（不使用动态内存分配）

1. 预分配

2. 空间时间权衡

3. 极简主义

通用编程思想

举一反三

1. 动态内存管理

2. 抽象与封装

3. 状态化思维与有限状态机

4. 预分配与空间时间权衡

5. 高内聚低耦合

6. 资源管理

总结

https://leetcode.cn/problems/valid-parentheses/description/

我的写法

#include <stdlib.h>


// 检查括号字符串是否有效的函数
bool isValid(char* s) {
    // 定义栈的顶部索引和底部索引
    int top = 0, bottle = 0;
    // 定义栈的大小
    int size = 10000;
    // 动态分配一个整型数组作为栈
    int* stack = (int*)malloc(size * sizeof(int));
    // 定义字符变量ch，用于遍历字符串
    int ch = ' ';


    // 遍历输入字符串
    for (int i = 0; (ch = s[i]) != '\0'; i++) {
        // 打印当前字符（用于调试）
        printf("%c", ch);
        // 如果字符是左括号之一，则将其压入栈中
        if (ch == '(' || ch == '{' || ch == '[') {
            stack[top++] = ch;
        } else {
            // 如果栈为空但遇到了右括号，说明不匹配
            if (top == 0) {
                return false;
            } else {
                // 检查栈顶与当前右括号是否匹配
                if (stack[top - 1] == '(' && ch == ')') {
                    top--; // 匹配则弹出栈顶
                } else if (stack[top - 1] == '{' && ch == '}') {
                    top--; // 匹配则弹出栈顶
                } else if (stack[top - 1] == '[' && ch == ']') {
                    top--; // 匹配则弹出栈顶
                } else {
                    // 不匹配则返回false
                    return false;
                }
            }
        }
    }
    // 遍历结束后，栈应该为空，如果不为空则返回false
    if (top != bottle) {
        return false;
    } else {
        return true; // 栈为空则返回true，表示字符串括号匹配
    }
}

这段代码实现了检查括号字符串是否有效的功能。下面是专业的点评和复杂度分析：

专业点评

代码结构与逻辑
- 代码结构清晰：函数 isValid 逻辑清晰，分为遍历字符串、检查括号类型、维护栈等部分。
- 使用栈数据结构合适：对括号匹配的问题，使用栈来解决是非常合适的，符合括号匹配的后进先出（LIFO）特性。
可能存在的改进点

内存管理：代码中使用了 malloc 动态分配栈空间，但在函数结束时没有释放分配的内存。如果 isValid 函数在大规模使用时会造成内存泄漏问题，应该使用 free(stack) 释放内存。
栈溢出检查：没有对 top 的值进行合法性检查，当字符过多时可能会导致栈溢出。可以通过动态调整栈大小来解决这个问题。
无用的变量：bottle 变量并没有实际用途，可以移除。
打印语句：printf("%c", ch); 用于调试的打印语句应在生产代码中删除，避免不必要的输出开销。

时间复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

遍历字符串的每一个字符需要 O(n) 的时间。
每个字符的入栈和出栈操作在均摊情况下都是 O(1) 的时间复杂度，因此总时间复杂度为 O(n)。

空间复杂度分析

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

最坏情况下，所有的字符都是左括号（例如字符串全是 ((((((），此时栈的大小会达到字符串的长度。
因此，栈的空间复杂度为 O(n)。

代码优化建议

bool isValid(char* s) {
    int top = 0;
    int size = 10000;
    int* stack = (int*)malloc(size * sizeof(int));
    if (stack == NULL) {
        return false; // 内存分配失败时返回false
    }
    int ch = ' ';
    for (int i = 0; (ch = s[i]) != '\0'; i++) {
        if (ch == '(' || ch == '{' || ch == '[') {
            stack[top++] = ch;
        } else {
            if (top == 0) {
                free(stack); // 释放内存
                return false;
            } else {
                if ((stack[top - 1] == '(' && ch == ')') ||
                    (stack[top - 1] == '{' && ch == '}') ||
                    (stack[top - 1] == '[' && ch == ']')) {
                    top--;
                } else {
                    free(stack); // 释放内存
                    return false;
                }
            }
        }
    }
    bool isValid = (top == 0);
    free(stack); // 释放内存
    return isValid;
}

内存管理：
动态调整栈大小（可选）：

如果预期字符串长度会很长，可以考虑动态调整栈大小以避免栈溢出。

总结来看，这段代码在逻辑上是正确的，但在内存管理和栈溢出检查方面还有优化空间。时间复杂度为 O(n)，空间复杂度为 O(n)，在大多数情况下表现良好。

我要更强

在括号匹配问题上，时间复杂度已经是最优的 O(n)，因为每个字符都需要检查一次。空间复杂度的优化可能性有限，因为在最坏情况下，所有字符都是左括号或有嵌套括号时，仍然需要 O(n) 的空间来存储这些括号。但是，我们可以考虑一些具体的优化方法：

使用动态数组（矢量）：动态调整栈的大小，以节省空间。
使用有限状态机：对某些特定情况可以优化，但一般情况下仍然需要 O(n) 的空间。

以下是几个优化方案及其实现代码：

优化方案1：使用动态数组

动态数组可以根据需要调整大小来节省空间。

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

// 动态数组结构
typedef struct {
    char* data;
    int capacity;
    int size;
} Stack;

// 初始化动态数组
Stack* createStack(int initialCapacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (char*)malloc(initialCapacity * sizeof(char));
    stack->capacity = initialCapacity;
    stack->size = 0;
    return stack;
}

// 释放动态数组
void freeStack(Stack* stack) {
    free(stack->data);
    free(stack);
}

// 动态数组压入元素
void push(Stack* stack, char value) {
    // 如果容量不足，增加容量
    if (stack->size == stack->capacity) {
        stack->capacity *= 2;
        stack->data = (char*)realloc(stack->data, stack->capacity * sizeof(char));
    }
    stack->data[stack->size++] = value;
}

// 动态数组弹出元素
char pop(Stack* stack) {
    return stack->data[--stack->size];
}

// 检查栈是否为空
bool isEmpty(Stack* stack) {
    return stack->size == 0;
}

// 检查栈顶元素
char top(Stack* stack) {
    return stack->data[stack->size - 1];
}

// 检查括号是否有效
bool isValid(char* s) {
    Stack* stack = createStack(128); // 初始容量设置为128
    for (int i = 0; s[i] != '\0'; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '{' || ch == '[') {
            push(stack, ch);
        } else {
            if (isEmpty(stack)) {
                freeStack(stack);
                return false;
            }
            char topElement = top(stack);
            if ((topElement == '(' && ch == ')') ||
                (topElement == '{' && ch == '}') ||
                (topElement == '[' && ch == ']')) {
                pop(stack);
            } else {
                freeStack(stack);
                return false;
            }
        }
    }
    bool result = isEmpty(stack);
    freeStack(stack);
    return result;
}

优化方案2：使用有限状态机

有限状态机适用于某些特定的字符串匹配场景，但对于括号匹配，效果不如栈明显。不过，以下是使用有限状态机的简单版本：

#include <stdbool.h>

#define MAX_STATES 128

typedef struct {
    int transitions[MAX_STATES][256];
    int currentState;
} StateMachine;

// 初始化状态机
void initStateMachine(StateMachine* sm) {
    sm->currentState = 0;
    for (int i = 0; i < MAX_STATES; i++) {
        for (int j = 0; j < 256; j++) {
            sm->transitions[i][j] = -1;
        }
    }
}

// 设定状态转换
void setTransition(StateMachine* sm, int fromState, char input, int toState) {
    sm->transitions[fromState][(unsigned char)input] = toState;
}

// 处理输入字符
void processInput(StateMachine* sm, char input) {
    int nextState = sm->transitions[sm->currentState][(unsigned char)input];
    if (nextState != -1) {
        sm->currentState = nextState;
    }
}

// 检查括号是否有效
bool isValid(char* s) {
    StateMachine sm;
    initStateMachine(&sm);

    // 定义状态转换
    setTransition(&sm, 0, '(', 1);
    setTransition(&sm, 1, ')', 0);
    setTransition(&sm, 0, '{', 2);
    setTransition(&sm, 2, '}', 0);
    setTransition(&sm, 0, '[', 3);
    setTransition(&sm, 3, ']', 0);

    for (int i = 0; s[i] != '\0'; i++) {
        processInput(&sm, s[i]);
    }

    return sm.currentState == 0;
}

优化方案3：简化逻辑（不使用动态内存分配）

如果预先知道字符串长度不会过长，可以使用固定大小的数组来避免动态内存分配。

#include <stdbool.h>

#define MAX_LENGTH 10000

bool isValid(char* s) {
    char stack[MAX_LENGTH];
    int top = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '{' || ch == '[') {
            stack[top++] = ch;
        } else {
            if (top == 0) {
                return false;
            }
            char topElement = stack[top - 1];
            if ((topElement == '(' && ch == ')') ||
                (topElement == '{' && ch == '}') ||
                (topElement == '[' && ch == ']')) {
                top--;
            } else {
                return false;
            }
        }
    }
    return top == 0;
}