04-12 19:20 上海交通大学算法工程师发布于上海

关注

牛客刷题题目（容器篇）（自用）

栈

AB3 有效括号序列

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列

括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

数据范围：字符串长度 $0\le n \le 10000$ 。要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$ 。

bool isValid(string s) {
        // write code here
        stack<char> sta;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s[i] == '(')
                sta.push(')');
            else if (s[i] == '[')
                sta.push(']');
            else if (s[i] == '{')
                sta.push('}');
            else if (sta.empty())		// 要记得先判断是不是空的，也就是有没有top()
                return false;
            else if (s[i] == sta.top())		// 然后才能放心地写top()
                sta.pop();
            else
                return false;
        }
        return sta.empty();
 }

AB5 点击消除

牛牛拿到了一个字符串。他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。但相同而不相邻、不相同的相邻字母都是不可以被消除的。牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？

int main() {
    string s;
    stack<char> sta;
    string ans;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (sta.empty()) sta.push(s[i]);	//用top()之前判断一下empty()
        else if (sta.top() == s[i]) {
            sta.pop();
            continue;
        } else sta.push(s[i]);
    }
    if (sta.empty()) cout << "0";
    while (!sta.empty()) {
        ans.push_back(sta.top());	//string可以push_back，也可以+=
        sta.pop();
    }
    reverse(ans.begin(),ans.end());		// reverse( BidirIt first, BidirIt last ); BidirIt指的是双向迭代器类型，如std::vector、std::list、std::deque 以及 std::string。
  
    // while (!sta.empty()) {
    //     ans += sta.top();
    //     sta.pop();
    // }
    // reverse(ans.begin(), ans.end());
  
    cout << ans;
}

AB2 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

0<=pushV.length == popV.length <=1000
-1000<=pushV[i]<=1000
pushV 的所有数字均不相同

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> sta;
        auto idx_push = pushV.begin();
        for (auto idx_pop = popV.begin(); idx_pop != popV.end(); ) {	// 遍历popV
            if (*idx_pop == *idx_push) {	//如果准备要push进来的刚好等于准备pop的，那就push完直接pop
                idx_pop++;
                idx_push++;
            }
		    else if(*idx_pop != *idx_push){		//如果不等于，就先把准备push的放进一个中间栈sta里
                sta.push(*idx_push);
                idx_push++;
            }
            else if(!sta.empty() && *idx_pop == sta.top()){	//如果sta.top()刚好等于准备pop的，那就pop掉
                sta.pop();
                idx_pop++;
            }
        }
        return sta.empty();		// 看看sta如果不空，那就是没有成功pop完
 }

队列

AB8 【模板】循环队列

请你实现一个循环队列，该循环队列可利用的空间大小等于 $n$ 个int型变量的大小。操作：push x：将 $x$ 加入到循环队列尾端。若循环队列已满，输出"full"(不含引号)，否则不输出任何内容。保证 $x$ 为int型整数。front：输出队首元素，队首不出队。若队列为空，输出"empty"(不含引号)。pop：输出队首元素，且队首出队。若队列为空，输出"empty"(不含引号)。

// 可以用结构体：一个数组，一个队首head,一个队尾rear，进行模拟
// 我这里直接用的vector
int main() {
    int n, q, num;
    string s;
    cin >> n >> q;
    vector<int> que;
    for (int i = 1; i <= q; i++) {
        cin >> s;
        if (s == "push") {
            cin >> num;
            if (que.size() == n) {
                cout << "full" << endl;
            } else {
                que.push_back(num);
            }
        } else if (s == "front") {
            if (que.empty()) {
                cout << "empty" << endl;
            } else {
                cout << que[0] << endl;
            }
        } else if (s == "pop") {
            if (que.empty()) {
                cout << "empty" << endl;
            } else {
                cout << que[0] << endl;
                auto it = que.begin();
                que.erase(it);
            }
        }
    }
}

向量

vector<vector<int>> mat(m, vector<int>(n, 0));	// m行n列矩阵，初始化为0

链表

AB11 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： $0 \le n \le 1000$ ， $-1000 \le 节点值 \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

    ListNode* Merge(ListNode* list1, ListNode* list2) {
        // write code here
        if (list1 == nullptr)		// 记得先判断是否是空的的情况
            return list2;
        else if (list2 == nullptr)
            return list1;
        ListNode* newhead = nullptr;	// 返回newhead
        ListNode* current = nullptr;	// 用current来编排合并后的链表
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                if (newhead == nullptr) {
                    newhead = current = list1;
                }
                else {
                    current->next = list1;
                    current = current->next;
                }
                list1 = list1->next;
            }
            else {
                if (newhead == nullptr) {
                    newhead = current = list2;
                }
                else {
                    current->next = list2;
                    current = current->next;
                }
                list2 = list2->next;
            }
        }
        if (list1 == nullptr) {		// 若list1已空，list2还剩一些元素
            current->next = list2;
        }
        else {
            current->next = list1;
        }
        return newhead;
    }

哈希

HJ10 字符个数统计

