TikTok真题第11天 | 1249.移除无效的括号、23.合并K个升序链表、773.滑动谜题

今天开始整hard题，果然费时。

1249.移除无效的括号

题目链接：1249.minimum-remove-to-make-valid-parentheses

解法：

这个题用栈来处理，用栈来记录左括号的位置，同时用一个向量来记录左括号和右括号是否有效（有效则不需要删除）。

如果遇到左括号，那么栈中弹入，同时该位置为无效（需要删除），待后面遇到右括号再置为有效。

如果遇到右括号，那么如果栈为空（前面没有左括号可以匹配），那么该位置无效；如果栈不为空，那么该位置有效，且把前面左括号（栈顶元素）改为有效。

最后把有效的元素取出来即可。

还有一种做法是直接在遍历字符的过程中，记录左括号，并且即时删除无效的右括号，最后遍历结束再删除左括号。这种即时删除的写法会在遍历过程中就改变字符串s，感觉还是容易出错，所以推荐遍历结束后，再同一删除。

参考题解：栈

边界条件：无

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> leftStack;
        // 如果是有效的，那么值为true
        vector<bool> validIdx(s.size(), true);
        for (int i=0; i<s.size(); i++) {
            if (s[i]=='(') {
                leftStack.push(i);
                // 暂时没匹配到右括号，所以目前是无效
                validIdx[i] = false;
            } else if (s[i]==')') {
                if (leftStack.empty()) {
                    // 没有左括号，所以右括号无效
                    validIdx[i] = false;
                } else {
                    // 前面的左括号改为有效
                    // 右括号初始化为有效，所以不用改
                    validIdx[leftStack.top()] = true;
                    leftStack.pop();
                }
            }
        }
        string res;
        for (int i=0; i<s.size(); i++) {
            if (validIdx[i]) {
                res += s[i];
            }
        }
        return res;
    }
};

23.合并K个升序链表

题目链接：23.merge-k-sorted-lists

解法：

（1）第一种方法是优先队列，即构造小根堆（队首元素最小），然后把所有链表添加到优先队列中，那么从队首到队尾是根据val进行升序排列的。

建立一个虚拟头节点，每次都把val最小的node添加作为next，同时把该node的next添加到优先队列中。最近返回虚拟头节点的next即可。

优先队列的思路比较好理解。

（2）第二种方法是分治合并。将?k个链表两两配对并将同一对中的链表合并；不断重复这个过程，直到剩下一个链表。

参考题解：优先队列

边界条件：

优先队列的复杂度：

分治合并的复杂度：

/**
 * 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:
    struct Status {
        int val;
        ListNode *ptr;
        // 重载小于操作符，val大的反而认为是小的
        // 因为优先队列默认是最大堆，即队首的元素是最大的，但是我们这里需要最小堆，所以把比较的逻辑反向
        bool operator < (const Status& sta) const {
            return val > sta.val;
        }
    };

    // 注意元素是Status而不是Status*，所以取属性是通过 s.val 而不是 s->val
    priority_queue<Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto& node: lists) {
            if (node) {
                q.push({node->val, node});
            }
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto s = q.top();
            q.pop();
            tail->next = s.ptr;
            tail = tail->next;
            if (s.ptr->next) {
                q.push({s.ptr->next->val, s.ptr->next});
            }
        }
        // 注意head不是指针，而是一个真正的对象，所以使用.而不是->来获取
        return head.next;
    }
};

/**
 * 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* mergeTwoLists(ListNode* a, ListNode* b) {
        if ((!a) || (!b)) return a? a:b;
        // 为啥不直接用 a和b 这俩指针呢
        ListNode head, *tail=&head, *aPtr=a, *bPtr=b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr;
                aPtr = aPtr->next;
            } else {
                tail->next = bPtr;
                bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr:bPtr);
        return head.next;
    }

    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l==r) return lists[l];
        if (l > r) return nullptr;
        int mid = l + (r - l) / 2;
        return mergeTwoLists(merge(lists, l, mid),merge(lists, mid+1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size()-1);
    }
};

773.滑动谜题

题目链接：773.sliding-puzzle

解法：

这个题实名表扬labuladong同志，题解写得很详细很通俗易懂，从0开始讲解，不需要前置知识。

这个题用BFS来处理，一次?移动?定义为选择?0?与一个相邻的数字（上下左右）进行交换，所以每次搜索的过程如下图所示：

一直搜下去，直到第一次出现了目标矩阵，那返回交换次数即可。

?其他的看题解吧，题解写得不错。参考题解：labuladong的BFS

边界条件：

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int m = 2, n = 3;
        string start;
        string target = "123450";
        // 将矩阵转为行优先的字符串
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                start += board[i][j] +'0';
            }
        }
        // 记录一维字符串中i位置的相邻索引
        vector<vector<int>> neighbor = {
            {1,3},
            {0,4,2},
            {1,5},
            {0,4},
            {3,1,5},
            {4,2}
        };

        queue<string> q;
        unordered_set<string> visited;
        q.push(start);
        visited.insert(start);

        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                string cur = q.front();
                q.pop();
                // 如果已经调整为目标矩阵，则返回结果
                if (cur == target) return step; 
                // 找到数字0的索引
                int idx = 0;
                while (cur[idx]!='0') {
                    idx++;
                }
                // 将数字0与相邻数字交换位置
                for (int adj: neighbor[idx]) {
                    string newBorad = cur;
                    swap(newBorad[adj], newBorad[idx]);
                    if (!visited.count(newBorad)) {
                        q.push(newBorad);
                        visited.insert(newBorad);
                    }
                }
            }
            step++;
        }
        return -1;
    }
};