矩阵乘法计算量估算（C++牛客网）

一时失言乱红尘 2022-11-12 14:57 215阅读 0赞

解题思路：

（1）两个栈

（2）注意栈为空的情况

#include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    
    int helper(vector<vector<int>> &v,string &s) {
        stack<char> s1;
        stack<pair<int,int>> s2;
        int count=0,sum=0;
        for(int i=0;i<s.length();i++) {
            if(s[i]=='(') s1.push(s[i]);
            else if('A'<=s[i] && s[i]<='Z') {
                s2.push({v[count][0],v[count][1]});
                count++;
            } else {
                if(s2.empty()) return sum; 
                auto a=s2.top();
                s2.pop();
                if(s2.empty()) return sum; 
                auto b=s2.top();
                s2.pop();
                sum+=b.first*b.second*a.second;
                s2.push({b.first,a.second});
                s1.pop();
                
            }
        }
        return sum;
    }
    
    int main() {
        int n;
        string s;
        while(cin>>n) {
            vector<vector<int>> v(n,vector<int>(2,0));
            for(int i=0;i<n;i++) {
                cin>>v[i][0]>>v[i][1];
            }
            cin>>s;
            cout<<helper(v,s)<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关 HJ70 矩阵乘法计算量估算

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

野性酷女/ 2024年03月27日 16:41/ 0 赞/ 30 阅读

相关【华为机试真题详解JAVA实现】—矩阵乘法计算量估算

![445ae6c2d2004579a7cc29b521ba8b25.png][] 目录一、题目描述二、解题代码 -------------------- 一、

向右看齐/ 2023年09月30日 22:59/ 0 赞/ 5 阅读

相关螺旋矩阵（C++牛客网）

解题思路：（1）设置方向，右下左上 class Solution { public: vector<vector<int>> d={

雨点打透心脏的1/2处/ 2023年01月13日 06:21/ 0 赞/ 130 阅读

相关大数乘法（C++牛客网）

解题思路：（1）数学思想 class Solution { public: / 代码中的类名、方法名、参数名已经指定，

朴灿烈づ我的快乐病毒、/ 2023年01月13日 06:09/ 0 赞/ 179 阅读

相关牛客网|蛇形矩阵

题目信息蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。例如，当输入5时，应该输出的三角形为： 1 3 6 10 15 2 5 9 14

我就是我/ 2022年11月16日 15:21/ 0 赞/ 179 阅读

相关矩阵乘法计算量估算（C++牛客网）

解题思路：（1）两个栈（2）注意栈为空的情况 include<iostream> include<vector> include<stack>

一时失言乱红尘/ 2022年11月12日 14:57/ 0 赞/ 216 阅读

相关矩阵乘法（C++牛客网）

解题思路：（1）三层循环 include<iostream> include<vector> using namespace std;

痛定思痛。/ 2022年11月12日 13:47/ 0 赞/ 300 阅读

相关蛇形矩阵（C++牛客网）

解题思路：（1）每次往右上角走，溢出则跳到初始记录的下一行 include<iostream> include<vector> usin

梦里梦外;/ 2022年10月22日 10:47/ 0 赞/ 175 阅读

相关牛客网|矩阵乘法

题目信息如果A是个x行y列的矩阵，B是个y行z列的矩阵，把A和B相乘，其结果将是另一个x行z列的矩阵C。这个矩阵的每个元素是由下面的公式决定的 ![4f0f11642

╰+哭是因爲堅強的太久メ/ 2022年10月22日 06:25/ 0 赞/ 190 阅读

相关华为OJ矩阵乘法计算量估算

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:3

r囧r小猫/ 2022年06月17日 08:48/ 0 赞/ 171 阅读