好未来笔试 - 0906

合并数组

题面

已知两个有序整形数组 a 和 b，请将两个数组合并成一个新的有序数组;

示例：

输入：[1,2,3],[-1,1,3,6]
输出：[-1,1,1,2,3,3,6]

思路与代码

合并数组一般使用双指针实现。

使用两个指针分别指向数组 a 和 b 的起始位置，然后比较两个指针所指向的元素，将较小的元素放入结果数组中，并将对应指针向后移动一位。重复这个过程，直到其中一个数组的所有元素都被处理完毕。最后，将另一个数组中剩余的元素直接添加到结果数组中。

vector<int> merge(vector<int>& a, vector<int>& b) {
    vector<int> res;
    int i = 0, j = 0;
    
    while (i < a.size() && j < b.size()) {
        if (a[i] < b[j]) {
            res.push_back(a[i++]);
        } else if (a[i] > b[j]) {
            res.push_back(b[j++]);
        } else {
            res.push_back(a[i++]);
            res.push_back(b[j++]);
        }
    }
    
    while (i < a.size()) {
        res.push_back(a[i++]);
    }
    
    while (j < b.size()) {
        res.push_back(b[j++]);
    }
    
    return res;
}

有效字符串

题面

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例：

输入："()[]{}"
输出：true

思路与代码

字符串的括号匹配问题，使用栈解决。

1. 初始化一个空栈 stack。
2. 遍历输入字符串 s 中的每个字符 c：
   • 如果 c 是左括号 '('、'[' 或 '{'，我们将它压入栈中。
   • 如果 c 是右括号 ')'、']' 或 '}'，我们检查栈是否为空。如果为空，说明右括号无法匹配，返回 $false$。
   • 如果栈不为空，我们检查栈顶元素是否与 c 匹配。如果不匹配，返回 $false$。否则，我们将栈顶元素弹出。
3. 最终，如果栈为空，说明所有括号都已正确匹配，返回 $true$。否则，返回 $false$。

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();
            st.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}