题解 | #矩阵乘法计算量估算#

矩阵乘法计算量估算

https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = Integer.parseInt(in.nextLine());
        int[][] matrixs = new int[num][2];
        for (int i = 0; i < num; i++) {
            String[] matrixItem = in.nextLine().split(" ");

            //合法性检验
            if (i != 0 && matrixs[i - 1][1] != Integer.parseInt(matrixItem[0])) {
                System.out.println("矩阵输入不合法");
                in.close();
            } else {
                matrixs[i][0] = Integer.parseInt(matrixItem[0]);
                matrixs[i][1] = Integer.parseInt(matrixItem[1]);
            }


        }
        String rule = in.nextLine();
        char[] ruleArr = rule.toCharArray();
        in.close();

        //使用栈结构,左括号则入栈；字母则取行列入栈，连续字母直接运算后只留下一个；右括号则出栈并去括号
        Stack<String> stk = new Stack<String>();

        int matrixIndex = 0;
        int counts = 0;
        for (char c : ruleArr) {
            if (c == '(') { //左括号入栈
                stk.push(c + "");
            } else if ( c >= 'A' && c <= 'Z') {     //矩阵符号
                int nowRow = matrixs[matrixIndex][0];
                int nowColumn = matrixs[matrixIndex][1];
                if ( !stk.peek().equals("(") && !stk.peek().equals(")") ) {
                                    //栈顶（前一个符号）也是字母，则可以立即进行运算得到矩阵入栈
                    int preColumn = Integer.parseInt(stk.pop());
                    int preRow = Integer.parseInt(stk.pop());
                    int count = preRow * preColumn * nowColumn;
                    stk.push(preRow + "");
                    stk.push(nowColumn + "");
                    counts += count;
                } else {            //前一个不是字母则将矩阵行列入栈
                    stk.push(nowRow + "");
                    stk.push(nowColumn + "");                    
                }
                matrixIndex++;
            } else if ( c == ')') {     //由于前面的运算，括号里最多只有一个矩阵的行列
                if ( stk.peek() == "(")  {  //括号里面为空，直接都出栈
                    stk.pop();
                } else if ( !stk.peek().equals("(") && !stk.peek().equals(")") ){
                    int nowColumn = Integer.parseInt(stk.pop());
                    int nowRow = Integer.parseInt(stk.pop());
                    stk.pop();      //弹出左括号
                    if ( stk.size() != 0 && !stk.peek().equals("(") && !stk.peek().equals(")") ){  
                        //去掉括号后如果又是矩阵，同样需要运算，但所幸，嵌套到这里就不用往更深了
                        int preColumn = Integer.parseInt(stk.pop());
                        int preRow = Integer.parseInt(stk.pop());
                        int count = preRow * preColumn * nowColumn;
                        stk.push(preRow + "");
                        stk.push(nowColumn + "");
                        counts += count;

                    } else {
                        stk.push(nowRow + "");
                        stk.push(nowColumn + "");
                    }
                }

            }
        }

        System.out.println(counts);




    }
}

看了其他大神的题解，都比较约定俗成的认为括号内只有两个连续的矩阵，即不会出现()、（ABC）、（A）这种情况，构思许久，写下这个，同样是以栈的方式实现，而且只需遍历一次就可以，就是逻辑判断啥的比较多，代码附上，还请大神可以优化优化，一起学习！

下面我主要讲讲字符串遍历思路，代码中也有相对应的注释。

左括号直接入栈；
如果是矩阵，判断之前是否也有矩阵，有则两个直接计算乘法次数，以及变成新矩阵入栈，如[3, 2] * [2, 5]转成[3, 5]；没有则直接入栈行和列；
如果是右括号，由于之前有运算，那么栈顶要么是矩阵，要么是左括号（考虑了字符串中输入了“()”的情况），总之思路是要消去两边括号，就像我们学习四则运算一样，括号内计算好了就可以去括号。例如（B），就popB，pop(，然后在压入B
这是我运行了用例之后有部分不通过发现的需要增加的判断，如果我们去了括号之后，发现有连续的矩阵在一起，比如A（B），去掉括号就是AB，还是需要运算后再继续遍历字符。具体就是在第3条压入B之前，判断栈顶是否是矩阵，是就采用第2条同样操作去处理连续字符串。

举个比较综合的例子，其栈的情况及操作分析：

(A((BCD)E)()(FG))

1.入栈，A和B入栈时都判断了前面没有矩阵相连，直接入栈：(, Ar, Ac, (, (, Br, Bc

2.矩阵C进来后判断到前面有B，运算：(, Ar, Ac, (, (, Br, Cc

3.矩阵D进来后判断到前面有矩阵，运算：(, Ar, Ac, (, (, Br, Dc

4.遇到')'，前面是刚刚计算的ABC的矩阵，因此出出，消掉括号'('，但再左边还是括号而不是矩阵，所以不用运算先：(, Ar, Ac, (, Br, Dc

题解 | #矩阵乘法计算量估算#

全站热榜