对于给定的字符串，统计其中的 $\sf{ASCII}$ 在 $0$ 到 $127$ 范围内的不同字符的个数。

$\hspace{15pt}$ 备注：受限于输入，本题实际输入字符集为 $\sf{ASCII}$ 码在 $33$ 到 $126$ 范围内的可见字符。您可以参阅下表获得其详细信息（您可能关注的内容是，这其中不包含空格、换行）。

    string s;
    set<char> se;
    unordered_map<char, int> m;
    cin >> s;
    for (int i=0; i<s.size(); i++) {
        se.insert(s[i]);	//重复的元素无法插入set，相当于会自己去重
    }
    cout << se.size();

HJ3 明明的随机数

$\hspace{15pt}$ 对于明明生成的 $n$ 个 $1$ 到 $500$ 之间的随机整数，你需要帮助他完成以下任务： $\hspace{23pt}\bullet\,$ 删去重复的数字，即相同的数字只保留一个，把其余相同的数去掉； $\hspace{23pt}\bullet\,$ 然后再把这些数从小到大排序，按照排好的顺序输出。 $\hspace{15pt}$ 你只需要输出最终的排序结果。

    set<int> s;
    int n, a;
    cin >> n;
    for (int i=0; i<n; i++){
        cin >> a;
        s.insert(a);
    }
    for (auto it = s.begin(); it!=s.end(); it++) {
        cout << *it << endl;
    }

HJ23 删除字符串中出现次数最少的字符

$\hspace{15pt}$ 对于给定的仅由小写字母构成的字符串，删除字符串中出现次数最少的字符。输出删除后的字符串，字符串中其它字符保持原来的顺序。 $\hspace{15pt}$ 特别地，若有多个字符出现的次数都最少，则把这些字符都删除。

    unordered_map<char, int> m;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {		//将出现次数存入map
        m[s[i]]++;
    }
     
    int min = 20;
    for (auto it=m.begin(); it!=m.end(); it++){		//比较map里的min
        min = (min<it->second)? min:it->second;
    }
    for (int i = 0; i < s.size(); i++){
        if (m[s[i]]==min) {		//如果是min，就跳过
            continue;
        }
        cout << s[i];
    }

HJ8 合并表记录

$\hspace{15pt}$ 数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，随后按照索引值的大小从小到大依次输出。

    map <int, int> m;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        m[x] += y;		// 熟悉哈希表操作
    }
    for (auto i : m) {
        cout << i.first << ' ' << i.second << endl;		// 熟悉哈希表操作
    }

HJ68 成绩排序

$\hspace{15pt}$ 对于给出的 $n$ 位同学的姓名和成绩，根据输入要求，按成绩升序或降序排列

        map<int, vector<string>> m;
		for (int i = 0; i < n; i++) {
        	cin >> name >> score;
        	m[score].push_back(name);		// map是按照键来排序的，即这里的socre，并且是字典序
    	}
		for (auto it = m.begin(); it != m.end(); it++) {	// 这样是从begin遍历到end
		for (auto it = m.rbegin(); it != m.rend(); it++) {		// 这样换句话来说是从end遍历到begin，但我们不能那样写，会报错

HJ41 称砝码

$\hspace{15pt}$ 对于给定的 $n$ 种砝码，重量互不相等，依次为 $m_1, m_2, \dots, m_n$ ，数量依次为 $x_1, x_2, \dots, x_n$ ， $\hspace{15pt}$ 现在要用这些砝码去称物体的重量（放在同一侧），问能称出多少种不同的重量。特别地，称重重量包括 $0$ 。

int main() {
    int n, m, x;
    vector<int> weight;
    vector<int> num;
    unordered_set<int> flag;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> m;
        weight.push_back(m);
    }
    for (int i = 0; i < n; i++) {
        cin >> x;
        num.push_back(x);
    }
 
    flag.insert(0);
    for (int idx = 0; idx < n; idx++) {
        for (int i = 1; i <= num[idx]; i++) { // i为选中的砝码数量
            unordered_set<int> tmp (flag);  // 为了不在迭代过程中随意改变迭代变量
            for (auto it = tmp.begin(); it != tmp.end(); it++) {
                // 对于所有的flag里的w都让他们加上weight[idx]
                flag.insert(*it + weight[idx]);
            }
        }
    }
    cout << flag.size() << endl;
}

其他

HJ101 排序

$\hspace{15pt}$ 对于给出的 $n$ 个整数组成的数组 $\{a_1, a_2, \dots, a_n\}$ ，根据输入要求，按升序或降序排列后输出。

    if (op==0) {
        sort(vec.begin(), vec.end());		// 升序
	    // sort随机访问迭代器容器都能用，如vector,deque,数组，如果是list, forward_list，则不能用std::sort，得用他自己的成员函数sort，例如：lst.sort();flst.sort();
	    // 另外，用sort对string排序的结果叫做按照 字典序 排序，从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的字母表顺序得出字符串的大小，称为字典序比较。
    }
    else {
        sort(vec.begin(), vec.end(), greater<int>());		// 降序
    }
    for (int v:vec) {
        cout << v << ' ';
    }