1 minute read

4/19

T20 有效的括号

重要反例：”(){}}{“ 说明不能左边栈、右边队列，还需保证顺序性，也就是左括号需要在遍历中先于对应的右括号出现。加上从做到右遍历字符串本身便是“老的优先”，或者说“先出现先匹配”的性质，所以不必额外建一个队列。直接遍历，根据即时性，只要右括号无法和当前栈顶左括号匹配或栈为空，直接返回false；若能匹配，pop栈顶，继续遍历。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) return false;

                char top = st.top();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }

                st.pop();
            }
        }

        return st.empty();
    }
};

T225 用队列实现栈

和昨天的题目不同，这一题没有平均时间复杂读为O（1）的解法，因为队列是先进先出的特性，无法实现倒转。注意：需要标记好谁是主队列。有趣的是，有个自旋方法可以实现仅用一个队列：

class MyStack {
public:
    queue<int> q;

    MyStack() {
        
    }
    
    void push(int x) {
        q.push(x);
        int n = q.size();
        while (n > 1) {
            q.push(q.front());
            q.pop();
            n--;
        }
    }
    
    int pop() {
        int res = q.front();
        q.pop();
        return res;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

对比一、二个队列实现栈的时间复杂度：

方法一：两个队列

在 pop / top 时搬运

操作 时间复杂度
push O(1)
pop O(n)
top O(n)
empty O(1)

特点：

  • 入栈快
  • 出栈慢

方法二：一个队列

在 push 时旋转

操作 时间复杂度
push O(n)
pop O(1)
top O(1)
empty O(1)

可以发现不同解法适应不同操作分布概率的业务逻辑。当然，一个队列也可以选择push正常，在pop、top上进行自旋，这就和两个队列时间复杂度分布相似，而在空间上优化了复杂度。

注意：

queue<int> q1, q2;
swap(q1, q2);

这里面swap 做的不是“逐个元素交换”，而是交换内部指针/结构体。时间复杂度仍为O（1）

4/18

T54 替换数字（卡码网）

这道题之前遇到过，仅仅一两周前，但我对最优思路印象很弱。这说明，需要提高复习频率，优化记忆方式，或以练习、手写的方式去强化记忆。
以及：字符串插入是低效的，需要统一移动左右区域。能赋值就赋值。换个顺序（从最右侧开始）或许有新天地。

T151 已刷过，见之前

这周刷的专题是“双指针法”，前面常有所覆盖

……以下题目均在之前出现过，链表专题后期统一手写刷题，略。
跳至“栈与队列”专题

T232 用栈实现队列

核心：利用将一个栈内的一组数据倒入另一个栈内后恰好反向的特性
注：在平板上自己画图，应对多种情况，尤其是穿插不同元操作的实例（已完成）

4/17

T344 反转字符串

简单，略

T27 移除元素

这道题我一开始想的方法过于复杂：先排序，再左右指针，左边移到第一个val处，右边直接和左边开始一个个交换直到重合或左边不再是val。这个解法有三个问题：首先排序增加了时间复杂度，多乘以了一个logn；其次，我没有优化可以跳过右侧V的情况；最后，以下统计数目的代码会出现如下错误：

if (left < nums.size() && nums[left] != val) {
    return left + 1;
}
return left;
}

假如是 xxxxxxxxxxxVVVVV这样的排序后结构，x表示不等于V，左右指针在V区域中间某处相遇，此时的left前后都是V，不能保证等同于有效元素个数，因此须改写如下：

//计算前面非 val 的个数
int k = 0;
while (k < nums.size() && nums[k] != val) {
    k++;
}

return k;

最优解：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0; // 指向下一个要填的位置
        
        for (int fast = 0; fast < nums.size(); fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        
        return slow;
    }
};

核心：
1、此题对元素内部顺序没有要求，因此无需排序
2、快指针经过的所有非V元素都已经赋值过慢指针对应的位置，因此不必担心慢指针覆盖非V元素——两个指针都是单调前进的
3、快指针遇到V即跳过，这样慢指针的每一个赋值都保证有效性，且快指针遍历完毕数组后，所有元素均已被考虑到

4/15（这两道题仔细复习KMP知识点后重做）

T28 找出字符串中第一个匹配项都下标【重要】

该题被归类为简单，因为暴力解法也能过。但这道题很重要，是KMP算法的核心应用。
注：复习KMP算法及其拓展应用

https://
www.bilibili.com/video/BV1PD4y1o7nd/?vd_source=2347c699c40e3a971470bde33b0f40de

https://www.bilibili.com/video/BV1M5411j7Xx/?vd_source=2347c699c40e3a971470bde33b0f40de

T459 重复的子字符串

误区：不能直接找首末最长匹配项，然后跳跃性遍历。

反例：
s = “abcabcabcabc”

最长前后缀：
“abcabcabc”

真正周期：
“abc”

关键：依旧KMP

4/13

T151 翻转字符串里的单词

【以下解法竟然不是O(1)，而是O(n)的，记住：往开头插入（insert at front）是 O(n)，而且通常会导致重新分配内存。本质上是在不断“构造新字符串”】

class Solution {
public:
    string reverseWords(string s) {
     //从右到左遍历字符串，如果一开始是空格，删除，直到遇见非空格。两个指针，一个指向当前单词开头，一个结尾
     //对于每个单词，直接拼接到s的开头，加一个空格
     //继续遍历，无视空格直到下一个单词
     //循环结束（s遍历完毕）   
    }
};

You May Also Enjoy