HJ70 矩阵乘法计算量估算

野性酷女 2024-03-27 16:41 30阅读 0赞

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

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package stack;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.Deque;
    import java.util.LinkedList;
    
    import static java.lang.Integer.parseInt;
    import static java.lang.System.in;
    
    /**
     * HJ70 矩阵乘法计算量估算
     */
    public class HJ70CalculationOfMatrixMultiplication {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            // 矩阵组数
            int groups = parseInt(bf.readLine());
            // 收集矩阵
            int[][] matrix = new int[groups][2];
            for (int i = 0; i < groups; i++) {
        
                int[] s = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                matrix[i][0] = s[0];
                matrix[i][1] = s[1];
            }
    
            // 矩阵运算顺序
            String actionStr = bf.readLine();
            bf.close();
    
            int result = matrixMultiplication(matrix, actionStr);
            System.out.println(result);
        }
    
        /**
         * HJ70 矩阵乘法计算量估算
         */
        private static int getSum(int groups, int[][] matrix, String actionStr) {
        
            int sum = 0;
            Deque<Integer> stack = new LinkedList<>(); // 存放矩阵行数和列数
            int j = groups - 1;
            for (int i = actionStr.length() - 1; i >= 0; i--) {
        
                if ('A' <= actionStr.charAt(i) && actionStr.charAt(i) <= 'Z') {
        
                    stack.push(matrix[j][1]); // 先入栈列
                    stack.push(matrix[j][0]); // 再入栈行
                    j--;
                } else if (actionStr.charAt(i) == '(') {
        
    
                    // 先入栈列再入栈行,所以先取出来行再取出来列
                    int x0 = stack.pop();
                    int y0 = stack.pop(); // 矩阵尺寸x0*y0
                    int x1 = stack.pop();
                    int y1 = stack.pop(); // 矩阵尺寸x1*y1
                    sum += x0 * y0 * y1;  // 两个矩阵的乘法次数为x0*y1*y0或x0*y1*x1（其中y0==x1）
                    stack.push(y1);       // 把相乘后得到的矩阵列数入栈
                    stack.push(x0);       // 把相乘后得到的矩阵行数入栈
                }
            }
            return sum;
        }
    
        /**
         * HJ70 矩阵乘法计算量估算
         */
        private static int matrixMultiplication(int[][] matrix, String actionStr) {
        
            int result = 0;
    
            int slow = 0;
            Deque<int[]> stack1 = new LinkedList<>(); // 存放矩阵行数和列数
            for (int fast = 0; fast < actionStr.length(); fast++) {
        
                if (actionStr.charAt(fast) == '(') {
        
                    // 啥也不做
                } else if ('A' <= actionStr.charAt(fast) && actionStr.charAt(fast) <= 'Z') {
        
                    stack1.push(matrix[slow]);
                    slow++;
                } else if (actionStr.charAt(fast) == ')') {
        
                    int[] pop2 = stack1.pop();
                    int[] pop1 = stack1.pop();
                    result += pop1[0] * pop2[1] * pop1[1];
                    int[] newMatrix = {
        pop1[0], pop2[1]};
                    stack1.push(newMatrix);
                }
            }
            return result;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b?tpId=37&tqId=21293&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=/exam/oj/ta?page=2&tpId=37&type=37&difficulty=undefined&judgeStatus=undefined&tags=&title=